Relax1000 数据结构 · 第6章图 · 题目¶

题号查询 · 同章解析

第6章图¶

本章 65 题；题目册印刷页 30–41。

Q1¶

连通的无向图 G 结点情况：16 个度为 4 的顶点，2 个度为 3 的顶点，5 个度为 2 的顶点，4 个度为 1 的结点。则 G 的边数有（）条。

A．84
B．42
C．27
D．64

查看解析

Q2¶

设有无向图 G=(V，E)和 G'=(V'，E')，若 G'是 G的生成树，则下面说法不正确的是（）。

A．G'为 G 的连通分量
B．G'是 G 的无环子图
C．G'为 G的子图
D．G'为 G 的极小连通子图且 V'=V

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q2 原页片段

查看解析

Q3¶

下列关于有向图强连通分量特性的叙述中，正确的是（）。

A．若有向图 G 有两个不同的强连通分量 c 和 c' ，设顶点〔公式/符号见原页版面片段〕,〔公式/符号见原页版面片段〕 ∈ 〔公式/符号见原页版面片段〕，顶点〔公式/符号见原页版面片段〕' ,〔公式/符号见原页版面片段〕' ∈ 〔公式/符号见原页版面片段〕'，若存在一条从u 到 u' 的路径〔公式/符号见原页版面片段〕 → 〔公式/符号见原页版面片段〕' ，则可能存在一条从 v' 到 v 的路径〔公式/符号见原页版面片段〕' → 〔公式/符号见原页版面片段〕
B．若在图 G 中加入一条新边，若该边的两个顶点都处于同一个强连通分量，则可能会增加 G 的强连通分量的个数
C．若在图 G 中加入一条新边，若该边的两个顶点 A和 A'分别处于不同的强连通分量，并且 A和A'彼此之间原先都没有路径，则添加后可能会减少 G 的强连通分量的个数
D．若在图 G 中加入一条新边，若该边的两个顶点 A和A' 分别处于不同的强连通分量，并且 A和A'之间原先有一条路径，则添加后可能会减少 G 的强连通分量的个数

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q3 原页片段

查看解析

Q4¶

一个有 n 个顶点和 n 条边的无向图一定是（）。

A．连通的
B．不连通的
C．无环的
D．有环的

查看解析

Q5¶

下列关于有向图强连通分量特性的叙述中，表示顶点 u 到顶点 v 的有向弧，下列说法正确的是（）。

A．若有向图 G 有两个不同的强连通分量 c 和 c' ，设顶点〔公式/符号见原页版面片段〕 ∈ 〔公式/符号见原页版面片段〕，顶点〔公式/符号见原页版面片段〕' ∈ 〔公式/符号见原页版面片段〕'，那么不可能存在弧
B．若有向图 G 有强连通分量 c，〔公式/符号见原页版面片段〕,〔公式/符号见原页版面片段〕 ∈ 〔公式/符号见原页版面片段〕，若删除弧，有向图 G 的强连通分量一定增加
C．若有向图 G 有两个不同的强连通分量 c 和 c' ，设顶点〔公式/符号见原页版面片段〕，〔公式/符号见原页版面片段〕 ∈ 〔公式/符号见原页版面片段〕，顶点〔公式/符号见原页版面片段〕'，〔公式/符号见原页版面片段〕' ∈ 〔公式/符号见原页版面片段〕'，若存在u→u'的路径，那么一定不存在
D．若有向图 G 有两个不同的强连通分量 c 和 c' ，设顶点〔公式/符号见原页版面片段〕 ∈ 〔公式/符号见原页版面片段〕，顶点〔公式/符号见原页版面片段〕' ∈ 〔公式/符号见原页版面片段〕'，若不存在，那么添加后，该图的强连通分量一定不变

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q5 原页片段

查看解析

Q6¶

一个有 28 条边的非连通无向图至少有（）个顶点。

A．7
B．8
C．9
D．10

查看解析

Q8¶

有向图的结点数为 4，则至少需要多少（）条边满足在任意条件下这个图是强连通图。

A．7
B．8
C．9
D．10

查看解析

Q9¶

如果 G 的强连通分量的数量等于 k>1，结点总数是 n，那么边数 m 应该满足（）。

A．〔公式/符号见原页版面片段〕 >= 〔公式/符号见原页版面片段〕 − 1
B．〔公式/符号见原页版面片段〕 >= 〔公式/符号见原页版面片段〕 − 〔公式/符号见原页版面片段〕 + 1
C．〔公式/符号见原页版面片段〕 <= (n − 1)(n − 2)
D．〔公式/符号见原页版面片段〕 <= 〔公式/符号见原页版面片段〕 − 1 2

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q9 原页片段

查看解析

Q10¶

具有 51 个顶点和 21 条边的无向图的连通分量最多为（）。

A．33
B．34
C．45
D．32

查看解析

Q11¶

下列关于图的陈述说法错误的是（）。

A．强连通的有向图的任何顶点到其他所有顶点都有弧
B．有向完全图一定是强连通有向图
C．DFS 生成树的高度一般不小于 BFS 生成树的高度
D．当各边上的权值相同时，BFS 算法可用来解决单源最短路径问题

查看解析

Q12¶

若具有 n 个顶点的图是一个环，则它有（）棵不同的生成树。

A．〔公式/符号见原页版面片段〕2
B．n
C．n-1
D．1

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q12 原页片段

查看解析

Q13¶

若一个具有 n 个顶点、e 条边的无向图是一个森林，则该森林中必有（）棵树。

A．n
B．e
C．n-e
D．1

查看解析

Q14¶

考虑一个有向图 G，假设该图中没有自环。以下关于有向图 G 的描述，错误的是（）。

A．如果 G的强连通分量的数量等于 k<n，结点总数是 n，那么边数 m≥n
B．如果 G 是一个有向树，那么 m=n-1
C．如果 G 是一个强连通图，那么 m≥n
D．如果 G是一个有向完全图，那么 m=n(n-1)

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q14 原页片段

查看解析

Q15¶

在如下图所示的有向图中，共有（）个强连通分量。

A．1
B．2
C．3
D．4

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q15 原页片段

查看解析

Q16¶

下列关于图的叙述，正确的是（）。
I．任意无向图的生成森林中顶点数量=边数+1
II．在一个连通无向图中，顶点数为 n，边数为 m，则它的生成树的边数为 n-1
III．对于有向无环图，可以通过拓扑排序来判断两个顶点之间是否有路径
IV．在一个无向图中，若从任意一个顶点出发都可以到达其他所有顶点，则这个图是连通图

A．仅 II，IV
B．仅 I、III
C．仅 I、II、IV
D．仅 II、III、IV

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q16 原页片段

查看解析

Q17¶

设 G是一个非连通无向图，有 10 条边，则该图的顶点数至少有（）个。

A．5
B．6
C．7
D．8

查看解析

Q18¶

下列关于图的存储结构说法，正确的是（）。

A．邻接表中找寻有向图某指定弧是否存在时间复杂度是 O(n+e)
B．邻接矩阵统计无向图某顶点的度，需要遍历该顶点再邻接矩阵的对应行和对应列上的元素
C．邻接多重表表示无向图时，表中非空指针数量是边数的 2 倍
D．邻接表统计对应顶点的出度方便但统计入度不方便，十字链表法与之相反

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q18 原页片段

查看解析

Q19¶

已知一个有向图的邻接表存储结构如右图所示，根据有向图的深度优先遍历算法，从顶点 1 出发，所得到的顶点序列是（）。

A．1，2，3，5，4
B．1，2，3，4，5
C．1，3，4，5，2
D．1，4，3，5，2

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q19 原页片段

查看解析

Q20¶

关于有向图的描述，正确的是（）。

A．从邻接矩阵中删除一个顶点的时间复杂度是 O(1)
B．有向图的入度和出度之和等于边数的两倍
C．有向图中的强连通分量不可能包含多个非连通子图
D．在有向无环图中，可以通过拓扑排序得到唯一的线性序列

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q20 原页片段

查看解析

Q21¶

设图的邻接矩阵 A如下所示，各顶点的入度依次是（）。

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

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q21 原页片段

查看解析

Q22¶

若无向图 G=(V,E)的邻接多重表如下图所示，则不属于该图的广度优先遍历序列的是（）。

A．abdce
B．decab
C．bacde
D．ecdab

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q22 原页片段

查看解析

Q23¶

一个含有 n 个顶点的连通且无环的简单无向图，在其邻接矩阵存储结构中共有（）个零元素。

A．〔公式/符号见原页版面片段〕2 − 2〔公式/符号见原页版面片段〕
B．〔公式/符号见原页版面片段〕2 − 2〔公式/符号见原页版面片段〕 − 2
C．〔公式/符号见原页版面片段〕2 − 2〔公式/符号见原页版面片段〕 + 2
D．2 〔公式/符号见原页版面片段〕 − 1

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q23 原页片段

查看解析

Q24¶

带权有向图 G 用邻接矩阵 A 存储，则顶点 i 的入度等于（）。

A．第 i 行非∞的元素之和
B．第 i 列非∞的元素之和
C．第 i 行非∞且非 0 的元素个数
D．第 i列非∞且非 0 的元素个数

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q24 原页片段

查看解析

Q25¶

下列关于邻接表和邻接矩阵的陈述中，错误的是（）。

A．求有向图的结点的入度必须遍历整个邻接表
B．在有向图的邻接表中，某个顶点 v 在链表中出现的次数等于该顶点的入度
C．若邻接矩阵中的主对角线以下的元素为 0，则该图必定存在一个拓扑排序序列
D．因为有向无环图具有拓扑序列，所以它的邻接矩阵必定是上三角矩阵或下三角矩阵

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q25 原页片段

查看解析

Q26¶

下面关于图的存储的叙述中正确的是（）。

A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C．用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关
D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q26 原页片段

查看解析

Q27¶

下列说法错误的是（）。

A．对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点
B．连通图上各边权值均不相同，则该图的最小生成树是惟一的
C．有 n 个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半
D．树的先根遍历算法可以理解为深度优先遍历法的一种特殊形式

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q27 原页片段

查看解析

Q28¶

下列说法错误的是（）。

A．强连通图不能进行拓扑排序
B．只要无向网中没有权值相同的边，其最小生成树就是唯一的。
C．如果表示某个图的邻接矩阵是对称矩阵，则该图不一定是无向图
D．从 n 个顶点的连通图中选取 n-1 条权值最小的边，即可构成最小生成树

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q28 原页片段

查看解析

Q29¶

如下无向图的邻接表，从顶点 2 到顶点 4 长度为 2 的路径数量为（）。

A．1
B．2
C．3
D．4

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q29 原页片段

查看解析

Q30¶

下图所示十字链表表示的有向图，入度为 2 的顶点有（）个。

A．1
B．2
C．3
D．4

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q30 原页片段

查看解析

Q31¶

已知图的邻接矩阵，则从顶点 0 出发按深度优先遍历的结点序列是（）。0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0

A．0243156
B．0136542
C．0134256
D．0361542

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q31 原页片段

查看解析

Q32¶

下列关于广度优先算法的说法中，正确的是（）。
I．当各边的权值相等时，广度优先算法可以解决单源最短路径问题
II．当各边的权值不等时，广度优先算法可用来解决单源最短路径问题
III．广度优先遍历算法类似于树中的后序遍历算法
IV．实现图的广度优先算法时，使用的数据结构是队列

A．I、IV
B．II、III、IV
C．II、IV
D．I、III、IV

查看解析

Q33¶

下列关于深度优先遍历算法，正确的有（）。
I．深度优先遍历有向图过程中，DFSTraverse（）调用 DFS 的次数是强连通分量的个数
II．深度优先遍历有向图过程中，回边的存在说明图中包含环
III．在有向图的深度优先遍历过程中，若一个顶点 u 访问过后，另外一个顶点 v 访问时发现有到这个顶点的边，那么该有向图一定存在环
IV．深度优先遍历算法遍历有向无环图，如果在退出 DFS 时依次输出顶点，得到的是逆拓扑排序

A．II、IV
B．I、II、III
C．II、III、IV
D．I、II、III、IV

查看解析

Q34¶

下列邻接表表示的有向图，从顶点 1 开始进行深度优先遍历，可能得到不同遍历序列个数有（）个。

A．2
B．3
C．4
D．5

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q34 原页片段

查看解析

Q35¶

用 Prim 算法求一个带权连通图的最小生成树，在算法执行的某个时刻，已选取的顶点集合 U={1,2,3}，已选取的边集合 TE={(1,2),(2,3)}，要选取下一条权值最小的边，应当从（）组中选取。

A．{(1,4),(3,4),(3,5),(2,5)}
B．{(3, 4),(3, 5), (4,5),(1,4)}
C．{(1.2),(2.3),(3,5)}
D．{(4.5).(1.3).(3.5)}

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q35 原页片段

查看解析

Q36¶

已知无向图 G 如下图所示，使用 Prim 算法求图 G 的最小生成树（从顶点 b 出发），加到最小生成树中的边依次是（）。

A．,,,,
B．,,,,
C．,,,,
D．,,,,

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q36 原页片段

查看解析

Q37¶

在求一个带权连通图的最小生成树时，已选取的边集是{(1,3)1，(3,4)3} ，(1,3)1 表示权值为 1的顶点 1 到顶点 3 的边。那么下一次选取，可能是 Kruskal 算法，但不可能是 Prim算法选取的边是()

A．(1,4)5
B．(4,5)4
C．(2,5)2
D．(5,6)4

查看解析

Q38¶

下列关于最小生成树的陈述中，错误的是（）。

A．设(u,v)是连通图 G 中的权重最小的边，那么(u,v)是 G 的某棵最小生成树中的一条边
B．设 e 是连通图 G=(V,E)的某条环路上权重最大的边，那么图 G中存在一棵不包含边 e的最小生成树
C．若图的所有边的权重有正有负，则任一连接所有结点且总权重最小的一个边集合必然形成一棵树
D．若 T 是图 G 的一棵最小生成树，如果减小了 T 中的一条边的权重，那么 T 仍然是 G的一棵最小生成树

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q38 原页片段

查看解析

Q39¶

下列关于最小生成树算法 Prim 和 Kruskal 算法，正确的有（）。
I．Prim 算法每轮选取离上一轮次选取的顶点距离最近的顶点
II．Prim 算法的时间复杂度可优化至〔公式/符号见原页版面片段〕
III．稠密图情况下，无向图采用邻接矩阵存储，Kruskal 算法的时间复杂度是〔公式/符号见原页版面片段〕 V2
IV．Kruskal 算法使用了并查集的数据结构

A．I、II、III、IV
B．II、III
C．II、IV
D．III、IV

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q39 原页片段

查看解析

Q40¶

下列关于图的最短路径的相关叙述中，正确的是（）。

A．最短路径一定是简单路径
B．Dijkstra 算法不适合求有回路的带权图的最短路径
C．Dijkstra 算法不适合求任意两个顶点的最短路径
D．Floyd 算法求两个顶点的最短路径时，〔公式/符号见原页版面片段〕ℎ〔公式/符号见原页版面片段〕−1一定是〔公式/符号见原页版面片段〕ℎ〔公式/符号见原页版面片段〕的子集

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q40 原页片段

查看解析

Q41¶

根据下图，关于 Dijkstra、Prim、Floyd 算法说法正确的是（）。

A．用 Dijkstra 算法求上面右图的结点 1 单源最短路径，到结点 2 和结点 3 的最短路径长度分别为 4和 7
B．用 Prim 算法求左图最小生成树，从结点 1 出发，得到的最小生成树保留的边权值为-3 和 6
C．Dijkstra 和 Prim 算法的思想都是基于贪心，都是从当前轮选出的结点作为中间结点去更新未处理结点的 path 数组，且更新的策略一样
D．用 Floyd 算法求右图的最短路径，经过一轮计算后，得到的矩阵〔公式/符号见原页版面片段〕0 =0 4 7 ∞ 0 ∞ ∞ −3 0

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q41 原页片段

查看解析

Q42¶

下列关于图的最短路径的相关叙述中，正确的是（）。
I．Dijkstra 算法求单源最短路径不允许边的权为负
II．Dijkstra 算法求每对顶点间的最短路径的时间复杂度是 O(n^2)
III．Floyd 算法求每对顶点间的最短路径允许边的权为负，但不允许含有负边的回路

A．I、II 和 III
B．仅 I
C．I和 III
D．II 和 III

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q42 原页片段

查看解析

审计旁注（非原文）：改答案为 B

Ⅰ正确；Ⅱ错，邻接矩阵实现的 Dijkstra 运行 n 次是 O(n³)；Ⅲ把“负权回路”误写成“含负边的回路”，后者不一定是负权回路。因此仅Ⅰ正确，选 B。王道回源：result.md [block: b_242_8, b_244_0, b_244_1]。

[定性修正 · 2026-09-01 逐题复核] 问题属实但处理方式应改：根因是题干把王道原文“不允许含负权回路”转抄成“含负边的回路”。正确处理是改回题干、答案维持 C（与王道原题一致），而不是把答案改成 B。

Q43¶

使用有向无环图描述表达式((a+b)(b(c+d))+(c+d)e)((c+d)*e)，需要的边的个数至少是（）

A．14
B．15
C．16
D．13

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q43 原页片段

查看解析

Q44¶

下列图的算法中，采用邻接表存储结构，假设顶点个数是 v，边的条数是 e，时间复杂度为O(v+e)的有()个
I.DFS
II. BFS
III. Prim
IV. Kruskal V. 拓扑排序
VI. dijkstra

A．3
B．4
C．5
D．6

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q44 原页片段

查看解析

Q45¶

已知有向图 G（V，E），其中 V={v0,v1,v2}，E={(v0，v1)6，(v0，v2)13，（v1，v0）10，（v1，v2）4，（v2，v0）5}，对于 Floyd 算法，迭代两趟的结果A1是（）

A．0 6 13 10 0 4 5 ∞ 0
B．0 6 10 9 0 4 5 11 0
C．0 6 13 10 0 4 5 11 0
D．0 6 10 10 0 4 5 11 0

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q45 原页片段

查看解析

Q46¶

用 Floyd 算法求下图的最短路径，得到的 dist 矩阵结果是（）。

A．1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
B．1 ∞ ∞ 0 2 1 1 1 3 1 1 2 1 2 1 1
C．0 0 0 0 2 0 1 1 3 1 0 2 1 2 1 0
D．0 ∞ ∞ ∞ 2 0 1 1 3 1 0 2 1 2 1 0

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q46 原页片段

查看解析

Q47¶

下列关于最短路径算法的叙述，正确的是（）。
I．Dijkstra 算法求有向图的单源最短路径，有向图可以带负权但是不能有负权环路
II．Dijkstra 算法的核心思想是贪心策略
III．Floyd 算法的核心思想是动态规划
IV．Dijkstra 算法求每对顶点之间的最短路径的时间复杂度是〔公式/符号见原页版面片段〕2

A．I、II、III
B．II、III、IV
C．II、III
D．全部

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q47 原页片段

查看解析

Q48¶

下图所示有向图的所有拓扑序列共有（）个。

A．4
B．6
C．5
D．7

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q48 原页片段

查看解析

Q49¶

已知有向图 G=(V，E)，其中 V={a, b, c, d, e, f, g}，E={}G 的拓扑序列是（）。

A．a，c，d，f，b，e，g
B．a，c，b，f，d，e，g;
C．a，c，d，e，b，f，g
D．a，b，e，c，d，f，g

原页版面片段（用于核对图表、公式、矩阵或代码）

第6章 Q49 原页片段

查看解析

Q50¶

下列关于图的说法中，正确的是（）。
I．有向图中顶点 V的度等于其邻接矩阵中第 V 行中 1 的个数
II．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵
III．在带权图 G 的最小生成树 G，中，某条边的权值可能会超过未选边的权值
IV．若有向无环图的拓扑序列唯一，则可以唯一确定该图