题目

1、任何一个带权的无向连通图的最小生成树（ ）。
A. 只有一棵
B. 有一棵或多棵
C. 一定有多棵
D. 可能不存在

2、一个赋权网络如下图所示。从顶点 a 开始，用 Prim 算法求出一棵最小生成树。

3、请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。(要求使用图画出每一步过程)。

4、用 dijkstra 标号法求下图中从 v₁到其余顶点的最短路径和距离。

5、已给下图，（ ）是该图的拓扑排序序列。

A. 1, 2, 3, 4
B. 1, 3, 2, 4
C. 1, 2, 4, 3
D. 1, 4, 2, 3

6、为判别有向图是否存在回路，可利用（ ）算法。
A. 最短路径
B. 深度优先遍历
C. 拓扑排序
D. 最小生成树

7、下列关于 AOE 网的叙述中，不正确的是（ ）。
A. 关键活动不按期完成就会影响整个工程的完成时间。
B. 任何一个关键活动提前完成，那么整个工程将会提前完成。
C. 所有的关键活动提前完成，那么整个工程将会提前完成。
D. 某些关键活动提前完成，那么整个工程将会提前完成。

8、下列 AOE 网表示一项包含 8 个活动的工程，通过同时加快若干活动的进度可以缩短整个工程的工期，下列选项中，加快其进度就可以缩短工程工期的是（ ）。

A. c 和 e
B. d 和 e
C. f 和 d
D. f 和 h

9、已知一个 AOE 网采用邻接矩阵存储，其邻接矩阵的三元组表示为 (1,2,1),(1,3,3)，(2,4,4),(2,5,10),(3,5,3),(4,6,6),(5,7,6),(5,8,7),(6,8,5),(7,8,6)。
（1）画出该 AOE 网。
（2）分别求出各事件的最早和最迟发生时间。
（3）分别求出各活动的最早和最迟发生时间。
（4）求出关键活动。

答案

1、B

2、

3、

4、

5、A

6、C

7、B

8、C
网中的关键路径并不唯一，且对于有几条关键路径的网，只提高一条关键路径上的关键动并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。f 和 d 在所有的关键路径上。

9、