现有长度为11且初始为空的散列表HT,散列函数是H(key)=key%7,采用线性探查(线性探测再散列)法解决冲突将关键字序列87,40,30,6,11,22,98,20依次插入到HT后,HT查找失败的平均查找长度是
A. 4
B. 5.25
C. 6
D. 6.29
散列表的比较次数,和探测次数,是相同还是相差1?谢谢
1. 构造散列表 根据散列函数 H(key) = key %7 以及线性再探测,构造出散列表,如下图
2. 计算失败的平均查找长度
计算失败,可以转换理解,就是在已经构造好的散列表上,我们再去插入一个新的值需要比较多少次。
比如,现在我再插入一个数 21,那么理论上应该存放在地址 0 的位置,但是地址 0 有 98 了,则我们线性再探测(就是依次增加一个地址,看是否为空,空则可以插入),同理地址 1 也存在元素。以此类推,我们一共要比较地址 0~7,发现都有值,直到比较地址 8 才为空。所以一共比较了 9 次。
对其他地址(0~6)用同样的方式去理解,则一共比较的次数是 9+8+7+6+5+4+3 = 42
这里要注意,因为我们的模是 7,所以计算的地址只可能在(0~6)这个范围,所以最后的结果是 42/7 =6
3.计算成功的平均查找长度 计算成功的长度,就是记录下每个数值比较了几次找到可存储的空间。 比如,本题每个数值比较(并存入)对应地址的次数如下图。
所以其 ASL = 1+1+1+1+1+1+1+1/8=1
note 1.注意失败与成功的查找长度的分母意义是不同的,失败时,分母是模的值;成功时,分母是元素个数。
西瓜不腻 回复 13245372484: 请问查找成功时,查找20是不是要2次啊
huyufeu1009 回复 西瓜不腻: 我感觉也是,求解答
方法一:推理
我们先构造出插...
用户登录可进行刷题及查看答案
我们先构造出插入所有元素后的散列表。
一般我们说计算成功查找长度需要统计的情况数量为散列表中元素数量。计算失败查找长度需要统计的情况数量为散列表中槽位数量。
但是这里命题组挖坑了,散列函数式模7的,但是散列表的长度为11,实际上剩下的4个槽位是永远不可能散列到的。也就是这里计算失败查找长度需要统计的情况数量为散列函数中是模数。
可以计算出0-6号槽位的失败需要探测的次数,如下图所示。
本题选C。
方法二:观察选项
下面提供秒题解法:
观察选项,C和D中整数部分均为6,二选一,正确概率50%。
个人偏向凑整,因为命题组编写题目的时候数字都是凑好的,算出小数点你不慌吗?
登录后提交答案