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

第九章 查找 9.25 int Search_Sq(SSTable ST,int key)/在有序表上顺序查找的算法,监视哨设在高下标端ST.elemST.length+1.key=key;for(i=1;ST.elemi.keykey;i+);if(iST.length|ST.elemi.keyhigh) return 0; /查找不到时返回0mid=(low+high)/2;if(ST.elemmid.key=key) return mid;else if(ST.elemmid.keykey)return Search_Bin_Recursive(ST,key,low,mid-1);else return Search_Bin_Recursive(ST,key,mid+1,high);/Search_Bin_Recursive 9.27 int Locate_Bin(SSTable ST,int key)/折半查找,返回小于或等于待查元素的最后一个结点号int *r;r=ST.elem;if(key=rST.length.key) return ST.length;low=1;high=ST.length;while(low=rmid.key&keyrmid+1.key) /查找结束的条件return mid;else if(keyL.idxL.blknum.maxkey) return ERROR; /超过最大元素low=1;high=L.blknum;found=0;while(low=high&!found) /折半查找记录所在块号midmid=(low+high)/2;if(keyL.idxmid-1.maxkey)found=1;else if(keyL.idxmid.maxkey)low=mid+1;else high=mid-1;i=L.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(kdata=key) return L.t;else if(L.t-datakey)for(p=L.h,i=1;p-data!=key;p=p-next,i+);elsefor(p=L.t,i=L.tpos;p-data!=key;p=p-next,i+);L.t=p; /更新t指针return p;/Search_CSList分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3. 9.30 typedef 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-datakey)while(p-datakey) p=p-pre;L.sp=p;else if(p-datadatanext;L.sp=p;return p;/Search_DSList分析:本题的平均查找长度与上一题相同,也是n/3. 9.31 int last=0,flag=1; int Is_BSTree(Bitree T)/判断二叉树T是否二叉排序树,是则返回1,否则返回0if(T-lchild&flag) Is_BSTree(T-lchild);if(T-datadata;if(T-rchild&flag) Is_BSTree(T-rchild);return flag;/Is_BSTree 9.32 int last=0; void MaxLT_MinGT(BiTree T,int x)/找到二叉排序树T中小于x的最大元素和大于x的最小元素if(T-lchild) MaxLT_MinGT(T-lchild,x); /本算法仍是借助中序遍历来实现if(lastdata=x) /找到了小于x的最大元素printf(a=%dn,last);if(lastdatax) /找到了大于x的最小元素printf(b=%dn,T-data);last=T-data;if(T-rchild) MaxLT_MinGT(T-rchild,x);/MaxLT_MinGT 9.33 void Print_NLT(BiTree T,int x)/从大到小输出二叉排序树T中所有不小于x的元素if(T-rchild) Print_NLT(T-rchild,x);if(T-datadata);if(T-lchild) Print_NLT(T-lchild,x); /先右后左的中序遍历/Print_NLT 9.34 void Delete_NLT(BiTree &T,int x)/删除二叉排序树T中所有不小于x元素结点,并释放空间if(T-rchild) Delete_NLT(T-rchild,x);if(T-datalchild;free(q); /如果树根不小于x,则删除树根,并以左子树的根作为新的树根if(T) Delete_NLT(T,x); /继续在左子树中执行算法/Delete_NLT 9.35 void Print_Between(BiThrTree T,int a,int b)/打印输出后继线索二叉排序树T中所有大于a且小于b的元素p=T;while(!p-ltag) p=p-lchild; /找到最小元素while(p&p-datadataa) printf(%dn,p-data); /输出符合条件的元素if(p-rtag) p=p-rtag;elsep=p-rchild;while(!p-ltag) p=p-lchild; /转到中序后继/while/Print_Between 9.36 void BSTree_Insert_Key(BiThrTree &T,int x)/在后继线索二叉排序树T中插入元素xif(T-datartag) /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-datax) /插入到左子树中if(!T-lchild) /T没有左子树时,作为左孩子插入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_Key 9.37 Status BSTree_Delete_key(BiThrTree &T,int x)/在后继线索二叉排序树T中删除元素xBTNode *pre,*ptr,*suc;/ptr为x所在结点,pre和suc分别指向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; /转到中序后继last=p;/while /借助中序遍历找到元素x及其前驱和后继结点if(!ptr) return ERROR; /未找到待删结点Delete_BSTree(ptr); /删除x结点if(pre&pre-rtag)pre-rchild=suc; /修改线索return OK;/BSTree_Delete_key void Delete_BSTree(BiThrTree &T)/课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动q=T;if(!T-ltag&T-rtag) /结点无右子树,此时只需重接其左子树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-rchild=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合并到T中if(S-lchild) BSTree_Merge(T,S-lchild);if(S-rchild) BSTree_Merge(T,S-rchild); /合并子树Insert_Key(T,S); /插入元素/BSTree_Merge void Insert_Node(Bitree &T,BTNode *S)/把树结点S插入到T的合适位置上if(S-dataT-data)if(!T-rchild) T-rchild=S;else Insert_Node(T-rchild,S);else if(S-datadata)if(!T-lchild) T-lchild=S;else Insert_Node(T-lchild,S);S-lchild=NULL; /插入的新结点必须和原来的左右子树断绝关系S-rchild=NULL; /否则会导致树结构的混乱/Insert_Node分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱. 9.39 void BSTree_Split(BiTree &T,BiTree &A,BiTree &B,int x)/把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于xif(T-lchild) BSTree_Split(T-lchild,A,B,x);if(T-rchild) BSTree_Split(T-rchild,A,B,x); /分裂左右子树if(T-datadataT-data) /其余部分与上一题同if(!T-rchild) T-rchild=S;else Insert_Node(T-rchild,S);else if(S-datadata)if(!T-lchild) T-lchild=S;else Insert_Node(T-lchild,S);S-lchild=NULL;S-rchild=NULL;/Insert_Key 9.40 typedef struct int data; int bf; int lsize; /lsize域表示该结点的左子树的结点总数加1 BlcNode *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) return T; /就是这个结点else if(T-lsizek)return Locate_BlcTree(T-lchild,k); /在左子树中寻找else return Locate_BlcTree(T-rchild,k-T-lsize); /在右子树中寻找,注意要修改k的值/Locate_BlcTree 9.41 typedef struct enum LEAF,BRANCH tag; /结点类型标识 int keynum; BPLink parent; /双亲指针 int keyMAXCHILD; /关键字 union BPLink childMAXCHILD;/非叶结点的孩子指针 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;ikeynum&keyp-keyi;i+); /确定关键字所在子树if(i=p-keynum) return ERROR; /关键字太大p=p-childi;for(i=0;ikeynum&key!=p-keyi;i+); /在叶子结点中查找if(i=p-keynum) return ERROR; /找不到关键字ptr=p;pos=i;return OK;/BPTree_Search 9.42 void TrieTree_Insert_Key(TrieTree &T,StringType 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&ibh.ptrord(keyi)last=p;p=p-bh.ptrord(keyi);i+; /自上而下查找if(p-kind=BRANCH) /如果最后落到分支结点(无同义词):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分析:当自上而下的查找结束时,存在两种情况.一种情况,树中没有待插入关键字的同义词,此时只要新建一个叶子结点并连到分支结点上即可.另一种情况,有同义词,此时要把同义词的叶子结点与树断开,在断开的部位新建一个下一层的分支结点,再把同义词和新关键字的叶子结点连到新分支结点的下一层. 9.43 Status TrieTree_Delete_Key(TrieTree &T,StringType key)/在Trie树T中删除字符串keyp=T;i=1;while(p&p-kind=BRANCH&ibh.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_Key 9.44 void Print_Hash(HashTable H)/按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法for(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_Hash int H(char *s)/求Hash函数if(s) return s0-96; /求关键字第一个字母的字母序号(小写)else return 0;/H 9.45 typedef *LNodeMAXSIZE CHashTable; /链地址Hash表类型 Status Build_Hash(CHashTable &T,int m)/输入一组关键字,建立Hash表,表长为m,用链地址法处理冲突.if(m1) return ERROR;T=malloc(m*sizeof(WORD); /建立表头指针向量for(i=0;idata=key;q-next=NULL;n=H(key);if(!Tn) Tn=q; /作为链表的第一个结点elsefor(p=Tn;p-next;p=p-next);p-next=q; /插入链表尾部.本算法不考虑排序问题./whilereturn OK;/Build_Hash 9.46 Status Locate_Hash(HashTable H,int row,int col,KeyType key,int &k)/根据行列值在Hash表表示的稀疏矩阵中确定元素key的位置kh=2*(100*(row/10)+col/10); /作者设计的Hash函数while(H.elemh.key&!EQ(H.elemh.key,key)h=(h+1)%20000;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个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?答：我们可以设立两个变量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 23 4 5 678 9 10 11 12 13第一次比较： a bc d e f (g) h ijkpq第二次比较： 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 23 4 5 678 9 1011 12 13第一次比较： a bc d e f (g) h ij kpq第二次比较：a bc d e fg h i (j)kpq第三次比较：a bc d e fgh ijk (p) q第四次比较：a bc d e fgh ijk pq经过四次比较，查找失败。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 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.对给定的关键字集合，以不同的次序插入初始为空的树中，是否有可能得到同一棵二叉排序树?答：有可能。如有两个序列：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 422/13443212/14/3新结点总是插入在二叉排序树的某个叶子上的。11.在一棵m阶的B-树中，当将一关键字插入某结点而引起该结点的分裂时，此结点原有多少个关键字?若删去某结点中的一个关键字，而导致结点合并时，该结点中原有几个关键字?答：在此树中，若由于一关键字的插入某结点而引起该结点的分裂时，则该结点原有m-1个关键字。若删去某结点中一个关键字而导致结点合并时，该结点中原有m/2-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)删去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/2).完全平衡的二叉树高为lgn,所以它的读盘次数至多也是lgn，它与上述B-树的读盘次数的比值约为lgt倍(此处底是2).16.为什么在内存中使用的B-树通常是3阶的，而不使用更高阶的B-树?答：因为查找等操作的cpu时间在B-树上是O(lgn(m/lgt),而m/lgt1,所以m较大时它所费时间比平衡的二叉排序树上相应操作时间大得多，因此，仅在内存中使用的B-树通常取最小值3.17.为什么二叉排序树长高时，新结点总是一个叶子，而B-树长高时，新结点总是根?哪一种长高能保证树平衡?答：因为在二叉排序树中，关键字总是作为一个叶子结点插入以原来的树中，所以当树增高时，新结点总是一个叶子；而B-树中关键字插入总是插入到叶子结点内部，在叶结点中的关键字数目尚未超过它能够容纳的数目之前是不会增加结点的，当关键字数超过结点可容纳的数目时，叶结点就会发生分裂，产生一个新结点(但不一定引起树增高)，并且将其中的中间结点传至上一层，只有当这种分裂操作传递至根结点并引起根结点的分裂时，才能引起树高增加，此时产生一个新的根结点。所以说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)return (int)(key0+key1*0.618+key2*10)%n;我们可以设计一个程序来看看用这个散列函数得到的所有关键字映射到区间的位置：#include #define n 11 filefile/ 以上用一个二维数组来存放关键字序列int i;for(i=0; i10;i+)printf(%d,Hash(s);19.对于一组给定的、固定不变的关键字序列，有可能设计出无冲突的散列函数H，此时称H为完备的散列函数(perfecthashing function)，若H能无冲突地将关键字完全填满散列表，则称H是最小完备(minimalperfect)的散列函数。通常找完备的散列函数非常困难，找最小完备的散列函数就更困难。请问：(1)若h是已知关键字集合K的完备的散列函数，若要增加一个新的关键字到集合K，一般情况下H还是完备的吗?(2)已知关键字集合为(81，129，301，38，434，216，412，487，234)，散列函数为H(x)=(x+18)/63,请问H是完备的吗?它是最小完备的吗?(3)考虑由字符串构成的关键字集合(Bret,Jane,Shirley,Bryce,Michelle,Heather)，试为散列表0.6设计一个完备的散列函数。(提示：考虑每个字符串的第3个字符，即s2)答：(1)一般情况下