# 1. 字符串排序在 word RAM 下达到 O(n · √log log n) 而非 Ω(n log n) 的原因。 A 比较下界适用于 word RAM 字符串排序 B 任何模型下字符串排序都必须 Ω(n log n) C word RAM 下字符串可用位运算/基数排序突破比较模型 Ω(n log n) ✓ 正确答案 D 字符串排序无法并行处理字符
# 2. 用会计法（banking method）证明动态数组 push_back 的 O(1) 平摊复杂度。 A 每次 push 预存 credit 覆盖扩容成本，平摊 O(1) ✓ 正确答案 B 扩容成本无法被平摊 C push_back 最坏是 O(n²) D 会计法不保证 credit 非负
# 3. 并查集的优化中按秩合并与路径压缩的联合时间复杂度为何近似 O(α(n))？ A 路径压缩单独就使树高 O(log n) B 按秩合并+路径压缩使 m 次操作 O(m·α(n))，α 为 Ackermann 反函数 ✓ 正确答案 C 并查集最坏 O(n²) D α(n) 随 n 快速增长
# 4. Karp 17 个平摊数据结构的方法差异在栈、队列、双端队列、计数器、双向计数器、动态树上的具体体现。 A 平摊分析只能用于栈 B 动态树需要 O(n) 平摊 C 计数器、栈、动态树都可用势能/会计法证明平摊 O(1) 或 O(log n) ✓ 正确答案 D 双端队列无法平摊
# 5. Paging 的 marking algorithm（FWF）与 LRU 的等价性证明？ A FWF 淘汰最近访问的页 B FWF 与 LRU 对同一访问序列缺失相同，竞争比相同 ✓ 正确答案 C 两者竞争比不同 D FWF 不标记页面
# 6. Paging 问题的 LRU 与 FIFO 的竞争比分析与 Belady's MIN（OPT）？ A LRU 竞争比为 1 B OPT 淘汰未来最远页，LRU/FIFO 都是 k-competitive ✓ 正确答案 C FIFO 比 OPT 更优 D OPT 是在线算法
# 7. Paging 问题的 LRU、FIFO、LFU 的竞争比分析中 FIFO 4-competitive、LRU k-competitive？ A LFU 达到最优竞争比 B LRU 与 FIFO 都是 k-competitive，LFU 竞争比无界 ✓ 正确答案 C FIFO 竞争比最优为 1 D LRU 竞争比小于 k
# 8. Secretary Problem 的 1/e 停止规则与最优策略的工程语义？ A 跳过前 n/e 个观察，之后选第一个超过记录最大者，成功概率 1/e ✓ 正确答案 B 应选第一个到达者 C 最优概率是 1/2 D 策略与 n 无关
# 9. Secretary Problem 的动态规划与 indicator variable 的最优性证明？ A 成功概率为 100% B DP 显示最优策略是均匀随机 C DP 证明最优为阈值策略，indicator 变量求选中概率得 1/e ✓ 正确答案 D indicator 变量无法用于证明
# 10. Word RAM 模型（字长 w=Θ(log n)）下排序下界 Ω(n log n) 是否仍成立，决策树与可计算函数族的边界。 A 比较下界不适用于 word RAM，但信息论码长下界在小字长下仍存在 ✓ 正确答案 B 任何模型排序都 Ω(n log n) C word RAM 字长越大排序越慢 D 决策树下界适用于 word RAM
# 11. Bit RAM 下 rank/select 操作 O(1) 答案为何依赖表大小 N=2^w 时的预计算？ A 需要块划分 + 基于 2^w 的预计算查表 ✓ 正确答案 B 无需预计算即可 O(1) C 表大小与块大小无关 D rank/select 只能 O(log n)
# 12. Karmarkar 线性规划内点法的平滑复杂度在 ILP benchmark 上的实测分布。 A 内点法只能解整数规划 B 内点法最坏情况下指数 C 理论多项式但常数大，实测在 ILP 松弛上迭代次数少、分布集中 ✓ 正确答案 D 平滑复杂度与实测无关
# 13. Range Tree（线段树的二维扩展）的构造与 O(log² n) 查询？ A x 维线段树每节点内嵌 y 维树，查询 O(log² n) ✓ 正确答案 B 空间 O(n) 且查询 O(log n) C 只能做一维查询 D 构造 O(n²)
# 14. Secretary Problem 在广告投放、招聘、股票择时、Job scheduling 的工程应用？ A 广告、招聘、择时等不可回退决策都用“先学习后阈值选择”思路 ✓ 正确答案 B 只适用于招聘 C 工程中必须知道 n 且固定 D 阈值策略与探索无关
# 15. Z-function 的字符串周期判定、最小表示法的 Duval 算法的工程取舍？ A Z 可用 Z[k]≥n−k 判周期，Duval 线性求最小旋转，都确定性无碰撞 ✓ 正确答案 B Z 无法判周期 C Duval 需要哈希 D 两者都 O(n²)
# 16. fusion tree 在 64-bit 字长下达到 O(log n / log w) 搜索的具体实现细节。 A 每节点只有 2 分支 B 用 sketch 位压缩使每节点 w 分支，树深 O(log n/log w) ✓ 正确答案 C 搜索复杂度 O(log n) D 无法用位并行
# 17. van Emde Boas 树在 Word RAM 下达到 O(log log u) 的下界来源中探针 vs 哈希 vs 字典树。 A vEB 与字典树深度相同 B vEB 复杂度是 O(log u) C 递归分簇使 u 逐层开方，复杂度 O(log log u)，达探针下界 ✓ 正确答案 D vEB 用哈希获得最坏 O(1)
# 18. 线段树的懒标记（Lazy Propagation）中区间更新/查询的复杂度与实现要点？ A 懒标记使更新变 O(n) B 懒标记把区间更新延迟到节点层，更新/查询均 O(log n) ✓ 正确答案 C 更新时无需判断完全覆盖 D 懒标记无法做区间查询
# 19. 树状数组与线段树的对比中哪些操作（区间最值/区间修改）只能用线段树？ A 线段树不支持区间求和 B 树状数组支持区间最值 C 两者功能完全等价 D 区间最值与区间修改（懒标记）通常只能用线段树 ✓ 正确答案
# 20. Manacher 算法在线性时间内求奇偶回文半径与 palindromic tree 的工程取舍？ A Manacher 求半径轻量，PAM 支持回文子串统计但实现复杂 ✓ 正确答案 B Manacher 无法求回文半径 C PAM 比 Manacher 更简单 D 两者都只能求最长回文
# 21. Suffix Automaton（SAM）的 right context、link、len 三数组与状态上界 2n-1 的工程语义？ A 状态含 len、link、转移，状态上界 2n−1，内存 O(n) ✓ 正确答案 B 状态数随 n 指数增长 C len 记录出现次数 D link 指向最长前缀状态
# 22. 回文树 Eertree 的两个根（奇偶）的 addChar 与状态上界 O(n) 的工程价值？ A 无法在线构建 B 回文树状态数可到 n² C 只有一个根 D 奇偶双根统一构建，状态数 ≤n，可在线统计回文 ✓ 正确答案
# 23. 组合类 labelled 与 unlabelled 的 EGF 差异在集合、循环、序列操作上的体现。 A 集合操作都是 exp B 两者都用 EGF C labelled 用 EGF（集合=exp），unlabelled 用 OGF（集合=MSET） ✓ 正确答案 D labelled 与 unlabelled 计数相同
# 24. 设计 black-box benchmark，验证外部排序库在不知道输入分布时的最坏退化。 A 只需测随机输入 B 用随机/逆序/重复/偏序等多分布+规模缩放发现最坏退化 ✓ 正确答案 C 退化与输入分布无关 D 无法 black-box 检测退化
# 25. AC0 电路只能识别 PARITY 之外的常数深度语言中 Furst-Saxe-Sipser 证明思路。 A Furst-Saxe-Sipser 证明 PARITY∈AC0 B PARITY 可用常数深度电路计算 C AC0 能算任意模函数 D 随机限制把 AC0 电路化简为常数函数，而 PARITY 保持结构，故 PARITY∉AC0 ✓ 正确答案
# 26. Belady's MIN（OPT）算法中 evict the page farthest in future 的 oracle 上界？ A OPT 缺失数最多 B OPT 是贪心在线算法 C OPT 淘汰未来最远页，是离线最优，作为在线算法下界 ✓ 正确答案 D OPT 无 oracle 上界
# 27. Conservative Paging 与 Aequo-Optimal 算法在确定性 vs 随机化？ A 确定性竞争比 ln k B 确定性 conservative 竞争比 k，随机化下界约 H_k（ln k），随机化更优 ✓ 正确答案 C 随机化竞争比等于 k D 随机化无法改善竞争比
# 28. Generalized Secretary Problem 中 rank-r selection 与 matroid secretary 的扩展？ A 只选单个最优 B 扩展为选满足 matroid 约束的最优集合，用采样+阈值算法 ✓ 正确答案 C 无约束也能选 D 竞争比恒为 1
# 29. Important Sampling 在偏分布估计中的方差缩减工程？ A 权重 w 与分布无关 B 重要性采样总是增加方差 C 用匹配 f 的分布采样并加权，可显著降低方差 ✓ 正确答案 D 无法处理罕见事件
# 30. KD-Tree 的范围查询与最近邻中每个维度轮换切分的中位点选择？ A 最近邻查询无需剪枝 B 中位点选择使树不可平衡 C 按轮换维度取中位点切分，范围/最近邻用空间剪枝，平均高效 ✓ 正确答案 D KD-Tree 最适合高维
# 31. Link-Cut Tree 的 access、splay、expose 操作在动态树问题？ A access 与路径查询无关 B LCT 只能静态树 C access 打通路径成 splay，link/cut/路径查询均 O(log n) 平摊 ✓ 正确答案 D splay 使复杂度 O(n)
# 32. Lyndon 分解与最小表示法（Duval 算法）在循环串匹配的工程价值？ A Duval 算法 O(n²) B 最小表示无法用于循环匹配 C 循环同构串的最小表示相同，可规范化后做相等判定 ✓ 正确答案 D 循环匹配必须哈希
# 33. Online Bipartite Matching 的 Ranking 算法 1-1/e 竞争比的工程价值？ A 随机化无法改进在线匹配 B 竞争比 1（最优） C 贪心即可达到 1-1/e D 给右部随机 rank，到达左部匹配最高 rank 邻居，竞争比 1-1/e ✓ 正确答案
# 34. PARITY 不属于 AC0 的 Håstad 切换引理如何被用于电路下界证明。 A 切换引理与电路下界无关 B 切换引理证明 PARITY∈AC0 C 随机限制不改变电路 D 随机限制使常数深度电路可压缩，而 PARITY 保持结构，故 PARITY∉AC0 ✓ 正确答案
# 35. Pertesi 风格局部搜索的平滑分析框架如何在 k-median、k-means 上获得多项式平滑界。 A 局部搜索总能找到全局最优 B 高斯扰动后局部最优接近全局最优且收敛多项式，解释实测有效 ✓ 正确答案 C 平滑分析否定局部搜索价值 D 扰动使局部搜索失效
# 36. Pólya 枚举定理如何把等价类计数降到 cycle index polynomial 的具体例子。 A cycle index 与群无关 B 用 cycle index 代入颜色数求不等价着色数，如正方形 2 色=6 ✓ 正确答案 C 需逐类枚举所有着色 D 无法处理对称群
# 37. Ski rental randomized 算法中随机化阈值 e/(e-1) 期望 competitive ratio 的工程价值？ A 竞争比与随机化无关 B 随机化阈值竞争比为 2 C 确定性阈值优于随机化 D 随机化阈值使期望竞争比 e/(e-1)≈1.58，优于确定性 2 ✓ 正确答案
# 38. Ski rental 与 secretary problem 共同点中先验未知的最优决策时机？ A 都在未知未来下做“何时行动”的阈值决策 ✓ 正确答案 B 两者都是离线问题 C 都只用确定性策略 D 决策时机与竞争比无关
# 39. Ski rental 在云 spot instance 购买 vs 按需租用的工程应用？ A 云资源无租买权衡 B 按需=租、预留=买，未知时长用阈值/竞争比决策 ✓ 正确答案 C 阈值策略与时长无关 D 预留实例总是最优
# 40. Ski rental 的 lower bound 中任何 randomized 算法 competitive ratio ≥ 1+1/e 的工程证明？ A 确定性算法竞争比更低 B 随机化算法可达到竞争比 1 C 下界证明不存在算法 D 任何随机化算法竞争比 ≥ e/(e-1)≈1.58，随机化阈值已经最优 ✓ 正确答案
# 41. Ski rental 问题的 2-竞争比算法中购买 vs 继续租的决策边界？ A 决策边界与 B 无关 B 一开始就买竞争比 2 C 全程租竞争比 2 D 租 B 次后买，成本 ≤2OPT，竞争比 2 ✓ 正确答案
# 42. Ski rental 问题的 deterministic 2-competitive 算法中买前租天数 = 1/价格？ A 租 B 天（B=价格）后买，竞争比 2 ✓ 正确答案 B 租 1 天就买竞争比 2 C 租天数与价格无关 D 买前租天数 = 价格/2
# 43. Spielman-Teng 平滑分析框架的严格数学定义及其在 Simplex 与 k-means 上的多项式平滑复杂度推导。 A 平滑复杂度等于最坏复杂度 B 对最坏输入加扰动衡量期望复杂度，解释 Simplex/k-means 实测高效 ✓ 正确答案 C 平滑分析否定多项式算法 D 扰动不改变复杂度
# 44. TC0 与 AC0 的边界中 MAJORITY 与 PARITY 都属于 TC0（且都不属于 AC0） A TC0 与 AC0 相同 B MAJORITY∉TC0 C TC0 加阈值门，可算 MAJORITY/PARITY 等 AC0 不能算的函数 ✓ 正确答案 D PARITY∈AC0
# 45. Treap 与 Randomized BST 的期望 O(log n) 与 split/merge 工程应用？ A Treap 树高最坏 O(n) 但期望 O(log n) B 随机优先级保证期望 O(log n) 树高，split/merge 支持区间操作 ✓ 正确答案 C split/merge 是 O(n) D Treap 无法可持久化
# 46. grey-box 模型下，Differential Power Analysis 攻击 RSA 的 cache timing 侧信道工程实现路径。 A 通过功耗/时间差异关联密钥位，用多次观测差分统计提取密钥 ✓ 正确答案 B 侧信道无法提取密钥 C cache timing 与密钥无关 D 只读物理字节即可
# 47. grey-box 自动调参（autotuning）为何对 JIT 编译器有显著加速并给出实测数据。 A 用实测反馈选最优编译参数，grey-box 缩搜索空间，可带来数倍加速 ✓ 正确答案 B 固定参数总是最优 C autotuning 增加编译时间无收益 D grey-box 不需结构信息
# 48. white-box 模型下，AES 的 white-box 加密为何无法在理论上抵抗 key extraction。 A 攻击者可观察全部表与执行，key extraction 理论上不可避免 ✓ 正确答案 B white-box 保证密钥安全 C 表编码可完全抵抗逆向 D key extraction 只在没看表时发生
# 49. 为什么平滑复杂度不能直接推出 P=NP 反而成为分析工具？ A 它是最坏复杂度特例 B 平滑复杂度可以推出 P=NP C 只保证扰动后期望高效，不覆盖最坏，故不能推出 P=NP ✓ 正确答案 D 与平均复杂度无关
# 50. 写出 OGF 与 EGF 的形式幂级数定义并证明 Catalan 数的 OGF 满足 C = 1 + z C²。 A 空树+根左右子树分解给出 C=1+zC²，解得 C_n=(1/(n+1))C(2n,n) ✓ 正确答案 B Catalan 无生成函数 C C=1-zC² D EGF 与 OGF 相同
# 51. 利用 analytic combinatorics 推导 hash collision 的 O(1/√n) 渐近式。 A 碰撞概率 ~ n²/(2m)，可用泊松/生成函数奇异分析得 O(1/√n) 类渐近 ✓ 正确答案 B 碰撞概率与 m 无关 C 生日悖论不适用 D 碰撞概率恒为 1
# 52. 区分 worst-case、average-case、smoothed complexity 在 branch-and-bound 求解器上的实测差异。 A B&B 恒为多项式 B 最坏指数、平均随机友好、平滑（扰动后）接近平均，实测远好于最坏 ✓ 正确答案 C 三种复杂度相同 D 平滑复杂度等于最坏
# 53. 在 black-box 假设下，3-SAT 的 sub-exponential 算法不可能超越指数级的下界构造。 A 3SAT 有 sub-exponential 算法 B black-box 构造 oracle 实例，证查询下界 2^Ω(n)，排除 sub-exponential ✓ 正确答案 C black-box 下界证明 P=NP D oracle 不支持 ETH
# 54. 平摊复杂度在 jemalloc、dlmalloc 的工程意义。 A 分配器合并/缓存用平摊分析保证平均 O(1) 分配 ✓ 正确答案 B 单次分配总是 O(1) C 平摊分析不适用分配器 D jemalloc 无平摊保证
# 55. 平滑分析在工业编译器 instruction scheduling 中的实际应用案例。 A 真实代码依赖图带结构，平滑分析解释启发式调度实测有效 ✓ 正确答案 B 指令调度总是多项式 C 启发式调度无理论依据 D 平滑分析与编译器无关
# 56. 持久化线段树（Persistent Segment Tree）的 path-copy 与版本控制的工程价值？ A 无法查询历史版本 B 持久化会复制整棵树 C path-copy 只复制更新路径，保留全部版本，支持区间第 k 大等 ✓ 正确答案 D path-copy 是 O(n) 更新
# 57. 构造卡型输入的 1/n 扰动族，证明其平滑复杂度从指数级降为多项式级的具体路径。 A 扰动不减复杂度 B 对卡型输入加 1/n 高斯扰动，破坏退化结构，使期望复杂度降为多项式 ✓ 正确答案 C 卡型输入不受扰动影响 D 1/n 扰动使复杂度更高
# 58. 用 Lagrange 反演求树的计数中度为 i 的节点数。 A 度 i 节点数需枚举 B Lagrange 反演无法用于树 C 用 C=zφ(C) 反演解系数，marking 得度 i 节点数闭式 ✓ 正确答案 D 反演只适用于 OGF
# 59. 用势能法（potential method）证明 splay 树 zig-zig 操作的 O(log n) 平摊界。 A splay 平摊 O(n) B 势能取树高 C 势能取秩和，旋转的秩变化被吸收，splay 平摊 O(log n) ✓ 正确答案 D 势能法无法证明 splay
# 60. 用物理法（physicist method）证明二进制计数器 increment 的 O(1) 平摊界。 A 势能取 0 的个数 B 计数器 increment 最坏 O(n) 且不平摊 C 势能取 1 的个数，增量翻转 t 位被 ΔΦ 抵消，平摊 O(1) ✓ 正确答案 D 平摊代价是 O(n²)
# 61. 用生成函数推导 Fibonacci 数的封闭公式 Binet 形式。 A Binet 公式不正确 B Fibonacci 无闭式 C 生成函数法需枚举 D F(z)=z/(1-z-z²)，部分分式展开得 Binet 公式 f_n=(φ^n-ψ^n)/√5 ✓ 正确答案
# 62. 给出 NL = coNL 的证明轮廓（Immerman-Szelepcsényi）。 A Immerman-Szelepcsényi 用非确定性计数可达节点，证明 STCON 的补在 NL ✓ 正确答案 B NL 对补不封闭 C coNL 严格大于 NL D 该定理与 STCON 无关
# 63. 设计一组覆盖 Gauss 扰动和 adversary 扰动两类输入的平滑复杂度单元测试。 A 只需测随机输入 B 只测无扰动输入 C 扰动不改变性能 D 覆盖 Gauss 扰动与 adversary 扰动，验证扰动后时间多项式、不退化 ✓ 正确答案
# 64. 设计实验对比 succinct data structure 在 bit RAM 与 word RAM 上的 cache miss 与指令数。 A 两种模型无差异 B 控制算法相同、对比 bit/word RAM 的 cache miss 与指令数，word RAM 查表更省 ✓ 正确答案 C 只测运行时间即可 D bit RAM 指令更少
# 65. 证明 L ⊆ NL ⊆ P 的关系与 Reingold 的 undirected STCON in L 的核心思想。 A 无向 STCON 不在 L B L⊆NL⊆P，Reingold 用图幂+膨胀+降维证明无向 STCON 在对数空间 ✓ 正确答案 C NL⊆L 成立 D Reingold 证明有向 STCON 在 L
# 66. 证明 STCON（s-t 连通性）是 NL 完全的，归约路径与验证者交互。 A STCON 不在 NL B 用配置图把 NL 机器编码为 s-t 路径，STCON 非确定 log 空间可判且 NL 完全 ✓ 正确答案 C 配置图是指数规模 D STCON 是 P 完全
# 67. 在线算法的竞争比中在线缓存（LRU/Belady）与在线调度问题的竞争比分析？ A 所有在线算法竞争比 1 B 缓存 LRU k-competitive、list scheduling 2-competitive，竞争比量化未知信息代价 ✓ 正确答案 C 竞争比与最优离线无关 D 在线调度竞争比无界
