资源描述:
《《数据结构》ds习题答案b》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、第七章集合与搜索树1.第137页,第(5),建立37,45,91,25,14,76,56,65为输入时的二叉搜索树,再从该树上依此删除76,45,则树形分别如何?逹成的二叉搜索树(b)删除76后(c)删除45后2.第137页,第(6)试写一个判定任意给定的二叉树是否二叉搜索树算法。intk二-8;boolfail二false;tempIatevoidBTree::IsBiTree(BTNode*p,int&k,bool&fail){if(p&&!fail){IsBiTree(p->lchild,k,fail);if(kelement)k=p->element
2、;elsefail=truc;IsBiTree(p->rchild,k,fail);}}3.第137页,第(12)5阶B-树的高度为2时,树中元素个数最少为多少?答:54.第137页,第(13)题从空树开始,以关键字序列:a,g,f,b,k,d,h,m,j,e,s,i,r,x,建立(1)4阶B-树;(2)5阶B-树。⑵5阶B-树1.第137页,第(14)题从上题的4阶B-树上依次删除a,c,f,ho1.第154页,第(3)题设散列表ht[ll],散列函数h(kcy)=key%11。采用线性探查法解决冲突,试用关键字值序列:70,25,80,35,60,45,50,55建立散列表。Key7025
3、803560455055h(Key)4332516001234567891055453525708060502.第154页,第(6)题给出用拉链方法解决冲突的散列表搜索操作的C++函数实现。templateboolLinkedHashTable::Search(constK&k,E&e)const{inti=k%M,j;HNode*p=ht[i];//元素结点类型Hnodewhile(p){if(p->elemcnt==k)rcturntrue;p=p->nextsynonym;}returnfalse;}3.第154页,第(3)题设散列表ht[ll],散列函
4、数h(key)=key%11。采用二次探查法解决冲突,试用关键字值序列:70,25,80,35,60,45,50,55建立散列表。Key7025803560455055h(Key)43325160012345678910453580257060501.第154页,第(4)题558035257060455012345678910对上题的例子,若采用双散列法,试以散列函数hi(key)=key%11,h2(key)=key%9+1建立散列表。Key7025803560455055hl(jkey)43325160h2(key)889971620第九章图i.第188页,第(1)题对下面的有向图求(1)
5、每个顶点的入度和出度;(2)强连通分量(3)邻接矩阵图题9-15II图题9-24312212122030占“度度顶入出1012345000000 110010020100103001010411000151000005(3)邻接矩阵(2)3个强连通分量第188页,第(2)题当以边〈1,0),<1,3>,〈2,1),〈2,4〉,<3,2〉,<3,4〉,〈4,0),<5,0)的次序从只有6个顶点没有边的图开始,通过依此插入这些边,画出该邻接表。(4,1〉,〈4,5〉,建立邻接表结构。012345EH3.第188页,第(4)题已知有向图的邻接表,试写出计算各顶点的入度的算法。template6、assT>voidLinkedGraph::Degree(){int*d=newint[n];inti;ENode*p;for(i=0;iadjvex]++;p=p->nextarc;}}for(i二0;i〈n;i++)cout<<"d["<7、接矩阵上实现有向图的深度优先搜索.templatcvoidMGraph::DFS(intv,boolvisitedf]){visited[v]=true;cout<