发布时间 : 星期六 文章第7章图习题和参考答案解析更新完毕开始阅读1379b00f03d276a20029bd64783e0912a2167c88
.WORD.格式.
第7章习题参考答案
一、单项选择题
参考答案： 1. B
6. B 11. C 16. A 21. C
2.A 3.B 7. D 8.A 12.A 13.C 17.D 18. D 22. B
4.B 9.D 14.C 19.D
5. A 10.C 15. B 20.A
二、填空题
参考答案： 1. 有, 无 2. n(n-1)/2, 0 3. n-1 4. 有
5. (n-1) 6. n-1 7. 连通分量 8. 稠密，稀疏
三、判断题
参考答案： 1. 否
6. 否 11. 否 16. 是
2. 否 3. 是 7. 是 8. 否 12. 是 13. 否 17. 否 18. 是 19. 是
4. 是 9. 否 14. 是 20. 否 21.
5. 是 10. 是 15. 是 否
四、运算题
参考答案：
1. 图G对应的邻接矩阵为
?0?1??1??1G.Edge??0??0?0??0?0?11100000?00110000??00101000??11000110? 10000000??01000000?00100011??00100100?00000100??
执行广度优先搜索的结果为V0V1V3V2V4V7V6V5V8，搜索结果不唯一。
2. 图G对应的邻接表为：
0 V0
1 V1 1 0 3 3 2 ∧ 1 ∧ 0 5 ∧ 3 2 V 2.专业资料.整理分享. 0 1 2 3 V3 7 ∧ 6 4 V4 1 ∧ .WORD.格式.
执行深度优先搜索的结果为：V0V1V4V3V6V7V8V2V5，搜索结果不唯一。 3. 以顶点 ① 为根的深度优先生成树（不唯一）：
① ①
② ③ ② ③
④ ⑤ ④ ⑤
以顶点 ② 为根的广度优先生成树：
①
② ③
④ ⑤
4. 深度优先生成森林为： 广度优先生成森林为： V0 V0
V3 V3
V 2V1 V2
V4 V5 V6
V7
V5 V6
V4 V7
V1
应用Kruskal算法顺序选出最小生成树的各条边为： ( 始顶点号，终顶点号， 权值 ) ( 0, 3, 1 ) ( 2, 5, 2 ) ( 1, 4, 3 ) ( 3, 5, 4 ) ( 3, 4, 5 )
5. 采用prim算法从顶点0开始构造最小生成树的过程：
S: 顶点号 0 0, 1 0, 1, 3 0, 1, 3, 2 0, 1, 3, 2, 4 Edge: 0 1 3 4 5 1 3 2 4 2 5 (顶点，顶点，权值) ( 0， 1， 9 ) ( 1， 3， 5 ) ( 1， 2， 7 ) ( 2， 4， 6 ) ( 2， 5， 7 ) .专业资料.整理分享.
.WORD.格式. 0, 1, 3, 2, 4, 5
0
9
7 1 2
5 7 6
3 4 5
6. 相应的AOV网络为： A1 A2
A4 A3 A0 A7
A5 A6
一个拓扑排序序列为：A0,A1,A4,A2,A5,A3,A6,A7。 注意：拓扑排序结果不唯一。 按拓扑有序的次序对所有顶点从新编号： 原编号 新编号 A0 A0 A1 A1 A4 A2 A2 A3 A5 A4 A3 A5 A6 A6 A7 A7
相应邻接矩阵为：
0?0?0??0?Edge??0?0??0?0???012345671010100?0100000??0001000??0001100?0000001??0000010?0000001??0000000??012 34567
7. 针对下图所示的AOE网络
10 2 4 2 6
1 19 6 4 15 11 5 5 3
各顶点（事件）的最早可能开始时间Ve(i)和最迟允许开始时间Vl(i)参看下表：
顶点 Ve Vl
1 0 0
2 19 19
3 15 15
4 29 37
5 38 38
6 43 43
.专业资料.整理分享.
.WORD.格式.
各边（活动）的最早可能开始时间Ee(k)和最迟允许开始时间El(k)参看下表：
边 Ee El
<1,2> <1,3> <3,2> <2,5> <3,5> <2,4> <4,6> <5,6> 0 17
0 0
15 15
19 19
15 27
19 27
29 37
38 38
如果活动k的最早可能开始时间Ee(k) 与最迟允许开始时间El(k)相等，则该活动是关键活动。本题的关键活动为<1,3>, <3,2>, <2,5>, <5,6>，它们组成关键路径。这些关键活动中任一个提前完成，整个工程就能提前完成。
整个工程最早在43天完成。由关键活动组成的AOV网络如图所示。 10 2 4 2 6
1 19 6 4 15 11 5 5 3
8. 带权有向图如图所示： 8
0 4 1 7 2 4 1 9 2
5 3 4
应用Dijkstra算法求从顶点V0到其他各顶点的最短路径Path和最短路径长度Len的步骤如下：
步骤 1 2 3 4 V0 V1 Path Len V0V1 V0V1 V0V1 V0V1 V0V1 V0V1 V0V1 4 4 4 4 4 4 4 V2 Path — V0V1V2 V0V1V2 V0V1V2 V0V1V2 V0V1V2 V0V1V2 V3 Len Path Len ∞ 8 8 8 8 8 8 V0V3 V0V3 V0V3 V0V3 V0V3 V0V3 V0V3 7 7 7 7 7 7 7 V4 Path — — — V0V3V4 V0V3V4 V0V1V2V4 V0V1V2V4 Len ∞ ∞ ∞ 12 12 10 10 动作 选V0V1 参照V1调整 选V0V3 参照V3调整 选V0V1V2 参照V2调整 选V0V1V2V4
.专业资料.整理分享.