模拟卷2 数据结构第41题

← 题目列表

模拟卷数据结构 ★★★★ 信号量解答题

第 41 题

（11 分）如下图所示：

（1）写出该图的邻接矩阵。

（2）写出全部拓扑序列。

（3）以 V1 为源点，以 V8 为终点，给出所有事件（和活动）允许发生的最早时间和最晚时间，并给出关键路径。

（4）求 V1 结点到各点的最短路径和距离。

信号量

[tag_link]

**【解析】** (1) 该图对应的邻接矩阵如下： $[图片] \infty \infty \infty \infty \infty \infty \infty \infty 2 \infty \infty \infty \infty \infty \infty \infty 3 \infty \infty \infty \infty \infty \infty \infty \infty 53 \infty \infty \infty \infty \infty \infty \infty 10 \infty \infty 2 \infty \infty \infty \infty \infty 4 \infty \infty \infty \infty \infty \infty \infty \infty 3 \infty \infty \infty \infty \infty \infty \infty \infty 61 \infty [图片]$

(2) 只有顶点 $V 1$ 的入度为 0，由此可以得到两个拓扑序列： $V 1, V 2, V 3, V 4, V 6, V 5, V 7, V 8$ 和 $V 1, V 3, V 2, V 4, V 6, V 5, V 7, V 8$ 。

(3) 关键路径共有 3 条，长 17。依次为： $V 1 \to V 2 \to V 4 \to V 6 \to V 8$ ， $V 1 \to V 3 \to V 5 \to V 7 \to V 8$ ， $V 1 \to V 2 \to V 4 \to V 6 \to V 5 \to V 7 \to V 8$ 。

事件	V1	V2	V3	V4	V5	V6	V7	V8
最早发生时间	0	2	3	7	13	11	16	17
最晚发生时间	0	2	3	7	13	11	16	17

活动	V2-V4	V3-V4	V3-V5	V4-V6	V6-V5	V5-V7	V6-V8	V7-V8
最早开始时间	2	3	3	7	11	13	11	16
最晚开始时间	2	4	3	7	11	13	11	16
时间余量	0	1	0	0	0	0	0	0

(4) 顶点 $V 1$ 到其他各顶点的最短路径和距离为：

$2 (V 1 \to V 2)$
$3 (V 1 \to V 3)$
$6 (V 1 \to V 3 \to V 4)$
$12 (V 1 \to V 3 \to V 4 \to V 6 \to V 5)$
$10 (V 1 \to V 3 \to V 4 \to V 6)$
$15 (V 1 \to V 3 \to V 4 \to V 6 \to V 5 \to V 7)$
$16 (V 1 \to V 3 \to V 4 \to V 6 \to V 5 \to V 7 \to V 8 或 V 1 \to V 3 \to V 4 \to V 6 \to V 8)$

← 上一题下一题 →