CSP-J/S 哈希表与哈希冲突综合测试

本试卷共 25 道单项选择题，每题 4 分，满分 100 分。

一、基本概念与哈希函数

1. 哈希冲突是指（ ）。

{{ select(1) }}

• 两个相同关键字被同时删除
• 两个不同关键字映射到同一个哈希地址
• 两个桶的下标不同
• 哈希表中没有空桶

2. 关于哈希表的时间复杂度，下列说法正确的是（ ）。

{{ select(2) }}

• 任何情况下查找都是 O(1)
• 分布均匀时平均接近 O(1)，最坏可能达到 O(n)
• 查找一定是 O(log n)
• 插入一定比查找慢

3. 关键字范围很小且空间允许时，最直接的数据组织方式通常是（ ）。

{{ select(3) }}

• 直接定址
• 双重散列
• 链地址法
• 字符串哈希

4. 使用除留余数法 h(x)=x mod m 时，选择质数作为 m（ ）。

{{ select(4) }}

• 能保证永远没有冲突
• 通常有助于改善分布，但仍可能发生冲突
• 会使所有关键字映射到同一位置
• 只适用于字符串

5. 在 C++ 中，为了把负数关键字 x 映射到 0～M-1，较稳妥的写法是（ ）。

{{ select(5) }}

• x % M
• (x % M + M) % M
• x / M
• abs(x / M)

6. 若 M=11，关键字 -3 使用 (x%M+M)%M 得到的地址是（ ）。

{{ select(6) }}

• 3
• 8
• -3
• 14

二、装填因子与冲突处理

7. 装填因子 α 的定义是（ ）。

{{ select(7) }}

• 桶数 ÷ 已存元素数
• 已存元素数 ÷ 桶数
• 冲突次数 ÷ 桶数
• 空桶数 ÷ 已存元素数

8. 对开放地址法而言，装填因子必须满足（ ）。

{{ select(8) }}

• α < 1
• α = 1
• α > 1
• 与桶数无关

9. 链地址法的装填因子（ ）。

{{ select(9) }}

• 必须小于 1
• 可以大于 1
• 必须等于 0
• 只能取整数

10. 线性探测发生冲突后，下一次探测地址通常是（ ）。

{{ select(10) }}

• (p+1) mod m
• p-1，且不能回绕
• 2p
• 随机选择任意桶

11. 线性探测到达表尾后仍未找到空桶时，应当（ ）。

{{ select(11) }}

• 立即覆盖表尾元素
• 回到表头继续探测
• 自动改用链地址法
• 删除初始地址中的元素

12. 线性探测容易形成较长的连续占用区，这种现象称为（ ）。

{{ select(12) }}

• 路径压缩
• 主聚集
• 拓扑排序
• 重复定义

13. 二次探测相对线性探测的主要作用是（ ）。

{{ select(13) }}

• 完全消除冲突
• 缓解主聚集
• 保证访问所有桶
• 自动按关键字排序

14. 双重散列中第二个哈希函数主要用于确定（ ）。

{{ select(14) }}

• 表的初始长度
• 探测步长
• 元素的大小
• 删除次数

15. 为了让双重散列的探测序列尽量遍历全部桶，步长通常应（ ）。

{{ select(15) }}

• 等于 0
• 与表长互质
• 大于表长
• 始终等于表长

三、查找、删除与手工模拟

16. 开放地址法查找时，遇到 DELETED 桶应当（ ）。

{{ select(16) }}

• 立即判定查找失败
• 继续沿探测序列查找
• 把它改成 EMPTY 后停止
• 覆盖为目标关键字

17. 开放地址法删除元素时不能简单改成 EMPTY，主要原因是（ ）。

{{ select(17) }}

• 会改变桶数
• 可能截断其他关键字的探测链
• 会导致编译错误
• EMPTY 只能用于链表

18. 表长为 7，h(x)=x mod 7，依次插入 10、17、24、31，使用线性探测，则 31 最终位于下标（ ）。

{{ select(18) }}

• 3
• 4
• 5
• 6

19. 上题中删除 17 并标记为 DELETED，查找 24 时依次检查的下标是（ ）。

{{ select(19) }}

• 3、4、5
• 5
• 3、4 后停止
• 4、5

20. 上述四个元素的成功查找长度分别为 1、2、3、4，平均成功查找长度为（ ）。

{{ select(20) }}

• 2
• 2.5
• 3
• 4

21. 为避免满表时线性探测陷入死循环，一次操作最多应检查（ ）。

{{ select(21) }}

• 1 个桶
• m/2 个桶
• m 个桶
• 不限制次数

四、链地址法与 C++ unordered 容器

22. 链地址法发生冲突时，应当（ ）。

{{ select(22) }}

• 覆盖原桶元素
• 把关键字放入对应桶的冲突链
• 向后寻找第一个空桶
• 重新排序全部关键字

23. 桶数为 7，依次头插 3、10、17，且三者都映射到桶 3，则桶 3 的链中顺序是（ ）。

{{ select(23) }}

• 3→10→17
• 17→10→3
• 10→3→17
• 顺序必然按数值升序

24. 关于 unordered_map 的遍历顺序，下列说法正确的是（ ）。

{{ select(24) }}

• 一定按 key 升序
• 一定按插入顺序
• 没有稳定的排序保证
• 一定按 value 降序

25. 仅想判断 unordered_map mp 中是否存在 x，更合适的写法是（ ）。

{{ select(25) }}

• mp[x] == 0
• mp.find(x) != mp.end()
• mp[x]++
• mp.clear()