第五章图¶
答案速对¶
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| A | C | B | D | C | B | C | D | D | D |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| A | A | C | A | C | B | C | B | B | C |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| C | D | B | D | A | B | C | C | B | B |
(一)图的基本概念¶
- 【2009-07】下列关于无向连通图特性的叙述中，正确的是（ ）。
I. 所有顶点的度之和为偶数
II. 边数大于顶点个数减1
III. 至少有一个顶点的度为1
A. 只有I
B. 只有II
C. I和II
D. I和III
解析
I 正确。无向图中的每条边会分别给两个端点的度贡献 1，因此所有顶点度数之和为
一定是偶数。这就是握手定理。
II 错误。含 n 个顶点的无向连通图至少有 
条边，树恰好达到这个下界。因此正确关系是
不一定严格大于。
III 错误。无向连通图不一定存在度为 1 的顶点。例如一个环中每个顶点的度都是 2。只有含至少两个顶点的树才一定有度为 1 的顶点。
答案：A
- 【2010-07】若无向图 G=(V,E) 中含有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是（ ）。
A. 6 B. 15 C. 16 D. 21
解析
这不是问“构造一个连通图最少需要几条边”，而是问“边任意分布时仍能保证连通”。
先求 7 个顶点的不连通简单图最多能有多少条边。
要让不连通图的边尽可能多，应让一个连通分量包含 6 个顶点并构成完全图，剩余 1 个顶点孤立。此时边数为
所以有 15 条边时仍可能出现“
加一个孤立顶点”，不能保证连通。
再增加一条边后，边数达到 16。任何不连通图都无法拥有这么多边，因此一定连通。
答案：C
- 【2017-07】已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是（ ）。
A. 10
B. 11
C. 13
D. 15
解析
所有顶点度数之和为
已知顶点贡献的度数为
其余顶点还需贡献
度。
题目说明其他顶点的度均小于 3，所以每个这样的顶点最多为 2 度。要用尽量少的顶点贡献 8 度，至少需要
个顶点。
因此顶点总数至少为
相应的度数序列可以构造成简单无向图，因此这个下界能够达到。
答案：B
- 【2022-06】对于无向图 G=(V,E) ，下列选项中正确的是（ ）。
A. 当 |V|>|E| 时， G 一定是连通的
B. 当 |V|<|E| ， G 一定是连通的
C. 当 |V|=|E|−1 ， G 一定是不连通的
D. 当 |V|>|E|+1 ， G 一定是不连通的
解析
含 
个顶点的无向连通图至少需要
条边。
D 的条件
等价于
边数低于连通图的最低要求，所以 G 一定不连通。
A 错误。
只说明 
；当恰好等于 
时，图可能是一棵树而连通，也可能因边分布不当而不连通。
B 错误。边数较多仍可能集中在某个分量内，留下孤立顶点。
C 错误。该条件等价于 
，图既可能连通，也可能不连通。
答案：D
(二)图的存储及基本操作¶
Tip
- 邻接矩阵
- 邻接表
- 邻接多重表、十字链表
- 【2013-07】设图的邻接矩阵 A 如下所示。各顶点的度依次是（ ）。
\(A=\begin{pmatrix} 0& 1& 0& 1\\ 0& 0& 1& 1\\ 0& 1& 0& 0\\ 1& 0& 0& 0 \end{pmatrix}\)
A. 1, 2, 1, 2
B. 2, 2, 1, 1
C. 3, 4, 2, 3
D. 4, 4, 2, 2
解析
矩阵不对称，所以表示的是有向图。
对有向图：
- 第 i 行元素之和是顶点 i 的出度；
- 第 i 列元素之和是顶点 i 的入度；
- 顶点的度等于入度与出度之和。
逐个计算：
- 顶点 1：出度 2，入度 1，总度数 3；
- 顶点 2：出度 2，入度 2，总度数 4；
- 顶点 3：出度 1，入度 1，总度数 2；
- 顶点 4：出度 1，入度 2，总度数 3。
所以各顶点度数为 3、4、2、3。
答案：C
- 【2024-04】若无向图 G=(V,E) 的邻接多重表如下图所示，则 G 中顶点 b 与 d 的度分别是
A. 0, 2
B. 2, 4
C. 2, 5
D. 3, 4
解析
与 b 关联的边为
所以 
。
与 d 关联的边为
所以 
。
答案：B
(三)图的遍历¶
Tip
- 深度优先搜索
- 广度优先搜索
- 【2012-05】对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。
A. O(n)
B. O(e)
C. O(n+e)
D. O(ne)
解析
广度优先遍历需要：
- 每个顶点至多入队、出队一次，耗时
； - 扫描每个顶点的邻接表。有向图的所有邻接表结点总数等于弧数 e，因此耗时
。
合计为
答案：C
- 【2013-08】若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（ ）。
A. h, c, a, b, d, e, g, f
B. e, a, f, g, b, h, c, d
C. d, b, c, a, h, e, f, g
D. a, b, c, d, h, e, f, g
解析
BFS 的关键性质是：先访问距离起点为 1 的所有顶点，再访问距离为 2 的顶点。
A 从 h 开始。h 的邻接点可按 c、a 入队，随后依次扩展出 b、d、e，再由 e 扩展 g、f，可以实现。
B 从 e 开始。e 的邻接点可按 a、f、g 入队；处理 a 时再发现 b、h，之后发现 c、d，可以实现。
C 从 d 开始。d 的邻接点可按 b、c 入队，随后依次发现 a、h、e、f、g，可以实现。
D 从 a 开始。a 的直接邻接点是 b、e、h，它们都属于第 1 层；c、d 属于更后面的层。序列却在访问 b 后立即访问 c、d，把第 2 层顶点放在尚未访问的 e、h 之前，违反 BFS 分层次序。
答案：D
- 【2015-05】设有向图 G=(V,E) ，顶点集 V={V0,V1,V2,V3} ，边集 E={(V0,V1),(V0,V2),(V0,V3),(V1,V3)} 。若从顶点 V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（ ）。
A. 2
B. 3
C. 4
D. 5
解析
结果取决于 
邻接点的选择顺序。
以 
开始：
以 
开始时，剩余顶点可以先访问 或 
：
以 开始时，剩余 
的先后顺序可以互换：
共 5 种不同 DFS 序列。
答案：D
- 【2016-06】下列选项中，不是下图深度优先搜索序列的是（ ）。
A. V1,V5,V4,V3,V2
B. V1,V3,V2,V5,V4
C. V1,V2,V5,V4,V3
D. V1,V2,V3,V4,V5
解析
A 可以实现：从 先进入 
，再沿 
深入。
B 可以实现：从 先进入 ，再沿 
深入。
C 可以实现：从 先进入 ，再沿 
深入。
D 不可能。访问 后， 有未访问的后继 ，DFS 必须立即递归进入 ，不能返回 去访问 。因此序列不可能是 
。
答案：D
(四)图的基本应用¶
- 【2019-06】用有向无环图描述表达式 (x+y)((x+y)/x) ，需要的顶点个数至少是（ ）。
A. 5
B. 6
C. 8
D. 9
解析
有向无环图可以让相同的子表达式共用同一个结点，而不必重复建立。
需要的结点为：
- 操作数 x；
- 操作数 y；
- 加法结点
，两次出现可以共用； - 除法结点
； - 最后的乘法结点。
所以最少需要 5 个顶点。
答案：A
最小(代价)生成树¶
- 【2012-08】下列关于最小生成树的叙述中，正确的是（ ）。
I. 最小生成树的代价唯一
II. 所有权值最小的边一定会出现在所有的最小生成树中
III. 使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同
IV. 使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不同
A. 仅I
B. 仅II
C. 仅I、III
D. 仅II、IV
解析
I 正确。一个图即使有多棵不同的最小生成树，它们的边集可以不同，但总代价都等于同一个最小值，因此最小代价唯一。
II 错误。如果若干条同为最小权值的边构成环，为避免生成树出现环，不可能把它们全部选入。某一条最小权边未必出现在所有最小生成树中。
III 错误。当最小生成树不唯一时，Prim 的起点以及权值相同时的选边次序都可能影响最终边集。
IV 错误。两个算法都用于求最小生成树，完全可能得到同一棵最小生成树；当最小生成树唯一时，它们必然得到同一边集。
答案：A
- 【2015-06】求下面带权图的最小（代价）生成树时，可能是克鲁斯卡尔（Kruskal）算法第2次选中但不是普里姆（Prim）算法（从 V4 开始）第2次选中的边是（ ）。
A. (V1,V3)
B. (V1,V4)
C. (V2,V3)
D. (V3,V4)
解析
Kruskal 按边权从小到大选择：
- 第 1 条一定是权值 5 的
； - 接下来有三条权值同为 8 的边，
、
、
都可能在不同的同权排序下成为第 2 条。
Prim 从 
开始：
- 第 1 条也是
，当前树内顶点为 
； - 第 2 条必须跨越“树内—树外”边界。权值最小的候选为 和
，均为 8。
边 的两个端点此时都在树外，所以不可能成为 Prim 的第 2 条边；但它可以成为 Kruskal 的第 2 条边。
答案：C
- 【2020-07】已知无向图G如下图所示，使用克鲁斯卡尔（Kruskal）算法求图G的最小生成树，加到最小生成树中的边依次是（ ）。
A. (b, f), (b, d), (a, e), (c, e), (b, e)
B. (b, f), (b, d), (b, e), (c, e), (a, e)
C. (a, e), (b, e), (c, e), (b, d), (b, f)
D. (a, e), (c, e), (b, e), (b, f), (b, d)
解析
按权值从小到大检查：
，权值 5，加入；
，权值 6，加入；
，权值 7。b、d、f 已经连通，加入该边会形成环，因此跳过；
，权值 9，加入；
，权值 10，加入；
，权值 11，将分量 
与 
连接，加入。
已经选中 5 条边，恰好达到 6 个顶点生成树所需的 
条边。
答案：A
最短路径¶
- 【2012-07】对如下有向图带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余最短路径的目标顶点依次是（ ）。
A. d, e, f
B. e, d, f
C. f, d, e
D. f, e, d
解析
从 a 开始：
- 初始距离为
，所以先确定 b。 - 经 b 松弛后，
，
，所以第二个确定 c。 - 经 c 松弛后：
；
；
。
因此第三个确定 f。
- 接着确定距离为 5 的 d。经 d 松弛后，
。 - 最后确定 e。
后续次序为 f、d、e。
答案：C
- 【2016-08】使用迪杰斯特拉（Djkstra）算法求下图中从顶点 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
解析
- 初始
，先确定 5； - 经 5 松弛，得到
，
仍为 5，所以确定 2； - 经 2 松弛，
，
仍为 11，所以确定 3； - 当前未确定顶点中
最小，确定 6； - 最后确定
。
次序为
答案：B
- 【2021-08】使用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
解析
初始化：
第一次确定距离最小的顶点 3，距离为 3。由 
松弛：
此时
第二次确定顶点 5，距离为 6。由 5 出发松弛：
所以第二条最短路径确定后：
答案：C
- 【2023-06】已知无向连通图 G 中各边的权值均为 1，下列算法中，一定能够求出图 G 中从某顶点到其余各顶点最短路径的是（ ）。
I. 普利姆（Prim）算法
II. 克鲁斯卡尔（Kruskal）算法
III. 图的广度优先搜索算法
A. 仅 I
B. 仅 III
C. 仅 I 和 II
D. I、II 和 III
解析
所有边权均为 1 时，路径长度就是路径所含边数。
BFS 从源点开始按层访问：
- 第 1 层距离为 1；
- 第 2 层距离为 2；
- 依此类推。
因此 BFS 第一次发现某顶点时得到的就是最短路径，III 正确。
Prim 和 Kruskal 求的是最小生成树，其目标是使整棵生成树的边权总和最小，而不是保证生成树中从指定源点到每个顶点的路径最短。
即使所有边权都为 1，不同生成树总权值相同，但树内的源点到某顶点路径可能比原图最短路径更长。因此 I、II 均不保证单源最短路径。
答案：B
拓扑排序¶
- 【2010-08】对下图进行拓扑排序，可以得到不同拓扑序列的个数是（ ）。
A. 4 B. 3 C. 2 D. 1
解析
最初只有 a 的入度为 0，所以 a 必须排在第一位。
删除 a 及其出边后，b 和 e 的入度都变为 0：
- 若先选 b，则 c 和 e 都可选：
- 选 c 后只能选 e，再选 d，得到 a、b、c、e、d；
- 选 e 后再选 c、d，得到 a、b、e、c、d。
- 若先选 e，之后只有 b 可选，再依次为 c、d，得到 a、e、b、c、d。
一共 3 种不同拓扑序列。
答案：B
- 【2011-08】下列关于图的叙述中，正确的是（ ）。
Ⅰ. 回路是简单路径
Ⅱ. 存储稀疏图，用邻接矩阵比邻接表更省空间
Ⅲ. 若有向图中存在拓扑序列，则该图不存在回路
A.仅Ⅱ
B.仅Ⅰ、Ⅱ
C.仅Ⅲ
D.仅Ⅰ、Ⅲ
解析
详细解析：
I 错误。简单路径要求路径中的顶点不重复，而回路的起点和终点相同，至少重复了首尾顶点，因此不能直接说“回路是简单路径”。
II 错误。邻接矩阵无论边多少都需要 
空间；邻接表只需 
空间。稀疏图中 
远小于 
，邻接表更省空间。
III 正确。存在拓扑序列等价于有向图是有向无环图。若存在有向回路，回路中的每个顶点都必须排在自己的前驱之后，无法形成线性拓扑次序。
答案：C
- 【2012-06】若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ ）。
A. 存在，且唯一
B. 存在，且不唯一
C. 存在，可能不唯一
D. 无法确定是否存在
解析
按顶点编号 
理解邻接矩阵。主对角线以下元素为 0，说明若存在弧 
，只能有
沿任何有向路径，顶点编号都会严格增大，因此不可能绕一圈回到原顶点，图中不存在有向环。
所以拓扑序列一定存在，编号自然顺序
就是一个拓扑序列。
但拓扑序列不一定唯一。如果某些顶点之间没有先后约束，它们可以交换位置。因此结论是“存在，可能不唯一”。
答案：C
- 【2014-07】对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（ ）。
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
解析
拓扑序列必须满足每条弧的起点在终点之前。
由 
可知 4 必须在 2 前，所以 A、B 中的“2、4”次序错误。
由 
可知 6 必须在 5 前，所以 C 中的“5、6”次序错误。
D 为 3、1、4、2、6、5：
- 3 在 1、6 前；
- 1 在 2、4 前；
- 4 在 2、6 前；
- 2、6 都在 5 前。
所有约束均满足。
答案：D
- 【2016-07】若将 n 个顶点 e 条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是（ ）。
A. O(n)
B. O(n+e)
C. O(n^2)
D. O(ne)
解析
以基于入度的拓扑排序为例：
- 初始化或检查每个顶点的入度，需要处理 n 个顶点；
- 每个顶点至多入栈或入队一次，共 ；
- 删除一个顶点时扫描其邻接表，每条弧只被扫描一次，共 。
因此总时间复杂度为
答案：B
- 【2018-07】下列选项中，不是如下有向图的拓扑序列的是（ ）。
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
解析
A、B、C 都满足：
- 1、5 在 2 之前；
- 2 在 3、6 之前；
- 3、6、5 在 4 之前。
D 的开头是 5、2、1。图中有弧
所以 1 必须排在 2 前。D 把 2 放在 1 前，违反拓扑约束。
答案：D
- 【2021-07】给定如下有向图，该图的拓扑有序序列的个数（ ）。
A. 1
B. 2
C. 3
D. 4
解析
依次观察入度为 0 的顶点：
- 初始只有 A，第一位只能是 A；
- 删除 A 后只有 B 可选；
- 删除 B 后只有 C 可选；
- 删除 C 后只有 D 可选；
- 删除 D 后只有 E 可选；
- 最后才是 F。
每一步都只有一个可选顶点，所以拓扑序列唯一：
答案：A
- 【2020-06】修改递归方式实现图的深度优先搜索（DFS）算法，将输出（访问）顶点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图G，若输出结果中包含G中全部顶点，则输出的顶点序列是G的（ ）。
A. 拓扑有序序列
B. 逆拓扑有序序列
C. 广度优先搜索序列
D. 深度优先搜索序列
解析
修改后的 DFS 会先递归处理当前顶点的所有后继，最后才输出当前顶点。
若有弧
当从 u 访问到 v 时，v 会在 u 之前完成并输出。因此输出序列中 v 位于 u 前面。
拓扑序列要求 u 位于 v 前面；当前输出恰好相反，所以是逆拓扑序列。
通常用 DFS 求拓扑排序时，也是按完成时间把顶点压栈，最后再把栈逆序弹出。题目直接按完成次序输出，所以得到逆拓扑次序。
答案：B
关键路径¶
- 【2013-09】下列AOE网表示一项包含8个活动的工程，通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是 （ ）。
A. c 和 e
B. d 和 c
C. f 和 d
D. f 和 h
解析
计算从源点 1 到汇点 6 的最长路径，可得到三条长度均为 27 的关键路径：
要缩短总工期，必须让所有关键路径都同时缩短。
- A 加快 c、e，但第三条关键路径
不受影响； - B 加快 d、c，但第三条关键路径不受影响；
- C 加快 f、d：前两条关键路径都含 d，第三条含 f，因此三条都缩短；
- D 加快 f、h，但第一条关键路径
不受影响。
答案：C
- 【2019-05】下图所示的 AOE 网表示一项包含 8 个活动的工程。活动 d 的最早开始时间和最迟开始时间分别是（ ）。
A. 3和7
B. 12和12
C. 12和14
D. 15和15
解析
活动 d 是弧 
，持续时间为 7。
先正向计算事件最早发生时间：
所以活动 d 的最早开始时间为
再反向计算：
活动 d 的最迟开始时间为
答案：C
- 【2020-08】若采用AOE网估算工程进度，则下列叙述中正确的是（ ）。
A. 关键路径是从源点到汇点边数最多的一条路径
B. 关键路径是从源点到汇点路径长度最长的路径
C. 增加任一关键活动的时间不会延长工程的工期
D. 缩短任一关键活动的时间将会缩短工程的工期
解析
AOE 网中，路径长度是路径上各活动持续时间之和。工程完工时间由源点到汇点的最长路径决定，这条路径称为关键路径，所以 B 正确。
A 错误。关键路径比较的是持续时间之和，不是边的条数。
C 错误。关键活动位于至少一条关键路径上，增加其持续时间会使对应关键路径变长，从而延长工程工期。
D 错误。若 AOE 网存在多条关键路径，缩短只位于其中一条关键路径上的某个活动，其他关键路径仍可能保持原工期，所以总工期未必缩短。
答案：B
- 【2022-07】下图是有 10 个活动的AOE网，时间余量最大的活动是（ ）。
A. c
B. g
C. h
D. j
解析
正向计算事件最早发生时间：
反向计算事件最迟发生时间：
活动余量等于“最迟开始时间减最早开始时间”。
对四个候选活动：
- c，
，余量为 
； - g，
，余量为 
； - h，
，余量为 
； - j，
，余量为 
。
最大余量是活动 g 的 6。
答案：B