目标

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

前置知识

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

环境、输入与预期输出

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

作答方法

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

题型覆盖与边界

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

选择题

答题进度已答 0/10正确 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每次查询前把整张图重新排序

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

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

完成清单

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

思考题

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

复盘

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