数据结构 · 图错题记录

本页按添加顺序整理图论错题，仅保留原题、选项和必要图形，不含答案与解析。

第 1 题

添加日期： 2026-09-19

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

A. 最短路径一定是简单路径
B. Dijkstra 算法不适合求有回路的带权图的最短路径
C. Dijkstra 算法不适合求任意两个顶点间的最短路径
D. Dijkstra 算法可以正确处理含有负权边的图

第 2 题

添加日期： 2026-09-19

下面的（　）方法可以判断出一个有向图是否有环（回路）。

Ⅰ. 深度优先遍历
Ⅱ. 拓扑排序
Ⅲ. 求最短路径
Ⅳ. 广度优先遍历

A. Ⅰ、Ⅱ、Ⅳ
B. Ⅰ、Ⅲ、Ⅳ
C. Ⅰ、Ⅱ、Ⅲ
D. 全部可以

第 3 题

添加日期： 2026-09-19

下列关于拓扑排序的说法中，正确的是（　）。

Ⅰ. 顶点数大于 1 的强连通图不能进行拓扑排序
Ⅱ. 在一个有向图的拓扑序列中，若顶点 $a$ 在顶点 $b$ 之前，则图中必有一条弧 <a, b>
Ⅲ. 若有向无环图的拓扑序列唯一，则可以唯一确定该图

A. Ⅰ和Ⅱ
B. Ⅰ、Ⅱ和Ⅲ
C. 仅Ⅰ
D. Ⅰ和Ⅲ

第 4 题

添加日期： 2026-09-19

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

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

第 5 题

添加日期： 2026-09-19

若一个有向图具有有序的拓扑排序序列，则它的邻接矩阵必定为（　）。

A. 对称
B. 稀疏
C. 三角
D. 一般

第 6 题

添加日期： 2026-09-19

下列关于图的说法中，正确的是（　）。

Ⅰ. 有向图中顶点 $V$ 的度等于其邻接矩阵中第 $V$ 行中 1 的个数
Ⅱ. 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵
Ⅲ. 在带权图 $G$ 的最小生成树 $G_1$ 中，某条边的权值可能会超过未选边的权值
Ⅳ. 若有向无环图的拓扑序列唯一，则可以唯一确定该图

A. Ⅰ、Ⅱ和Ⅲ
B. Ⅲ和Ⅳ
C. Ⅲ
D. Ⅳ

第 7 题

添加日期： 2026-09-19

下图所示的 AOE 网中，关键路径长度为（　）。

A. 16
B. 17
C. 18
D. 19

第 8 题

添加日期： 2026-09-19

若某带权图为 $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₁, v₂>5, <v₁, v₃>6, <v₂, v₅>3, <v₃, v₅>6, <v₃, v₄>3, <v₄, v₅>3, <v₄, v₇>1, <v₄, v₈>4, <v₅, v₆>4, <v₅, v₇>2, <v₆, v₁₀>4, <v₇, v₉>5, <v₈, v₉>2, <v₉, v₁₀>2}

（注：边括号外的数据表示边上的权值），则 $G$ 的关键路径的长度为（　）。

A. 19
B. 20
C. 21
D. 22

第 9 题

添加日期： 2026-09-19

【2010 统考真题】对右图进行拓扑排序，可得不同拓扑序列的个数是（　）。

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

第 10 题

添加日期： 2026-09-19

【2012 统考真题】若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（　）。

A. 存在，且唯一
B. 存在，且不唯一
C. 存在，可能不唯一
D. 无法确定是否存在

第 11 题

添加日期： 2026-09-19

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

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

第 12 题

添加日期： 2026-09-19

【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