《数据结构题集答案 第9章 查找.docx》由会员分享，可在线阅读，更多相关《数据结构题集答案 第9章 查找.docx（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第九章 查找 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);els
2、e 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) r
3、eturn 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-
4、); /依次查找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
5、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 l
6、ast=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); /本算法仍是借助中序
7、遍历来实现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,
8、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的元
9、素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*
10、)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(
11、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&l
12、ast-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)/课本上给出的删除二叉排序树
13、的子树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;
14、/重接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); /插入
15、元素/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分析:这是一个与课本上不同
16、的插入算法.在合并过程中,并不释放或新建任何结点,而是实行修改指针的方式来完成合并.这样,就必需依据后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱. 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-d
17、ata) /其余部分与上一题同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; /含
18、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 typed
19、ef 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
20、+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针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 TrieTr
21、ee_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+;els
22、e /假如最终落到叶子结点(有同义词):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分析:当自上而下的查找结束时,存在两种状况.一种状况,树中没有待插入关键字的同义词,此时只要新建一个叶子结点并连到分支结点上即可.另一种状况,有同义词,此时要把
23、同义词的叶子结点与树断开,在断开的部位新建一个下一层的分支结点,再把同义词与新关键字的叶子结点连到新分支结点的下一层. 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; /没找到待删除元素/T
24、rieTree_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 typ
25、edef *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; /插入链表尾部.本算法不考虑排序问题./whileretu
26、rn 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函数为
27、行数前两位与列数前两位所组成的四位数再乘以二,用线性探测法处理冲突.当矩阵的元素是随机分布时,查找的时间困难度为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则再与
28、min相比较，在最好的状况下，一路比较下去都不用与min相比较，所以这种状况下，至少要进行n-1次比较就能找到最大元与最小元。(顺便说一下，最坏状况下，要进行2n-3次比较才能得到结果)2.若对具有n个元素的有序的依次表与无序的依次表分别进行依次查找，试在下述两种状况下分别探讨两者在等概率时的平均查找长度：(1)查找不胜利，即表中无关键字等于给定值K的记录；(2)查找胜利，即表中有关键字等于给定值K的记录。答：查找不胜利时，需进行n+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表与无序表是一样的。查找胜利时，平均查找长度为(n+1)/2,有序表与无序表也是一样的。因为依次查找对
29、表的原始序列的有序性不感爱好。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.为什么有序的单链表不能进行折半查找答：因为链表无法进行随机访问，假如要访问链表的中间结点，就必需先从头结点起先进行依次访问，这就要奢侈许多时间，还不如进行依次查
30、找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。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一次比较胜
31、利。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之后的二
32、叉排序树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
33、 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
34、，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这个集合，依据不同的插入次序可以得到不同的二叉排序树