第7章图的答案.doc

第7章图











































1.√
2. ×
3.×
4.×
5.×
6.√
7.×
8.×
9.×
10.×
11.√
12.×
13.√
14.×
15.×
16.×
17.√
18.×
19.×
20.×
21.×
22.×
23.×
24.×
25.×
26.√
27.×
28.√
29.×
30.×
31.√
32.√
33.×
34.×
35.×
36.√
37.×
38.×
39.×
40.×
41.√
42.×
43.×
44.√
45.×
46.×
47.×
48. √
49.×
部分答案解释如下。
2. 不一定是连通图,可能有若干连通分量 11. 对称矩阵可存储上(下)三角矩阵
16. 邻接矩阵中元素值可以存储权值
21. 只有无向连通图才有生成树 22. 最小生成树不唯一,但最小生成树上权值之和相等
26. 是自由树,即根结点不确定
35. 对有向无环图,拓扑排序成功;否则,图中有环,不能说算法不适合。
42. AOV网是用顶点代表活动,弧表示活动间的优先关系的有向图,叫顶点表示活动的网。
45. 能求出关键路径的AOE网一定是有向无环图
46. 只有该关键活动为各关键路径所共有,且减少它尚不能改变关键路径的前提下,才可缩短工期。
,AOE网中关键路径是从“源点”到“汇点”路径长度最长的路径。自然,关键路径上活动的时间延长多少,整个工程的时间也就随之延长多少。

,n-1条边的无向连通图 3. 生成树
4. 45 5. n(n-1)/2 6 . 7. 9 8. n
9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n 15. N
16. 3 17. 2(N-1) 18. 度出度 19. 第I列非零元素个数 2e
21.(1)查找顶点的邻接点的过程(2)O(n+e) (3)O(n+e) (4)访问顶点的顺序不同(5)队列和栈
22. 深度优先
,答案不唯一。本题按邻接表存储结构,邻接点按字典序排列。
K
B
A
J
E
I
D
C
F
A
D
F
C
E
B
K
I
J
25题(1) 25题(2)
(prim)算法和克鲁斯卡尔(Kruskal)算法
29. O(eloge) 边稀疏 (n2) O(eloge)
31.(1)(Vi,Vj)边上的权值都大的数(2)1 负值(3)为负边
32.(1)n-1 (2)普里姆(3)最小生成树
(n2) 37. 50,经过中间顶点④ 38. 75 (n+e)
40.(1)活动(2)活动间的优先关系(3)事件(4)活动边上的权代表活动持续时间
42.(1)某项活动以自己为先决条件(2)荒谬(3)死循环
43.(1)零(2)Vk度减1,若Vk入度己减到零,则Vk顶点入栈(3)环
44.(1)p<>nil (2)visited[v]=true (3)p=g[v].firstarc (4)p=p^.nextarc
45.(1)g[0].vexdata=v (2)g[j].firstin (3)g[j].firstin (4)g[i].firstout (5)g[i].firstout (6)p^.vexj (7)g[i].firstout (8)p:=p^.nexti (9)p<>nil (10)p^.vexj=j
(11)firstadj(g,v0) (12)not visited[w] (13)nextadj(g,v0,w)
46.(1)0 (2)j (3)i (4)0 (5)indegree[i]==0 (6)[vex][i