2023年练习题第6章.pdf

《2023年练习题第6章.pdf》由会员分享，可在线阅读，更多相关《2023年练习题第6章.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第六章的练习题 一、选择题 1设无向图的顶点个数为 n，则该图最多有（）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En2 2一个 n 个顶点的连通无向图，其边的个数至少为（）。An-1 Bn Cn+1 Dnlogn；3要连通具有 n 个顶点的有向图，至少需要（）条边。An-l Bn Cn+l D2n 4n 个结点的完全有向图含有边的数目（）。An*n Bn（n）Cn2 Dn*（nl）5一个有 n 个结点的图，最少有（）个连通分量，最多有（）个连通分量。A0 B1 Cn-1 Dn 6在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等

2、于所有顶点出度之和的（）倍。A1/2 B2 C1 D4 7一个图中包含 K个连通分量，若按深度优先搜索方法访问所有结点，则必须调用（）次深度优先搜索遍历算法。A1 BK-1 CK DK+1 8下列哪一种图的邻接矩阵是对称矩阵？（）A有向图 B无向图 CAOV 网 DAOE网 9 从邻接阵矩可以看出，该图共有（）个顶点；如果是有向图该图共有（）条弧；如果是无向图，则共有（）条边。A9 B3 C6 D1 E以上答案均不正确 A5 B4 C3 D2 E以上答案均不正确 A5 B4 C3 D2 E以上答案均不正确 10对某个无向图的邻接矩阵来讲，（）。A第 i 行上的非零元素个数和第 i 列的非零元素

3、的个数一定相等 B矩阵中的非零元素个数等于图中的边数 C第 i 行上，第 i 列上非零元素总数等于顶点 vi 的度数 D矩阵中非全零行的行数等于图中的顶点数 11无向图 G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是（）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b 12.设图如右所示，在下面的 5 个序列中，符合深度优先遍历的序列有多少？（）a e b d f c a c f d e b a e d

4、 f c b a e f d c b a e f d b c 010101010A abedcfA5 个 B4 个 C3 个 D2 个 第 12 题图 第 13 题图 13.下图中给出由 7 个顶点组成的无向图。从顶点 1 出发，对它进行深度优先遍历得到的序列是()，而进行广度优先遍历得到的顶点序列是（）。A1354267 B1347652 C1534276 D1247653 E以上答案均不正确 A1534267 B1726453 Cl354276 D1247653 E以上答案均不正确 14下面哪一方法可以判断出一个有向图是否有环（回路）：A深度优先遍历 B.拓扑排序 C.求最短路径 D.求关

5、键路径 15.已知有向图 G=(V,E)，其中 V=V1,V2,V3,V4,V5,V6,V7，E=,G的拓扑序列是（）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7 CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V7 16一个有向无环图的拓扑排序序列（）是唯一的。A一定 B不一定 17.在有向图 G的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是（）。AG中有弧 BG中有一条从 Vi 到 Vj 的路径 CG中没有弧 DG中有一条从 Vj 到 Vi 的路径 二、填空题 1.设无向图 G 有 n

6、个顶点和 e 条边，每个顶点 Vi 的度为 di（1=i=n，则 e=_ 2G是一个非连通无向图，共有 28 条边，则该图至少有_个顶点。3.在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_条弧。4在有 n 个顶点的有向图中，每个顶点的度最大可达_。5N个顶点的连通图的生成树含有_条边。6有 N个顶点的有向图，至少需要量_条弧才能保证是连通的。7右图中的强连通分量的个数为_个。8N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_个非零元素。9在图 G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_；对于有向图来说等于该顶点的_。10.在有向图的邻接

7、矩阵表示中，计算第 I 个顶点入度的方法是_。11.已知一无向图 G=（V，E），其中 V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点 a 开始遍历图，得到的序列为 abecd，则采用的是_遍历方法。12.一无向图 G（V，E），其中 V（G）=1,2,3,4,5,6,7，E（G）=（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）,对该图从顶点 3 开始进行遍历，去掉遍历中未走过的边，得一生成树 G(V，E）,V（G）=V（G），E（G）=（1,3），（3,6），（7,3），（1,2）

8、，（1,5），（2,4），则采用的遍历方法是_。13.按下图所示，画出它的广度优先生成树_和深度优先生成树_。14求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树。15.有向图 G=(V,E),其中 V(G)=0,1,2,3,4,5，用 三元组表示弧 及弧上的权 d.E(G)为,，则从源点 0 到顶点 3 的最短路径长度是_，经过的中间顶点是_。16AOV 网中,结点表示_,边表示_。AOE网中,结点表示_,边表示_。17在 AOV网 中，存在环意味着_，这是_的；对程序的数据流图来说，它表明存在_。18.当一个 AOV 网用邻接表表示时，可按下列方法进行拓扑排序。（1）查邻接表中

9、入度为_的顶点，并进栈；（2）若栈不空，则输出栈顶元素 Vj，并退栈；查 Vj 的直接后继 Vk，对 Vk入度处理，处理方法是_；（3）若栈空时，输出顶点数小于图的顶点数，说明有_，否则拓扑排序完成。三、应用题 1 首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出从面点 1 开始的深度，广度优先遍历的结果。3 6 7 5 8 9 4 2 1 2下面的邻接表表示一个给定的无向图 （1）给出从顶点 v1 开始,对图 G用深度优先搜索法进行遍历时的顶点序列；（2）给出从顶点 v1 开始,对图 G用广度优先搜索法进行遍历时的顶点序列。3设 G=(V,E)以邻接表存储，如图所示，试画出从顶

10、点 1 出发的图的深度优先和广度优先生成树。4已知一个无向图如下图所示，要求分别用 Prim 和 Kruskal 算法生成最小树（假设以为起点，试画出构造过程）。第 4 题 第五题 5请看无向加权图。（1）写出它的邻接矩阵；（2）按 Prim 算法求从顶点 1 出发的最小生成树，并给出构造最小生成树过程中辅助数组的各分量值。辅助数组内各分量值：Y Closedge 2 3 4 5 6 7 8 U V-U Adjvex Lowcost Adjvex Lowcost Adjvex Lowcost Adjvex Lowcost Adjvex Lowcost 123451341241232423455

11、1 2 6 5 4 3 20 10 11 6 6 18 10 14 5 9 Adjvex Lowcost Adjvex Lowcost Adjvex Lowcost 6已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M),下表给定了这六大城市之间的交通里程:世界六大城市交通里程表(单位:百公里)（1）画出这六大城市的交通网络图;（2）画出该图的邻接表表示法;（3）画出该图按权值递增的顺序来构造的最小(代价)生成树.7下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下

12、一个边结点的指针。试求：由顶点 V1到顶点V3的最短路径。8已知图的邻接矩阵为：V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V1 0 1 1 1 0 0 0 0 0 0 V2 0 0 0 1 1 0 0 0 0 0 V3 0 0 0 1 0 1 0 0 0 0 PE N PA L T M PE 109 82 81 21 124 N 109 58 55 108 32 PA 82 58 3 97 92 L 81 55 3 95 89 T 21 108 97 95 113 M 124 32 92 89 113 V1V2V3V4V5V6233429625336230338542110

13、618123456(顶点边)（出边表）V4 0 0 0 0 0 1 1 0 1 0 V5 0 0 0 0 0 0 1 0 0 0 V6 0 0 0 0 0 0 0 1 1 0 V7 0 0 0 0 0 0 0 0 1 0 V8 0 0 0 0 0 0 0 0 0 1 V9 0 0 0 0 0 0 0 0 0 1 V10 0 0 0 0 0 0 0 0 0 0 当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出：（1）以顶点 V1为出发点的唯一的深度优先遍历；（2）以顶点 V1为出发点的唯一的广度优先遍历；（3）该图唯一的拓扑有序序列。四、算法题 1编写图的创建算法（邻接矩阵和邻接表，分无向、有向和带权图）。2读懂图的遍历算法。