# 1. 斐波那契堆的摊还分析中 extract-min 是 O(log n) 摊还、decrease-key 是 O(1) 摊还，势函数 Φ=t+2m 如何支撑这两个界？ A 两者都是 O(log n) B extract-min 摊还 O(1)，decrease-key 摊还 O(log n) C extract-min 摊还 O(log n)，decrease-key 摊还 O(1) ✓ 正确答案 D 势函数 Φ=t+2m 中 t 表示标记节点数
# 2. 动态中位数的双堆法中左大根堆+右小根堆能在 O(log n) 插入、O(1) 取中位数，两堆大小如何平衡与调整？ A 插入 O(1)，取中位数 O(log n) B 插入 O(log n)，取中位数 O(1) ✓ 正确答案 C 插入和取中位数都是 O(log n) D 两堆大小差可以任意大
# 3. 并查集的两种优化中为什么按秩合并保证树高 O(log n)，路径压缩单独使用均摊 O(log n)，两者结合得到反阿克曼 O(α(n))？ A 按秩合并一定比路径压缩更有效 B 路径压缩单独使用即可达到 O(α(n)) C 按秩合并保证树高 O(log n)，与路径压缩结合后均摊 O(α(n)) ✓ 正确答案 D 两者结合后最坏情况仍是 O(n)
# 4. 主席树求静态区间第 k 小的过程中为什么查询要同时在 root[r] 与 root[l-1] 上做差分，每层 O(1) 比较、总复杂度 O(log n)？ A 查询需在 root[r] 与 root[l-1] 上同时下降做差分，每层 O(1)，总 O(log n) ✓ 正确答案 B 只需在 root[r] 上下降即可 C 查询复杂度为 O(n log n) D 不需要持久化，普通线段树即可
# 5. 可合并堆（左偏堆/斜堆/配对堆）的应用场景中为什么 Dijkstra/Prim 工程上仍常用二叉堆而不用斐波那契堆？ A 左偏堆的 merge 是 O(1) B 斐波那契堆的 merge 操作是 O(1) C 二叉堆的 decrease-key 是 O(1) D 斐波那契堆理论最优但实现复杂、常数大，工程上 Dijkstra/Prim 仍常用二叉堆 ✓ 正确答案
# 6. 二项堆的结构与合并中二项树 B_k 的节点数恰为 2^k，合并两个二项堆如何用二进制加法类比做到 O(log n)？ A 二项堆中每阶数的树可以有多棵 B 二项树 B_k 的节点数为 k+1 C 合并二项堆需要 O(n) 次操作 D 二项树 B_k 的节点数为 2^k，堆结构与 n 的二进制表示对应 ✓ 正确答案
# 7. 树状数组与线段树的功能/复杂度对比中 BIT 代码短、常数小但仅支持前缀操作；线段树功能全但空间 4n、常数大 A BIT 代码短、常数小、空间 O(n)，但比线段树功能受限 ✓ 正确答案 B 线段树空间为 O(n)，与 BIT 相同 C BIT 支持任意区间操作 D 线段树常数比 BIT 更小
# 8. 二叉堆的建堆为什么是 O(n)，自底向上 sift-down 的求和分析，与逐个插入 O(n log n) 的差异？ A 逐个插入建堆的复杂度是 O(n) B 自底向上 sift-down 建堆的复杂度是 O(n log n) C 自底向上 sift-down 建堆的复杂度是 O(n) ✓ 正确答案 D 建堆必须从第一个节点开始
# 9. Sparse Table 的 O(1) 查询中为什么取 min/max 是幂等（idempotent）操作所以区间可以重叠，而区间和不能这样预处理？ A Sparse Table 支持区间和查询 B 只有幂等操作（如 min/max）才能允许区间重叠，实现 O(1) 查询 ✓ 正确答案 C Sparse Table 支持动态修改 D 区间和也可以用重叠区间求值
# 10. 二叉堆、二项堆、斐波那契堆的复杂度对比中哪些操作在哪种堆上更优，工程上为何多用二叉堆？ A 二叉堆的 merge 是 O(1) B 斐波那契堆的 decrease-key 与 merge 均摊 O(1)，但常数大、实现复杂 ✓ 正确答案 C 二项堆的 extract-min 是 O(1) D 斐波那契堆在实际中一定比二叉堆快
# 11. 树状数组如何实现区间加与区间求和，用两个 BIT（差分数组）推导查询公式的过程？ A 用两个 BIT 分别维护差分数组 d 与 i·d，即可 O(log n) 完成区间加与区间求和 ✓ 正确答案 B 单用一个 BIT 即可同时支持区间加与区间求和 C 区间加只能在线段树上实现 D 区间求和的公式是 Σ d[j] 即可
# 12. 线段树与树状数组的互相转化中哪些区间操作（区间加、区间最值）只能用线段树？ A BIT 可以任意区间求最值 B 区间最值（如区间加后求区间最大）只能用线段树，BIT 无法直接实现 ✓ 正确答案 C 区间加与区间求和必须用线段树 D BIT 的功能完全覆盖线段树
# 13. Treap 的期望深度中随机优先级使 Treap 等价于随机 BST，期望高度 O(log n) 如何由随机 BST 分析得到？ A 随机优先级使 Treap 等价于随机 BST，期望深度 O(log n) ✓ 正确答案 B 随机优先级使 Treap 期望深度 O(n) C 优先级固定时 Treap 仍期望 O(log n) D Treap 需要显式维护平衡因子
# 14. Link-Cut Tree 的 access 操作中虚实链切换需要 splay 与路径聚合，access 的摊还复杂度 O(log n) 如何由 splay 势能证明？ A access 通过 splay 与虚实切换把根到 u 的路径聚合为实链，摊还 O(log n) ✓ 正确答案 B access 每次都需要重建整棵树 C splay 的均摊复杂度是 O(n) D access 不涉及虚实链切换
# 15. 线段树懒标记（Lazy Propagation）的原理中延迟下推区间更新标记，仅在需要访问子节点时才 push_down，保证 O(log n) 单次更新 A 每次区间更新都要下推到所有叶子 B 完全覆盖的区间直接更新并打标记，仅需要时 push_down，单次更新 O(log n) ✓ 正确答案 C 懒标记使单次区间更新复杂度为 O(n) D push_down 每次更新都执行
# 16. 可持久化线段树的版本共享中为什么修改只新建 O(log n) 个节点、旧版本节点不被改动就能保证历史查询正确？ A 旧版本节点会被修改以同步新版本 B 每次修改都要复制整棵树 C 修改只新建 O(log n) 个节点，旧版本节点不可变，历史查询正确 ✓ 正确答案 D 无法进行历史查询
# 17. 树状数组（Fenwick Tree）的 lowbit 设计与前缀查询/单点更新，与线段树的适用边界？ A lowbit(i) 等于 i 的最高位 B 节点 i 覆盖 [1, i] C BIT 可以直接支持任意区间最值查询 D 节点 i 覆盖 [i-lowbit(i)+1, i]，前缀查询与单点更新均 O(log n) ✓ 正确答案
# 18. Top Tree 与 LCT 的对比中竞赛中的动态树问题多用 LCT 或树链剖分，Top Tree 的 cluster 抽象何时才值得实现？ A LCT 只能处理静态树 B Top Tree 的实现比 LCT 简单 C 树链剖分支持动态 link/cut D 竞赛动态树问题多用 LCT 或树链剖分，Top Tree 的 cluster 抽象实现复杂，仅在需高级聚合时使用 ✓ 正确答案
