义词,此时要把同义词的叶子结点与树断开,在断开的部位新建一个下一层的分支结点,再把同义词和新关键字的叶子结点连到新分支结点的下一层. 9.43
Status TrieTree_Delete_Key(TrieTree &T,StringType key)//在Trie树T中删除字符串key {
p=T;i=1;
while(p&&p->kind==BRANCH&&i<=key[0]) //查找待删除元素 {
last=p;
p=p->bh.ptr[ord(key[i])]; i++; }
if(p&&p->kind==LEAF&&p->lf.k=key) //找到了待删除元素 {
last->bh.ptr[ord(key[i-1])]=NULL; free(p); return OK; }
else return ERROR; //没找到待删除元素 }//TrieTree_Delete_Key 9.44
void Print_Hash(HashTable H)//按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法 {
for(i=1;i<=26;i++)
for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex]) //线性探测 if(H(H.elem[j].key)==i) printf(\}//Print_Hash
int H(char *s)//求Hash函数 {
if(s) return s[0]-96; //求关键字第一个字母的字母序号(小写) else return 0; }//H 9.45
typedef *LNode[MAXSIZE] CHashTable; //链地址Hash表类型
Status Build_Hash(CHashTable &T,int m)//输入一组关键字,建立Hash表,表长为m,用链地址法处理冲突. {
if(m<1) return ERROR;
T=malloc(m*sizeof(WORD)); //建立表头指针向量 for(i=0;i while((key=Inputkey())!=NULL) //假定Inputkey函数用于从键盘输入关键字 { q=(LNode*)malloc(sizeof(LNode)); q->data=key;q->next=NULL; n=H(key); if(!T[n]) T[n]=q; //作为链表的第一个结点 else { for(p=T[n];p->next;p=p->next); p->next=q; //插入链表尾部.本算法不考虑排序问题. } }//while return OK; }//Build_Hash 9.46 Status 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.elem[h].key&&!EQ(H.elem[h].key,key)) h=(h+1) 000; if(EQ(H.elem[h].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 14 15 16 17 18 19 20 21 22 23 一、基础知识题 1.对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较? 答：我们可以设立两个变量max和min用于存放最大元和最小元(的位置)，第一次取两个元素进行比较，大的放入max，小的放入min，从第2次开始，每次取一个元素先和max比较，如果大于max则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，一路比较下去都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元和最小元。(顺便说一下，最坏情况下，要进行2n-3次比较 才能得到结果) 2.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：(1)查找 不成功，即表中无关键字等于给定值K的记录；(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)lg(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 2 3 4 5 6 7 8 9 10 11 12 13 第一次比较： [a b c d e f (g) h i j k p q] 第二次比较： [a b (c)d e f] g h i j k p q 第三次比较： [a(b)]c d e f g h i j k p q 经过三次比较，查找成功。 g的查找过程如下： [a b c d e f (g) h i j k p q] 一次比较成功。 n的查找过程如下： 下标： 1 2 3 4 5 6 7 8 9 10 11 12 13 第一次比较： [a b c d e f (g) h i j k p q] 第二次比较： a b c d e f g [h i (j) k p q] 第三次比较： a b c d e f g h i j [k (p) q] 第四次比较： a b c d e f g h i j [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 if for int virtual public template T\的中序序列是：case class const do for if int private protected public template virtual while T\的后序序列是：const class case for int if private template public virtual protected while do 二叉排序树T如下图： 删去for后的二叉排序树如下图：圈内的for表示再插入后的结点： 7.对给定的关键字集合，以不同的次序插入初始为空的树中，是否有可能得到同一棵二叉排序树? 答：有可能。如有两个序列：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； (b) 924, 220, 911, 244, 898, 258, 362, 363; (c) 925, 202, 911, 240, 912, 245, 363; (d) 2, 399, 387, 219, 266, 382, 381, 278, 363. 答：(c)是不可能查找到的序列。我们可以把这四个序列各插入到一个初始为空的二叉排序树中，结果可以发现，(c)序列所形成的不是一条路径， 而是有分支的，可见它是不可能在查找过程中访问到的序列。 10.设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点 总是插在二叉排序树的某叶子上吗? 答：此命题正确。假设最小元有左孩子，则根据二叉排序树性质，此左孩子应比最小元更小，如此一来就产生矛盾了，因此最小元不可能有左孩子， 对于最大元也是这个道理。 但最大元和最小元不一定是叶子，它也可以是根、内部结点(分支结点)等，这得根据插入结点时的次序而定。如3，1，2，4 这个集合，根据不同的插入次序可以得到不同的二叉排序树： ○3 / \\ ○1 ○4 \\ ○2 ○2 / \\ ○1 ○3 \\ ○4 ○4 \\ ○3 \\ ○2 \\ ○1 ○2 / \\ ○1 ○4 / ○3 新结点总是插入在二叉排序树的某个叶子上的。 11.在一棵m阶的B-树中，当将一关键字插入某结点而引起该结点的分裂时，此结点原有多少个关键字?若删去某结点中的一个关键字，而导致结点 合并时，该结点中原有几个关键字? 答：在此树中，若由于一关键字的插入某结点而引起该结点的分裂时，则该结点原有m-1个关键字。 若删去某结点中一个关键字而导致结点合并时，该结点中原有┌m/2┐-1个关键字。 12.在一棵B-树中，空指针数总是比关键字数多一个，此说法是否正确?请问包含8个关键字的3阶B-树(即2-3树)最多有几个结点?最少有几个结