首页 > 试题广场 >

(二次探测)假设要在一个散列表(表中的各个位置为0,1,..

[问答题]
(二次探测)假设要在一个散列表(表中的各个位置为0,1,...,m-1)中查找关键字k,并假设有一个散列函数h将关键字空间映射到集合{0,1,...,m-1}上,查找办法如下:
1.计算值j=h(k),置i=0。
2.探查要找的关键字k的位置j,或者找到了,或者该位置为空,并结束查找。
3.置i=i+1.如果i=m,则表已满,于是终止探查;否则,设j=(i+j)mod m,返回到步骤2.
    假设m是2的幂。
a.通过给出下面等式中c1和c2的适当值,来证明该方案是一般的“二次探查”法的一个实例。
                          
b.证明:在最坏情况下,这个算法要检查表中的每一个位置。

这道题你会答吗?花几分钟告诉大家答案吧!