# 1. CLRS 第 26 章 Ford-Fulkerson 在 BFS/DFS 增广路径选择与残留网络维护。 A 最大流和最小割没有关系 B 用 DFS 找任意增广路径一定是多项式时间 C 残留网络只需要正向边，不需要反向边 D 用 BFS 找最短增广路径即 Edmonds-Karp，O(V*E^2)，残留网络的反向边用于修正流量 ✓ 正确答案
# 2. 回滚技巧（rollback）与真持久化的区别中为什么只回退到最近版本的问题可以用栈加时间戳，省掉 O(log n) 空间？ A 真持久化只需 O(1) 空间 B 回滚也能随机访问任意版本 C 真持久化可随机访问任意历史版本，回滚只能按 LIFO 栈序回退，回滚用栈记修改点 O(1) 空间 ✓ 正确答案 D 回滚会破坏历史版本
# 3. CLRS 第 22 章 BFS/DFS 在邻接表与隐式图 (grid) 模板的工程封装。 A BFS 必须用递归实现 B BFS 用队列求无权图最短路，隐式图用方向数组+边界判断+visited 生成邻居，核心遍历骨架一致 ✓ 正确答案 C 隐式图不需要 visited 标记 D grid 图不能做 BFS
# 4. CLRS 第 28 章矩阵乘法的 Strassen 在 64×64 以上方阵的工程门槛。 A Strassen 对任何规模都优于朴素乘法 B Strassen 常数因子大、数值稳定性差，需在较大矩阵（如 64×64 以上）才划算，且常与朴素/分块乘法结合 ✓ 正确答案 C Strassen 数值稳定性极好，适合所有矩阵 D Strassen 复杂度是 O(n^3)
# 5. CLRS 第 17 章摊还分析在动态数组、splay 树、Fibonacci 堆的工程化势能函数选择。 A 势能函数必须实际存储在数据结构中 B 动态数组用容量差、splay 用 Σlog(size)、Fibonacci 堆用标记节点数，都让昂贵操作被势能抵消 ✓ 正确答案 C 三种结构用同一个势能函数 D 摊还分析与实际操作无关
# 6. CLRS 理论与竞赛模板的差距中理论复杂度分析如何指导实际常数优化？ A 常数优化与理论无关，可以完全忽略复杂度 B 理论最优算法一定竞赛最快 C 理论大 O 忽略常数、面向最坏情况，理论指导选算法、常数优化指导实现方式 ✓ 正确答案 D 竞赛不需要考虑缓存局部性
# 7. 可持久化的本质与路径复制中修改一个节点为何要重建 O(log n) 个新节点，旧版本为何不受影响？ A 修改一个节点只需复制该节点本身 B 每次修改沿根到叶路径复制 O(log n) 个新节点，旧节点不变，未修改子树被新旧版本共享 ✓ 正确答案 C 旧版本会被新版本覆盖破坏 D 可持久化需要复制整棵树
# 8. 可持久化数组的实现中如何用可持久化线段树模拟任意下标数组的历史版本，单次修改的复杂度与空间？ A 可持久化数组不能按下标查询 B 单点修改需要 O(n) 空间 C 可持久化数组只能查询最新版本 D 用可持久化线段树以下标为叶，单点修改路径复制 O(log n) 时间与空间，历史根形成版本栈 ✓ 正确答案
# 9. KACTL 模板的工程化取舍中头文件的常数优化（静态数组、位运算）与可读性的平衡？ A KACTL 完全放弃可读性，不写任何注释 B KACTL 用静态数组、位运算、全局变量追求常数与简洁，同时用注释与规范命名兼顾可读性 ✓ 正确答案 C KACTL 优先使用动态分配与面向对象封装 D KACTL 不考虑缓存局部性
# 10. 可持久化 DSU 的实现细节中为什么按秩合并比路径压缩更适合可持久化，路径压缩破坏历史结构的原理？ A 按秩合并不保证树高有界 B 路径压缩非常适合可持久化 C 可持久化 DSU 直接复制整个数组即可 D 路径压缩会原地修改大量父指针破坏历史共享，故可持久化 DSU 用按秩合并+可持久化数组存父指针与秩 ✓ 正确答案
# 11. CLRS 第 24 章 Bellman-Ford 在负权环检测的 early termination 优化。 A Bellman-Ford 不支持负权边 B early termination 会漏掉负权环 C 某轮无松弛即收敛可提前终止，但负权环检测仍需跑满 n 轮判断是否还能松弛 ✓ 正确答案 D 负权环检测只需跑 n-1 轮
# 12. CLRS 第 21 章不相交集 (DSU) 在按秩合并 + 路径压缩的工业实现差异。 A 工业 DSU 不用按秩合并 B 工业实现必须用递归 find C 路径压缩会让 DSU 复杂度变成 O(n^2) D 工业实现用数组存 parent/rank、迭代 find 压缩路径，与理论的路径压缩+按秩合并算法一致但常数更小 ✓ 正确答案
# 13. CLRS 第 23 章 MST 的 cut property 在工程实现中替换边的判定逻辑。 A Prim 必须用并查集 B Kruskal 不需要排序边 C cut property 只适用于带负权图 D cut property 保证割中最小权边在某个 MST 中，Kruskal 用并查集判环、Prim 用优先队列取最小横切边 ✓ 正确答案
# 14. CLRS 第 25 章 Floyd-Warshall 的位运算优化 (Roy-Warshall) 在传递闭包的工程取舍。 A bitset 优化复杂度是 O(n^2) B 位运算优化会改变传递闭包结果 C 用 bitset 把每行向量化，布尔转移变位运算，复杂度从 O(n^3) 降到 O(n^3/word) ✓ 正确答案 D 传递闭包只能用 BFS 求
# 15. CLRS 第 29 章线性规划单纯形法在工业求解器 (GLPK、COIN-OR) 的工程实现差异。 A 工业求解器不做任何数值处理 B 工业求解器直接照搬教科书实现即可 C 单纯形法最坏情况也是多项式 D 工业求解器用稀疏矩阵、revised simplex、预求解、选主元与扰动处理数值与退化，能处理大规模问题 ✓ 正确答案
# 16. KACTL Fenwick 树 (Binary Indexed Tree) 的 1-indexed 与 0-indexed 在不同题目模板的统一封装。 A BIT 不支持前缀和查询 B BIT 天然支持 0-indexed，无需偏移 C lowbit 对 0 也有定义 D BIT 必须 1-indexed（lowbit 定义），统一封装可对外 0-indexed 内部偏移 +1 ✓ 正确答案
# 17. KACTL Convex Hull Trick 的 Li Chao Tree 与 deque 版本在单调斜率/任意斜率的工程取舍。 A Li Chao Tree 只能处理单调斜率 B deque 版本支持任意斜率插入 C 单调斜率用 deque 维护凸壳 O(1) 摊还，任意斜率/在线插入用 Li Chao Tree O(log C) ✓ 正确答案 D 两种实现复杂度相同且实现难度相同
# 18. KACTL Dinic 的当前弧优化在稠密图与稀疏图的常数因子差异。 A 当前弧会把 Dinic 复杂度降到 O(VE) B 当前弧优化只对稀疏图有用 C 当前弧记录每个节点 DFS 边进度，跳过已饱和边，稠密图受益显著、稀疏图受益较小 ✓ 正确答案 D 当前弧优化会改变最大流结果
# 19. KACTL HashMap 头文件中 hash_combine 64-bit splitmix64 随机种子与 128-bit 乘法 hash 的工程实现取舍。 A 哈希函数越简单越好，不必考虑碰撞 B splitmix64 用随机种子充分混合输入抗碰撞，128-bit 乘法 hash 取高 64 位保证均匀，二者都旨在均匀且抗构造 ✓ 正确答案 C 随机种子会降低哈希速度且无安全收益 D 128-bit 乘法 hash 的结果一定唯一
# 20. KACTL Segment Tree 的 push_down 与 query 顺序在 lazy 标记冲突的边界处理。 A push_down 应在返回后执行 B query 不需要 push_down C update/query 递归前需先 push_down 下传懒标记，返回后 push_up，多标记需定义组合优先级（如赋值覆盖加） ✓ 正确答案 D 懒标记组合顺序无关紧要
# 21. KACTL Sparse Table 在 2D 区间查询的 O(1) 模板与位运算 shift 依赖。 A 2D 稀疏表用 4 维 (k,l,i,j) 覆盖子矩形，4 个重叠子矩形 O(1) 查询，依赖 log2 与位移且要求幂等操作 ✓ 正确答案 B 2D 稀疏表查询是 O(n) C 稀疏表支持区间更新 D 稀疏表只支持可逆操作
# 22. KACTL Treap 的 split/merge 在 implicit key 与 explicit key 模式下的实现差异。 A Treap 不能做区间操作 B 两种模式分裂依据相同 C implicit key 模式按键值分裂 D explicit key 按键值分裂作有序集合，implicit key 按子树大小分裂实现序列，两者差异仅在分裂依据 ✓ 正确答案
# 23. KACTL 头文件的 #pragma once 与 namespace 风格在团队代码库的工程取舍。 A namespace 在团队库中可有可无 B #pragma once 是标准 C++ 指令 C #pragma once 简洁但非标准，namespace 隔离符号避免冲突，团队库偏向规范与隔离、竞赛模板偏向简洁 ✓ 正确答案 D include guard 比 #pragma once 更简洁
