第 1 题

图通常由哪两部分组成？

{{ select(1) }}

• 顶点和边
• 根和叶子
• 数组和队列
• 状态和转移

第 2 题

无向图的一条边表示（ ）。

{{ select(2) }}

• 只能单向到达
• 两个方向都可通过
• 没有顶点
• 一定有环

第 3 题

有向图顶点 B 被两条边指向，则 B 的入度至少为（ ）。

{{ select(3) }}

• 0
• 1
• 2
• 3

第 4 题

路径 A-B-C-D 的长度（边数）是多少？ {{ input(4) }}

第 5 题

树的重要特点是（ ）。

{{ select(5) }}

• 连通且无环
• 一定有环
• 边数不固定
• 所有点度相同

第 6 题

图遍历使用 visited 的主要原因是（ ）。

{{ select(6) }}

• 自动排序
• 避免重复访问和环
• 计算权值
• 节省所有空间

第 7 题

n 个顶点的邻接矩阵空间复杂度是（ ）。

{{ select(7) }}

• $O(n)$
• $O(n^2)$
• $O(\log n)$
• $O(1)$

第 8 题

邻接表存 n 个点 m 条边，空间通常是（ ）。

{{ select(8) }}

• $O(n+m)$
• $O(n^2)$
• $O(m^2)$
• $O(1)$

第 9 题

无向图邻接矩阵通常（ ）。

{{ select(9) }}

• 关于主对角线对称
• 一定全为1
• 只有上三角
• 不含0

第 10 题

稀疏图通常更适合（ ）。

{{ select(10) }}

• 邻接矩阵
• 邻接表

第 11 题

邻接矩阵判断 u、v 是否有边通常为（ ）。

{{ select(11) }}

• $O(1)$
• $O(n)$
• $O(n^2)$
• $O(m)$

第 12 题

邻接表遍历 u 的邻居，工作量主要与（ ）有关。

{{ select(12) }}

• u 的度数
• 全图顶点平方
• 矩阵行数
• 图是否有根