| 查看: 944 | 回复: 0 | ||
[求助]
关于哈希查找不成功的查找长度的一道题
|
|
2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。 将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为： H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。 (1) 请画出所构造的散列表。 (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 查找不成功的查找长度，百度上给出的解法是： 等概率情况下查找不成功的平均查找长度： 接下来讨论不成功的情况, 看表2，计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可， 但根据哈希函数地址为MOD7，因此初始只可能在0~6的位置。等概率情况下，查找0~6位置查找失败的查找次数为： 看地址0，到第一个关键字为空的地址2的距离为3，因此查找不成功的次数为3. 地址1， 到第一个关键为空的地址2的距离为2，因此查找不成功的次数为2. 地址2， 到第一个关键为空的地址2的距离为1，因此查找不成功的次数为1. 地址3，到第一个关键为空的地址4的距离为2，因此查找不成功的次数为2. 地址4，到第一个关键为空的地址4的距离为1，因此查找不成功的次数为1. 地址5，到第一个关键为空的地址2(注意不是地址9，因为初始只可能在0~6之间，因此循环回去)的距离为5，因此查找不成功的次数为5. 地址6，到第一个关键为空的地址2(注意不是地址9，因为初始只可能在0~6之间，因此循环回去)的距离为4，因此查找不成功的次数为4. 因此查找不成功的次数表如下表所示 Key 7 8 30 11 18 9 14 Count 3 2 1 2 1 5 4 (表4) 所以ASLunsuccess= （3+2+1+2+1+5+4）/ 7 = 18/7。 我能够理解初始在0至6的地址，但是为什么查找不成功时，只能在0至6的地址上查找，而不能继续向高于6的地址查找。明明计算查找成功的长度时，就已经向后查找了，为什么不成功时就不能向后查找。 小弟初来乍到，请各位大神教我！小弟先谢过了！ |
回复此楼» 猜你喜欢
博士申请都是内定的吗？
已经有13人回复
-
谈谈两天一夜的“延安行”
已经有8人回复
-
氨基封端PDMS和HDI反应快速固化
已经有11人回复
-
之前让一硕士生水了7个发明专利，现在这7个获批发明专利的维护费可从哪儿支出哈？
已经有11人回复
-
论文投稿求助
已经有4人回复
-
Applied Surface Science 这个期刊。有哪位虫友投过的能把word模板发给我参考一下嘛
已经有3人回复
-
投稿精细化工
已经有6人回复
