第七章习题参考答案
单项选择题
1. A 2. D 3. D 4. C 5. B 6. B 7. B 8. A 9. B 10. D 11. A 12. C 13. A 填空题
1、0，n(n-1)/2 ，0，n(n-1) 2、n+2e 3、N 4、遍历 n个出边表，计算数据域为j的结点个数 5、将矩阵的第j行全部置为零 6、回路 7邻接矩阵，邻接表 8、先根，栈，按层次，队列 问答题
1. 深度优先搜索序列：0,2,3,5,6,1,4 广度优先搜索序列：0,2,3,5,6,1,4 2. 深度优先搜索序列：0,3,6,4,1,5,2 广度优先搜索序列：0,3,2,6,5,4,1 3. Prim过程如图所示 50 V1 60 V3 V1 V1 V3 52 45 V3 50 65 42 V2 50 V4 V7 V2 V4 V7 V2 V4 V7 40 30 V5 V6 V5 70 V6 V5 V6 (a)
(b) (c)
V1 V3 V1 V3 V1
50 50 50 V3 V2 V4 V7 V2 V4 V7 V2 V4 V7 40 40 50 40 50 30
V5 V6 V5 V6 V5 V6
(d) (e) (f) V1 V3 50 50 V1 V3 V2 V4 42 45 V7 42 50 30 V2 V4 V7 40 50 30 V5 V6 40 V5 V6
(g)
(h)
、
Kruskal过程如图所示。 V1 V1 V3 V3
V4 V4 V7 V2 V7 V2 30 V5 V6
(a)
V1 V3 45 42 V7 V4 V2 30 40 V5 V6 (d)
40 V5 30 (b)
V1 V2 40 V5 V4 30 (c)
V3 42 V7 V6 V6 50 V2 40 V1 V4 V5 30 (e)
V3 42 45 V7 V6 42 V4 V7 V2 50 30 40 V5 V6 (f)
50 V1 V3 45
4. 求解过程如下表所示。 终点 从v0到各终点的D值和最短路径的求解过程 i=1 V1 V2 ∞ 10 (v0,v2) V3 V4 ∞ 30 60 (v0,v2,v3) 30 (v0,v4) (v0,v4) V5 Vj S 100 (v0,v5) V2 100 (v0,v5) V4 90 (v0,v4,v5) V3 {v0,v2,v3,v4} 60 (v0,v4,v3,v5) V5 {v0,v2,v3,v4,v5} 50 (v0,v4,v3) i=2 ∞ i=3 ∞ i=4 ∞ i=5 ∞ 无
{v0,v2} {v0,v2,v4} 5. 关键路径如图所示。
a9=4 v1 a2=4 v5 v3 a5=3 v11 a15=6 v8 a13=10
图
v9 v1001 a14=1 四、算法设计题
1. 分析：先设置一个空的邻接表，然后在邻接矩阵上查找值不为空的元素，找到后在邻接表的对应单链表中插入相应的边表结点。算法如下：
void mattolist( adjmatrix a, adjlist b, int n) { for (i=0;i for (j=n-1;j>=0;j--) if (a[i][j]!=0) { p=(lkList)malloc(sizeof (Lnode)); p?adjvex=j; p?nextarc=b[i].firstarc; b[i].firstarc=p; } }//mattolist 2. 分析：先建立一个空的邻接矩阵，然后在邻接表上顺序地取每个单链表中的表结点，如果表结点不为空，则将邻接矩阵中对应单元的值置为1。算法如下： void listtomat (adjlist b, int n , adjmatrix a ) { for (i=0;i while (p) { a[i][p?adjvex]=1; p=p?nextarc; } } }//listtomat 3. 分析：邻接表存储结构中边表恰好就是出边表，因此，其表头数组中firstarc域 为空的个数等于出度为零的元素个数。算法如下： int sum_zero(adjlist a, int n ) { count=0; for (i=0;i if (a[i][j].firstarc= =Null) count++; return (count); }//sum_zero