# 1. Splay 树的均摊 O(log n) 如何通过伸展操作实现？zig/zig-zig/zig-zag 三种情况的旋转规则与势能函数 Φ=Σlog(size(x)) 的摊还分析 A 先旋父节点，再旋目标节点 ✓ 正确答案 B 不旋转 C 只旋目标一次 D 先旋目标节点，再旋父节点
# 4. Splay 的'工作集定理'中访问最近访问过的元素摊还 O(log n)，访问频率越高的元素越靠近根 A 最近访问过的元素摊还代价低，高频元素靠近根 ✓ 正确答案 B 所有元素访问代价相同 C Splay 树是严格平衡的 D 访问代价与频率无关
# 5. Treap 如何用随机优先级+旋转维持期望 O(log n) 平衡？证明期望树高为 O(log n)（等价于随机 BST 的期望高度） A 随机优先级使树等价于随机 BST，期望高度 O(log n) ✓ 正确答案 B 使用 AVL 旋转 C 树是完美平衡 D 使用哈希
# 6. Treap 与笛卡尔树的等价性中 Treap 的插入顺序按 priority 排序后构建的笛卡尔树即为该 Treap A 两者都是严格平衡 B 两者都使用哈希 C 两者都保存键序与优先级堆序 ✓ 正确答案 D 两者无关
# 7. Treap 的期望 O(log n) 与 AVL/红黑树的严格 O(log n) 在工程中的取舍中 Treap 常数小但最坏概率存在，红黑树稳定但旋转复杂 A Treap B 跳表 C 红黑树/AVL ✓ 正确答案 D 张量
# 11. Splay 在 LCT（Link-Cut Tree）中作为辅助树的角色中 preferred path 上的 Splay 维护路径信息，access 操作中的 splay 暴露路径 A 把目标节点到根的路径打通并暴露为一个 Splay ✓ 正确答案 B 删除整棵树 C 查找最小值 D 构建笛卡尔树
# 12. 为何 Redis 的 zset 选跳表而非 Treap/Splay（概率平衡 vs 确定性旋转），实现复杂度、范围查询、并发友好性 A 跳表查找更快 B 跳表实现简单、范围查询自然、并发友好 ✓ 正确答案 C Treap 复杂度更高 D Splay 更省内存
# 15. 无旋 Treap 的可持久化中 split/merge 时复制路径上的节点即可实现 O(log n) 的持久化平衡树 A 原地旋转 B 在 split/merge 时复制路径上的节点，生成新版本 ✓ 正确答案 C 使用哈希 D 不保留版本
# 16. 无旋 Treap（FHQ Treap）的 split/merge 操作如何替代旋转？按值分裂与按秩分裂的实现，惰性标记在 merge 中的下推顺序 A split 与 merge ✓ 正确答案 B 左旋与右旋 C 红黑染色 D 哈希
# 17. 跳表与 B+ 树在磁盘/内存场景的对比中跳表适合内存（无旋转、简单），B+ 树适合磁盘（高分支因子、页对齐） A B+ 树无查找 B B+ 树实现更简单 C B+ 树高分支因子 + 页对齐，减少磁盘 I/O ✓ 正确答案 D 跳表不能范围查询
