《数据结构》ds习题答案b

《《数据结构》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占“度度顶入出1012345000000110010020100103001010411000151000005(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)题已知有向图的邻接表，试写出计算各顶点的入度的算法。template

6、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<