数据结构之图的应用题目
数据结构之图的应用题目
01. 任何一个无向连通图的最小生成树()。
- A. 有一棵或多棵
- B. 只有一棵
- C. 一定有多棵
- D. 可能不存在
答案：A
解释：
在一个无向连通图中，最小生成树（MST）必定存在。虽然可能存在多棵最小生成树，但也有可能仅有一棵。因此，选项A是正确的。
02. 用 Prim 算法和 Kruskal 算法构造图的最小生成树，所得到的最小生成树( )。
- A. 相同
- B. 不相同
- C. 可能相同，可能不同
- D. 无法比较
答案：C
解释：
不同的算法（如Prim和Kruskal）可能生成不同的最小生成树，特别是当图中存在相同权值的边时。然而，如果无向连通图的最小生成树是唯一的，则两种算法生成的最小生成树一定是相同的。因此，选项C是正确的。
03. 以下叙述中，正确的是()。
- A. 只要无向连通图中没有权值相同的边，则其最小生成树唯一
- B. 只要无向图中有权值相同的边，则其最小生成树一定不唯一
- C. 从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树
- D. 设连通图 G含有n个顶点，则含有n个顶点、n-1条边的子图一定是G的生成树
答案：A
解释：
选项A是正确的，因为如果无向连通图中没有权值相同的边，最小生成树是唯一的。选项B错误，因为无向图中即使有权值相同的边，也不一定导致最小生成树不唯一（如图是树的情况）。选项C是错误的，因为选取的n-1条边可能形成回路。选项D是错误的，因为含有n个顶点、n-1条边的子图可能构成回路或不连通。
04. 以下叙述中，正确的是()。
- A. 最短路径一定是简单路径
- B. Dijkstra算法不适合求有回路的带权图的最短路径
- C. Dijkstra算法不适合求任意两个顶点的最短路径
- D. Floyd算法求两个顶点的最短路径时，path1一定是path的子集
答案：A
解释：
选项A是正确的，因为最短路径的定义要求它是简单路径，即不重复经过任何顶点。选项B错误，Dijkstra算法可以用于有回路的带权图，但不能用于带有负权边的图。选项C错误，因为Dijkstra算法适合求任意两个顶点的最短路径，前提是没有负权边。选项D错误，Floyd算法在更新路径时，可能会导致path不再是path的子集。
05. 已知带权连通无向图 $ G=(V,E) $，其中 $ V= { V_1, V_2, V_3, V_4, V_5, V_6 } \(，\) E={(V_1,V_2)10,(V_1,V_3)2,(V_3,V_4)2,(V_3,V_6)11,(V_2,V_5)1,(V_4,V_5)4,(V_4,V_6)6,(V_5,V_7)7,(V_6,V_7)3} $（注:顶点偶对括号外的数据表示边上的权值），从源点 $ V_1 $ 到顶点 $ V_7 $ 的最短路径上经过的顶点序列是()。
答案：B
不难求出最短路径为\(v_1→v_3一v_4→v_6→v_7\)。
06. 下面的( )方法可以判断出一个有向图是否有环(回路)。
I.深度优先遍历 II，拓扑排序III，求最短路径IV，求关键路径
- A. I、II
- B. I、III、IV
- C. I、II、III
- D. 全部可以
答案：A
解释：
使用深度优先遍历（DFS）可以检测一个有向图是否有环。在 DFS
中，如果在访问某个节点之前发现有回边指向该节点，则说明存在环。拓扑排序只适用于无环图，因此不能用于检测环。选项
II
也适用，而求最短路径（III）和求关键路径（IV）则不适合用于检测环。因此，选项
A 是正确的。
07. 在有向图 G 的拓扑序列中，若顶点 $ v $ 在顶点 $ u $ 之前，则下列情形不可能出现的是( )。
- A. G 中有弧 $ (u, v) $
- B. G 中没有弧 $ (v, u) $
- C. G 中有一条从 $ u $ 到 $ v $ 的路径
- D. G 中有一条从 $ v $ 到 $ u $ 的路径
答案：D
解释：
若顶点 $ v $ 在顶点 $ u $ 之前出现在拓扑序列中，则不可能存在从 $ v $ 到
$ u $ 的路径（即选项
D），因为这将形成一个环，从而破坏拓扑排序的定义。选项 A 和 C
都是可能的，而选项 B 只是说明 $ v $ 和 $ u $ 之间没有直接的边。
08. 若一个有向图的顶点不能排在一个拓扑序列中，则可判定该有向图()。
- A. 是一个有根的有向图
- B. 是一个强连通图
- C. 含有多个入度为 0 的顶点
- D. 含有顶点数目大于 1 的强连通分量
答案：D
解释：
如果一个有向图不能排成拓扑序列，意味着图中必然存在环。根据图论的定义，环的存在意味着图中至少有一个强连通分量。特别地，如果这个强连通分量中包含两个或更多的顶点，则这些顶点之间必然存在回路。因此，选项
D 是正确的。
- 选项 A 错误，因为有向图可能包含多个根或不包含根。
- 选项 B 错误，强连通图的所有顶点之间都有路径，但并不意味着不能有拓扑序列。
- 选项 C 错误，因为有向图可以有多个入度为 0 的顶点，即使存在环。
总结来说，无法生成拓扑序列的有向图中，必然包含一个顶点数目大于 1 的强连通分量。
09. 以下关于拓扑排序的说法中，错误的是()。
- 若某有向图存在环路，则该有向图一定不存在拓扑排序。
- 在拓扑排序算法中为暂存入度为零的顶点，可以使用栈，也可以使用队列。
- 若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1。
- A. I、II
- B. II、III
- C. II
- D. III
答案：D
解释：
- 选项 I 正确。若有向图存在环路，则该图一定不存在拓扑排序，因为拓扑排序要求图是无环的。
- 选项 II 正确。暂存入度为零的顶点可以使用栈或队列，具体取决于具体实现。
- 选项 III 错误。虽然在一些情况下，唯一的拓扑排序可能导致图的入度和出度最多为1，但这并不总是成立。比如，一个链式结构的图可以有唯一的拓扑排序，但某些顶点的入度和出度可能大于1。
10. 若一个有向图的顶点不能排成一个拓扑序列，则判定该有向图()。
- A. 含有多个出度为0的顶点
- B. 是个强连通图
- C. 含有多个入度为0的顶点
- D. 含有顶点数大于1的强连通分量
答案：D
解释：
如果一个有向图中的顶点不能排成拓扑序列，这表明图中存在环。因此，必然存在一个顶点数大于1的强连通分量，因为强连通分量中必然有回路。
- 选项 A 错误，因为有向图中可以有多个出度为0的顶点，但这并不影响是否存在拓扑序列。
- 选项 B 错误，虽然强连通图一定有环，但并不意味着所有无法排成拓扑序列的图都是强连通的。
- 选项 C 错误，入度为0的顶点数目与图是否存在拓扑序列无直接关系。
11. 下图所示有向图的所有拓扑序列共有()个。
- A. 4
- B. 6
- C. 5
- D. 3
答案：C
解释：
根据题目给出的信息，图的所有拓扑排序序列包括：
- ABCFDEG
- ABCDFEG
- ABCDEFG
- ABDCFEG
- ABDCEFG
因此，有5个拓扑序列。
拓扑排序步骤
- 计算每个顶点的入度：
- 对于图中的每个顶点，统计有多少条边指向该顶点（即该顶点的入度）。
- 找到入度为零的顶点：
- 在所有顶点中找出入度为零的顶点，作为起始点。
- 选择一个入度为零的顶点：
- 将其中一个入度为零的顶点添加到拓扑排序序列中。
- 更新其他顶点的入度：
- 将刚刚选择的顶点从图中移除，并更新与其相连的其他顶点的入度。
- 例如，如果有一条从顶点A指向顶点B的边，那么顶点B的入度减一。
- 重复步骤 2-4：
- 重复步骤2-4，直到所有的顶点都被处理。如果所有顶点都已加入拓扑序列，停止。
12. 若一个有向图具有有序的拓扑排序序列，则它的邻接矩阵必定为()。
- A. 对称
- B. 稀疏
- C. 三角
- D. 一般
答案：C
解释：
对于具有有序拓扑排序的有向图，邻接矩阵可以构造成一个上三角矩阵，且主对角元全为零。这意味着没有自环，并且每个顶点的邻接关系遵循拓扑排序的顺序，因而它的邻接矩阵必定是三角形的。若去掉“有序”一词，则邻接矩阵不一定是三角矩阵。
13. 下列关于图的说法中，正确的是()。
I. 有向图中顶点V的度等于其邻接矩阵中第V行中1的个数。
II.
无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。
III. 在图G的最小生成树G中，某条边的权值可能会超过未选边的权值。
IV. 若有向无环图的拓扑序列唯一，则可以唯一确定该图。
- A. I、II 和 III
- B. III 和 IV
- C. III
- D. IV
答案：C
解释：
- 选项 I 错误。顶点V的度是其入度和出度之和，邻接矩阵中第V行中1的个数只表示出度。
- 选项 II 错误。无向图的邻接矩阵一定是对称矩阵，但有向图的邻接矩阵不一定是非对称的（如存在两条方向相反的边）。
- 选项 III 正确。最小生成树中的边并不保证是图中权值最小的n-1条边，因为可能存在权值较小但不连通的边。
- 选项 IV 错误。有向无环图的拓扑序列唯一并不能唯一确定该图，因为不同的图可以有相同的拓扑排序。
综上所述，正确的答案是 C。
14. 若某带权图为 $ G=(V,E) $，其中
- $ V= {V_1, V_2, V_3, V_4, V_5, V_6, V_7, V_8, V_9, V_{10}} $
- $ E={<V_1, V_2>_5, <V_1, V_3>_6, <V_2, V_5>_3, <V_3, V_5>_6, <V_3, V_4>_3, <V_4, V_5>_1, <V_4, V_7>_1, <V_4, V_8>4, <V_5, V_6>4, <V_5, V{7}>2, <V_6, V{10}>4, <V_7, V{9}>5, <V_8, V{9}>2,<V{9},V{10}>_2} $
关键路径的长度为()。
- A. 19
- B. 20
- C. 21
- D. 22
15. 下面关于求关键路径的说法中，不正确的是()。
- A. 求关键路径是以拓扑排序为基础的
- B. 一个事件的最早发生时间与以该事件为始的弧的活动的最早开始时间相同
- C. 一个事件的最迟发生时间是以该事件为尾的弧的活动的最迟开始时间与该活动的持续时间的差
- D. 关键活动一定位于关键路径上
答案：C
解释：
一个事件的最迟发生时间等于Min{以该事件为尾的弧的活动的最迟开始时间，最迟结束时间与该活动的持续时间的差}。
事件的最迟发生时间（Latest Event Time, LET）：这是指在项目管理中，事件可以发生的最后时刻，超过这个时刻可能会影响整个项目的进度。换句话说，它是该事件允许的最大时间限制。
以该事件为尾的弧的活动：在活动—事件图（AOE图）中，某个事件的尾部是指那些以该事件为终点的活动。例如，如果有活动 A（从事件 X 到事件 Y），则 Y 是事件 X 的尾部。事件 X 的最迟发生时间需要考虑所有以它为尾的活动。
最迟开始时间（Latest Start Time, LST）：这是指一个活动可以开始的最后时刻而不延误后续的项目进度。
最迟结束时间（Latest Finish Time, LFT）：这是指一个活动可以结束的最后时刻，而不影响后续事件的最早开始时间。
根据你的描述，事件的最迟发生时间可以表示为：
$ = { (), - } $
具体含义
- LST（以该事件为尾的活动的最迟开始时间）：
- 这表示所有以该事件为尾的活动必须在此时间之前开始。如果这个时间晚于事件的最迟发生时间，事件可以在此时间之前的任何时刻发生。
- LFT - 活动持续时间：
- 这表示活动的最迟结束时间减去该活动的持续时间。换句话说，活动必须在此时之前完成才能不影响后续的事件。
16. 下列关于关键路径的说法中，正确的是()。
I. 改变网上某一关键路径上的任一关键活动后，必将产生不同的关键路径
II. 在 AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少
III. 缩短关键路径上任意一个关键活动的持续时间可缩短关键路径长度
IV. 缩短所有关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度
V. 缩短多条关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度
A. II 和 IV
B. I、II 和 IV
C. II 和 IV
D. I 和 II
答案：C
解释：
若改变的是所有关键路径上的公共活动，则不一定会产生不同的关键路径(延长必然不会导致，只有缩短才有可能导致)。根据关键路径的定义，可知Ⅱ正确。关键路径是源点到终点的最长路径，只有所有关键路径的长度都缩短时，整个图的关键路径才能有效缩短，但也不能任意缩短，一旦缩短到一定程度，该关键活动就可能会变成非关键活动。
17. 用 DFS 遍历一个无环有向图，并在 DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( )
- A. 逆拓扑有序
- B. 拓扑有序
- C. 无序的
- D. 无法确定
答案：A
解释：
在深度优先搜索（DFS）中，当一个顶点被访问后，它会被放入栈中。DFS
继续遍历该顶点的所有后继（邻接）顶点，直到没有更多可遍历的顶点。当 DFS
返回（即顶点出栈）时，先遍历的后继顶点会被先处理并输出。因此，输出的顶点序列是逆拓扑序列，因为在有向图中，依赖关系会使得后继顶点先被访问并输出，而当前顶点在其后被输出。
18. 对下图进行拓扑排序，可得不同拓扑序列的个数是()
- A. 4
- B. 3
- C. 5
- D. 2
答案：B
解释：
在题目中提到的图中，可以通过对其进行拓扑排序来获取不同的顶点排列。根据
DFS 或 Kahn
算法等方法，可以得出不同的拓扑序列。根据给出的选项和图的结构，可能存在 3
种不同的拓扑序列。
19. 下列关于最小生成树的叙述中，正确的是()。
I. 最小生成树的代价唯一
II. 所有权值最小的边一定会出现在所有的最小生成树中
III. 使用 Prim 算法从不同顶点开始得到的最小生成树一定相同
IV. 使用 Prim 算法和 Kruskal 算法得到的最小生成树总不相同
A. 仅 I
B. 仅 II
C. 仅 I、III
D. 仅 II、IV
答案：A
解释：
- I 正确：最小生成树的代价（即权值总和）是唯一的，前提是图中的边权值各不相同。
- II 错误：权值最小的边不一定出现在所有的最小生成树中，特别是在存在环的情况下。
- III 错误：不同起点可能导致不同的最小生成树，尤其在存在多个相同权值的边时。
- IV 错误：在边权唯一的情况下，Prim 算法和 Kruskal 算法会得到相同的最小生成树。
综上所述，只有 I 是正确的，答案选 A。
20.【2012 统考真题】对下图所示的有向带权图，若采用 Dijkstra 算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是()。
- A. d, e, f
- B. e, d, f
- C. f, d, e
- D. f, e, d
答案：C
21.【2013 统考真题】下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是()。
- A. C 和 e
- B. d 和 c
- C. f 和 d
- D. f 和 h
答案：C
解释：
找出 AOE网的全部关键路径为\(bdcg、bdeh\)和\(bfh\)。根据定义，只有关键路径上的活动时间同时减少时，才能缩短工期。选项
A、B和D并不包含在所有的关键路径中，只有C包含，因此只有加快/和d的进度才能缩短工期。
22.【2012 统考真题】若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是()。
- A. 存在，且唯一
- B. 存在，且不唯一
- C. 存在，可能不唯一
- D. 无法确定是否存在
答案： A. 存在，且唯一
解释：
在使用邻接矩阵存储的有向图中，如果矩阵中主对角线以下的元素均为零，意味着从顶点
\(i\) 到顶点 \(j\)（当 \(i <
j\)）之间可能存在边，而从顶点 \(j\) 到顶点 \(i\)
之间一定不存在边。这表明该图是一个无环图，因此至少存在一个拓扑序列。
对于拓扑序列的唯一性，当对角线以下的元素为零时，虽然存在拓扑序列，但可能有多个序列存在。例如，若图的邻接矩阵为：
$ \[\begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}\]$
在这种情况下，存在多个拓扑序列。因此，正确的选项应为 C. 存在，可能不唯一，而不是 A. 存在，且唯一。
23.【2014 统考真题】对下图所示的有向图进行拓扑排序，得到的拓扑序列可能是()。
- A. 3, 1, 2, 4, 5, 6
- B. 3, 1, 2, 4, 6, 5
- C. 3, 1, 4, 2, 5, 6
- D. 3, 1, 4, 2, 6, 5
答案：D
解释：
按照拓扑排序的算法，每次都选择入度为0的结点从图中删除，此图中一开始只有结点3的入度为0;删除结点3后，只有结点1的入度为0:删除结点1后，只有结点4的入度为0;删除结点4后，结点2和结点6的入度都为0，此时选择删除不同的结点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为3,1.4,2.6.5和
3.1.4.6.2.5，选 D。
24.【2015 统考真题】求下面的带权图的最小(代价)生成树时，可能是 Kruskal 算法第 2 次选中但不是 Prim 算法（从 \(V_4\) 开始）第 2 次选中的边是()。
- A. $(V_1, V_3) $
- B. $(V_1, V_4) $
- C. $(V_2, V_3) $
- D. $(V_3, V_4) $
答案：C
直接进行模拟即可。
25.【2016 统考真题】使用 Dijkstra 算法求下图中从顶点 1 到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是()。
- A. 5, 2, 3, 4, 6
- B. 5, 2, 3, 6, 4
- C. 5, 2, 4, 3, 6
- D. 5, 2, 6, 3, 4
答案：B
根据 Diikstra 算法，从顶点1到其余各顶点的最短路径如下表所示。
26.【2016 统考真题】若对 \(n\) 个顶点、\(e\) 条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是( )。
- A. \(O(n)\)
- B. \(O(n +
e)\)
- C. \(O(n^2)\)
- D. \(O(ne)\)
答案： B. \(O(n + e)\)
解释：
拓扑排序的常用算法之一是 Kahn 算法 或
深度优先搜索（DFS）法，这两种方法的时间复杂度都与图的存储结构密切相关。如果使用
邻接表 存储有向图，算法的时间复杂度为 \(O(n + e)\)，其中：
- \(n\) 表示图中的顶点数
- \(e\) 表示图中的弧（边）数
这是因为：
- 初始化入度或访问标记 的操作需要遍历所有顶点，时间复杂度是 \(O(n)\)。
- 访问每个顶点的出边 时，需要遍历每条弧，时间复杂度是 \(O(e)\)。
因此，总的时间复杂度是 \(O(n + e)\)，即顶点数与弧数的线性加和。
27.【2018 统考真题】下列选项中，不是如下有向图的拓扑序列的是( )
- A. 1, 5, 2, 3, 6, 4
- B. 5, 1, 2, 6, 3, 4
- C. 5, 1, 2, 3, 6, 4
- D. 5, 2, 1, 6, 3, 4
答案：D
拓扑排序每次选取入度为0的结点输出,经观察不难发现拓扑序列前两位一定是1,5或5,1，
(因为只有1和5的入度均为0，且其他结点都不满足仅有1或仅有5作为前驱)。D错误。
28.【2019 统考真题】下图所示的 AOE 网表示一项包含8个活动的工程。活动 d 的最早开始时间和最迟开始时间分别是()。
- A. 3 和 7
- B. 12 和 12
- C. 12 和 14
- D. 15 和 15
答案： C
解释：
活动d的最早开始时间等于该活动弧的起点所表示的事件的最早发生时间，活动d的最早开始时间等于事件
2的最早发生时间max{a,b+c}=max(3,12}=12。活动d的最迟开始时间等于该活动弧的终点所表示的事件的最迟发生时间与该活动所需时间之差，先算出图中关键路径长度为27(对于不复杂的选择题，找出所有路径计算长度)，那么事件4的最迟发生时间为min{27-g}=min{27-6}=21，活动d的最迟开始时间为21-d=21-7=14。常规方法:按照关键路径算法算得到下表。
29.【2019 统考真题】用有向无环图描述表达式 \((x+y)((x+y)/x)\)，需要的顶点个数至少是( )
- A. 5
- B. 6
- C. 8
- D. 9
答案： A
解释： 先将该表达式转换成有向二叉树，注意到该二叉树中有些顶点是重复的，为了节省存储空间，可以去除重复的顶点(使顶点个数达到最少)，将有向二叉树去重转换成有向无环图。
30.【2020 统考真题】已知无向图 G，如下所示，使用克鲁斯卡尔 (Kruskal) 算法求图 G 的最小生成树，加到最小生成树中的边依次是()
答案：
解释：
见下图：
31.【2020 统考真题】修改递归方式实现的图的深度优先搜索 (DFS) 算法，将输出 (访问) 顶点信息的语句移到退出递归前 (即执行输出语句后立刻退出递归)。采用修改后的算法遍历有向无环图 G，若输出结果中包含 G 中的全部顶点，则输出的顶点序列是 G 的()。
- A. 拓扑有序序列
- B. 逆拓扑有序序列
- C. 广度优先搜索序列
- D. 深度优先搜索序列
答案：B
解释：
在 DFS
中，如果在回溯时输出节点信息，得到的结果会是逆拓扑排序，因为当一个节点所有邻接节点都已被访问后，该节点才会被输出。因此，输出的顶点序列是
G 的逆拓扑有序序列。
32.【2020 统考真题】若使用 AOE 网估算工程进度，则下列叙述中正确的是( )。
- A. 关键路径是从源点到汇点边数最多的一条路径
- B. 关键路径是从源点到汇点路径长度最长的路径
- C. 增加任一关键活动的时间不会延长工程的工期
- D. 缩短任一关键活动的时间将会缩短工程的工期
答案： B
解释：
- 关键路径（Critical
Path）是从源点到汇点的路径中所需时间最长的一条路径，因此选项 B
正确。
- 选项 A 错误，因为关键路径并不是边数最多的路径。
- 选项 C 错误，因为增加关键活动的时间会直接影响到工程的总工期。
- 选项 D 错误，因为缩短关键活动的时间可以缩短工期，但不是每个关键活动都可以缩短，因此不一定会缩短总工期。
33.【2021 统考真题】给定如下有向图，该图的拓扑有序序列的个数是()。
- A. 1
- B. 2
- C. 3
- D. 4
答案：A
解释：
求拓扑序列的过程:从图中选择无入边的结点，输出该结点并删除该结点的所有出边，重复上述过程，直至全部结点都已输出，这样求得的拓扑序列为ABCDEF。每次输出一个结点并删除该结点的所有出边后，都发现有且仅有一个结点无入边，因此该拓扑序列唯一。
34.【2021
统考真题】使用 Dijkstra
算法求下图中从顶点1到其余各顶点的最短路径，将当前找到的从顶点1到顶点2,
3, 4, 5的最短路径长度保存在数组
dist中，求出第二条最短路径后，dist中的内容更新为()
- A. 26, 3, 14, 6
- B. 25, 3, 14, 6
- C. 21, 3, 14, 6
- D. 15, 3, 14, 6
答案：C
解释：
Dijkstra 算法用于求解从起点到图中各顶点的最短路径。算法的基本步骤如下：
- 初始化：
- 顶点集 SSS 只包含起点（在本题中为顶点 1）。
- 数组
dist用来记录从顶点 1 到各个顶点的最短路径，初始时，直接相连的边的权值赋给相应的顶点，其他的初始化为 ∞∞（表示不可达）。
- 迭代更新：
- 每次从未处理的顶点集中选择距离起点最近的顶点，将其加入顶点集 SSS。
- 以此顶点为中间点，检查是否可以通过该顶点得到更短的路径，如果是，则更新
dist数组。
