GESP 7级客观题｜哈希表｜课后作业

考试频率：高频。本卷共 6 题。

1. 某个哈希表键值x为整数，H(x) = x % p是常用的哈希函数之一，要求p选择素数是因为这样不会产生冲突。（）

   {{ select(1) }}

• 对
• 错

2. 以下哪个方案不能合理解决或缓解哈希表冲突（ ）。

   {{ select(2) }}

• 在每个哈希表项处，使用不同的哈希函数再建立一个哈希表，管理该表项的冲突元素。
• 在每个哈希表项处，建立二叉排序树，管理该表项的冲突元素。
• 使用不同的哈希函数建立额外的哈希表，用来管理所有发生冲突的元素。
• 覆盖发生冲突的旧元素。

3. 无论哈希表采用何种方式解决冲突，只要管理的元素足够多，都无法避免冲突。（ ）

   {{ select(3) }}

• 对
• 错

4. 一个哈希表，包括$n$个位置（分别编号0~(n-1)），每个位置最多仅能存储一个元素。该哈希表只有插入元素和查询两种操作，没有删除或修改元素的操作。以下说法错误的是（ ）。

   {{ select(4) }}

• 如果哈希函数取值范围为0 ~ (n-1)，且当发生哈希函数碰撞时循环向后寻找空位，则查询操作的最差时间复杂度为 。（“循环向后”指：0向后一位为1，1向后一位为2，……，(n-2)向后一位为(n-1)，(n-1)向后一位为0）
• 如果哈希函数取值范围为0 ~ (n-1)，且当发生哈希函数碰撞时仅循环向后一个位置寻找空位，则查询操作的最差时间复杂度为 。
• 如果哈希函数取值范围为0 ~ (m-1)（m < n），且当发生哈希函数碰撞时仅在m ~ (n-1)的范围内寻找空位，则查询操作的最差时间复杂度为 。
• 查询操作时，如果发现查询元素经哈希函数对应的位置为空位，该查询元素仍可能出现在哈希表内。

5. MD5是一种常见的哈希函数，可以由任意长度的数据生成128位的哈希值，曾广泛应用于数据完整性校验。中国科学家的系列工作首次发现了可实用的MD5破解方法。之后，MD5逐渐被其他哈希函数所取代。

   {{ select(5) }}

• 正确
• 错误

6. 现使⽤有 N 个表项的哈希表， 从 M 个元素中进⾏查找。 该哈希表为解决哈希函数冲突， 为每个表项处建⽴单 链表存储冲突元素。 其查找操作的最坏情况时间复杂度为O(M)。

   {{ select(6) }}

• 正确
• 错误