算法设计 第6讲（上）图论 I：MST 与最短路 — 章节练习

第6讲上图论 IMST 与最短路 — 章节练习一、单项选择题共 37 题每题 4 个选项图表示邻接矩阵与邻接表1. 对于一个具有 |V| 个顶点、|E| 条边的图使用邻接矩阵存储的空间复杂度是A. O(|V| |E|)B. O(|V|^2)C. O(|E|)D. O(|V|)2. 关于邻接矩阵和邻接表的适用场景正确的是A. 邻接矩阵适合存储稀疏图邻接表适合存储稠密图B. 邻接矩阵适合存储稠密图邻接表适合存储稀疏图C. 两者都适合存储稠密图D. 两者都适合存储稀疏图3. 对于一个接近完全图的稠密无向图以下说法正确的是A. |E| 远小于 |V|^2应使用邻接表B. |E| 接近 |V|^2邻接矩阵能提供 O(1) 的边存在性判断C. 该图就是零图null graphD. 无论稠密还是稀疏邻接表总是优于邻接矩阵BFS广度优先搜索与 DFS深度优先搜索4. 在 BFS 算法中顶点被标记为三种颜色。其中灰色顶点表示A. 尚未被发现的顶点B. 已被发现但其邻接表尚未完全探索完毕C. 所有邻接顶点都已被探索完毕D. 已被加入广度优先树但距离尚未确定5. BFS 算法的时间复杂度是A. O(|V|)B. O(|E|)C. O(|V| |E|)D. O(|V| × |E|)6. BFS 算法中所用的核心辅助数据结构是A. 栈StackB. 优先队列Priority QueueC. 队列QueueD. 并查集Union-Find7. 在 DFS 中顶点 v 的时间戳 d[v] 和 f[v] 分别记录的是A. d[v] 发现时刻f[v] 完成时刻B. d[v] 入队时刻f[v] 出队时刻C. d[v] 深度f[v] 高度D. d[v] 前驱编号f[v] 后继编号8. 在有向图的 DFS 中第一次探索边 (u, v) 时若 v 的颜色为灰色则该边属于A. 树边Tree edgeB. 返回边Back edgeC. 前向边Forward edgeD. 交叉边Cross edge​如果第一次探索(u,v)时v是白色 就是树边如果第一次探索(u,v)时v是灰色 就是返回边如果第一次探索(u,v)时v是黑色 就是前向边返回边从后代指向祖先树边拓展方向交叉边两边的节点不存在祖先-后代关系【时间节点不重叠】前向边从祖先指向后代隔代否则叫树边树边Tree edges在DFS过程中首次访问一个新节点时所经过的边。它们构成了DFS生成树的骨架。例如从节点u到其子节点v的边(u,v)就是树边。返回边Back edges从一个节点u指向其祖先节点v的边。这类边的存在通常意味着图中存在环。自环self-loop也被视为返回边。前向边Forward edges从一个节点u指向其非直接子节点的后代v的边。它不是树边但连接了祖先和后代。交叉边Cross edges所有不属于以上三类的边。它们可能连接同一DFS树中无祖先-后代关系的节点或者连接不同DFS树中的节点。​9. 在无向图的 DFS 中以下说法正确的是A. 可能出现树边、返回边、前向边和交叉边B. 每条边要么是树边要么是返回边不可能出现前向边或交叉边C. 可能出现前向边但不可能出现交叉边D. 可能出现交叉边但不可能出现前向边10. 白路径定理White-Path Theorem指出在 DFS 森林中v 是 u 的后代当且仅当A. u.d v.dB. 在时刻 u.d存在一条从 u 到 v 的全由白色顶点组成的路径C. f[u] f[v]D. v 在 u 的邻接表中11. 以下哪种类型的图可以进行拓扑排序A. 含有环的有向图B. 无向图C. 有向无环图DAGD. 任何有向图MST基本概念、割与安全边12. 以下关于生成树的描述正确的是A. 生成树可能包含环B. 生成树是原图的一个无环连通子图连接所有顶点C. 生成树一定包含原图的所有边D. 一个连通无向图只有唯一一棵生成树13. 设割 (X, Y) 是顶点集 V 的一个划分。称边 (u, v) “跨越”cross该割当且仅当A. u, v 都在 X 中B. u, v 都在 Y 中C. u ∈ X 且 v ∈ Y或 u ∈ Y 且 v ∈ XD. u, v 分别在两个不同的连通分量中14. 割 (X, Y) “尊重”respect边集 A 的含义是A. A 中的所有边都跨越该割B. A 中没有任何边跨越该割C. A 中的所有边权值都不为零D. A 包含跨越该割的最小权边15. 一条跨越割 (X, Y) 的轻边light edge是指A. 权值为 0 的边B. 跨越该割的所有边中权值最小的边C. 全图中权值最小的边D. 权值为负数的边16. Theorem 23.1安全边定理设 A 是某棵 MST 的子集割 (X, Y) 尊重 A(u, v) 是跨越 (X, Y) 的一条轻边则A. (u, v) 一定包含在所有 MST 中B. (u, v) 对于 A 是安全的即 A ∪ {(u, v)} 仍是某棵 MST 的子集C. (u, v) 一定不包含在任何 MST 中D. 必须将 A 中的某条边删除后才能加入 (u, v)17. 在安全边定理的证明中若当前 MST T 不包含轻边 (u, v)构造新 MST T’ 的方法是A. 直接删除 T 中任意一条边再加入 (u, v)B. 在 T 中加入 (u, v) 形成环删除环上另一条跨越同一割的边 (x, y)C. 重新运行 Kruskal 算法D. 删除 T 中权值最大的边再加入 (u, v)18. Corollary 23.2 指出设 C 是森林 G_A (V, A) 中的一个连通分量(u, v) 是连接 C 与其他分量的一条轻边则A. (u, v) 对于 A 不是安全边B. (u, v) 对于 A 是安全的C. (u, v) 会形成环D. (u, v) 的权值必须为 0Kruskal 算法与 Prim 算法19. Kruskal 算法的核心步骤是A. 从一个顶点开始不断扩展树B. 按边权递增顺序考察每条边若加入后不形成环则加入C. 每次选择连接已选顶点集与未选顶点集的最小权边D. 使用动态规划计算最小生成树20. Kruskal 算法中检测边 (u, v) 是否形成环所使用的数据结构是A. 栈StackB. 队列QueueC. 并查集Union-Find含 Find 和 Union 操作D. 哈希表Hash Table21. Kruskal 算法与 Prim 算法的一个重要区别是A. Prim 算法只能用于有向图B. 在 Prim 算法中边集 A 始终形成一棵树在 Kruskal 算法中A 可能是一个森林C. Kruskal 算法使用优先队列D. Prim 算法需要排序所有边22. 使用二叉堆binary heap实现的 Prim 算法的时间复杂度为A. O(|V| |E|)B. O(|V||E|)C. O(|E| log |V|)D. O(|V|^2)23. 对稀疏图|E| O(|V|)和稠密图|E| O(|V|^2)以下复杂度对比正确的是A. 稀疏图Kruskal 更快稠密图Prim 更快B. 稀疏图Prim 更快稠密图Kruskal 更快C. 两者在稀疏图上一样快D. 两者在稠密图上一样快MST 重要性质24. 如果连通无向图 G 中所有边的权值互不相同则关于 MST 的说法正确的是A. 图 G 可能有多棵不同的 MSTB. 图 G 的最小生成树是唯一的C. 图 G 一定没有 MSTD. MST 的总权值依赖于算法选择25. 关于最小权边属于某棵 MST这一性质的证明可以采用的方法是A. 设 A 为空集取割 ({u}, V − {u})由 Theorem 23.1 得 (u, v) 是安全边B. 由归并排序的结论直接得到C. 该性质不成立D. 由 Dijkstra 算法的正确性推出最短路问题与最优子结构26. Lemma 24.1最短路径的最优子结构的内容是A. 任何路径的子路径都是最短路径B. 最短路径的任意子路径也是相应端点之间的最短路径C. 最短路径一定不包含环D. 最短路径的权值等于每条边权值的乘积27. 假设图中不存在负权环一条从源点 s 到顶点 v 的最短路径最多包含多少条边A. |V|B. |V| − 1C. |E|D. |V| 1松弛操作Relaxation及其性质28. 松弛操作 RELAX(u, v, w) 的核心逻辑是A. d[v] min(d[v], d[u] w(u, v))B. d[v] max(d[v], d[u] w(u, v))C. d[v] d[u] w(u, v)D. d[v] d[u] − w(u, v)29. 三角不等式Triangle Inequality, Lemma 24.10指出对于任意边 (u, v) ∈ E有A. δ(s, v) ≤ δ(s, u) w(u, v)B. δ(s, v) ≥ δ(s, u) w(u, v)C. δ(s, v) δ(s, u) w(u, v)D. δ(s, v) ≤ δ(s, u) − w(u, v)30. 收敛性质Convergence Property, Lemma 24.14指出若 s ↝ u → v 是一条从 s 到 v 的最短路径且在松弛 (u, v) 之前已有 d[u] δ(s, u)则松弛后A. d[v] 保持不变B. d[u] 可能变小C. d[v] δ(s, v) 且之后不再改变D. d[v] δ(s, v) 但之后可能再变Bellman-Ford 算法31. Bellman-Ford 算法需要执行 |V| − 1 轮松弛的根本原因是A. 因为图中有 |V| − 1 个顶点需要处理B. 因为最短路径最多包含 |V| − 1 条边每轮至少能正确确定一条边的距离C. 因为算法需要检测 |V| − 1 种不同的负权环D. 因为 |V| − 1 是最小生成树的边数32. Bellman-Ford 算法如何检测从源点 s 可达的负权环A. 检查所有顶点的 d[v] 是否为负数B. 在第 |V| 轮再对所有边松弛一次若还能使某个 d[v] 减小则存在负权环C. 检查图中是否有权值为负的边D. 计算所有环的平均权值DAG 上的最短路径与 Dijkstra 算法33. 在有向无环图DAG上求解单源最短路径时最高效的做法是A. 先拓扑排序再按拓扑序依次松弛每条边B. 直接运行 Bellman-Ford 算法C. 先运行 DFS 再运行 BFSD. 使用 Floyd-Warshall 算法34. Dijkstra 算法能够正确求解最短路径的前提条件是A. 图中不能有环B. 所有边的权值必须非负C. 图必须是无向图D. 图必须是连通的35. Dijkstra 算法正确性证明中使用的循环不变式loop invariant是A. 每次迭代开始时对所有顶点 v 都有 d[v] δ(s, v)B. 每次迭代开始时对已加入集合 S 的顶点 v有 d[v] δ(s, v)C. 每次迭代开始时优先队列 Q 中所有顶点的 d 值均已正确D. 每次迭代开始时所有边的松弛操作都已执行完毕36. 关于 Dijkstra 算法中二叉堆binary heap与斐波那契堆Fibonacci heap的比较正确的是A. 二叉堆的 EXTRACT-MIN 更快B. 斐波那契堆的 DECREASE-KEY 摊还时间为 O(1)二叉堆为 O(log |V|)C. 斐波那契堆的 INSERT 更慢D. 两者复杂度完全相同Floyd-Warshall 算法选学37. Floyd-Warshall 算法的核心递推关系是A. d^{(k)}{ij} min(d^{(k-1)}{ij}, d^{(k-1)}{ik} d^{(k-1)}{kj})B. d^{(k)}{ij} d^{(k-1)}{ij} d^{(k-1)}{ik}C. d^{(k)}{ij} max(d^{(k-1)}{ij}, d^{(k-1)}{ik} d^{(k-1)}{kj})D. d^{(k)}{ij} min(d^{(k-1)}{ij}, d^{(0)}{ik} d^{(0)}_{kj})二、判断题共 20 题正确打 √错误打 ×图表示1. 对于稠密图|E| 接近 |V|^2邻接矩阵通常优于邻接表因为判断任意两点之间是否有边只需 O(1) 时间且空间开销与邻接表在同一量级。 2. 邻接矩阵总是比邻接表占用更少的存储空间。 BFS / DFS3. 在 BFS 中队列 Q 里相邻顶点的 d 值最多相差 1。 4. 在无向图的 DFS 中每条边要么是树边要么是返回边不可能出现前向边或交叉边。 5. 在一个有向图中进行 DFS如果按照结束时间 f[v] 的递减顺序输出顶点即可得到该图的一个拓扑排序。 MST6. 一棵具有 |V| 个顶点的树有 |V| 条边。 7. 如果连通无向图 G 中所有边的权值互不相同则 G 的最小生成树是唯一的。 8. 在 Kruskal 算法中加入一条边之前会先用 Find 操作检查其两个端点是否属于同一连通分量。 9. 在 Prim 算法中每次从优先队列中取出的顶点 u其 key[u] 值表示 u 到当前已构造的 MST 部分的最短距离。 10. 安全边定理Theorem 23.1和 Corollary 23.2 是 Kruskal 算法和 Prim 算法正确性的理论基础。 11. 对于任意连通无向图全局权值最小的边一定属于某棵最小生成树。 最短路 — 松弛性质12. 三角不等式 δ(s, v) ≤ δ(s, u) w(u, v) 对图中任意边 (u, v) 都一定成立。 13. 上界性质Upper-bound Property保证在任何时刻对任意顶点 v最短路径估计 d[v] 不会小于真实最短路径权值 δ(s, v)。 14. 路径松弛性质Path-relaxation Property说明只要按最短路径上边的顺序进行松弛中间可以插入其他松弛操作最终该路径终点的距离估计一定会收敛到正确值。 Bellman-Ford15. Bellman-Ford 算法在第 |V| 轮即 |V| − 1 轮之后再执行一轮对所有边进行松弛如果还能更新某个顶点的 d 值则说明图中存在从源点可达的负权环。 16. Bellman-Ford 算法可以正确处理含有负权边但不含负权环的图。 DAG 最短路径17. 在 DAG 上求最短路径时只需要按拓扑序松弛每条边一次即可得到正确结果不必像 Bellman-Ford 那样进行 |V| − 1 轮。 Dijkstra18. 如果图中存在负权边但不存在负权环Dijkstra 算法仍然能保证得到正确的单源最短路径。 19. Dijkstra 算法使用斐波那契堆代替二叉堆实现优先队列时总时间复杂度从 O((|V| |E|) log |V|) 改进为 O(|V| log |V| |E|)主要原因是 DECREASE-KEY 操作的摊还时间从 O(log |V|) 降为 O(1)。 Floyd-Warshall20. Floyd-Warshall 算法的时间复杂度为 O(|V|^3)其基本思想是每次允许使用一个新顶点作为中间顶点来逐步改进最短路径估计。 三、答案与解析单项选择题答案题号答案简要解析1B邻接矩阵大小为2B邻接矩阵适合稠密图3B完全图4B白色未发现灰色已发现但邻接表未探索完黑色探索完毕。5C初始化 O(6CBFS 用队列Queue实现逐层遍历。7Ad[v] 是发现时刻discovery timef[v] 是完成时刻finishing time。8B灰色表示 v 是 u 的祖先故为返回边back edge。9BTheorem 22.10无向图 DFS 中只有树边和返回边。10B白路径定理v 是 u 的后代 ⟺ 在 u.d 时刻存在全白路径 u→…→v。11C拓扑排序要求有向无环图DAG。12B生成树是无环连通子图连接所有顶点边数为13C边 (u,v) 跨越割 (X,Y) 当两端分别落在 X 和 Y 中。14B尊重意味着 A 中没有边跨越该割。15B轻边是跨越某个割的所有边中权值最小的边。16BTheorem 23.1轻边 (u,v) 对 A 是安全的可安全加入。17B加入 (u,v) 产生环删去环上另一条跨割边 (x,y)得新 MST T’。18BCorollary 23.2连接不同分量的轻边对 A 安全。19BKruskal 按边权递增序考察不形成环则加入。20C并查集Union-Find通过 Find 检测同分量Union 合并。21BPrim 中 A 始终成树Kruskal 中 A 是森林。22C23A稀疏时 Kruskal O(24B权值互异时 MST 唯一。25AA ∅割 ({u}, V−{u}) 尊重 A(u,v) 是轻边由 Thm 23.1 得 (u,v) 安全属于某棵 MST。26BLemma 24.1最短路径的子路径也是最短路径。27B无负权环时最短路径是简单路径最多28A松弛操作若 d[u] w(u,v) d[v] 则更新 d[v]。29A三角不等式 δ(s,v) ≤ δ(s,u) w(u,v)。30C收敛性质d[v] 在松弛后达到正确值且不再改变。31B最短路径最多32B第33A拓扑排序 O(34BDijkstra 要求所有边权非负负权边会导致已加入 S 的顶点可能不是真正最短路。35B循环不变式对已加入集合 S 的顶点 v有 d[v] δ(s,v)。36B斐波那契堆 DECREASE-KEY 摊还 O(1)二叉堆 O(log37AFloyd-Warshalld^{(k)}{ij} min(d^{(k-1)}{ij}, d^{(k-1)}{ik} d^{(k-1)}{kj})。判断题答案题号答案解析1√稠密图时邻接矩阵的 O(2×对于稀疏图邻接矩阵的 O(3√这是 BFS 正确性证明中 Lemma 8.3 的结论。4√Theorem 22.10无向图 DFS 中每条边非树边即返回边。5√按 f[v] 递减顺序输出顶点即可得到拓扑排序。6×7√所有边权互异时 MST 唯一MST Property 2 的推论。8√先 Find(u) 和 Find(v) 判断是否同分量若不同则 Union 合并。9√key[u] 是 u 到当前 MST 集合 U V − Q 的最小边权。10√Kruskal 和 Prim 都基于 Corollary 23.2而该推论由 Theorem 23.1 保证。11√可由 Theorem 23.1 取 A∅、割 ({u}, V−{u}) 证明。12√从 s 到 v 的最短路径不会比先经最短路到 u 再走 (u,v) 更长。13√Lemma 24.11d[v] ≥ δ(s,v) 始终成立且一旦达到正确值不再改变。14√Lemma 24.15按路径顺序松弛可插入其他操作终点 d 最终正确。15√第16√Bellman-Ford 支持负权边只要无负权环就能正确求解。17√DAG 无环拓扑序已消除顺序依赖每条边松弛一次即可Theorem 24.5。18×Dijkstra 依赖非负权边保证贪心正确性。负权边会导致已加入 S 的顶点被后续更短路径推翻。19√二叉堆 DECREASE-KEY O(log n)斐波那契堆摊还 O(1)。20√Floyd-Warshall 的三重循环结构决定 O(