首页 > 试题广场 >

设哈希表长 M=14,哈希函数 H(key)=key mod

[单选题]
设哈希表长 M=14,哈希函数 H(key)=key mod 11,表中已有 4 个元素,其关键字分别是 4、27、61、84,如果用二次探测再散列处理冲突,关键字为 49 的结点的地址是( )
  • 9
  • 8
  • 3
  • 2
初始用4mod11=4,27mod11=5,61mod11=6,84mod11=7,所以哈希表目前的状态是: 
4  5  6  7 
4  27  61  84
二次探测再散列,又叫平方探测再散列。例如所给值49mod11=5,现在5的位置上已有值,所以查找5+1^2=6的位置,6也有值,查找5-1^2=4的位置,4有值,查找5+2^2=9的位置,9为空,所以49放置在9的位置上
如果9不为空,则查找依次查找如下位置:5-2^2,5+3^2...
发表于 2018-12-09 15:04:27 回复(1)
得到的哈希表:
4个元素只探测了一次,最后插入的49探测了4次
49%11=5,冲突
(5+1)%14=6,冲突
(5-1)%14=4,冲突
(5+4)%14=9,成功插入

其中有9个地址对应数据为空,只需比较一次;
地址4处查找3次,(4,5,3)
地址5处查找5次,(5,6,4,9,1)
地址6处查找4次,(6,7,5,10)
地址7处查找2次,(7,8)
地址9处查找2次,(9,10)
编辑于 2021-04-06 23:46:54 回复(0)
选A

发表于 2020-07-15 11:15:46 回复(0)
查找成功的平均查找长度ASL=(1+1+1+1+4)/5=1.6
解析:4、27、61、84的比较次数都为1次,(4个数字地址都不冲突,所以每个数字都只比较1次)
49一共比较4次(地址5、6、4、9共4次)

查找失败的平均查找长度ASL=3
首先表长为14.地址为0-13
0-2都为空,所以失败次数共为3次
从3开始到下次为空查找失败的比较次数为(3一次,4一次,5一次,6一次,7一次、8一次,9一次,10一次,10地址为空失败,停止)共8次
从4开始到下次为空查找失败的比较次数为(4一次、5一次、6一次、7一次、8一次、9一次、10一次)共7次
同理从5开始(5,6,7,8,9,10)共6次
6(678910)5次
7(78910)4次
8 3次
9 2次
10-13都为1次,共4次
所以查找失败的ASL=(3+8+7+6+5+4+3+2+4)/14(14个地址)=3

如有错误请指正!虚心学习
发表于 2019-11-12 22:51:41 回复(0)