数据结构 用c++语言描述 习题答案02.pdf

《数据结构 用c++语言描述 习题答案02.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章集合与搜索树1．第137页，第（5）,建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依此删除76，45，则树形分别如何？2．第137页，第（6）试写一个判定任意给定的二叉树是否二叉搜索树算法。intk=-∞;boolfail=false;templatevoidBTree::IsBiTree(BTNode*p,int&k,bool&fail){if(p&&!fail){IsBiTree(p->lchild,k,fail);if(kelement)k=p->element;elsefail=t

2、rue;IsBiTree(p->rchild,k,fail);}}3．第137页，第（8）以下列序列为输入，从空树开始构造AVL搜索树。（1)A，Z，B，Y，C，X（2)A,V,L,T,R,E,I,S,O,K4．第137页，第（12）5阶B-树的高度为2时，树中元素个数最少为多少？答:55．第137页，第（13）题从空树开始，以关键字序列：a,g,f,b,k,d,h,m,j,e,s,i,r,x,建立(1)4阶B-树;(2)5阶B-树。(1)4阶B-树(2)5阶B-树6．第137页，第（14）题从上题的4阶B-树上依次删除a,e,f,h。第八章散列与跳表1．第154页，

3、第（3）题设散列表ht[11]，散列函数h(key)=key%11。采用线性探查法解决冲突，试用关键字值序列：70，25，80，35，60，45，50，55建立散列表。2．第154页，第（6）题给出用拉链方法解决冲突的散列表搜索操作的C++函数实现。templateboolLinkedHashTable::Search(constK&k,E&e)const{inti=k%M,j;HNode*p=ht[i];//元素结点类型Hnodewhile(p){if(p->element==k)returntrue;p=p->nextsynony

4、m;}returnfalse;}3．第154页，第（3）题设散列表ht[11]，散列函数h(key)=key%11。采用二次探查法解决冲突，试用关键字值序列：70，25，80，35，60，45，50，55建立散列表。4．第154页，第（4）题对上题的例子，若采用双散列法，试以散列函数h1(key)=key%11，h2(key)=key%9+1建立散列表。第九章图1．第188页，第（1）题对下面的有向图求(1)每个顶点的入度和出度；(2)强连通分量(3)邻接矩阵2．第188页，第（2）题当以边〈1，0〉，〈1，3〉，〈2，1〉，〈2，4〉，〈3，2〉，〈3，4〉，〈4，

5、0〉，〈4，1〉，〈4，5〉，〈5，0〉的次序从只有6个顶点没有边的图开始，通过依此插入这些边，建立邻接表结构。画出该邻接表。3．第188页，第（4）题已知有向图的邻接表，试写出计算各顶点的入度的算法。templatevoidLinkedGraph::Degree(){int*d=newint[n];inti;ENode*p;for(i=0;iadjvex]++;p=p->nextarc;}}for(i=0;i

6、d["<voidMGraph::DFS(intv,boolvisited[]){visited[v]=true;cout<<""<

7、．第188页，第（10）题设某项工程由图题9-3所示的工序组成。若各工序以流水方式进行（即串行进行）。(1)画出给工程的AOV网络；(2)给出该工程的全部合理的工程流程。7．第188页，第（11）题设有边集合：〈0，1〉，〈1，2〉，〈4，1〉，〈4，5〉，〈5，3〉，〈2，3〉(1)求此图的所有可能的拓扑序列；(2)若以此顺序通过加入边的方式建立邻接表，则在该邻接表上执行拓扑排序算法（TopoSort），则得到的拓扑序列是其中哪一种？8.第188页，第（13）题使用普里姆算法以1为源点，画出图题9-5的无向图的最小代价生成树。9.第188页，第（1