# 1. Hopcroft-Karp 在二分图上的 BFS 分层、DFS 阻塞与时间复杂度 O(E√V) 的推导如何走通？ A 它只使用 BFS 而不使用 DFS，复杂度为 O(E log V) B BFS 分层图可以随意复用在后续轮次中不用重建 C 它的最坏复杂度是 O(VE)，与朴素增广路相同 D 匹配数至少增加 √V 后，最短增广路长度必然超过 √V，从而只需 O(√V) 轮 ✓ 正确答案
# 2. Tarjan 的强连通分量算法如何在单次 DFS 内同时记录时间戳、低值、根栈与回溯？ A 算法需要两遍 DFS，第一遍排序第二遍反图上跑 B low[v] 只由树边更新，不看回边 C 当 dfn[v]==low[v] 时说明 v 及其子树已全部是一个 SCC，可弹出栈 ✓ 正确答案 D 跳出栈的条件是 low[v]==0
# 3. 后缀数组与后缀树中如何用后缀数组实现最长重复子串与模式匹配，构造算法复杂度？ A SA 无法表达 LCP 信息 B 后缀数组匹配模式复杂度是 O(n log n) C 后缀树必须用 O(n log n) 构造，无法线性完成 D 最长重复子串长度等于 height 数组的最大值 ✓ 正确答案
# 4. LSD 与 MSD 基数排序用于字符串排序中 LSD 要求稳定排序，MSD 递归切分时如何控制递归深度与内存？ A LSD 的每次低位排序必须稳定，才能保证高位权优先 ✓ 正确答案 B MSD 无需递归，是纯迭代算法 C LSD 对共享长前缀的串效率最高 D MSD 的递归深度与字符串数量成正比
# 5. 后缀数组的用途汇总中最长重复子串、不同子串计数与模式出现次数如何用 SA 加 LCP 在 O(n) 回答？ A height 数组需要用 O(n log n) 才能构造 B 最长重复子串等于 height 的最小值 C 模式出现次数无法用 SA 区间表示 D 本质不同子串数 = n(n+1)/2 − Σ height ✓ 正确答案
# 6. Burrows-Wheeler Transform 的 LF-mapping、排序后缀数组与 run-length 编码为什么能提高压缩率？ A BWT 与后缀数组无关 B BWT 是不可逆的，无法用于无损压缩 C LF-mapping 用于把文本展开成后缀数组 D BWT 把相同上下文的字符聚到相邻位置，从而利于 run-length 压缩 ✓ 正确答案
# 7. Ford-Fulkerson、Edmonds-Karp、Dinic、SAP、GAP 优化在 BFS/DFS 层数、阻塞流与 gap heuristic 上的迭代逻辑是什么？ A Ford-Fulkerson 的时间复杂度与容量无关 B Edmonds-Karp 用 DFS 找增广路 C GAP 启发式是增加层数以加速 D Dinic 用 BFS 分层后 DFS 求阻塞流，复杂度上界 O(V²E) ✓ 正确答案
# 8. Gabow SCC 算法与 Kosaraju 算法的双 DFS 路径相比时间常数与栈深？ A Kosaraju 的时间复杂度是 O(V+E) 但常数优于 Gabow B Gabow 需要两遍 DFS C Kosaraju 需要两遍 DFS 且需存储反图，常数大于单遍算法 ✓ 正确答案 D 所有 SCC 算法都必须建反图
# 9. Hopcroft-Karp 在 10^6 节点、10^7 边上为何需要 ELS、CSR、静态数组？ A 动态分配在每次 BFS 中开销可忽略 B 链表邻接表在大图上比 CSR 更快 C CSR 用 offset+adj 两个数组紧凑存储邻接表，缓存友好 ✓ 正确答案 D ELS 是确保 BFS 正确性的必要条件
# 10. KMP 的 prefix function π[i] 与 Z-function 之间的等价性和边界下标如何互换？ A π[i] 表示 s[i:] 与 s 的 LCP B Z[i] 表示 s[0..i] 的最长真 border C 两者描述同一信息，可在 O(n) 内互相转换 ✓ 正确答案 D 两者无法互相推导
# 11. LCP array 的 Kasai 算法、RMQ 区间最小查询、Phi/PLCP 数组如何服务 longest common substring？ A Kasai 算法构造 height 需要 O(n log n) B 任意两后缀的 LCP 等于它们之间相邻 height 的最小值 ✓ 正确答案 C 最长公共子串与 height 无关 D RMQ 无法用于 LCP 查询
# 12. Manacher 算法如何在线性时间内同时给出奇偶回文半径？请对比 DP 与滚动哈希。 A 它必须用 DP 的 O(n²) 转移 B 它利用当前最右回文右端点与对称中心复用信息，达到 O(n) ✓ 正确答案 C 它只能处理奇回文 D 它的正确性依赖哈希无碰撞
# 13. RE2、grep、ICU、Boost regex 等引擎的自动机构造、回溯、NFA 模拟在指数爆炸上的不同选择是什么？ A 所有引擎都采用 Thompson 构造 B 回溯引擎总能在最坏情况下线性完成 C 捕获组是 NFA 模拟引擎的天然特性 D NFA 模拟引擎（如 RE2）保证线性时间，避免指数回溯 ✓ 正确答案
# 14. 为什么 AC 自动机的 failure 边常使用 BFS 而非 DFS？请解释构造复杂度的差别。 A 用 BFS 可保证子节点的 failure 由已确定的父链递推，总复杂度 O(n) ✓ 正确答案 B DFS 构造 failure 的复杂度总是 O(n) C failure 指向最长前缀所在节点 D failure 边构造与遍历顺序无关
# 15. 2-SAT 的蕴含图、强连通分量、拓扑序与可行赋值如何在线性时间内求取？ A 子句 (x∨y) 只产生一条蕴含边 B x 与 ¬x 在同一 SCC 时无解，否则按拓扑序可线性赋值 ✓ 正确答案 C 2-SAT 需要指数级时间判定 D 拓扑序赋值不保证正确性
# 16. FM-Index 的 occurrence array、checkpoint、backward search 与 bitvector rank/select 如何支持子串查询？ A backward search 从 P 末字符开始用 LF 逐步扩展匹配区间 ✓ 正确答案 B occurrence 数组必须全量存储，无法压缩 C FM-Index 需要在查询时解压全文 D rank 操作用于构建后缀数组而非查询
# 17. Kuhn-Munkres 算法的可行顶点标号、相等子图、交替树、复杂度 O(n^3) 的关键不变量？ A 交替树用于提高可行标号的值 B 可行标号要求 l(x)+l(y) ≤ w(x,y) C 相等子图中的完全匹配即全局最大权匹配 ✓ 正确答案 D KM 复杂度为 O(n²)
# 18. Trie 与 Ternary Search Trie 中字符集大时的存储优化与查找性能对比？ A Trie 在大字符集下比 TST 更省内存 B Trie 每节点固定 3 个指针 C TST 查找时间与字符集大小成正比 D TST 每节点 3 个指针，用字符比较换空间，适合大字符集 ✓ 正确答案
# 19. Rabin-Karp 滚动哈希中哈希碰撞的概率分析与多重哈希防御？ A 单模数越大碰撞概率越高 B 滚动哈希更新必须 O(k) C 碰撞不影响正确性，无需处理 D 单哈希碰撞概率约为 O(k/M)，可加多个独立模数降低 ✓ 正确答案
# 20. 双哈希与生日悖论中单个 64 位哈希在 10 亿量级输入下碰撞概率不可忽略，双哈希如何把概率压到可忽略？ A 64 位哈希在 10^9 输入下碰撞概率约 n²/2/2^64，不可忽略 ✓ 正确答案 B 双哈希把碰撞概率提高到单哈希的平方 C 生日悖论与哈希无关 D 64 位哈希在任何规模下碰撞概率都为 0
# 21. 正则表达式到 NFA、ε-NFA、DFA 的 Thompson 构造与子集构造在什么规模下必须切分或状态压缩？ A ε-NFA 比 DFA 状态更少所以总优先构建 B Thompson 构造总是产生指数状态 C 子集构造可能使 DFA 状态数达到 2^|Q|，规模大时需切分或改 NFA 模拟 ✓ 正确答案 D DFA 状态数不会超过 NFA 状态数
# 22. 流式字符串匹配中固定 sliding window 与动态字典更新为何常使用滚动哈希 + 候选集？ A 滚动哈希每次滑动都需重算整个窗口 B 滚动哈希让窗口滑动时 O(1) 更新，候选集只对同哈希模式校验 ✓ 正确答案 C 候选集必须包含字典中所有模式 D 动态字典更新会导致哈希失效
# 23. 给出 KMP 预处理的最坏情况下界，并对比 Boyer-Moore 坏字符/好后缀规则在英文/二进制模式上的实际胜率。 A KMP 预处理下界是 O(n) B BM 在英文大字符集上靠坏字符跳跃常比 KMP 快，但在二进制小字符集上优势减弱 ✓ 正确答案 C BM 最坏情况也是 O(n+m) D 坏字符规则在二进制上跳跃最大
# 24. AC 自动机在敏感词替换、IDS、DNA motif 扫描、模式字典容量 10k–10M 时的内存与初始化代价？ A 初始化复杂度与字典中模式数无关 B 字符集越大内存越小 C 内存主要取决于节点数×字符集大小×指针，10M 模式可能需数 GB ✓ 正确答案 D DNA 字符集（4 字符）比 ASCII 更占内存
# 25. APX-hardness 与多项式时间近似方案 PTAS、FPTAS 的关系如何在 MAX-3SAT、METRIC-TSP 上落地？ A PTAS 与近似常数无关 B FPTAS 复杂度关于 1/ε 指数增长 C METRIC-TSP 有任意 ε 的 PTAS D APX-hard 问题在 P≠NP 下无 PTAS，如 MAX-3SAT ✓ 正确答案
# 26. Aho-Corasick 自动机的 goto、failure、output 三表如何构造，并怎样在文本流上做增量匹配？ A output 只在 goto 命中时报告，不经 failure B failure 表用 BFS 构建，指向最长真后缀对应的前缀状态 ✓ 正确答案 C 匹配时失配必须回退到 root 重新扫描 D AC 匹配复杂度为 O(n·m)
# 27. B 树与 LSM 在随机写、顺序写、压缩、读路径上的对比？分别适合什么 OLTP 负载？ A 两者原地更新且读路径相同 B B 树随机写放大更大但读路径更慢 C LSM 点查无需检查多层 SSTable D LSM 把随机写转成顺序写，用压缩换写吞吐，适合写密集负载 ✓ 正确答案
# 28. B 树的阶、节点分裂、合并与延迟合并如何影响磁盘页 I/O 与写放大？ A 分裂只发生在删除时 B 阶越大树越高 C 延迟合并会立即增加写放大 D 页大小决定树高与点查 I/O，分裂/合并频率影响写放大 ✓ 正确答案
# 29. Dinic 的当前弧优化、分层图压缩与并发/并行最大流在多核环境下的瓶颈是什么？ A 分层图压缩会引入更多边 B 当前弧优化避免重复扫描已用尽边，每轮阻塞流降到 O(E) ✓ 正确答案 C 多核并行时共享容量数组无竞争 D 当前弧优化增加每轮复杂度
# 30. Huffman 编码的最优性证明、长度受限变体、范式 Huffman 与 B-ary 树如何兼顾压缩率和块大小？ A 每步合并两个最小权可得到最优前缀码，压缩率最优 ✓ 正确答案 B 长度受限变体会降低压缩率到非最优 C 范式 Huffman 需要传完整码树 D B-ary 变体每步合并两个节点
# 31. Intractability 中“反多项式等价”与“反指数等价”分别在密码学与算法竞赛中的应用？ A 反多项式等价与复杂度类无关 B 指数归约用于算法竞赛证明多项式可解 C 多项式归约保持多项式可解性，用于 NP 完全性；指数归约用于密码学困难性 ✓ 正确答案 D 归约只能单向保持难度
# 32. Intractability 中 co-NP、PSPACE、#P、APX、FPT、ETH 与 Strong ETH 的关系以及它们对应的难解类？ A FPT 属于 APX 的子类 B NP ⊆ PSPACE，co-NP 是补问题的 NP，#P 是计数类 ✓ 正确答案 C ETH 断言 3SAT 存在多项式算法 D #P 比 NP 更简单
# 33. LZW 的码本初始大小、CODE_MAX、clear code 与 early change 在 GIF/TIFF 中的差异是什么？ A 所有格式都用固定位宽 B GIF 用 clear code 重置码本并可能 early change，TIFF 无 clear code 用可变位宽 ✓ 正确答案 C clear code 用于增加码本 D LZW 码本从 2^32 开始
# 34. Planar separator、Lipton-Tarjan 定理与图划分、几何算法、近似算法中的递归切分如何用？ A 递归切分不能用于近似算法 B 分离器大小为 O(n) C 分离器只适用于非平面图 D 任意 n 顶点平面图存在 O(√n) 分离器，可分治求解 ✓ 正确答案
# 35. Push-Relabel 的 FIFO、Highest-Label、Wave 与全局间隙启发式各自适合的网络类型？ A Highest-Label 选择最高标号活动点，减少 relabel，适合深图 ✓ 正确答案 B FIFO 总是最快的 C gap 启发式增加标号层数 D Wave 用于单点处理
# 36. Push-Relabel 的 relabel、push、discharge 调度、highest-label 与 gap/全局重标对性能的影响是什么？ A highest-label 总是增加 relabel B relabel 次数与性能无关 C gap 与全局重标能减少 relabel 次数，显著提升性能 ✓ 正确答案 D discharge 只做 push 不做 relabel
# 37. P、NP、NP-Hard、NP-Complete 四个复杂度类的定义、彼此关系与共同点反例？ A P 是 NP 的真子集 B NP-Hard 问题一定属于 NP C NP-Complete = NP ∩ NP-Hard，而停机问题属于 NP-Hard 但不属于 NP ✓ 正确答案 D NP-Complete 一定属于 P
# 38. Rabin-Karp 的滚动哈希、模运算、double hashing 与多模式切分如何控制碰撞概率？ A 模数越大碰撞概率越高 B 双哈希把碰撞概率降到单哈希的平方，逐字符确认消除误报 ✓ 正确答案 C 多模式切分会增加碰撞概率 D 滚动哈希无法更新窗口
# 39. Sentinel 字节、终止符、$符号在 suffix array 与 FM-Index 中为什么必须最小且唯一？ A $ 必须最小且唯一，保证后缀两两不同且排序唯一 ✓ 正确答案 B $ 可以大于所有字符 C 终止符可以多次出现 D 无终止符时排序依然唯一
# 40. Steiner Tree 的 2-approximation（基于 MST）、11/7 近似、欧几里得平面下 PTAS 的核心思想与不可近似性边界？ A 基于 MST 可得 2-近似，欧几里得平面有 PTAS，一般图 APX-hard ✓ 正确答案 B 一般图 Steiner Tree 有 PTAS C MST 长度恒等于最优 Steiner 树 D 欧几里得平面无近似算法
# 41. Suffix Array 与 Suffix Tree 在常数因子、易实现性、内存上的工程权衡是什么？ A Suffix Tree 内存比 SA 更小 B SA 内存紧凑、易实现，是 Suffix Tree 的紧凑替代 ✓ 正确答案 C SA 无法配合 LCP 做查询 D Suffix Tree 构建比 SA 简单
# 42. Suffix Array 的 SA-IS、DC3、Skew 线性构造算法在内存与运行时间上的取舍是什么？ A SA-IS 需要 O(n²) 空间 B DC3 常数比 SA-IS 更小 C 线性构造比 O(n log n) 倍增更慢 D SA-IS 用诱导排序，常数小、内存省，优于 DC3 的大常数 ✓ 正确答案
# 43. Suffix Automaton 的 SAM 性质、最小表示、子串出现次数统计、endpos 等价类如何证明？ A 状态数与 n 成正比但常数可到 n² B 状态数 ≤2n−1，出现次数可由 link 树后序累加得到 ✓ 正确答案 C 出现次数无法从 SAM 统计 D endpos 等价类与状态无关
# 44. Suffix Automaton 的扩展树 link/cnext 结构和广义 SAM 如何支持多串查询？ A 多串插入必须重建整个自动机 B link 边用于转移字符 C 广义 SAM 把多串并入同一自动机，支持多串子串统计 ✓ 正确答案 D 广义 SAM 无法统计出现次数
# 45. Z-function 的朴素 Z-array、Z-box 维护和与 prefix function 的转换关系是什么？ A Z 与 π 无法转换 B 朴素 Z 实现已经是 O(n) C Z-box 维护最右匹配区间复用信息，总复杂度 O(n) ✓ 正确答案 D Z-box 使算法复杂度 O(n²)
# 46. 为什么 Huffman 对极端偏斜分布需要 length-limited 修正，否则编码长度可能爆炸？ A length-limited 会增大码长到 n B 偏斜越长码长越短 C 码长与符号数无关 D 极端偏斜下最长码长可接近 n，需 length-limited 修正 ✓ 正确答案
# 47. 为什么 Karp 列表中的 STEINER-TREE 没有强不可近似性？请给近似比下界。 A 下界接近无穷大 B 它是强不可近似的，近似比无界 C 它有 PTAS D 它有常数近似（2/1.55）但 APX-hard，近似比下界为常数（如 96/95） ✓ 正确答案
# 48. 为什么“NP 完全问题没有多项式解”不直接等于“无法工程化”请给三个反例与可接受的近似。 A 有界树宽不会帮助求解 B NP 完全问题在任何实例上都无法求解 C 近似算法只在 P=NP 时有效 D NP 完全是最坏情况下界，实际实例可借规模/结构/近似/启发式求解 ✓ 正确答案
# 49. 为什么常用 SAP/GAP 模板实现 Dinic？请从常数因子、调试性和竞赛经验分析。 A GAP 启发式增加复杂度上界 B SAP 需要显式分层数组 C SAP+GAP 是 Dinic 的隐式标号实现，常数小、调试简单 ✓ 正确答案 D SAP 与 Dinic 复杂度不同
# 50. 为何 FM-Index 的查询是 O(|P|) 但常数很大，请说明 rank/select 块大小选择的影响？ A 查询常数等于 O(1) B 块越小 rank 越慢 C rank 与块大小无关 D 查询 O(|P|) 但每步 rank 常数大，块大小是空间/时间权衡 ✓ 正确答案
# 51. 从 3SAT 到 HAMILTON-CYCLE、TSP、SUBSET-SUM 的多步归约如何避免中间问题泄漏？ A 只要单向蕴含即可 B 归约需保证双向蕴含且构造多项式、可逆，避免语义泄漏 ✓ 正确答案 C 归约可以放大实例规模到指数 D 组件可互相干扰
# 52. 从 3SAT 到 INDEPENDENT-SET、VERTEX-COVER、CLIQUE、HAMPATH 的归约如何构造可逆映射？ A 独立集与 3SAT 无关 B 只需建变量节点 C 每子句建三角形+变量冲突边，独立集大小=子句数当且仅当可满足 ✓ 正确答案 D 归约不是可逆的
# 53. 从 SUBSET-SUM 到 PARTITION、KNAPSACK、BIN-PACKING 的归约如何保持多项式与可逆性？ A KNAPSACK 把每个数作物品、目标作容量，解可逆映射回子集 ✓ 正确答案 B PARTITION 与 SUBSET-SUM 无关 C 归约会改变元素集合 D 归约需要指数时间
# 54. 前缀/后缀混合搜索的 Indexing by FM-Index 与 hybrid Suffix Array-Tree 各有什么适用负载？ A FM-Index 空间紧凑适合子串计数，hybrid SA-Tree 适合混合前缀/后缀查询 ✓ 正确答案 B FM-Index 无法做子串计数 C hybrid 结构空间更小 D 两者都只支持精确前缀
# 55. 单位容量网络、二部图匹配、最大匹配与最小点覆盖、Konig 定理在任务分配中的工程对应？ A 最小点覆盖与最大匹配无关 B 二部图匹配需要非单位容量 C Konig 定理只适用于一般图 D 最大匹配=单位容量最大流，Konig 定理给出最大匹配=最小点覆盖 ✓ 正确答案
# 56. 外存模型的 cache-oblivious B 树、log-structured merge tree、buffered repository tree 的设计差异？ A COB 树需要知道内存大小 B LSM 有最优单点读 C COB 树优化单点访问、LSM 适合写密集、buffered repository tree 适合批量操作 ✓ 正确答案 D buffered repository tree 不适合批量操作
# 57. 如何测试正则引擎在病态输入上的最坏情况？举出 cataclysmic backtracking 的真实反例。 A 回溯引擎对任何输入都线性 B 模式如 ^(a+)+$ 对 a 串加不匹配尾会指数级回溯 ✓ 正确答案 C 嵌套量词不会导致指数回溯 D NFA 模拟引擎也会指数回溯
# 58. 平面图的 Euler 公式、面着色、4 色定理与多项式时间分离器在子图同构中的作用？ A 4 色定理保证平面图可任意着色 B 平面图子图同构是 NP 完全 C Euler 公式给出 E≤3V−6，平面分离器使平面子图同构可多项式 ✓ 正确答案 D 平面图无分离器性质
# 59. 怎样把目标识别问题归约到 3SAT 并验证归约的语义保真度？ A 归约只需单向蕴含 B 只需编码约束无需验证 C 用变量编码决策、子句编码约束，Tseitin 变换得 3 子句并验证双向蕴含 ✓ 正确答案 D 3SAT 无法表达互斥约束
# 60. 怎样设计一组单元测试覆盖 B 树节点分裂与合并的左右边界？ A 应覆盖分裂/合并的临界键数与左右兄弟方向及根特例 ✓ 正确答案 B 只测根节点即可 C 合并不会改变树高 D 分裂不需更新父键
# 61. 最大流最小割定理、Menger 定理、连通度、边/点割与有向/无向差异如何在工程问题中应用？ A 有向图无割概念 B 连通度与最大流无关 C 最大流=最小割，Menger 给出连通度=最大不相交路径数 ✓ 正确答案 D 点割与边割等价
# 62. 网络流的最小费用流、successive shortest path、cycle canceling 与 cost scaling 在物流与排产中如何选型？ A 三种算法复杂度相同 B cycle canceling 不适合负环 C cost scaling 复杂度与流量成正比 D 小规模用 successive shortest path，大规模成本差异大用 cost scaling ✓ 正确答案
# 63. Commentz-Walter 算法如何将 Boyer-Moore 思想扩展到多模式匹配，why does it not dominate AC？ A 它扩展 BM 的跳跃到多模式，但最坏 O(n·m)，不如 AC 稳健 ✓ 正确答案 B 它最坏线性且构造简单 C 它主导多模式匹配 D 它不需要 trie
# 64. Wu-Manber 算法的字符块大小、shift 表、hash 表、稀疏跳跃如何在大字典上控制误命中？ A B 字符块哈希决定 shift 跳跃，稀疏 hash 表控制误命中与内存 ✓ 正确答案 B B 越大跳跃越少 C 它不需要 hash 表 D 它最坏线性
# 65. 弦图（Chordal Graph）、完美图、间隔图、平面图、强弦图、树宽、团数与最小填充的判定与构造？ A 平面图是弦图 B 弦图由完美消除序判定，间隔图是弦图特例，树宽与最小填充相关 ✓ 正确答案 C 完美图不含弦图 D 最小填充与树宽无关
# 66. 怎样为一个 5GB 文本库选择 AC vs Wu-Manber vs Suffix Automaton 的索引？ A 对 5GB 文本建 SAM 内存很小 B Wu-Manber 最坏线性适合全库 C 固定大量模式全库扫描首选 AC，最坏线性且内存可控 ✓ 正确答案 D AC 无法处理大模式集
# 67. 正则表达式匹配的自动机中 NFA 模拟与回溯式引擎的性能差异？ A NFA 模拟线性但特性受限，回溯引擎功能丰富但最坏指数 ✓ 正确答案 B 回溯引擎最坏线性 C NFA 模拟支持反向引用 D 两者最坏相同
# 68. 最小表示法（Duval 算法）与 Lyndon 分解中如何在线性时间内求循环同构串的字典序最小者？ A Duval 算法只能比较两个串 B 最小旋转需要 O(n²) C Lyndon 分解与最小表示无关 D Duval 算法在线性时间内求最小旋转，基于 Lyndon 分解 ✓ 正确答案
