第7章图习题及参考答案

上传人:飞*** 文档编号:35355720 上传时间:2018-03-14 格式:PDF 页数:8 大小:229.16KB
返回 下载 相关 举报
第7章图习题及参考答案_第1页
第1页 / 共8页
第7章图习题及参考答案_第2页
第2页 / 共8页
第7章图习题及参考答案_第3页
第3页 / 共8页
第7章图习题及参考答案_第4页
第4页 / 共8页
第7章图习题及参考答案_第5页
第5页 / 共8页
点击查看更多>>
资源描述

《第7章图习题及参考答案》由会员分享,可在线阅读,更多相关《第7章图习题及参考答案(8页珍藏版)》请在金锄头文库上搜索。

1、1 第 7 章习题一、单项选择题1.在无向图中定义顶点的度为与它相关联的()的数目。A. 顶点B. 边C. 权D. 权值2.在无向图中定义顶点vi与 vj之间的路径为从vi到达 vj的一个() 。A. 顶点序列B. 边序列C. 权值总和D. 边的条数3.图的简单路径是指()不重复的路径。A. 权值B. 顶点C. 边D. 边与顶点均4.设无向图的顶点个数为n,则该图最多有()条边。A. n- 1 B. n(n- 1)/2 C. n(n+1)/2 D. n(n- 1) 5.n 个顶点的连通图至少有()条边。A. n - 1 B. n C. n+1 D. 0 6.在一个无向图中,所有顶点的度数之和等

2、于所有边数的( ) 倍。A. 3 B. 2 C. 1 D. 1/2 7.若采用邻接矩阵法存储一个n 个顶点的无向图,则该邻接矩阵是一个( )。A. 上三角矩阵B. 稀疏矩阵C. 对角矩阵D. 对称矩阵8.图的深度优先搜索类似于树的()次序遍历。A. 先根B. 中根C. 后根D. 层次9.图的广度优先搜索类似于树的()次序遍历。A. 先根B. 中根C. 后根D. 层次10. 在用Kruskal 算法求解带权连通图的最小(代价)生成树时,选择权值最小的边的原则是该边不能在图中构成() 。A. 重边B. 有向环C. 回路D. 权值重复的边11. 在用 Dijkstra 算法求解带权有向图的最短路径问

3、题时,要求图中每条边所带的权值必须是() 。A. 非零B. 非整C. 非负D. 非正12. 设 G1 = (V1, E1) 和 G2 = (V2, E2) 为两个图,如果V1 V2,E1 E2,则称() 。A. G1是 G2的子图B. G2是 G1的子图C. G1是 G2的连通分量D. G2是 G1的连通分量13. 有向图的一个顶点的度为该顶点的() 。A. 入度B. 出度C. 入度与出度之和D. (入度出度 )2 14. 一个连通图的生成树是包含图中所有顶点的一个()子图。A. 极小B. 连通C. 极小连通D. 无环15. n (n1) 个顶点的强连通图中至少含有()条有向边。A. n -

4、1 B. n n(n- 1)/2 D. n(n- 1) 16. 在一个带权连通图G 中,权值最小的边一定包含在G 的()生成树中。A. 某个最小B. 任何最小C. 广度优先D.深度优先17. 对于具有e条边的无向图,它的邻接表中有()个结点。A. e- 1 B. e C. 2(e- 1) D. 2e 18. 对于如图所示的带权有向图,从顶点1 到顶点 5 的最短路径为() 。A.1, 4, 5 B. 1, 2, 3, 5 C. 1, 4, 3, 5 D. 1, 2, 4, 3, 5 1 2 63 89 5 5 4 1 2 3 2 19. 一个有 n 个顶点和n 条边的无向图一定是() 。A.

5、连通的B. 不连通的C. 无环的D. 有环的20. 对于有向图,其邻接矩阵表示比邻接表表示更易于() 。A. 求一个顶点的度B. 求一个顶点的邻接点C. 进行图的深度优先遍历D. 进行图的广度优先遍历21. 与邻接矩阵相比,邻接表更适合于存储()图。A. 无向B.连通C.稀疏D. 稠密图22. 为了实现图的广度优先遍历,BFS 算法使用的一个辅助数据结构是() 。A. 栈B. 队列C. 二叉树D. 树 二、填空题1.用邻接矩阵存储图,占用存储空间数与图中顶点个数_关,与边数 _关。2.n (n0) 个顶点的无向图最多有_条边,最少有_条边。3.n (n0) 个顶点的连通无向图最少有_条边。4.

6、若 3 个顶点的图G 的邻接矩阵为010001010 ,则图 G 一定是 _向图。5.n (n0) 个顶点的无向图中顶点的度的最大值为_。6.(n0) 个顶点的连通无向图的生成树至少有_条边。7.在使用 Kruskal 算法构造连通网络的最小生成树时,只有当一条候选边的两个端点不在同一个_上,才有可能加入到生成树中。8.求解带权连通图最小生成树的Prim 算法适合于 _图的情形,而Kruskal 算法适合于 _图的情形。 三、判断题1.一个图的子图可以是空图,顶点个数为0。2.存储图的邻接矩阵中,矩阵元素个数不但与图的顶点个数有关,而且与图的边数也有关。3.对一个连通图进行一次深度优先搜索(d

7、epth first search)可以遍访图中的所有顶点。4.有 n (n1) 个顶点的无向连通图最少有n- 1 条边。5.如果无向图中各个顶点的度都大于2,则该图中必有回路。6.如果有向图中各个顶点的度都大于2,则该图中必有回路。7.图的广度优先搜索(breadth first search)算法不是递归算法。8.有 n 个顶点、 e 条边的带权有向图的最小生成树一般由n 个顶点和n- 1 条边组成。9.对于一个边上权值任意的带权有向图,使用 Dijkstra 算法可以求一个顶点到其它各个顶点的最短路径。10. 有回路的有向图不能完成拓扑排序。11. 对任何用顶点表示活动的网络(AOV 网

8、)进行拓扑排序的结果都是唯一的。12. 用边表示活动的网络(AOE 网)的关键路径是指从源点到终点的路径长度最长的路径。13. 对于 AOE 网络,加速任一关键活动就能使整个工程提前完成。14. 对于 AOE 网络,任一关键活动延迟将导致整个工程延迟完成。15. 在 AOE 网络中,可能同时存在几条关键路径,称所有关键路径都需通过的有向边为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。16. 用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中的顶点个数有关,而与图的边数无关。17. 邻接表只能用于有向图的存储,邻接矩阵对于有向图和无向图的存储都适用。18.

9、 邻接矩阵只适用于稠密图(边数接近于顶点数的平方),邻接表适用于稀疏图(边数远小于顶点数的平方)19. 存储无向图的邻接矩阵是对称的,因此只要存储邻接矩阵的下(上)三角部分就可以了。20. 连通分量是无向图中的极小连通子图。3 21. 在 AOE 网络中一定只有一条关键路径。 四、运算题1.设连通图G 如图所示。试画出该图对应的邻接矩阵表示,并给出对它执行从顶点V0开始的广度优先搜索的结果。2.设连通图G 如图所示。试画出该图及其对应的邻接表表示,并给出对它执行从V0开始的深度优先搜索的结果。3.对于如图所示的有向图,试写出:(1) 从顶点出发进行深度优先搜索所得到的深度优先生成树;(2) 从

10、顶点出发进行广度优先搜索所得到的广度优先生成树4.设有向图G 如图所示。试画出从顶点V0开始进行深度优先搜索和广度优先搜索得到的DFS 生成森林和 BFS 生成森林。5.设有一个连通网络如图所示。试按如下格式,应用Kruskal 算法给出在构造最小生成树过程中顺序选出的各条边。V0V1V2V5V4 V3V6V7V8V0V1V2V5V4 V3V6V7V8V1V2V3V4V7V6V0V50 1 2 3 4 5 6 6 1 8 7 5 3 4 2 6 4 ( 始顶点号,终顶点号,权值) ( , , ) ( , , ) ( , , ) ( , , ) ( , , ) 6.设有一个连通网络如图所示。试采

11、用prim 算法从顶点0 开始构造最小生成树。 (写出加入生成树顶点集合 S和选择边Edge 的顺序)S: 顶点号Edge: (顶点,顶点,权值) 0 ( ,) 0 ( ,) 0 ( ,) 0 ( ,) 0 ( ,) 0 7.有八项活动 , 每项活动要求的前驱如下: 活动A0 A1 A2 A3 A4 A5 A6 A7 前驱无前驱A0 A0 A0, A2 A1 A2, A4 A3 A5, A6 (1) 试画出相应的AOV 网络 , 并给出一个拓扑排序序列。(2) 试改变某些结点的编号, 使得用邻接矩阵表示该网络时所有对角线以下的元素全为0。8.试对下图所示的AOE 网络(1) 这个工程最早可能在

12、什么时间结束。(2) 确定哪些活动是关键活动。画出由所有关键活动构成的图,指出哪些活动加速可使整个工程提前完成。9.设带权有向图如图所示。试采用Dijkstra 算法求从顶点0 到其他各顶点的最短路径和最短路径长度。1 11 15 19 10 2 2 3 4 4 5 5 6 6 1 2 3 4 6 5 0 9 10 7 5 11 8 7 7 1 8 2 4 4 5 9 1 2 3 4 0 5 第 7 章习题参考答案一、单项选择题参考答案:1. B 2.A 3.B 4.B 5. A 6. B 7. D 8.A 9.D 10.C 11. C 12.A 13.C 14.C 15. B 16. A 1

13、7.D 18. D 19.D 20.A 21. C 22. B 二、填空题参考答案 :1. 有, 无2. n(n- 1)/2, 0 3. n- 1 4. 有5. (n- 1) 6. n- 1 7. 连通分量8. 稠密,稀疏 三、判断题参考答案:1. 否2. 否3. 是4. 是5. 是6. 否7. 是8. 否9. 否10. 是11. 否12. 是13. 否14. 是15. 是16. 是17. 否18. 是19. 是20. 否21. 否四、运算题参考答案:1.图 G 对应的邻接矩阵为0010000000010010001100010000000001000000000100110001110001

14、01001000011001000001110G.Edge执行广度优先搜索的结果为V0V1V3V2V4V7V6V5V8,搜索结果不唯一。2.图 G 对应的邻接表为:3 1 3 2 0 3 1 0 3 5 0 1 2 6 7 6 6 2 1 3 7 8 0 V01 V12 V23 V34 V45 V56 V67 V78 V86 执行深度优先搜索的结果为:V0V1V4V3V6V7V8V2V5,搜索结果不唯一。3.以顶点 为根的深度优先生成树(不唯一):以顶点 为根的广度优先生成树:4.深度优先生成森林为:广度优先生成森林为:应用 Kruskal 算法顺序选出最小生成树的各条边为:( 始顶点号,终顶

15、点号,权值) ( 0, 3, 1 ) ( 2, 5, 2 ) ( 1, 4, 3 ) ( 3, 5, 4 ) ( 3, 4, 5 ) 5.采用 prim 算法从顶点0 开始构造最小生成树的过程:S: 顶点号Edge: (顶点,顶点,权值) 0 ( 0,1,9 ) 0, 1 ( 1,3,5 ) 0, 1, 3 ( 1,2,7 ) 0, 1, 3, 2 ( 2,4,6 ) 0, 1, 3, 2, 4 ( 2,5,7 ) 0, 1, 3, 2, 4, 5 V1V2V3V4V7V6V0V5V1V2V3V4V7V6V0V50 1 2 3 4 5 1 5 3 4 2 1 2 3 4 6 5 0 9 7 5

16、 7 7 6.相应的 AOV 网络为:一个拓扑排序序列为:A0,A1,A4,A2,A5,A3,A6,A7。注意:拓扑排序结果不唯一。按拓扑有序的次序对所有顶点从新编号:原编号A0 A1 A4 A2 A5 A3 A6 A7 新编号A0 A1 A2 A3 A4 A5 A6 A7 相应邻接矩阵为:76543210000000001000000001000000100000000011000000010000000001000010101076543210Edge7.针对下图所示的AOE 网络各顶点(事件)的最早可能开始时间Ve(i)和最迟允许开始时间Vl(i) 参看下表:顶点1 2 3 4 5 6 Ve 0 19 15 29 38 43 Vl 0 19 15 37 38 43 各边(活动)的最早可能开始时间E

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 研究报告 > 综合/其它

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号