（5） 有以下3个强连通分量
【21， 7，3】（选自《数据结构题集》7.4，选做题）
试对教科书7.1节中图7.3（a）所示的无向图 (如下图)，画出其广度优先生成森林。
答：其广义优先生成森林如下：
【22， 7，4】（选自《数据结构题集》7.5，选做题）
已知以二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
1 2 3 4 5 6 7 8 9 10
1 0 0 0 0 0 1 0 1 0 1
2 0 0 0 0 0 1 0 0 0 0
3 0 1 0 0 0 0 1 0 0 0
4 0 0 1 0 0 0 0 1 0 0
5 0 0 0 1 0 0 0 0 1 0
6 0 0 0 0 1 0 0 0 0 1
7 1 1 0 0 0 0 0 0 1 0
8 0 0 1 0 0 0 0 0 0 0
9 1 0 0 1 0 0 0 1 0 0
10 0 0 0 0 1 0 1 0 1 0
答：其深度优先生成树和广度优先生成树分别如下：
【23， 7，4】（选自《数据结构题集》7.7，必做题） 请对下图的无向带权图，
（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。
答：(1) 其邻接矩阵为
a b c d e f g h
a 0 4 3 0 0 0 0 0
b 4 0 5 5 9 0 0 0
c 3 5 0 5 0 0 0 5
d 0 5 5 0 7 6 5 4
e 0 9 0 7 0 3 0 0
f 0 0 0 6 3 0 2 0
g 0 0 0 5 0 2 0 6
h 0 0 5 4 0 0 6 0
按普里姆算法，得最小生成树为
(2) 其邻接表为：
按克鲁斯卡尔算法求得的最小生成树同上。
【24， 7，5】（选自《数据结构题集》7.10，选做题）
对于题7.10图所示的AOE网络，计算各活动弧的e（ai）和l（aj）函数值、各事件（顶点）的ve（vi）和vl（vj）函数值；列出各条关键路径
解：e（ai）为活动ai的最早开始时间，l（aj）为活动aj最迟必须开始的时间，ve（ai）为事件的最早发生时间，vl（aj）为事件的最迟发生时间 活动 （α，A） （α，B） （α，D） （α，F） （α，G） （α，I） （A，C） （B，C） （D，C） （D，E） （D，J） （F，E） 事件 α A B C D E ve（ai） 0 1 6 11 3 34 vl（aj） 0 20 24 26 19 34 事件 G H I J K ω ve（ai） 3 13 1 31 22 44 vl（aj） 3 13 7 31 22 44 e（ai） 0 0 0 0 0 0 1 6 3 3 3 4 L（aj） 19 18 16 4 0 6 20 24 19 26 25 23 L-e 19 18 16 4 0 6 19 18 16 23 22 19 活动 （F，H） （G，ω） （G，H） （I，H） （C，E） （H，C） （H，J） （H，K） （K，J） （J，E） （J，ω） （E，ω） e（ai） 4 3 3 1 17 13 13 13 22 31 31 34 L（aj） 8 23 3 7 26 22 27 13 22 31 32 34 L-e 4 20 0 6 26 9 14 0 0 0 1 0 F
4 8 关键路经：α—G—H—K—J—E—ω
【25， 7，6】（选自《数据结构题集》7.11，必做题）
试利用Dijkstra算法求题7.11图中从顶点a到其他各顶点间的最短路径，写出执行算法中各步的状态。
解： 终点 Dist K＝1 K＝2 K＝3 K＝4 K＝5 K＝6 b 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) c 2 (a,c) d 12 (a,d) 12 (a,d) 11 (a,c,f,d) 11 (a,c,f,d) e 10 (a,c,e) 10 (a,c,e) f 6 (a,c,f) g 16 (a,c,f,g) 16 (a,c,f,g) S {a,c} {a,c,f} {a,c,f,e} {a,c,f,e,d} 14 {a,c,f,e,d,g} (a,c,f,d,g) {a,c,f,e,d,b}
【26， 9，1】（选自《数据结构题集》9.3，必做题）
画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 解：其判定树如下：