CSP-J/S 图论基础与算法综合测试

本试卷共 25 道单项选择题，每题 4 分，满分 100 分。

一、图的概念、度数与存储

1. 一个无向图有 8 条边，则所有顶点的度数之和为（ ）。

{{ select(1) }}

• 8
• 16
• 24
• 32

2. 一个有向图有 12 条边，则所有顶点的入度之和为（ ）。

{{ select(2) }}

• 6
• 12
• 24
• 与顶点数量有关

3. 含 10 个顶点的无向简单完全图共有（ ）条边。

{{ select(3) }}

• 20
• 45
• 90
• 100

4. 对于顶点数和边数都较大的稀疏图，通常更合适的存储方式是（ ）。

{{ select(4) }}

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

5. 无向图使用邻接矩阵存储时，矩阵通常具有的性质是（ ）。

{{ select(5) }}

• 关于主对角线对称
• 每一行的元素都相同
• 主对角线必须全为 1
• 所有非零元素只出现在上三角

6. 链式前向星存储含 m 条边的无向图时，边数组通常至少需要容纳（ ）条存储边。

{{ select(6) }}

• m/2
• m
• 2m
• m^2

二、DFS、BFS 与拓扑排序

7. BFS 最核心的数据结构是（ ）。

{{ select(7) }}

• 栈
• 队列
• 并查集
• 邻接矩阵

8. 求无权图中两点之间经过的最少边数，应优先使用（ ）。

{{ select(8) }}

• DFS
• BFS
• Kruskal
• Floyd 必须使用

9. 使用邻接表遍历一张含 n 个顶点、m 条边的图，DFS 或 BFS 的时间复杂度通常为（ ）。

{{ select(9) }}

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

10. 关于 DFS/BFS 的遍历序列，下列说法正确的是（ ）。

{{ select(10) }}

• 从同一点出发时序列永远唯一
• 序列可能受到邻接点存储和访问顺序影响
• DFS 与 BFS 的序列一定相同
• 只有完全图才可以遍历

11. 一张有向图能够完成拓扑排序的充要条件是（ ）。

{{ select(11) }}

• 图必须连通
• 图没有重边
• 图中没有有向环
• 每个顶点入度相同

12. Kahn 拓扑排序结束后，若输出的顶点数量小于 n，说明（ ）。

{{ select(12) }}

• 图一定不连通
• 图中存在有向环
• 图中存在负权边
• 图一定是二分图

13. 要输出字典序最小的拓扑序列，应把保存入度为 0 顶点的普通队列改成（ ）。

{{ select(13) }}

• 小根堆
• 大根堆
• 栈
• 并查集

三、并查集、最小生成树与最短路

14. 并查集判断 x、y 是否属于同一集合时，应比较（ ）。

{{ select(14) }}

• x == y
• fa[x] == fa[y]
• find(x) == find(y)
• size[x] == size[y]

15. 一个含 n 个顶点的连通图，其任意生成树都恰有（ ）条边。

{{ select(15) }}

• n-2
• n-1
• n
• 与原图边数相同

16. Kruskal 算法处理边的基本顺序是（ ）。

{{ select(16) }}

• 按端点编号从小到大
• 按边权从大到小
• 按边权从小到大
• 任意顺序都能保证最优

17. Kruskal 判断加入一条边是否会形成环，通常使用（ ）。

{{ select(17) }}

• 队列
• 并查集
• 哈希表
• 邻接矩阵

18. 关于最小生成树，下列说法正确的是（ ）。

{{ select(18) }}

• 最小生成树不能包含负权边
• 边权互不相同时最小生成树唯一
• 最小生成树等同于任意两点最短路径
• 不连通图一定存在包含所有顶点的生成树

19. Dijkstra 算法的基本适用前提是（ ）。

{{ select(19) }}

• 图必须无向
• 所有边权非负
• 所有边权相同
• 图必须是一棵树

20. Dijkstra 中路径权值之和可能很大，因此距离数组通常优先使用（ ）。

{{ select(20) }}

• bool
• char
• long long
• short

21. Floyd 算法三重循环中，表示中转点的变量 k 应放在（ ）。

{{ select(21) }}

• 最外层
• 最内层
• 任意一层均可
• 不需要循环 k

22. 下列关于最短路径和最小生成树的说法正确的是（ ）。

{{ select(22) }}

• 两者选出的边数一定相同
• 两者优化目标完全相同
• 最短路优化点之间的路径，MST 优化连接全部顶点的总成本
• Dijkstra 可以直接替代 Kruskal 求 MST

四、二分图、欧拉路与平面图

23. 一个无向图是二分图，当且仅当它（ ）。

{{ select(23) }}

• 不存在任何环
• 不存在奇数长度的环
• 所有顶点度数为偶数
• 一定是连通图

24. 一个忽略孤立点后连通的无向图恰有两个奇度顶点，则它（ ）。

{{ select(24) }}

• 一定存在欧拉回路
• 存在欧拉路但不存在欧拉回路
• 一定是树
• 一定不是二分图

25. 一棵树作为连通平面图时，面数 F 为（ ）。

{{ select(25) }}

• 0
• 1
• 2
• n-1