首页 > 试题广场 >

设哈希表长为14,哈希函数是H(key)=key%11,表中

[单选题]

设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15386184共四个,现要将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是(    )

  • 8
  • 3
  • 5
  • 9
哈希 15 38 61 84 ... 49 ..
%11 4 5 6 7
5 ...

49%11=5,此时发生冲突,按二次探测法:
1.(5+1^2)%14=6   冲突
2.(5-1^2)%14=4  冲突
3.(5+2^2)%14=9  不冲突
4.(5-2^2)%14=1  (如有必要)
看明白了吧,选D
发表于 2017-06-16 15:13:35 回复(4)
49%11=5被占用了
(5+1^2)%11=6还是被占用了
(5-1^2)%11=4被占用了
(5+2^2)%11=9未被占用,所以在9的位置放入49
发表于 2017-06-04 15:05:43 回复(5)
二次探测法是指平方探测法
发表于 2017-11-10 15:10:05 回复(0)
用二次探测再散列法解决冲突。。。
发表于 2017-06-16 12:19:10 回复(1)
H-i = (H(key) + d-i)%m               i = i, 2, ..., m-1
其中,H(key)为散列函数,m为散列表表长,d-i为增量序列
二次探测法:
d-i = 1^2, -1^2, 2^2, -2^2, ..., +k^2, -k^2(k<=m/2)

49%11=5,此时发生冲突,按二次探测法:
1.(5+1^2)%14=6   冲突
2.(5-1^2)%14=4  冲突
3.(5+2^2)%14=9  不冲突, 所以将5填入序号为9的位置
4.(5-2^2)%14=1  (如有必要)


发表于 2020-02-28 10:21:10 回复(0)
开放定址法:Hi=(H(key)+di)%m 包括:线性探测法,平方探测法,再散列法 ◎线性探测法:当di=0,1,2,…,m-1时,称为线性探测法。缺点:元素容易聚集; ◎平方探测法(又称 二次探测法):当di=0,1,-1,4,-4,9,-9,…,k²,-k²,其中k≤2/m,m为散列表长度。优点:可以避免堆积问题,缺点:不能探测到散列表上的所有单元,但至少能探测到一半单元。 ◎再散列法(又称 双散列法):需要两个散列函数, 第一个散列函数:H(key) 第二个散列函数:Hash2(key) Hi=(H(key)+i*Hash2(key))%m
发表于 2019-05-19 15:25:20 回复(0)
选a阿,冲突后要%14,要不然11往后的空间就一直空闲了
发表于 2021-12-11 13:49:39 回复(1)
对于已有的4个关键字15,38,61,84,
通过哈希函数得到的哈希值分别为:
15 % 11 = 4
38 % 11 = 5
61 % 11 = 6
84 % 11 = 7
对于新的关键字49:
49 % 11 = 5
和关键字38的哈希值冲突了。这里解决冲突的方法是开放定址法中的二次探测法(也叫平方探测法)。
对于已经计算出来的哈希值H = 5
那么下一个放入的位置是 
(H + i2) % 11     
(H -  i2) % 11    其中i的值为1,2,...
当i = 2时,(H + 22) % 11 = 9  ,没有产生冲突。
---------------------------------------------------------------
菜鸟一枚,有错欢迎指出
发表于 2020-08-21 21:56:57 回复(1)
不是8?
发表于 2017-05-23 19:06:02 回复(7)
是9
发表于 2022-03-19 16:17:44 回复(0)
突然脑子抽了以为是二次哈希
发表于 2020-10-06 16:59:14 回复(0)
是按照+1-1+4-4的顺序
发表于 2019-12-18 12:54:28 回复(0)
二次探测是指平均探测法
发表于 2019-12-05 00:15:56 回复(0)
(key+N^2) %k = 
N从+-1开始取
发表于 2019-08-06 21:01:19 回复(0)
2次探测法就是平方探测法
发表于 2019-03-11 08:09:25 回复(0)
5被38占用后 找5+1^2=5+1=6(被61占用) 找5-1=5-1^2=4(被15占用) 找5+2*2=9(空闲可用) 注意表是从0开始
发表于 2018-12-18 11:37:22 回复(0)
需不需要- i^2题目没说清楚,数据结构与算法分析--机械工业出版社 原文:如果表大小是4K+3的素数,且使用解决冲突方法是F(i)=+-i^2 那么整个表均可以被探测到,其代价是程序稍微复杂.也就是说如果不是使用4K+3(题目就不是素数)或者不是正负i2 也是可以的,这题刚刚好-的时候有元素,如果下次又没有元素且没有说明使用的解决方法,光一个二次探测完全不够说明问题。这本书讲的就是:流行的选择是F(i)=i^2.
发表于 2017-12-04 18:55:38 回复(0)