Skip to content

2022年 408 数据结构 第 7 题

数据结构2022年选择题2分

题目

下图是一个有 10 个活动的 AOE 网,时间余量最大的活动是 ( )。

a=2b=5c=1d=3e=3f=4g=1h=1i=4j=1v1v2v3v4v5v6

错因

A

只看到 c 的持续时间短(=1)就以为余量大。但余量与活动持续时间长短无关,要算 才能比较。c (2→3) 实际余量 ,远小于 g 的 6。把"看起来轻量"当成"余量大"是典型直觉错误。

C

把 h(4→5) 与 g(3→6) 混淆——两者持续时间都为 1,看起来差不多。但 h 处于"4→5→6"路径上,前置活动 4 已经被关键路径 (b-e-i) 拉到 ,h 的早开始 、晚开始 ,余量只有 2。而 g 是从 3 直接跨到终点 6 的"捷径",绕过了关键路径上的紧约束,余量自然最大。

D

j(5→6) 的早开始 、晚开始 ,余量 。选 D 的人可能只看到"j 也是从中间汇入终点的小活动"就当作和 g 一样,但 5 是 b-e-h 与 b-f 共同推到的较紧节点,留给 j 的弹性远小于 g。

总解析

思路:AOE 网每个活动 的时间余量公式

求解步骤:① 拓扑序求各事件的最早发生时间 ;② 逆拓扑序求最迟发生时间 ;③ 对每个活动算 slack。

Step 1:求 (从 v1 顺推,取入边 max)

事件公式
v1起点0
v22
v35
v48
v59
v612

工程总工期 =

Step 2:求 (从 v6 逆推,取出边 min)

事件公式
v6终点 = 12
v511
v48
v35
v24
v10

Step 3:算每个活动的 slack

活动slack
a1→2204−2=22
b1→3505−5=00
c2→3125−1=42
d2→4328−3=53
e3→4358−3=50
f3→54511−4=72
g3→61512−1=116
h4→51811−1=102
i4→64812−4=80
j5→61912−1=112

关键路径是 b → e → i(slack 全为 0),总工期 12。g 的余量最大 = 6——它从 v3 直接跨到终点 v6,路径自由度大,比所有其他活动都松。

最终答案是 B(g)

下图把关键路径(红色)和最大余量活动 g(蓝色)画了出来:

a=2b=5c=1d=3e=3f=4g=1h=1i=4j=1v1v2v3v4v5v6

最后更新:

🎬 可视化演示
加载中...

提示:可在可视化区直接操作播放、步进、修改参数