# 1. Scapegoat 树的重建机制中沿路径找第一个 size(child)>α·size(node) 的节点整棵重建，α 的取值如何影响均摊 O(log n)？ A α 取值必须严格小于 0.5 才能保证平衡 B 每次插入都需要重建整棵树 C 插入后沿路径找第一个 size(child) > α·size(node) 的节点整棵重建，均摊 O(log n) ✓ 正确答案 D 重建后该子树仍可能很快再次失衡，导致均摊 O(n)
# 2. Rabin-Karp 滚动哈希如何把字符串匹配降到期望 O(n+m)，为什么取大素数模能降低冲突概率？ A 该算法最坏和期望都是 O(n+m) B 取大素数模的目的是使哈希值总能被整除 C 滚动哈希能把每个窗口的哈希值在 O(1) 内由前一个窗口推出 ✓ 正确答案 D 哈希相等时即可直接判定匹配，无需逐字符核验
# 3. FNV-1a 哈希的 avalanche 性质中为什么适合短字符串但在长输入上混淆不足，与 MurmurHash/xxHash 在质量与速度上的取舍？ A FNV-1a 简单快速，适合短字符串，但长输入时混淆不足 ✓ 正确答案 B FNV-1a 在长输入上的混淆效果优于 MurmurHash C xxHash 的质量一定比 FNV-1a 差 D FNV-1a 的 avalanche 性质与输入长度无关
# 4. 哈希函数的均匀性要求与常见实现中除法散列、乘法散列与字符串哈希（BKDR/DJB）的选择？ A DJB 字符串哈希用除以 33 的方式计算 B 乘法散列依赖 m 的质因数分解 C 除法散列中 m 取素数可减少周期性聚集 ✓ 正确答案 D 均匀性只要求输入相同输出必相同
# 5. 哈希攻击与安全哈希中为什么不可预测的盐/随机种子能防御针对哈希表的 DoS 攻击？ A 随机种子必须公开以便攻击者验证 B 固定哈希函数配合更大的表就能完全防御哈希攻击 C 随机种子使攻击者无法预知哈希值，从而无法预先构造碰撞集 ✓ 正确答案 D 哈希攻击只能影响链地址法，不影响开放寻址
# 6. AVL 树的平衡维护中插入后如何沿路径回溯更新平衡因子，LL/LR/RR/RL 四种旋转为何都能使子树高度复原，删除的旋转次数上限？ A RL 型失衡只需一次右旋 B 删除时最多只需一次旋转 C 插入后只需一次旋转（或双旋）即可恢复平衡，因为旋转后子树高度复原 ✓ 正确答案 D 平衡因子为 ±2 时无需旋转即可恢复
# 7. 开放寻址（线性探测/二次探测/双重哈希）vs 链地址法的工程权衡中缓存友好性 vs 高负载因子下的退化 A 线性探测能完全避免聚集 B 链地址法对缓存更友好 C 开放寻址缓存友好但高负载因子下退化明显 ✓ 正确答案 D 开放寻址在负载因子为 2 时性能依然最佳
# 8. 双哈希（double hashing）的探测序列中为什么二次探测只产生约一半的不同序列而双哈希有 n 种，双哈希对表长与步长互质的要求？ A 二次探测能产生约 m 种不同的探测序列 B 双哈希的探测序列与二次探测完全相同 C 双哈希要求步长 h2(k) 与表长 m 互质，以保证探测覆盖整个表 ✓ 正确答案 D 表长取合数时双哈希序列一定覆盖全表
# 9. 哈希表的装载因子与冲突解决中链地址法与开放寻址（线性/二次/双重探测）的期望性能对比？ A 线性探测在负载因子接近 1 时期望探测次数急剧增长 ✓ 正确答案 B 链地址法在负载因子接近 1 时性能急剧恶化 C 开放寻址可以容忍任意高的负载因子 D 二次探测的期望性能一定比双哈希差
# 10. 哈希表扩容时的 rehash 策略中为什么渐进式 rehash（如 Redis）能避免单次全量迁移的停顿？ A 渐进式 rehash 能把总迁移开销从 O(n) 降到 O(log n) B 渐进式 rehash 期间只使用旧表 C 每次操作只迁移一小部分元素，把单次全量迁移的停顿摊薄到各次操作 ✓ 正确答案 D 渐进式 rehash 要求所有元素一次性迁移完毕
# 11. 布隆过滤器的假阳性率推导中 k 个哈希函数与 m 位数组、n 个元素时最优 k 约等于 (m/n)ln2 如何得到？ A k 越大假阳性率越低，没有最优值 B 最优 k 与 m/n 无关，恒为常数 C 最优 k 约为 (m/n)·ln2，由对假阳性率求导得到 ✓ 正确答案 D 最优 k 约为 (m/n)·ln(n)
# 12. 表达式的三种表示中中缀/前缀/后缀如何互相转换，后缀表达式如何用栈求值？ A 后缀表达式无需括号和优先级，可直接用栈求值 ✓ 正确答案 B 中缀表达式一定比后缀表达式更简短 C 前缀表达式求值需要维护两个栈 D 后缀表达式中运算符位于两个操作数之间
# 13. 一致性哈希的原理与分布式系统应用中环形哈希空间 + 虚拟节点，节点增删时仅迁移 O(1/N) 数据 A 节点增删时所有键的映射都会改变 B 节点增删时仅迁移约 1/N 的数据，其余键保持不变 ✓ 正确答案 C 虚拟节点用于减少哈希值的位数 D 一致性哈希只能用于缓存，不能用于存储
# 14. 线性同余哈希（LCG）的缺陷中 LCG 的低位周期短、随机性差，不适合做哈希函数，工程上如何用 splitmix64/Murmur 混合？ A LCG 已经具备良好的 avalanche 性质 B LCG 的高位比特周期比低位更短 C splitmix64 通过线性相乘得到均匀分布，无需异或 D LCG 的低位比特周期短，随机性差，不适合做哈希函数 ✓ 正确答案
# 15. 压缩前缀树（Patricia/radix tree）的空间优化中为什么把单分支路径压缩为边能减少节点数，在 IPv4/IPv6 路由查找中的应用？ A 压缩会增大存储空间 B 压缩后查找时无法沿路径匹配 C radix tree 不适合 IP 路由的最长前缀匹配 D 把单分支路径压缩为一条边可减少节点数 ✓ 正确答案
# 16. Masstree 的 Trie 前缀分层+B+树组合中这种结构能兼顾共享前缀压缩与缓存友好，其乐观并发（版本号 CAS）如何保证一致性？ A Masstree 只使用 Trie，不使用 B+树 B Trie 分层压缩共享前缀，B+树提供缓存友好的节点组织 ✓ 正确答案 C 乐观并发要求读操作必须加锁 D CAS 只能用版本号更新，不能更新节点内容
# 17. MinHash 的 Jaccard 估计中为什么 min-hash 相等概率等于 Jaccard 相似度，为达到 ε 误差需要 O(1/ε²) 个哈希函数的推导？ A min-hash 相等的概率等于 1 - Jaccard B min-hash 相等的概率等于 Jaccard 相似度 ✓ 正确答案 C 只需 1 个哈希函数即可精确估计 Jaccard D 达到 ε 误差需要 O(1/ε) 个哈希函数
# 18. Radix Tree（基数树）与前缀树（Trie）的差异中为什么按二进制位分叉的 radix tree 更省空间，在 IP 路由/字典前缀上的应用？ A radix tree 的节点数一定多于字符级 Trie B 前缀树按二进制位分叉 C radix tree 无法用于 IP 路由 D 按二进制位分叉并压缩单分支路径，使 radix tree 更省空间 ✓ 正确答案
