假设散列表长度为 11，散列函数为 H(key)=key%7，冲突处理方法为开放地址法的二次探测再散列。已知表中已有记录的关键字为 32,17,9,27，现要将关键字为 45 的记录加入表中，则放入的位置是（ ）。

首先，将关键字为 45 代入散列函数 H(key)=key%7，得到 H(45)=3。由于 H(45) 对应的位置已经被占用，因此需要使用开放地址法的二次探测再散列来解决冲突。

二次探测再散列的探测序列为：
H'(key, i) = (H(key) + c1 * i + c2 * i^2) % m，其中 c1 和 c2 是两个常数，m 是散列表长度。

假设 c1 = 1，c2 = 3，则探测序列为：
H'(45, 0) = 3
H'(45, 1) = 7 % 11 = 7
H'(45, 2) = 12 % 11 = 1
H'(45, 3) = 19 % 11 = 8
H'(45, 4) = 28 % 11 = 6
H'(45, 5) = 39 % 11 = 6
H'(45, 6) = 52 % 11 = 8
...

依次探测下去，直到找到一个空闲位置为止。在本例中，第 6 次探测时发现位置 6 是空闲的，因此关键字为 45 的记录应该插入到位置 6。

因此，答案为：6。

相关问题

16. 假设散列表长度为 11，散列函数为 H(key)=key%7，冲突处理方法为开放地址法的二次探测再散列。已知表中已有记录的关键字为 32,17,9,27，现要将关键字为 45 的记录加入表中，则放入的位置是（ ）。

首先，将关键字为 45 代入散列函数 H(key)=key%7，得到 H(45)=3。由于 H(45) 对应的位置已经被占用，因此需要使用开放地址法的二次探测再散列来解决冲突。

二次探测再散列的探测序列为：
H'(key, i) = (H(key) + c1 * i + c2 * i^2) % m，其中 c1 和 c2 是两个常数，m 是散列表长度。

假设 c1 = 1，c2 = 3，则探测序列为：
H'(45, 0) = 3
H'(45, 1) = 7 % 11 = 7
H'(45, 2) = 12 % 11 = 1
H'(45, 3) = 19 % 11 = 8
H'(45, 4) = 28 % 11 = 6
H'(45, 5) = 39 % 11 = 6
H'(45, 6) = 52 % 11 = 8
...

依次探测下去，直到找到一个空闲位置为止。在本例中，第 6 次探测时发现位置 6 是空闲的，因此关键字为 45 的记录应该插入到位置 6。

因此，答案为：6。

给定散列表大小为11，散列函数为h(key)=key%11。按照线性探测冲突解决策略连续插入散列值相同的5个元素。问：此时该散列表的平均不成功查找次数是多少？

根据线性探测冲突解决策略，当插入一个元素时，如果该元素的散列值已经被占用，则向后探测直到找到一个空位置插入。因此，插入5个散列值相同的元素时，它们会被依次插入到散列表的位置0、1、2、3、4上。

当进行查找时，如果要查找的元素在散列表中不存在，则需要依次查找位置0、1、2、3、4，直到找到一个空位置或者找到要查找的元素。因此，平均不成功查找次数为(0+1+2+3+4)/5=2.

因此，该散列表的平均不成功查找次数为2。