数据结构单元8练习参考答案

《数据结构单元8练习参考答案》由会员分享，可在线阅读，更多相关《数据结构单元8练习参考答案（17页珍藏版）》请在装配图网上搜索。

1、单元练习8一.判断题(下列各题,对的的请在前面的括号内打；错误的打 ）（）(1）图可以没有边，但不能没有顶点。()(2)在无向图中，(V1,V2)与(V,V1）是两条不同的边。(）（）邻接表只能用于有向图的存储。（）（4)一种图的邻接矩阵表达是唯一的。()(）用邻接矩阵法存储一种图时，所占用的存储空间大小与图中顶点个数无关,而只与图的边数有关。(）（)有向图不能进行广度优先遍历。（)(7）若一种无向图的以顶点1为起点进行深度优先遍历,所得的遍历序列唯一，则可以唯一拟定该图。()(8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角(或下三角）部分就可以了。（)（9)用邻接表法存储图时

2、,占用的存储空间大小只与图中的边数有关,而与结点的个数无关。（）(10)若一种无向图中任一顶点出发,进行一次深度优先遍历,就可以访问图中所有的顶点,则该图一定是连通的。二填空题（1） 图常用的存储方式有邻接矩阵和 邻接表 等。（2） 图的遍历有： 深度优先搜 和广度优先搜等措施。（3） 有条边的无向图邻接矩阵中，1的个数是 _2n_。（4） 有向图的边也称为 _ 弧_ 。（5） 图的邻接矩阵表达法是表达 _顶点_之间相邻关系的矩阵。（6） 有向图G用邻接矩阵存储,其第i行的所有元素之和等于顶点i的 _出度_。（7） n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为: O(2）。（8） n个

3、顶点e条边的图若采用邻接表存储，则空间复杂度为: (n) 。（9） 设有一稀疏图，则G采用 _邻接表_存储比较节省空间。（10） 设有一稠密图G，则G采用 _邻接矩阵_存储比较节省空间。（11） 图的逆邻接表存储构造只合用于 有向_图。（12） n个顶点的完全无向图有 n（n-1)/2_ 条边。（13） 有向图的邻接表表达适于求顶点的 出度 。（14） 有向图的邻接矩阵表达中，第i列上非0元素的个数为顶点Vi的 入度 。（15） 对于具有n个顶点的图，其生成树有且仅有 - 条边。（16） 对n个顶点，e条弧的有向图,其邻接表表达中，需要 n+e 个结点。（17） 从图中某一顶点出发,访遍图中其

4、他顶点，且使每一顶点仅被访问一次，称这一过程为图的 遍历 。（18） 无向图的邻接矩阵一定是 对称 矩阵。（19） 一种连通网的最小生成树是该图所有生成树中 权 最小的生成树。（20） 若规定一种稠密图的最小生成树,最佳用 rim 算法来求解。三选择题（1）在一种图中,所有顶点的度数之和等于图的边数的（ ）倍。 A.2 . 1 C. 2 D 4(2）在一种有向图中,所有顶点的入度之和等于所有顶点的出度之和的( B ）倍。 A.2 B C. D. 4(3）对于一种具有n个顶点的有向图的边数最多有（ B )。 A.n n(-1) C(n-)2 Dn(4)在一种具有n个顶点的无向图中，要连通所有顶点

5、至少需要（ C )条边。 A.n B+1 C n-1 D.n/2(5)有8个结点的有向完全图有( C )条边。 A.14 B. 28 C. 56 D. 12(6)深度优先遍历类似于二叉树的( )。 先序遍历 B.中序遍历 C.后序遍历 D.层次遍历（）广度优先遍历类似于二叉树的( )。 A.先序遍历 B.中序遍历 C后序遍历 D.层次遍历（8）任何一种无向连通图的最小生成树( A )。 A.只有一棵 B一棵或多棵 一定有多棵 D.也许不存在（9)无向图顶点的度是关联于该顶点( ）的数目。 A.顶点 B边 C序号 D下标(1)有n个顶点的无向图的邻接矩阵是用( B )数组存储。 A一维Bn行n列

6、 C.任意行列 .n行任意列（11)对于一种具有n个顶点和e条边的无向图,采用邻接表表达,则表头向量大小为( C )。 n-1n+1 n D+e（1）在图的表达法中,表达形式唯一的是（ ）。 A邻接矩阵表达法 B邻接表表达法 C.逆邻接表表达法 D邻接表和逆邻接表表达法（）在一种具有n个顶点e条边的图中,所有顶点的度数之和等于( C )。 A.n .e C. 2n D.2e(1)下图中,度为3的结点是( B ）。12354 V1 B.V2 C. V3 D. V12354（15）下图是(A ）。 A.连通图 强连通图 C 生成树 D. 无环图(1）如下图所示,从顶点a出发，按深度优先进行遍历,则

7、也许得到的一种顶点序列为（ D ）。abcfdeA ,b，e,c,，fB ,c，b，dC. ，e，b，c,f,dD. ，d，f，c，b(7）如下图所示，从顶点出发，按广度优先进行遍历，则也许得到的一种顶点序列为(A )。abcfdeA. a,b，e,c,fB. a,，,c,f，C. a,，b，c,f,dD. a，e，d,f,c，（1)最小生成树的构造可使用（ A )算法。 A.prim算法 B卡尔算法 C哈夫曼算法 D迪杰斯特拉算法(9）下面有关图的存储构造的论述中对的的是( A )。A 用邻接矩阵存储图,占用空间大小只与图中顶点数有关，而与边数无关B 用邻接矩阵存储图，占用空间大小只与图中边

8、数有关，而与顶点数无关 C 用邻接表存储图,占用空间大小只与图中顶点数有关,而与边数无关 D 用邻接表存储图,占用空间大小只与图中边数有关，而与顶点数无关(20）连通分量是( C )的极大连通子图。 A树 .图 C无向图.有向图四.应用题（30分).有向图如下图所示，画出邻接矩阵和邻接表解：（1）邻接矩阵 1 2 5()邻接表123524351542. 已知一种无向图有个结点，9条边,这9条边依次为（,1）,（0，2），(0,4),(0，5）,(1,2）,（2,3)，(2,），（,4),(4，)。试画出该无向图,并从顶点0出发,分别写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。(5分)

9、231D045解：从顶点0出发的深度优先搜索遍历的结点序列：0 2 3 4 5（答案不唯一)从顶点出发的广度优先搜索遍历的结点序列:0 12 4 5 3（答案不唯一) 已知一种无向图的顶点集为：a，b，c，d,e,其邻接矩阵如下,画出草图，写出顶点出发按深度优先搜索进行遍历的结点序列。(5分）解:acbed（1) (）深度优先搜索：a b d e (答案不唯一) 广度优先搜索: e d （答案不唯一) 4.网G的邻接矩阵如下，试画出该图,并画出它的一棵最小生成树。2543125431解: 最小生成树： 1 10 8 3 13 7 4 75. 已知某图G的邻接矩阵如图,(）画出相应的图; (2）

10、要使此图为完全图需要增长几条边。解:134242D31(1）(2）完全无向图应具有的边数为：n*(n-1)12=4*(4-1)2=6,因此还要增长2条边（如右图)。6已知如图所示的有向图，请给出该图的：（1） 每个顶点的入/出度;（2） 邻接表；(3） 邻接矩阵。解:（1) (2）顶点123456入度321122出度022313（3)7如图，请完毕如下操作:() 写出无向带权图的邻接矩阵；（) 设起点为,求其最小生成树。 解：（1）邻接矩阵为: （2）起点为，可以直接由原始图画出最小生成树 8.给定下列网G: （1） 画出网G的邻接矩阵；（2） 画出网G的最小生成树。解:(1)邻接矩阵 (）最

11、小生成树FBEDACGD五程序题填空题图G为有向无权图，试在邻接矩阵存储构造上实现删除一条边(v，)的操作：leteArc(G,，w)。若无顶点v或w,返回“EROR”；若成功删除,则边数减1，并返回“O”。（提示:删除一条边的操作，可以将邻接矩阵的第i行所有置0 )解:Sau elter（MGraph&G,charv,h w） /在邻接矩阵表达的图G上删除边(v，w） (=Locatex(G,v)）0) return ROR ; if （(j=LocteVex(,w)）rrn EROR ; if (G.arcij.ad) Garcsi.adj= 0 ; Garm ; （或 G.arnm=Ga

12、rcnum1 ） retu OK ; 六.算法题1 编写一种无向图的邻接矩阵转换成邻接表的算法。2 以知有个顶点的有向图邻接表,设计算法分别实现如下功能：(1)求出图中每个顶点的出度、入度。(2）求出G中出度最大的一种顶点，输出其顶点序号。（3）计算图中度为0的顶点数。1 解：本题思想是逐个扫描邻接矩阵的各个元素，若第i行第列的元素为1，则相应的邻接表的第i个单链表上增长一种j结点。vd trs(int dgesn,djladj)int i,;edgeode*p;or(i=0;in;i+） adji.data;ai.linkULL; for (i=0;in；i+）for (j=0;jadjve

13、x=j;p-next=adj.k;ajilk=； 2.(1）求出度的思想：计算出邻接表中第i个单链表的结点数即可。int outegre(ajlist dj,nt v)nt dge=0;edode *p;p=adjvink;whil (！=NUL) gree+;p=p-nx; retu egree;oid printo(adjls adj,intn）in ,degree;rintf(The Otegree re:n);o(0；iavx=) degre+; pp-ne； retrn degre；vod rntn(jlisad,in n）ini,degr；rit（e Inereea：n);for

14、(i=0;i；i） eg=Ineg(aj,n,i);pinf(%d,d）,i,ge）; (2)求最大度的算法voaxoudgree（adjlis adj,intn）in mxeree=0,v=0,dee,;for(i0;in；i+) egreeotdegree(a，i)；f (egeeaxgre) mader=ere;maxvi; pritf（mxoutdegre%d,mxvertex%,maxdegre,mav)；（)求度为0的顶点数的算法int otzer（adjlistadj,nt n）int m=0,i;fr (=0;in;+) if (oudegre(dj,i)=0) m+; ret

15、urnnm；模拟考题 已知如图所示的有向图,请给出该图的:（1） 每个顶点的入度和出度;（2） 逆邻接表。 解：（1） (2）顶点123456入度321122出度0223132. 给定下列网: （1） 写出网G以B为顶点的广度优先遍历的序列;（2） 画出网G的最小生成树。解：(1）以B为顶点的广度优先遍历的序列: (2)最小生成树FBEDACGD B A E F C D3 无向图G如图所示,（1）试画出邻接矩阵；（2）写出从A出发的深度优先遍历的序列。DCADBGEF解：（1) 邻接矩阵 （2)从A出发的深度优先遍历的序列: A BD G F(不唯一）3. 已知图G的邻接表如下，以顶点1为出发

16、点，完毕下列问题:12423524155(1)写出以顶点1为出发点的广度优先遍历序列；(2)画出以顶点1为出发点的深度优先搜索得到的一棵二叉树。解:（1）广度优先遍历序列:1，,4，3 （2）深度优先搜索得到的一棵二叉树:532D14532D145试填空完毕深度优先搜索的递归函数。#dfineMAXVE 100 /定义图的最大顶点数truct verex in n; / 顶点编号 car data; / 顶点的信息;tydftruct grapsut vertx vxsAXVEX; / 顶点集合int edesMAXEX MAVX； / 边的集合sdjmax；nt visitedMAVEX;viddf(ajlstdj,int v) / 深度优先搜索的递归函数 ti; strucdgend *p; for(=1;iink ; hle ( p！=NULL ) if（isitedp-djvex= 0 ) / 从的未访问过的邻接点出发进行深度优先搜索 df（adj, padvex ）； p-net; / 找v的下一种邻接点