《数据结构题集》答案第9章查找

1、第九章 查找9.25int Search_Sq(SSTable ST,int key)/ 在有序表上顺序查找的算法 , 监视哨设在 高下标端ST.elemST.length+1.key=key; for(i=1;ST.elemi.key>key;i+);if(i>ST.length|ST.elemi.key<key) return ERROR;return i;/Search_Sq分析: 本算法查找成功情况下的平均查找长度为 ST.length/2, 不成功情况下为 ST.length.9.26int Search_Bin_Recursive(SSTable ST,int k

2、ey,int low,int high)/折半查找的递归算法if(low>high) return 0; / 查找不到时返回 0 mid=(low+high)/2;if(ST.elemmid.key=key) return mid;else if(ST.elemmid.key>key)return Search_Bin_Recursive(ST,key,low,mid-1);else return Search_Bin_Recursive(ST,key,mid+1,high);/Search_Bin_Recursive9.27int Locate_Bin(SSTable ST,in

3、t key)/折半查找 , 返回小于或等于待查元素的最后一个结点号int *r;r=ST.elem;if(key<r.key) return 0;else if(key>=rST.length.key) return ST.length;low=1;high=ST.length; while(low<=high) mid=(low+high)/2; if(key>=rmid.key&&key<rmid+1.key) / 查找结束的条件 return mid;else if(key<rmid.key) high=mid; else low=mi

4、d; / 本算法不存在查找失败的情况 , 不需要 return 0; /Locate_Bin9.28 typedef struct int maxkey; int firstloc; Index; typedef struct int *elem;int length;Index idxMAXBLOCK; / 每块起始位 置和最大元素 , 其中 idx0 不利用 , 其内容初始化为 0,0 以利于折半查找int blknum; / 块的数目 IdxSqList; /索引顺序表类型int Search_IdxSeq(IdxSqList L,int key)/分块查找 , 用折半查找法确定记录所在

5、块 , 块内采用顺序查找法 if(key>L.idxL.blknum.maxkey) return ERROR; /超过最大元素low=1;high=L.blknum;found=0; while(low<=high&&!found) / 折半查找记录所在块号 mid mid=(low+high)/2; if(key<=L.idxmid.maxkey&&key>L.idxmid-1.maxkey)found=1; else if(key>L.idxmid.maxkey)low=mid+1; else high=mid-1; i=L.

6、idxmid.firstloc; / 块的下界 j=i+blksize-1; / 块的上界 temp=L.elemi-1; / 保存相邻元素 L.elemi-1=key; / 设置监视哨 for(k=j;L.elemk!=key;k-); /顺序查找L.elemi-1=temp; / 恢复元素 if(k<i) return ERROR; /未找到return k;/Search_IdxSeq分析: 在块内进行顺序查找时 , 如果需要设置监视哨 , 则必须先保存相邻块的相邻 元素, 以免数据丢失 .9.29typedef struct LNode *h; /h 指向最小元素LNode *t

7、; /t 指向上次查找的结点 CSList;LNode *Search_CSList(CSList &L,int key)/ 在有序单循环链表存储结构上的 查找算法 , 假定每次查找都成功 if(L.t->data=key) return L.t;else if(L.t->data>key) for(p=L.h,i=1;p->data!=key;p=p->next,i+);else for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i+);L.t=p; / 更新 t 指针return p;/Search_CSL

8、ist分析: 由于题目中假定每次查找都是成功的 , 所以本算法中没有关于查找失败的 处理. 由微积分可得 , 在等概率情况下 , 平均查找长度约为 n/3.9.30typedef struct DLNode *pre; int data;DLNode *next; DLNode;typedef struct DLNode *sp;int length; DSList; / 供查找的双向循环链表类型DLNode*Search_DSList(DSList &L,int key)/ 在有序双向循环链表存储结构上 的查找算法 , 假定每次查找都成功p=L.sp; if(p->data&g

9、t;key)while(p->data>key) p=p->pre;L.sp=p;else if(p->data<key)while(p->data<key) p=p->next;L.sp=p;return p;/Search_DSList分析: 本题的平均查找长度与上一题相同 , 也是 n/3.9.31int last=0,flag=1;int Is_BSTree(Bitree T)/ 判断二叉树 T 是否二叉排序树 , 是则返回 1, 否则返 回0if(T->lchild&&flag) Is_BSTree(T->l

10、child); if(T->data<last) flag=0; / 与其中序前驱相比较 last=T->data;if(T->rchild&&flag) Is_BSTree(T->rchild);return flag;/Is_BSTree9.32int last=0;void MaxLT_MinGT(BiTree T,int x)/ 找到二叉排序树 T 中小于 x 的最大元素和 大于 x 的最小元素if(T->lchild) MaxLT_MinGT(T->lchild,x); / 本算法仍是借助中序遍历来 实现if(last<

11、x&&T->data>=x) / 找到了小于 x 的最大元素 printf("a=%dn",last);if(last<=x&&T->data>x) / 找到了大于 x 的最小元素 printf("b=%dn",T->data);last=T->data;if(T->rchild) MaxLT_MinGT(T->rchild,x);/MaxLT_MinGT9.33从大到小输出二叉排序树 T 中所有不小于 xvoid Print_NLT(BiTree T,int x)/

12、的元素if(T->rchild) Print_NLT(T->rchild,x);if(T->data<x) exit(); /当遇到小于 x 的元素时立即结束运行printf("%dn",T->data);if(T->lchild) Print_NLT(T->lchild,x); /先右后左的中序遍历/Print_NLT9.34void Delete_NLT(BiTree &T,int x)/ 删除二叉排序树 T 中所有不小于 x 元素结 点, 并释放空间if(T->rchild) Delete_NLT(T->r

13、child,x);if(T->data<x) exit(); /当遇到小于 x 的元素时立即结束运行q=T;T=T->lchild;free(q); / 如果树根不小于 x, 则删除树根 , 并以左子树的根作为新的树根 if(T) Delete_NLT(T,x); /继续在左子树中执行算法/Delete_NLT9.35void Print_Between(BiThrTree T,int a,int b)/打印输出后继线索二叉排序树 T 中所有大于 a 且小于 b 的元素p=T;while(!p->ltag) p=p->lchild; /找到最小元素while(p&

14、amp;&p->data<b)if(p->data>a) printf("%dn",p->data); / 输出符合条件的元素 if(p->rtag) p=p->rtag;else p=p->rchild; while(!p->ltag) p=p->lchild; / 转到中序后继/while/Print_Between9.36void BSTree_Insert_Key(BiThrTree &T,int x)/ 在后继线索二叉排序树 T 中插 入元素 xif(T->data<x) /

15、插入到右侧if(T->rtag) /T没有右子树时 , 作为右孩子插入 p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode); q->data=x;T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p; / 修改原线索else BSTree_Insert_Key(T->rchild,x);/T有右子树时 , 插入右子树中/ifelse if(T->data>x) /插入到左子树中if(!T->lchild) /T没有左子树时 , 作为左孩子插入

16、 q=(BiThrNode*)malloc(sizeof(BiThrNode); q->data=x;T->lchild=q; q->rtag=1;q->rchild=T; / 修改自身的线索else BSTree_Insert_Key(T->lchild,x);/T有左子树时 , 插入左子树中/if/BSTree_Insert_Key9.37Status BSTree_Delete_key(BiThrTree &T,int x)/在后继线索二叉排序树 T中删除元素 xBTNode*pre,*ptr,*suc;/ptr 为 x 所在结点 ,pre 和 su

17、c 分别指向 ptr 的前 驱和后继p=T;last=NULL; /last始终指向当前结点 p 的前一个 ( 前驱 )while(!p->ltag) p=p->lchild; /找到中序起始元素while(p)if(p->data=x) / 找到了元素 x 结点pre=last;ptr=p;else if(last&&last->data=x) suc=p; /找到了 x 的后继if(p->rtag) p=p->rtag;elsep=p->rchild;while(!p->ltag) p=p->lchild; / 转到中序

18、后继last=p;/while / 借助中序遍历找到元素 x 及其前驱和后继结点if(!ptr) return ERROR; /未找到待删结点Delete_BSTree(ptr); / 删除 x 结点if(pre&&pre->rtag)pre->rchild=suc; / 修改线索return OK;/BSTree_Delete_keyvoid Delete_BSTree(BiThrTree &T)/ 课本上给出的删除二叉排序树的子树 T 的算法 , 按照线索二叉树的结构作了一些改动q=T;if(!T->ltag&&T->rtag

19、) /结点无右子树 , 此时只需重接其左子树T=T->lchild;else if(T->ltag&&!T->rtag) /结点无左子树 , 此时只需重接其右子树T=T->rchild;else if(!T->ltag&&!T->rtag) /结点既有左子树又有右子树p=T;r=T->lchild;while(!r->rtag)s=r;r=r->rchild; / 找到结点的前驱 r 和 r 的双亲 sT->data=r->data; / 用 r 代替 T 结点if(s!=T)s->rchi

20、ld=r->lchild;else s->lchild=r->lchild; / 重接 r 的左子树到其双亲结点上q=r;/elsefree(q); / 删除结点/Delete_BSTree分析: 本算法采用了先求出 x 结点的前驱和后继 , 再删除 x 结点的办法 , 这样修改 线索时会比较简单 , 直接让前驱的线索指向后继就行了 . 如果试图在删除 x 结点 的同时修改线索 , 则问题反而复杂化了 .9.38 void BSTree_Merge(BiTree &T,BiTree &S) 把二叉排序树 S合并至U T 中if(S->lchild) BS

21、Tree_Merge(T,S->lchild);if(S->rchild) BSTree_Merge(T,S->rchild); /合并子树Insert_Key(T,S); / 插入元素/BSTree_Mergevoid Insert_Node(Bitree &T,BTNode *S)/ 把树结点 S 插入至 T 的合适位置上 if(S->data>T->data)if(!T->rchild) T->rchild=S;else Insert_Node(T->rchild,S);else if(S->data<T->

22、data)if(!T->lchild) T->lchild=S;else Insert_Node(T->lchild,S);S->lchild=NULL; /插入的新结点必须和原来的左右子树断绝关系S->rchild=NULL; /否则会导致树结构的混乱/Insert_Node分析: 这是一个与课本上不同的插入算法 . 在合并过程中 , 并不释放或新建任何结 点, 而是采取修改指针的方式来完成合并 . 这样, 就必须按照后序序列把一棵树中 的元素逐个连接至另一棵树上 , 否则将会导致树的结构的混乱 .9.39void BSTree_Split(BiTree &am

23、p;T,BiTree &A,BiTree &B,int x)/把二叉排序树 T分裂为两棵二叉排序树 A和B,其中A的元素全部小于等于x,B的元素全部大于x if(T->lchild) BSTree_Split(T->lchild,A,B,x);if(T->rchild) BSTree_Split(T->rchild,A,B,x); /分裂左右子树if(T->data<=x) Insert_Node(A,T);else Insert_Node(B,T); / 将元素结点插入合适的树中/BSTree_Splitvoid Insert_Node(B

24、itree &T,BTNode *S)/ 把树结点 S 插入至 T 的合适位置上 if(!T) T=S; /考虑到刚开始分裂时树 A和树B为空的情况else if(S->data>T->data) / 其余部分与上一题同if(!T->rchild) T->rchild=S; else Insert_Node(T->rchild,S);else if(S->data<T->data)if(!T->lchild) T->lchild=S;else Insert_Node(T->lchild,S);S->lchil

25、d=NULL;S->rchild=NULL;/Insert_Key9.40typedef struct int data;int bf;int lsize; /lsize域表示该结点的左子树的结点总数加 1BlcNode *lchild,*rchild; BlcNode,*BlcTree; / 含 lsize 域的平衡二叉排序树类型BTNode *Locate_BlcTree(BlcTree T,int k)/ 在含 lsize 域的平衡二叉排序树 T中确定第k小的结点指针if(!T) return NULL; /k 小于 1 或大于树结点总数if(T->lsize=k) retu

26、rn T; / else if(T->lsize>k)就是这个结点return Locate_BlcTree(T->lchild,k); /在左子树中寻找else return Locate_BlcTree(T->rchild,k-T->lsize);/ 在右子树中寻找 ,注意要修改 k 的值 /Locate_BlcTree9.41typedef struct enum LEAF,BRANCH tag; / 结点类型标识int keynum;BPLink parent; /双亲指针int keyMAXCHILD; / 关键字 union BPLinkchildMA

27、XCHILD;/ 非叶结点的孩子指针struct rectype *infoMAXCHILD;/ 叶子结点的信息指针BPNode *next; / 指向下一个叶子结点的链接 leaf; BPNode,*BPLink,*BPTree;/B+ 树及其结点 类型Status BPTree_Search(BPTree T,int key,BPNode *ptr,int pos)/B+树中按关键字随机查找的算法 , 返回包含关键字的叶子结点的指针 ptr 以及关键字在叶子 结点中的位置 posp=T;while(p.tag=BRANCH) / 沿分支向下查找 for(i=0;i<p->key

28、num&&key>p->keyi;i+); / 确定关键字所在子树 if(i=p->keynum) return ERROR; /关键字太大p=p->childi; for(i=0;i<p->keynum&&key!=p->keyi;i+); / 在叶子结点中查找 if(i=p->keynum) return ERROR; /找不到关键字ptr=p;pos=i;return OK;/BPTree_Search9.42void TrieTree_Insert_Key(TrieTree &T,StringTyp

29、e key)/ 在 Trie 树 T 中插 入字符串 key,StringType 的结构见第四章 q=(TrieNode*)malloc(sizeof(TrieNode); q->kind=LEAF;q->lf.k=key; / 建叶子结点 klen=key0;p=T;i=1; while(p&&i<=klen&&p->bh.ptrord(keyi) last=p; p=p->bh.ptrord(keyi); i+; / 自上而下查找 if(p->kind=BRANCH) / 如果最后落到分支结点 ( 无同义词 ):直接连上

30、叶子p->bh.ptrord(keyi)=q; / p->bh.num+;else / 如果最后落到叶子结点 ( 有同义词 ): r=(TrieNode*)malloc(sizeof(TrieNode); / 建立新的分支结点 last->bh.ptrord(keyi-1)=r; /用新分支结点取代老叶子结点和上一层的联系r->kind=BRANCH;r->bh.num=2; r->bh.ptrord(keyi)=q;r->bh.ptrord(p->lf.ki)=p; /新分支结点与新老两个叶子结点相连/TrieTree_Insert_Key分析

31、: 当自上而下的查找结束时 , 存在两种情况 . 一种情况 , 树中没有待插入关键 字的同义词 , 此时只要新建一个叶子结点并连到分支结点上即可 . 另一种情况 , 有 同义词 , 此时要把同义词的叶子结点与树断开 , 在断开的部位新建一个下一层的 分支结点 , 再把同义词和新关键字的叶子结点连到新分支结点的下一层 .9.43Status TrieTree_Delete_Key(TrieTree &T,StringType key)/在 Trie 树 T 中删除字符串 keyp=T;i=1;while(p&&p->kind=BRANCH&&i<

32、;=key0) / 查找待删除元素 last=p; p=p->bh.ptrord(keyi); i+;if(p&&p->kind=LEAF&&p->lf.k=key) /找到了待删除元素 last->bh.ptrord(keyi-1)=NULL; free(p); return OK;else return ERROR; / 没找到待删除元素 /TrieTree_Delete_Key9.44void Print_Hash(HashTable H)/ 按第一个字母顺序输出 Hash 表中的所有关键 字, 其中处理冲突采用线性探测开放定址法f

33、or(i=1;i<=26;i+) for(j=i;H.elemj.key;j=(j+1)%hashsizesizeindex) /线性探测 if(H(H.elemj.key)=i) printf("%sn",H.elemj);/Print_Hashint H(char *s)/求 Hash 函数if(s) return s0-96; / 求关键字第一个字母的字母序号 ( 小写 ) else return 0;/H9.45typedef *LNodeMAXSIZE CHashTable; / 链地址 Hash 表类型Status Build_Hash(CHashTabl

34、e &T,int m)输入一组关键字,建立 Hash表,表长为m,用链地址法处理冲突.if(m<1) return ERROR;T=malloc(m*sizeof(WORD); / 建立表头指针向量 for(i=0;i<m;i+) Ti=NULL;while(key=Inputkey()!=NULL) / 假定 Inputkey 函数用于从键盘输入关 键字 q=(LNode*)malloc(sizeof(LNode); q->data=key;q->next=NULL;n=H(key);if(!Tn) Tn=q; / 作为链表的第一个结点else for(p=T

35、n;p->next;p=p->next); p->next=q; / 插入链表尾部 . 本算法不考虑排序问题 ./whilereturn OK;/Build_Hash9.46Status Locate_Hash(HashTable H,int row,int col,KeyType key,int &k)/ 根据行列值在Hash表表示的稀疏矩阵中确定元素 key的位置k h=2*(100*(row/10)+col/10); / 作者设计的 Hash 函数 while(H.elemh.key&&!EQ(H.elemh.key,key) h=(h+1)%2

36、0000;if(EQ(H.elemh.key,key) k=h;else k=NULL;/Locate_Hash分析：本算法所使用的Hash表长20000,装填因子为50%,Hash函数为行数前两位 和列数前两位所组成的四位数再乘以二 , 用线性探测法处理冲突 . 当矩阵的元素 是随机分布时 , 查找的时间复杂度为 O(1).另解：第九章 查找习题及答案题号： 1 2 3 4 5 6 7 8 9 10 11 12 13 1415 16 17 1819 20 21 22 23一、基础知识题1. 对含有 n 个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?答：我们可以设立两个变量m

37、ax和min用于存放最大元和最小元 (的位置)，第一次取两个元素进行比较，大的放入max，小的放入 min，从第2次开始，每次取一个元素先和max比较，如果大于 max则以它替换 max并结束本次比较；若小于 max则再与min相比较，在最好的情况下，一路比较下去都不用和 min 相比较，所以这种情况下，至少要进行 n-1 次比较就能找到最大元和最小元。 (顺便说一下，最坏情况下，要进行 2n-3 次比较才能得到结果 )2. 若对具有 n 个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：(1) 查找不成功，即表中无关键字等于给定值 K

38、 的记录； (2) 查找成功，即表中有关键字等于给定值 K 的记录。答：查找不成功时，需进行n+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表和无序表是一样的。查找成功时，平均查找长度为 (n+1)/2, 有序表和无序表也是一样的。因为顺序查找对表的原始序列的有序性不感兴趣。3. 画出对长度为 18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。答：请看题图。等概率情况下，查找成功的平均查找长度为：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556也可以用公式代，大约为： ASL=(18+1)l

39、g(18+1)/18-1=3.346查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5. 如图：4. 为什么有序的单链表不能进行折半查找 ?答： 因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问， 这就要浪费很多时间， 还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。5. 设有序表为 (a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值 b,g 和 n 进行折半查找的过程。解： b 的查找过程如下 (其中括号表示当前查找区间，圆括号表示当前比较的关键字)下标：1 23 4 5 67 8

40、9 10 11 12 13第一次比较： a bc d e f (g) h ij k p q第二次比较：a b (c)d e f gh ijkpq第三次比较：a(b)c d e fgh ijkpq经过三次比较，查找成功。g 的查找过程如下：a b c d e f (g) h i j k p q一次比较成功。n 的查找过程如下：下标：1 2第一次比较： a b第二次比较：a b第三次比较：a b第四次比较：a b3 4 5 67 8 9 10c d e f (g) h ijc d e fg h i (j)c d e f gh ic d e fg h i11 12 13k p qk p qjk (p

41、) qj k p q经过四次比较，查找失败。6. 将(for, case, while, class, protected, virtual, public,private, do, template, const ,if,int)中的关键字依次插入初态为空的二叉排序树中，请画岀所得到的树T。然后画岀删去for之后的二叉排序树T',若再将for插入T'中得到的二叉排序树T''是否与T相同？最后给岀T"的先序、中序和后序序列。答：见题图 :T"的先序序列是： do case class const while protected private

42、 iffor int virtualpublic templateT"的中序序列是：case class const do for if int privateprotected public template virtual whileT"的后序序列是：const class case for int if private templatepublic virtual protected while do二叉排序树 T 如下图：删去 for 后的二叉排序树如下图：圈内的 for 表示再插入后的结点：7. 对给定的关键字集合，以不同的次序插入初始为空的树中，是否有可能得到同

43、一棵二叉排序树？答：有可能。如有两个序列： 3， 1， 2， 4 和 3 ， 4， 1， 2，它们插入空树所得的二叉排序树是相同的。8. 将二叉排序树 T的先序序列中的关键字依次插入一空树中，所得和二叉排序树T'与T"是否相同？为什么？答：这两棵二叉树完全相同。9. 设二叉排序树中关键字由 1至1000 的整数构成，现要查找关键字为 363的结点，下述关键字序列哪一个不可能是在二叉排序树上查找到的序列(a) 2 ， 252， 401 ， 398， 330, 344 ， 397， 363；(c) 925, 202, 911, 240, 912, 245, 363;(d) 2,

44、399, 387, 219, 266, 382, 381, 278, 363.答： (c) 是不可能查找到的序列。我们可以把这四个序列各插入到一个初始为空的二叉排序树中，结果可以发现， (c) 序列所形成的不是一条路径，而是有分支的，可见它是不可能在查找过程中访问到的序列。10. 设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗 ?答：此命题正确。假设最小元有左孩子，则根据二叉排序树性质，此左孩子应比最小元更小，如此一来就产生矛盾了，因此最小元不可能有左孩子，对于最大元也是这个道理。但最

45、大元和最小元不一定是叶子，它也可以是根、内部结点 ( 分支结点 ) 等，这得根据插入结点时的次序而定。如3，1， 2，4这个集合，根据不同的插入次序可以得到不同的二叉排序树：03/ 01 040202/ 0103040403020102/ 03新结点总是插入在二叉排序树的某个叶子上的。?若删去某结点中的一个关键字，而导致结点11. 在一棵m阶的B-树中，当将一关键字插入某结点而引起该结点的分裂时，此结点原有多少个关键字合并时，该结点中原有几个关键字答：在此树中，若由于一关键字的插入某结点而引起该结点的分裂时，则该结点原有m-1 个关键字。若删去某结点中一个关键字而导致结点合并时，该结点中原有厂

46、m/2q-1个关键字。12. 在一棵B-树中，空指针数总是比关键字数多一个，此说法是否正确？请问包含8个关键字的3阶B-树(即2-3树)最多有几个结点？最少有几个结点？画出这两种情况的B-树。答：这个说法是正确的。包含8个关键字的3阶B-树最多有7个结点，最少有 4个结点。见题图。 : 图如下：13. 从空树开始，依次输入20 , 30, 50 , 52 ,60 , 68, 70，画出建立2-3树的过程。并画出删除50和68后的B-树状态。答：过程如下：(1) 插入 20, 30： (2) 插入 50：(3) 插入 52： (4)插入 60：(5) 插入 68： (6)插入 70：(7) 删去

47、 50： (8) 删去 6814。画出依次插入 z,v,o,p,w,y 到图9.12(h)所示的5阶B-树的过程。答：如图：第一步,插入 z:第二、三步 , 插入 v,o ：第四五六步,插入 p,w,y:15. 在含有n个关键字的m阶B-树中进行查找，至多读盘多少次？完全平衡的二叉排序树的读盘次数大约比它大多少倍？答：在含有n个关键字的 m阶B-树中进行查找至多读盘次数不超过B-树高h,即logt(n+1)/2)+1,(注，此处t为底，值是除根外的每个内部结点的最小度数厂m/2n ).完全平衡的二叉树高为lgn,所以它的读盘次数至多也是lgn，它与上述B-树的读盘次数的比值约为lgt倍(此处底

48、是2).16. 为什么在内存中使用的B-树通常是3阶的，而不使用更高阶的B-树？答：因为查找等操作的cpu时间在B-树上是O(lgn ? (m/lgt), 而m/lgt>1,所以m较大时它所费时间比平衡的二叉排序树上相应操作时间大得多，因此，仅在内存中使用的B-树通常取最小值3.17. 为什么二叉排序树长高时，新结点总是一个叶子，而B-树长高时，新结点总是根？哪一种长高能保证树平衡？答：因为在二叉排序树中，关键字总是作为一个叶子结点插入以原来的树中，所以当树增高时，新结点总是一个叶子；而B-树中关键字插入总是插入到叶子结点内部，在叶结点中的关键字数目尚未超过它能够容纳的数目之前是不会增加

49、结点的，当关键字数超过结点可容纳的数目时，叶结点就时，才能引起树高增加，此时产生一个新的根结点。所以说B 树长高时，新结点总是根。显然，后一种长高总能保证树的平衡。18. 已知关键字序列为 (PAL,LAP,PAM,MAP,PAT,PET,SET,SAT,TAT,BAT) 试为它们设计一个散列函数，将其映射到区间0.n-1 上，要求碰撞尽可能的少。这里 n=11,13,17,19.解：我的设计的散列函数是这样的，把关键字串中的每一个字符按其所在位置分别将其 ASCII 值乘以一个不同的数，然后把这些值相加的和去对 n 求余，余数即为散列表中的位置。函数如下：int Hash (char key

50、)return (int)(key0+key1*0.618+key2*10)%n;我们可以设计一个程序来看看用这个散列函数得到的所有关键字映射到区间的位置：#include <stdio.h>#define n 11 file&#58/ 先用 11 来代入，我们可以用13， 17，19 依次代入验证int Hash (char key)return (int)(key0+key1*0.618+key2*10)%n;file&#58/ 此处我用了系数 1， 0.618 和 10，你也可以用其他的数代入看有没有更好的系数void main()chars104="

51、;PAL","LAP","PAM","MAP","PAT","PET","SET","SAT","TAT","BAT"/ 以上用一个二维数组来存放关键字序列int i;for(i=0; i<10;i+)printf("%d ",Hash(s );19. 对于一组给定的、固定不变的关键字序列，有可能设计出无冲突的散列函数H,此时称H为完备的散列函数(perfecthashing function)，若H能无冲突地将关键字完全填满散列表，则称H是最小完备(minimalperfect) 的散列函数。通常找完备的散列函数非常困难，找最小完备的散列函数就更困难。请问：(1)若h是已知关键字集合K的完备的散列函数，若要增加