# 1. 主定理（Master Theorem）三种情况的完整陈述与典型示例中 Case 1 T(n)=8T(n/2)+n² → O(n³)、Case 2 T(n)=2T(n/2)+n → O(n log n)、Case 3 T(n)=2T(n/2)+n² → O(n²)，以及正则条件的验证 A Case 2 的结论是 T(n)=Θ(n^(log_b a)·log n) ✓ 正确答案 B 三种情况都要求正则条件成立 C Case 1 要求 f(n)=Ω(n^(log_b a+ε)) D 主定理适用于所有形如 T(n)=a·T(n/b)+f(n) 的递推式，无需任何条件
# 2. 动态数组（ArrayList/vector）的均摊分析中扩容因子 2 时 push_back 的均摊 O(1) 证明（聚合法与势能法两种路径），扩容因子 1.5 的均摊代价变化 A 用聚合法看，前 n 次 push_back 的总扩容代价约 2n，故均摊 O(1) ✓ 正确答案 B 扩容发生在 size 大于 capacity 时 C 势能法要求势函数必须恒为非负下滑，且每次扩容后势能增大 D 扩容因子改为 1.5 后均摊代价变为 O(log n)
# 3. 分治算法递推式的建立与求解中归并排序 T(n)=2T(n/2)+Θ(n)、Strassen T(n)=7T(n/2)+Θ(n²)、最近点对 T(n)=2T(n/2)+Θ(n)，从递推到主定理的完整推导链 A Strassen 的 T(n)=7T(n/2)+Θ(n²) 属于主定理 Case 2 B 最近点对合并阶段是 O(n²) 的二次扫描 C 归并排序递推式 T(n)=2T(n/2)+Θ(n) 由主定理求解为 Θ(n log n) ✓ 正确答案 D 三者的递推式都可直接归为 Case 1
# 4. Akra-Bazzi 之外的递推求解中 T(n)=T(n/2)+T(n/4)+n 这类非标准递推如何用递归树与猜测代入法求渐近界？ A 每层代价按公比 1 递减，总代价为 O(n log n) B 该递推式可直接套用标准主定理三种情况求得 Ω(n²) C 递归树每层总代价为 n·(3/4)^k，几何收敛得 T(n)=O(n) ✓ 正确答案 D 代入法猜测 T(n)=O(n) 时无需调整常数即可成立
# 5. 递归与迭代实现归并排序的差异中自顶向下有 O(log n) 递归栈深，自底向上可做到 O(1) 辅助空间，递推式 T(n)=2T(n/2)+n 如何对应两者的运行代价？ A 自顶向下递归栈深为 O(n)，因为递归树有 n 个叶子 B 自底向上每轮子数组长度固定且每轮代价为 O(n log n) C 自底向上可避免递归调用栈，从而把辅助空间降到 O(1)（或 O(n) 辅助数组） ✓ 正确答案 D 两者总共的合并代价不同，递推式只适用于递归版本
# 6. 递推式的求解方法中代入法、递归树、主定理各自的适用条件与局限，如何证明大 O 上界？ A 主定理适用于所有形式的递推式，包括子问题规模不等的情形 B 主定理要求 f(n) 与 n^(log_b a) 必须相差至少一个指数因子 C 递归树法只能用于求解，不能用于猜测渐近界 D 代入法需先猜测上界，再用数学归纳选择足够大的常数 c 吸收余项来证明 O 上界 ✓ 正确答案
# 7. 均摊分析的三种方法中聚合分析、记账法（核算法）、势能法的原理与典型例子（动态数组扩容）？ A 三种方法都需要显式设计势函数或存款，缺一不可 B 势能法无需势函数，只需保证总代价与操作次数成正比 C 记账法要求势函数在任意时刻非负 D 聚合法把 n 次操作看作整体求总代价再均摊，记账法和势能法基于逐次操作分配均摊代价 ✓ 正确答案
# 8. T(n)=2T(n/2)+n 这类递推式如何用递归树展开求精确解，主定理不适用的边界条件有哪些？ A 递归树展开展开得总代价 = n·log₂n + n，即 Θ(n log n) ✓ 正确答案 B 主定理在 f(n) 与 n^(log_b a) 只差对数因子时可直接套用 Case 1 C 递归树每层代价为 n/2，共 log n 层，故总代价 n log n/2 D 子问题规模不等（如 T(n)=T(n/3)+T(2n/3)+n）时标准主定理仍适用
# 9. 均摊分析中的势能函数如何构造，以二进制计数器为例，说明每次 increment 均摊 O(1) 的势能推导（势取 1 的个数）？ A 势取 1 的个数时，第 i 次 increment 势能变化为 2−t_i，均摊代价恰为常数 2 ✓ 正确答案 B 势函数取 0 的个数更合适，因为翻转时 0 变 1 会释放势能 C 单次 increment 最坏 O(k)，故均摊也必然是 O(k) D 势能法要求势函数必须单调递增才有效
# 10. 均摊分析中势能函数的选择启发式中势能常取数据结构的规模对数或未完成操作数，选取错误会怎样？ A 势能应代表数据结构中已积累、未来可能付出的潜在工作量，且须非负并随操作合理升降 ✓ 正确答案 B 势函数必须取数据结构的规模对数，否则均摊分析必然错误 C 势函数只要求非负，与操作的实际代价无关 D 势能越大越好，可以任意设定以压低均摊界
# 11. 主定理 case1 与 case3 的边界中当 f(n) 与 n^(log_b a) 只差对数因子时主定理为何失效，需要用什么技巧？ A f(n)=n^(log_b a)·log n 时 Case 1 仍适用，因为 log n 比 n^ε 增长快 B 主定理对任何 f(n) 都能给出正确结果，不存在失效 C 该情形可通过递归树或 Case 2 的推广形式求解为 Θ(n^(log_b a)·log² n) ✓ 正确答案 D 对数因子差距时 Case 3 仍适用，结论为 Θ(n·log n)
# 12. Splay 树的单次操作最坏情况中为什么单次访问可能花费 O(n)（如反复访问叶子），但 m 次操作的总代价仍是 O((m+n)log n)（摊还）？ A 单次访问最坏 O(n)，因此 m 次总代价最坏也是 O(mn) B 单次访问最坏 O(n)，但 m 次总代价摊还为 O((m+n)log n)，因为势能账本约束了总代价 ✓ 正确答案 C Splay 树每次访问都是 O(log n)，不存在最坏 O(n) D 摊还上界要求每次操作的实际代价都必须是 O(log n)
# 13. Akra-Bazzi 定理对主定理的推广中处理 T(n)=T(n/3)+T(2n/3)+n 等子问题规模不等的情形，求解 p 使得 Σa_i·b_i^p=1 的步骤 A Akra-Bazzi 只适用于子问题规模相等的递推式 B 该递推式可用标准主定理直接求解为 Θ(n²) C p 应满足 Σ a_i·b_i^{-p}=1 D 需解 (1/3)^p+(2/3)^p=1，得 p=1，故 T(n)=Θ(n log n) ✓ 正确答案
# 14. Splay 树的势能函数设计中Φ(T)=Σ_{x∈T} r(x)=Σ log(size(x)) 如何保证 m 次操作总代价 O((m+n)log n)，Access Lemma 的证明思路 A 势能取 Σ log(size(x)) 后，单次访问摊还代价为 O(log n)，m 次总代价 O((m+n)log n) ✓ 正确答案 B Access Lemma 证明依赖 zig-zig 旋转每一次都增加势能 O(n) C 势能取 Σ log(size(x)) 后，单次访问的最坏代价也降为 O(log n) D 证明中每步的摊还代价无法抵消，需要额外假设
# 15. 聚合法（Aggregate Method）vs 记账法（Accounting Method）vs 势能法（Potential Method）的适用场景对比中何时选哪种方法最简洁，势能函数选取的启发式原则 A 三种方法结果完全相同，任何一道题选用任一种都最简洁 B 势能法只能用于动态数组，不能用于 Splay 树 C 聚合法最适合总代价易求和的场景，记账法适合需区分操作类型，势能法适合需严格证明或势能自然存在的场景 ✓ 正确答案 D 记账法不需要维护存款非负的条件
# 16. 势能法的应用中二进制计数器、Splay 树等场景如何选取势函数，均摊界如何保证？ A 势能法要求势函数必须单调递减，否则均摊界失效 B 二进制计数器取 1 的个数为势函数，Splay 树取 Σ log(size(x))，二者均摊界均由"总实际代价≤总摊还代价−最终势能"保证 ✓ 正确答案 C 二进制计数器无法用势能法分析，只能用聚合法 D Splay 树的势函数取节点个数即可，无需取对数
# 17. 主定理的三个分支（case1/2/3）分别适用于哪些增长形态，多项式大于/小于的判定细节？ A 三个分支均要求 f(n) 与 n^(log_b a) 相差多项式因子，仅差对数因子时落入 Case 2 推广 ✓ 正确答案 B Case 1 适用于 f(n) 快于 n^(log_b a)，Case 3 适用于 f(n) 慢于 n^(log_b a) C Case 2 只允许 f(n)=Θ(n^c)，不允许带 log 因子 D Case 3 无需任何正则条件即可成立
# 18. 主定理中 f(n) 与 n^(log_b a) 的多项式大小比较中当两者同阶（case2）时解的形式？ A Case 2 要求 f(n) 与 n^c 相差多项式因子 B Case 2 的解始终是 Θ(n^c)，与 log 因子无关 C 当 f(n)=Θ(n^c·log^k n) 时，解为 T(n)=Θ(n^c·log^(k+1) n) ✓ 正确答案 D Case 2 只在 k=0 时成立，k>0 需用 Case 1
