假定有k个关键字互为同义词,若用线性探测再散列法把这k个关键字存入散列表中,至少要进行____次探测.

k2pd 1年前 已收到3个回答 举报

朋友的约会 幼苗

共回答了15个问题采纳率:80% 举报

至少需要 1 + 2 + ...+ k-1 = k(k-1)/2 次探测.
解析:在Hash表中存入第一个同义关键字后,后面至少连续有k-1个单元为空,则按线性探测再散列法可依次存入剩余的k-1个关键字,这样探测次数最少.

1年前

3

岭野 幼苗

共回答了2个问题 举报

k(k-1)/2
散列表的查找过程和建表过程类似。假设给定的值为K,根据建表时设定的散列函数H,计算出散列地址H(K),若表中该地址对应的空间未被占用,则查找失败,否则将该地址中的值与K比较,若相等则查找成功,否则按建表时设定的处理冲突方法找下一个地址,如此反复下去,直到某个地址空间未被占用(查找失败)或者关键字比较相等(查找成功)为止。
此处的查找就可以看成探测,固由以上结论得1...

1年前

1

pigtails 幼苗

共回答了1个问题 举报

K(K+1)/2
其实就是1+2+3+4+......+K
每次存入关键字的时候都要探测的,只是如果冲突,再继续探测。

1年前

0
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 18 q. 0.030 s. - webmaster@yulucn.com