数据结构（C语言版）（第2版）课后习题答案

① ③

?? ?

?4 ? 3 ??? ??? ??? ?????43????????? 5 ? ?4??????6????? ?559?? 5 ? 5 ? ? ?

59???5???5?76547?3??63?2?5?2?6 ②

a b c d e f g

→ → → → → → → b a a b b d d 4 4 3 5 9 6 5 → → → → → → → c c b c d e f 3 5 5 5 7 3 2 →→ → → → → d d e f g h → e 9 5 5 → h 5 7 → f 6 →

3 2

6

5 → h 4 g

（3）已知图的邻接矩阵如图6.34所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

（4）有向网如图6.35所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。

图6.28 邻接矩阵

47

图6.35 有向网 图6.34 邻接矩阵

表6.9 D 终点 b c d e f g i=1 15 (a,b) 2 (a,c) 12 (a,d) ∞ ∞ ∞ S 终点集 {a,c} {a,c,f} {a,c,f,e} i=2 15 (a,b) 12 (a,d) 10 (a,c,e) 6 (a,c,f) ∞ i=3 15 (a,b) 11 (a,c,f,d) 10 (a,c,e) 16 (a,c,f,g) i=4 15 (a,b) 11 (a,c,f,d) 16 (a,c,f,g) {a,c,f,e,d} i=5 15 (a,b) 14 (a,c,f,d,g) {a,c,f,e,d,g} {a,c,f,e,d,g,b} i=6 15 (a,b)

（5）试对图6.36所示的AOE-网： ① 求这个工程最早可能在什么时

间结束；

② 求每个活动的最早开始时间和

最迟开始时间；

③ 确定哪些活动是关键活动

48