目标

• 从边集读出邻接矩阵与邻接表，并检查有向、无向存储语义；
• 比较指定边查询、邻居枚举和全图扫描的时间与空间复杂度；
• 根据图的密度和高频操作选择矩阵、邻接表、边集数组或混合索引。

前置知识

建议先阅读6.2 图的存储结构，并能区分逻辑边数 $m$ 与邻接记录数。

环境、输入与预期输出

• 环境：任意现代浏览器；建议准备纸笔手写矩阵或邻接表。
• 输入：本页按源文件顺序整理的 20 道四选一选择题。
• 预期输出：一份独立作答记录，以及每道错题的复杂度依据或表示选择理由。

作答方法

1. 先写清图的方向、权重和底层容器，再判断复杂度；
2. 点击“提交答案”后核对答案与选项辨析；
3. 做错的题点击“重新作答”，并补写被忽略的实现前提；
4. 完成全部题目后再查看答案总览。

题型覆盖与边界

类型	本 Lab 的处理方式
正常情况	比较矩阵、动态数组邻接表和边集数组的常见操作
边界情况	单独考查零权边、自环、平行边、无向边双向记录和有向图行列含义
转换情况	比较矩阵与邻接表的转换成本，并保留无向多重图的自环语义
易错情况	区分逻辑边与存储记录，并避免脱离容器类型背复杂度

选择题

答题进度已答 0/20正确 0

第 1 题

难度★考点邻接矩阵、无向图、对称性标识ch06-02-q01

用 $0/1$ 邻接矩阵存储一张不含自环的简单无向图。下列说法正确的是（ ）。

请选择一个答案

A矩阵一定关于主对角线对称

B矩阵每一行的元素和都相等

C主对角线元素必须全部为 1

D矩阵的上三角和下三角可以表示两张不同的图

第 2 题

难度★★考点邻接矩阵、有向图、入度、出度标识ch06-02-q02

有向图包含边 $0\to 1$、$0\to 2$、$2\to 1$、$1\to 3$。若邻接矩阵第 $i$ 行表示从 $i$ 出发的边，则顶点 $1$ 的入度和出度分别为（ ）。

查看提示

先数指向 1 的箭头，再数从 1 出发的箭头。

请选择一个答案

A$1,2$

B$2,1$

C$2,2$

D$1,1$

第 3 题

难度★★考点邻接表、无向图、逻辑边、邻接记录标识ch06-02-q03

一张不含自环的简单无向图有 $m=7$ 条逻辑边。若邻接表为每条无向边分别保存 $u\to v$ 与 $v\to u$ 两条邻接记录，则所有邻接表长度之和为（ ）。

请选择一个答案

A7

B9

C14

D49

第 4 题

难度★★考点邻接表、邻接矩阵、稀疏图、空间复杂度标识ch06-02-q04

有 $100000$ 个顶点、$300000$ 条有向边，并且算法需要频繁枚举每个顶点的实际出邻居。下列主要存储方式最合适的是（ ）。

请选择一个答案

A邻接表

B$100000\times 100000$ 的邻接矩阵

C只保存顶点数组而不保存边

D为每个顶点保存一份完整矩阵

第 5 题

难度★★考点邻接矩阵、相邻查询、邻居枚举、复杂度标识ch06-02-q05

对含 $n$ 个顶点的图使用普通邻接矩阵。判断指定边 $u\to v$ 是否存在，以及枚举顶点 $u$ 的全部邻居，时间复杂度分别为（ ）。

请选择一个答案

A$\mathrm{\Theta }(1)$；$\mathrm{\Theta }(n)$

B$\mathrm{\Theta }(n)$；$\mathrm{\Theta }(1)$

C$\mathrm{\Theta }(m)$；$\mathrm{\Theta }(n+m)$

D$\mathrm{\Theta }(n^2)$；$\mathrm{\Theta }(n^2)$

第 6 题

难度★★★考点邻接表、动态数组、相邻查询、复杂度标识ch06-02-q06

邻接表的每个顶点使用未排序动态数组保存出边，且没有额外索引。忽略取得表头的常数操作，最坏情况下判断指定边 $u\to v$ 是否存在所需检查的邻接记录数，以及完整枚举 $u$ 的全部出邻居所需访问的邻接记录数，分别是（ ）。

查看提示

先写明“未排序动态数组、无额外索引”这个实现前提。

请选择一个答案

A最多 $1$ 条；恰好 $1$ 条

B最多 ${\mathrm{deg}}^{+}(u)$ 条；恰好 ${\mathrm{deg}}^{+}(u)$ 条

C最多 $n$ 条；恰好 $n$ 条

D最多 $m$ 条；恰好 $m$ 条

第 7 题

难度★★★考点邻接矩阵、邻接表、图遍历、复杂度标识ch06-02-q07

同一套“访问每个顶点并检查其全部邻居”的完整图遍历，使用邻接矩阵与邻接表时，时间复杂度通常分别为（ ）。

请选择一个答案

A$\mathrm{\Theta }(n+m)$；$\mathrm{\Theta }(n^2)$

B$\mathrm{\Theta }(n^2)$；$\mathrm{\Theta }(n+m)$

C$\mathrm{\Theta }(m)$；$\mathrm{\Theta }(n)$

D两者始终都是 $\mathrm{\Theta }(n+m)$

第 8 题

难度★★★考点带权图、邻接矩阵、零权边、optional标识ch06-02-q08

带权图允许权重为 $0$ 的边。若使用邻接矩阵，下列设计最能避免把“零权边”误判为“没有边”的是（ ）。

请选择一个答案

A规定矩阵值为 0 一律表示没有边

B用 std::optional<Weight> 或独立存在位区分边是否存在

C把所有零权边直接删除

D把零权边的权重自动改成 1

第 9 题

难度★★考点边集数组、Kruskal、全边扫描、存储选型标识ch06-02-q09

下列任务最适合直接以边集数组作为主要输入表示的是（ ）。

请选择一个答案

A反复枚举某一个顶点的全部邻居

B按边权排序后执行 Kruskal 算法

C以 $O(1)$ 时间查询任意指定点对是否相邻

D统计邻接矩阵每一行的非零项

第 10 题

难度★★★★考点邻接表、哈希索引、混合表示、工程选型标识ch06-02-q10

一个大规模稀疏社交图既要频繁枚举用户的好友，又要频繁判断两人是否直接相连。若可以用额外空间换查询速度，下列设计最合理的是（ ）。

查看提示

两类高频操作可以由主存储和辅助索引分别服务。

请选择一个答案

A只用邻接矩阵

B只用无索引边集数组

C以动态数组实现的邻接表为主存储，并维护哈希索引加速指定边查询

D每次查询前把整张图重新排序

第 11 题

难度★★★考点邻接矩阵、距离矩阵、自环标识ch06-02-q11

一张不含自环的带权图使用邻接矩阵存储；随后 Floyd 算法另建距离矩阵。关于两个矩阵的主对角线，正确的是（ ）。

请选择一个答案

A两个矩阵的对角线都必须为 0

B邻接矩阵对角线应表示是否存在自环；距离矩阵的 d(i,i) 可初始化为 0

C邻接矩阵对角线为 0 说明每个顶点都有零权自环

D距离矩阵对角线为 0 时，邻接矩阵也必须保存零权边

第 12 题

难度★★考点带权图、邻接矩阵、度标识ch06-02-q12

带权无向图的邻接矩阵第 u 行中有三个存在的边，权重分别为 2、5、7。顶点 u 的度为（ ）。

请选择一个答案

A3

B14

C21

D无法确定

第 13 题

难度★★★考点多重图、邻接矩阵、平行边标识ch06-02-q13

若带权邻接矩阵的每个单元只保存一个权值，依次加入两条平行边 u→v，权重分别为 4 和 9，第二次写入通常会（ ）。

请选择一个答案

A自动保存两条边及两个权重

B把单元中的 4 覆盖为 9

C把权重自动相加为 13

D拒绝整个图不再允许任何边

第 14 题

难度★★★考点邻接表、无向图、删除边、复杂度标识ch06-02-q14

无向图以未排序动态数组邻接表存储。删除逻辑边 {u,v} 且不维护位置索引，最坏情况下需要扫描的邻接记录量级为（ ）。

请选择一个答案

AΘ(1)

BO(deg(u)+deg(v))

CΘ(n²)

DO(m²)

第 15 题

难度★★考点邻接表、遍历顺序、排序标识ch06-02-q15

为使 DFS/BFS 按顶点编号稳定访问邻居，建图后把每个邻接表排序。下列说法正确的是（ ）。

请选择一个答案

A排序会改变图中可达关系

B排序只改变遍历时的邻居处理顺序，不改变图本身

C排序后所有邻接表的长度都会相同

D排序能把邻接表完整遍历固定为 Θ(n²)

第 16 题

难度★★★考点邻接矩阵、无向图、空间复杂度标识ch06-02-q16

不含自环的简单无向图的邻接矩阵可以只保存上三角区域。该优化最准确的描述是（ ）。

请选择一个答案

A空间从 Θ(n²) 降为 Θ(n+m)

B空间约减半，但渐近量级仍为 Θ(n²)

C查询指定边必然从 Θ(1) 变为 Θ(n)

D能够保存任意数量的平行边

第 17 题

难度★★★考点表示转换、邻接表、邻接矩阵、复杂度标识ch06-02-q17

把含 n 个顶点、m 条边的邻接表转为普通邻接矩阵，先初始化 n×n 的空矩阵，再写入边。总时间复杂度为（ ）。

请选择一个答案

AΘ(m)

BΘ(n+m)

CΘ(n²+m)，即 Θ(n²)

DΘ(m²)

第 18 题

难度★★★考点表示转换、邻接矩阵、邻接表、复杂度标识ch06-02-q18

把普通 n×n 邻接矩阵转为邻接表时，即使原图很稀疏，也必须先完成的工作是（ ）。

请选择一个答案

A只扫描实际存在的 m 条边

B检查全部 n² 个矩阵单元

C对每个顶点做一次二分查找

D为每条边运行一次 BFS

第 19 题

难度★★★★考点表示转换、边集数组、自环、多重图标识ch06-02-q19

无向多重图的邻接表可能含自环。若转换为每条逻辑边只出现一次的边集数组，只保留 u<v 的邻接记录会产生的问题是（ ）。

请选择一个答案

A会重复保留所有平行边

B会丢弃自环 (u,u)

C会把所有边权自动变为 0

D会使转换时间变为 Θ(n²)

第 20 题

难度★★★考点CSR、静态图、邻接表、缓存局部性标识ch06-02-q20

一张超大稀疏图构建后几乎不再修改，主要操作是顺序枚举邻居，并希望减少大量小对象的开销、改善连续访问。合适的表示起点是（ ）。

请选择一个答案

A普通邻接矩阵

BCSR 等压缩邻接结构

C每次枚举前重新扫描边集数组

D为每个顶点复制一份完整矩阵

答案总览（建议完成全部题目后查看）

1. 第 1 题：A
2. 第 2 题：B
3. 第 3 题：C
4. 第 4 题：A
5. 第 5 题：A
6. 第 6 题：B
7. 第 7 题：B
8. 第 8 题：B
9. 第 9 题：B
10. 第 10 题：C
11. 第 11 题：B
12. 第 12 题：A
13. 第 13 题：B
14. 第 14 题：B
15. 第 15 题：B
16. 第 16 题：B
17. 第 17 题：C
18. 第 18 题：B
19. 第 19 题：B
20. 第 20 题：B

完成清单

• 20 道题均在展开答案前独立作答；
• 能说明无向邻接表为何通常保存 $2m$ 条记录；
• 能分别写出矩阵与邻接表完整遍历的复杂度；
• 能为至少两个实际场景给出“表示 + 理由”，而不只写结构名称。

思考题

1. 为什么“邻接表查询边是 $O(1)$”必须附加哈希等实现前提？
2. 零权边存在时，怎样把“边是否存在”和“权重是多少”分开？
3. 维护邻接表与哈希索引两个视图时，怎样避免更新不一致？
4. 为什么把邻接表转为矩阵的成本主要由初始化矩阵决定？

复盘

• 我是否先确认了图的方向和底层容器，再套复杂度？
• 我最容易把哪一种结构的优势误认为所有操作都快？
• 哪道题最能体现“图的规模与高频操作决定存储方式”？