CSP 校队 9.9｜图论基础与遍历专项

本题用于 CSP 校队第一轮专项训练。请独立完成；卡住超过 90 秒先跳过。

客观题提交后由椰子 OJ 自动判分。

---

第 1 题

一个无向图中所有顶点的度数之和为 38，则该图的边数是？

{{ select(1) }}

• 19
• 38
• 76
• 无法确定

第 2 题

一个有向图所有顶点的入度之和为 31，则该图有多少条有向边？

{{ select(2) }}

• 15
• 31
• 62
• 无法确定

第 3 题

一个含 10 个顶点的简单无向图，最多有多少条边？

{{ select(3) }}

• 10
• 20
• 45
• 90

第 4 题

一个含 12 个顶点的连通无向图，至少需要多少条边？

{{ select(4) }}

• 10
• 11
• 12
• 22

第 5 题

一棵包含 20 个顶点的树可以看作一种特殊的连通无向图，它有多少条边？

{{ select(5) }}

• 18
• 19
• 20
• 21

第 6 题

关于无向图的邻接矩阵，下列说法正确的是？

{{ select(6) }}

• 一定是上三角矩阵
• 关于主对角线对称
• 每行只能有一个 1
• 不能表示带权图

第 7 题

当图很稀疏、顶点多而边相对较少时，通常更节省空间的存储方式是？

{{ select(7) }}

• 邻接矩阵
• 邻接表
• 二维前缀和
• 栈

第 8 题

路径 1 → 3 → 4 → 7 → 9 的路径长度是？

{{ select(8) }}

• 3
• 4
• 5
• 9

第 9 题

无向图顶点为 1..8，边为 {1-2, 2-3, 4-5, 5-6, 4-6, 7-8}。该图有多少个连通分量？

{{ select(9) }}

• 2
• 3
• 4
• 5

第 10 题

无向图边为 {1-2,1-3,2-4,3-5,4-5,5-6}，邻接点均按编号从小到大访问。从 1 开始 BFS，访问序列是？

{{ select(10) }}

• 1 2 4 5 3 6
• 1 2 3 4 5 6
• 1 3 2 5 4 6
• 1 2 3 5 4 6

第 11 题

沿用上一题的图和邻接点顺序，从 1 开始 DFS，访问序列是？

{{ select(11) }}

• 1 2 3 4 5 6
• 1 2 4 5 3 6
• 1 3 5 4 2 6
• 1 2 4 3 5 6

第 12 题

关于 DFS 与 BFS，下列说法正确的是？

{{ select(12) }}

• BFS 通常使用栈，DFS 通常使用队列
• BFS 通常使用队列，递归 DFS 的调用过程可看作使用系统栈
• DFS 只能用于树，不能用于图
• BFS 与 DFS 的访问顺序永远相同