2026-05-25 图及算法

单项选择题

1. n 个顶点的无向完全图的边数为（ ）。

2. 设无向图 G=(V, E)，和 G'=(V', E')，如果 G' 是 G 的生成树，则下面说法中错误的是（ ）。

3. 已知一个无向图 G 含有 18 条边，其中度数为 4 的顶点个数为 3，度数为 3 的顶点个数为 4，其他顶点的度数均小于 3，请问图 G 所含的顶点个数至少是（ ）。

4. 给定一个无向图 G，从顶点 V0 出发进行无向图 G 的深度优先遍历，访问的边集合为：{(V0,V1), (V0,V4), (V1,V2), (V1,V3), (V4,V5), (V5,V6)}，则下面哪条边（ ）不能出现在 G 中？

5. 已知一个有向图 G 的邻接入边表（或称逆邻接表）如下图所示，从顶点 v0 出发对该图 G 进行深度优先周游，得到的深度优先周游结点序列为（ ）。

v0 -> 1 -> 3
v1 -> 0 -> 2
v2 -> ∧
v3 -> 2 -> 4
v4 -> 1 -> ∧

判断题（对填 Y，错填 N）

6. 强连通分量是有向图中的最小强连通子图。

7. 用相邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

8. 若定义一个有向图的根是指可以从这个结点可到达图中任意其他结点，则可知一个有向图中至少有一个根。

9. 对任意一个连通的、无环的无向图，从图中移除任何一条边得到的图均不连通。

10. 任一有向图的拓扑序列既可以通过深度优先搜索求解，也可以通过宽度优先搜索求解。

11. 对任一连通无向图 G，其中 E 是权值最小的边，那么 E 必然属于任何一个最小生成树。

12. 对一个包含负权值边的图，迪杰斯特拉 (Dijkstra) 算法能够给出最短路径问题的正确答案。

填空题

13. 如果一个图节点多而边少（稀疏图），适宜采用邻接矩阵和邻接表中的 ________ 方式进行存储。

14. 在广度优先遍历、拓扑排序、求最短路径三种算法中，可以判断出一个有向图是否有环（回路）的是 ________ 。

15. 有 n（n≥2）个顶点的有向强连通图最少有 ________ 条边。