假设散列表长度为 11,散列函数为 H(key)=key%7,冲突处理方法为开放地址法的二次探测再散列。已知表中已有记录的关键字为 32,17,9,27,现要将关键字为 45 的记录加入表中,则放入的位置是( )。
时间: 2024-03-31 08:32:46 浏览: 10
首先,将关键字为 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。
10.设散列函数为h(key)=key%101,解决冲突的方法为线性探测,表中用"-1"表示空单元。
可以回答这个问题。对于给定的关键字key,散列函数h(key)=key%10,解决冲突的方法为线性探测。如果发生冲突,就在散列表中往后查找,直到找到一个空单元或者查找到整个散列表。如果查找到整个散列表,就说明散列表已满,无法再插入新的元素。