现有长度为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
N诺智能批改可自动批改答案并给出反馈,每次使用将消耗 1个诺币
您当前的诺币数量: 个
N诺正在智能批改,预计需要30秒,请稍候...
散列表的比较次数,和探测次数,是相同还是相差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 回复 西瓜不腻: 我感觉也是,求解答
小灰机 回复 13245372484: 为什么查找失败最后没有加2?反而只是到3?
方法一:推理
我们先构造出插...
登录后提交答案