# 1. 排序算法综合比较表中快排/归并/堆排/插入/计数/基数/桶排序在时间（最好/平均/最坏）、空间、稳定性、原地性、并行友好性上的取舍 A 插入排序的平均复杂度是 O(n log n) B 堆排序稳定且原地 C 计数排序适用于值域很大的数据 D 归并排序稳定但需 O(n) 辅助空间，快排原地但最坏 O(n²) ✓ 正确答案
# 2. DFS 的递归与迭代实现中迭代版需要显式栈且入栈顺序影响遍历顺序，递归版在深链图（10^5 层）上的栈溢出如何规避？ A 迭代 DFS 用显式栈避免递归栈溢出，但入栈顺序影响遍历顺序 ✓ 正确答案 B 递归 DFS 的栈在堆上，深度不受限 C 迭代 DFS 的遍历顺序与递归完全一致，与入栈顺序无关 D 深链图应该用 BFS 而非显式栈
# 3. 线性时间选择（Median of Medians）中按 5 个一组分组取中位数能保证至少 3n/10 个元素在 pivot 两侧，最坏 O(n) 递推式如何解？ A 5 个一组能保证每侧至少 3n/10 个元素，递推式 T(n)=T(n/5)+T(7n/10)+O(n) 解为 O(n) ✓ 正确答案 B 3 个一组即可保证线性时间 C 该算法无法保证最坏情况线性 D 递推式中 1/5+7/10=1，不收敛
# 4. 有向图判环的 DFS 三色标记法中为什么 gray 节点再被访问说明有环，与拓扑排序 Kahn 算法的对比？ A DFS 中再次遇到 gray 节点说明存在环 ✓ 正确答案 B 再次遇到 black 节点说明存在环 C 三色标记法无法用于有向图 D Kahn 算法也依赖 DFS 栈
# 5. Introsort 的退化防御中递归深度超过 2·log2(n) 就切换到堆排序，三取样中位数如何进一步降低退化概率？ A 递归深度超过 2·log2(n) 时切换堆排序，防御快排退化到 O(n²) ✓ 正确答案 B Introsort 完全不用堆排序 C 三取样中位数会增加最坏复杂度 D Introsort 的最坏复杂度是 O(n²)
# 6. 拓扑排序的应用中编译依赖与任务编排中如何检测循环依赖，Kahn 算法删除入度为零节点的过程？ A 拓扑排序适用于任意有向图 B Kahn 算法需要 DFS 栈 C 反复删除入度为零的节点，若最终节点数不足则存在环 ✓ 正确答案 D 入度为零的节点一定只有一个
# 7. AOE 网的关键路径中先拓扑排序求事件最早发生时间 ve、再逆拓扑求最迟发生时间 vl，活动松弛量 l-e=0 的关键活动如何确定，多条关键路径并存时总工期如何取，整体复杂度 O(V+E)？ A 关键路径一定唯一 B 关键活动是指持续时间最长的活动 C ve 按逆拓扑序计算 D 关键活动是松弛量 l-e=0 的活动，总工期为汇点最早时间 ve ✓ 正确答案
# 8. 邻接表 BFS 的复杂度中为什么每个顶点入队一次、每条边被扫描一次，总时间 O(V+E)，空间 O(V) 与队列容量上界的关系？ A 每个顶点可能入队多次，总时间 O(V²) B 每个顶点入队一次、每条边扫描一次，总时间 O(V+E)，空间 O(V) ✓ 正确答案 C 空间复杂度为 O(V+E) D 队列容量上界可以超过 V
# 9. 计数排序与桶排序的原理及适用条件中数据范围小且已知时 O(n+k)，桶排序在均匀分布下期望 O(n) A 计数排序适用于任意大数据 B 计数排序在值域小且已知时 O(n+k)，桶排序在均匀分布下期望 O(n) ✓ 正确答案 C 桶排序最坏情况也是 O(n) D 计数排序是不稳定的
# 10. Kahn 拓扑排序中为什么不断删除入度为零的节点能处理完整个 DAG，处理完后仍有剩余节点即说明存在环？ A Kahn 算法只能判断是否有环，不能求拓扑序 B 无环图也可能中途无入度为零的节点 C 剩余节点入度都大于 0 说明无环 D DAG 必有入度为零的节点，反复删除可处理完；仍有剩余即存在环 ✓ 正确答案
# 11. Kosaraju 算法为什么需要第二次在反图上按完成时间逆序 DFS，为什么第一次 DFS 的结束顺序能保证第二次遍历的连通分量恰为 SCC？ A 第二趟在反图上按第一趟完成时间逆序 DFS，所得连通块恰为 SCC ✓ 正确答案 B 两趟都在原图上 DFS C 第一趟即可单独求出 SCC D 反图上的 DFS 无法区分 SCC
# 12. 邻接表与邻接矩阵的适用场景与空间/时间复杂度差异？ A 邻接矩阵空间 O(V²)、判边 O(1)，适合稠密图；邻接表空间 O(V+E)，适合稀疏图 ✓ 正确答案 B 邻接表判边是 O(1) C 邻接矩阵遍历整图是 O(V+E) D 邻接矩阵适合稀疏图
# 13. 二分图判定为什么用 BFS 染色即可，奇环与二分图的关系，染色冲突说明什么？ A 二分图判定必须用 DFS 而非 BFS B 二分图可以有奇环 C 染色冲突说明图没有环 D BFS 两色染色即可判定，染色冲突说明存在奇环，图非二分图 ✓ 正确答案
# 14. 手写图遍历时邻接表使用有哪些常见误区（重复边、方向、自环）？ A 有向图也需双向建边 B 无向图需双向建边，且 visited 应在入队时标记避免重复入队 ✓ 正确答案 C 自环在遍历时无需任何处理 D 重复边不影响遍历结果
# 15. 排序稳定性在多级排序中的工程意义中如先按年龄排再按部门排，稳定排序保证同部门内年龄有序 A 稳定排序能保证第二次排序后主要键相同元素保持次要键顺序 ✓ 正确答案 B 不稳定排序更适合多级排序 C 多级排序应从主要键开始排 D 稳定性只影响性能不影响结果
# 16. Gabow 算法与 Tarjan SCC 的对比中 Gabow 用两个栈（路径栈+辅助栈）代替 low-link 值，为什么辅助栈的弹出恰好界定一个 SCC？ A Gabow 用路径栈 + 辅助栈界定 SCC，原理与 Tarjan 的 low 判定等价 ✓ 正确答案 B Gabow 不需要任何栈 C 辅助栈的弹出区间与 SCC 无关 D Tarjan 无法识别 SCC
# 17. Tarjan 求强连通分量的 low-link 中 low[v]=min(dfn[v], 树边 low[to], 回边 dfn[to]) 能正确识别 SCC，根的判定为何特殊？ A low 值只由 dfn 决定 B 树边应取 dfn[to] 而非 low[to] C 每个节点都是 SCC 根 D low[v]=min(dfn[v], 树边 low[to], 回边 dfn[to])，low==dfn 的节点是 SCC 根 ✓ 正确答案
# 18. 图建模中邻接表在稀疏图/社交网络等场景的应用？ A 邻接表空间 O(V+E)，适合稀疏图，遍历邻居 O(deg(v)) ✓ 正确答案 B 邻接表空间 O(V²) C 社交网络是稠密图，适合邻接矩阵 D 邻接表遍历任意顶点邻居需 O(V)
# 19. 邻接表的数据结构与建图要点（头插尾插、加权边）？ A 无向图需双向建边，加权边用带 to 和 weight 的 Edge 表示 ✓ 正确答案 B 有向图也需双向建边 C 头插与尾插对遍历结果无任何影响 D 邻接表无需关注顶点下标
