# 1. Redis ZSET 的跳表实现细节中节点结构（score/member/level/span）、backward 指针的作用、zslRandomLevel 的概率参数选择（p=1/4 vs p=1/2） A backward 指针用于跨层跳跃 B backward 指针用于逆序遍历，span 用于 O(1) 排名，zslRandomLevel 用 p=1/4 平衡内存与性能 ✓ 正确答案 C p=1/2 比 p=1/4 更省内存 D 跳表节点不包含 span 字段
# 2. 跳表的查找/插入/删除过程中从最高层逐层下降的搜索路径与节点层数随机化的关系？ A 删除只需更新底层指针 B 查找只走底层 C 插入的新节点层数由键值决定 D 查找从最高层逐层右移后下降，插入/删除需维护各层前驱指针 ✓ 正确答案
# 3. 跳表期望时间复杂度 O(log n) 的概率证明中从顶层到底层的搜索步数分析、高概率界 O(log n) with probability 1-1/n^c 的 Chernoff bound 推导 A 期望搜索步数 O(n) B 期望搜索步数 O(log n)，可用 Chernoff 界证明高概率不超过 O(log n) ✓ 正确答案 C 层数期望与 n 无关，恒为常数 D Chernoff 界证明跳表最坏也是 O(log n)
# 4. 跳表 vs 红黑树中范围查询、实现复杂度与并发友好性的权衡？ A 红黑树范围查询比跳表更简单 B 跳表范围查询、实现、并发都更友好，但用更多内存换简单 ✓ 正确答案 C 跳表无法实现并发 D 红黑树实现比跳表简单
# 5. 跳表与哈希索引的选择中范围查询场景选跳表而精确点查选哈希，Redis 中两者如何互补？ A 哈希索引支持范围查询 B 精确点查用哈希 O(1)，范围查询用跳表，Redis ZSET 两者互补 ✓ 正确答案 C 跳表点查是 O(1) D Redis 只用跳表，不用哈希
# 6. 跳表的期望空间与时间复杂度推导中 P(level=i) 的几何分布与期望指针数？ A 期望指针数与 p 无关 B 每个节点期望指针数为 2 C 每个节点期望指针数 1/(1-p)，总空间 O(n/(1-p)) ✓ 正确答案 D 总空间与 n 无关
# 7. 跳表节点层数的随机化中几何分布与期望层数 O(log n) 的推导？ A 期望层数 O(log n) B 层数服从均匀分布 C 层数服从几何分布，期望层数 1/(1-p)，最大层数 O(log_{1/p} n) ✓ 正确答案 D 最大层数与 n 无关
# 8. 跳表与平衡 BST（AVL/红黑树）在实现复杂度、范围查询、并发友好性上的权衡中为什么 Redis 选择跳表而非红黑树？ A 红黑树实现比跳表简单 B 跳表实现简单、范围查询高效、并发友好，故 Redis 选择跳表 ✓ 正确答案 C 跳表范围查询比红黑树困难 D 红黑树在功能上完全覆盖跳表
# 9. 跳表 level 生成的概率模型中几何分布 P(level=i)=p^(i-1)(1-p)、期望层数 1/(1-p)、最大层数 O(log_{1/p} n) 的推导 A 最大层数与 p 无关 B P(level=i)=p(1-p)^(i-1) C 期望层数是 O(log n) D P(level=i)=p^(i-1)(1-p)，期望层数 1/(1-p)，最大层数 O(log_{1/p} n) ✓ 正确答案
# 10. Redis ZSET 如何用 span 字段实现 O(log n) 的 rank（排名）查询，member 反向查找的代价如何？ A member 反向查找在跳表内 O(1) 完成 B rank 查询需要遍历底层链表 C span 是跳表节点的分数 D 沿搜索路径累加 span 可得 rank，O(log n)；member 反向查找借助 dict ✓ 正确答案
# 11. 跳表查找的正确性中从最高层开始、每层尽可能右移再下降的贪心搜索不会错过目标，层间下降时指针更新的不变量是什么？ A 不变量只在底层成立 B 贪心搜索可能跳过目标 C 每层都向右走到末尾 D 每层保持"当前节点≤目标<后继"的不变量，逐层下降最终收敛到目标 ✓ 正确答案
# 12. 跳表删除节点的边界处理中如何找到并更新所有指向被删节点的前驱指针，与插入过程的对称性？ A 删除不需要记录前驱 B 删除只需更新底层指针 C 记录各层前驱后逐层跳过被删节点并更新 span，与插入过程对称 ✓ 正确答案 D 删除后 span 无需调整
# 13. 跳表的空间开销分析中期望每节点指针数 2 的推导，以及 p=1/2 与 p=1/4 的取舍？ A p=1/2 时每节点 4 个指针 B 期望指针数 1/(1-p)，p=1/2 时约 2，p=1/4 时约 4/3，p 越小越省内存 ✓ 正确答案 C 期望指针数与 p 无关 D p 越大越省内存
# 14. 跳表的空间复杂度与缓存表现中为什么在内存数据库（Redis/LevelDB）中优于 B+Tree？ A 跳表比 B+Tree 更适合磁盘扫描 B B+Tree 在内存中比跳表更简单 C 跳表实现简单、适合内存与无锁并发，在内存数据库（Redis/LevelDB）中优于 B+Tree ✓ 正确答案 D 跳表不支持并发
# 15. 并发跳表的锁策略中 per-node lock coupling（hand-over-hand locking）vs 乐观锁（lock-free with CAS）vs RCU 读优化，各自适用场景与 ABA 问题 A RCU 适合写多读少的场景 B lock-free 跳表无需处理 ABA C hand-over-hand 锁简单但并发度低，lock-free CAS 并发高但需处理 ABA，RCU 适合读多写少 ✓ 正确答案 D hand-over-hand 是无锁的
# 16. LevelDB/RocksDB 的 MemTable 为何选用跳表，写放大与读放大的权衡、与 SkipList 的 immutable 快照（Iterator pin）机制、对比 B+Tree memtable 的 trade-off A B+Tree 实现比跳表简单，更适合 MemTable B 跳表实现简单、支持范围查询与并发，immutable 快照用 Iterator pin 固定引用，故 MemTable 选跳表 ✓ 正确答案 C MemTable 用跳表是为了减少写放大 D 跳表不支持范围查询
# 17. 跳表与 B+Tree 在数据库/存储引擎索引场景的对比中为什么 LSM 的 MemTable 选跳表？ A B+Tree 实现比跳表简单 B 跳表比 B+Tree 更适合磁盘存储 C B+Tree 适合磁盘（高扇出缓存友好），跳表适合内存，故 LSM MemTable 选跳表 ✓ 正确答案 D MemTable 应该用 B+Tree 而非跳表
