">

">

如题图所示长度为13的散列表,其散列函数为H(key)=key mod 13,在表中已填入键值分别为16,30,54的元素。
(1)现要插入键值为29的元素,应用二次探测法,计算填入散列表中单元的序号。(要求给出求解过程)
(2)二次探测法有什么缺点?

如题图所示长度为13的散列表,其散列函数为H(key)=key mod 13,在表中已填入键值分别为16,30,54的元素。
(1)现要插入键值为29的元素,应用二次探测法,计算填入散列表中单元的序号。(要求给出求解过程)
(2)二次探测法有什么缺点?


【正确答案】:(1)H(29)=29mod13=3,地址3已有键值为16的元素,产生冲突。当发生冲突时,应用二次探测法,得到下一个地址d₁=(3+1²)mod13=4仍冲突,则再求下一个地址d₂=(3-1²)mod13=2仍冲突,直到散列地址为d₃=(3+2²)mod13=7时其位置上没有元素,则元素填入散列表中序号为7的位置。
(2)不易探测到整个散列表的所有空间。
Top