题目
设哈希表长为14，哈希函数是H（key）=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（）。A. 8B. 3C. 5D. 9
设哈希表长为14，哈希函数是H（key）=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（）。
A. 8
B. 3
C. 5
D. 9
题目解答
答案
D. 9
解析
步骤 1：计算哈希值
根据哈希函数H(key) = key % 11，计算关键字49的哈希值。
\[ H(49) = 49 \% 11 = 5 \]
步骤 2：检查哈希值对应的位置是否已占用
检查哈希表中位置5是否已占用。根据题目，表中已有数据的关键字为15，38，61，84，计算它们的哈希值：
\[ H(15) = 15 \% 11 = 4 \]
\[ H(38) = 38 \% 11 = 5 \]
\[ H(61) = 61 \% 11 = 6 \]
\[ H(84) = 84 \% 11 = 8 \]
位置5已被关键字38占用，因此需要使用二次探测法解决冲突。
步骤 3：使用二次探测法解决冲突
二次探测法的公式为：
\[ H_i = (H(key) + i^2) \% m \]
其中，m为哈希表的长度，i为探测次数。
\[ H_1 = (5 + 1^2) \% 14 = 6 \% 14 = 6 \]
位置6已被关键字61占用，继续探测。
\[ H_2 = (5 + 2^2) \% 14 = 9 \% 14 = 9 \]
位置9未被占用，因此关键字49可以放入位置9。
根据哈希函数H(key) = key % 11，计算关键字49的哈希值。
\[ H(49) = 49 \% 11 = 5 \]
步骤 2：检查哈希值对应的位置是否已占用
检查哈希表中位置5是否已占用。根据题目，表中已有数据的关键字为15，38，61，84，计算它们的哈希值：
\[ H(15) = 15 \% 11 = 4 \]
\[ H(38) = 38 \% 11 = 5 \]
\[ H(61) = 61 \% 11 = 6 \]
\[ H(84) = 84 \% 11 = 8 \]
位置5已被关键字38占用，因此需要使用二次探测法解决冲突。
步骤 3：使用二次探测法解决冲突
二次探测法的公式为：
\[ H_i = (H(key) + i^2) \% m \]
其中，m为哈希表的长度，i为探测次数。
\[ H_1 = (5 + 1^2) \% 14 = 6 \% 14 = 6 \]
位置6已被关键字61占用，继续探测。
\[ H_2 = (5 + 2^2) \% 14 = 9 \% 14 = 9 \]
位置9未被占用，因此关键字49可以放入位置9。