| 查看: 967 | 回复: 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的地址查找。明明计算查找成功的长度时，就已经向后查找了，为什么不成功时就不能向后查找。 小弟初来乍到，请各位大神教我！小弟先谢过了！ |
回复此楼» 猜你喜欢
284求调剂
已经有10人回复
-
一志愿山东大学药学学硕求调剂
已经有4人回复
-
07化学280分求调剂
已经有4人回复
-
298-一志愿中国农业大学-求调剂
已经有12人回复
-
求材料，环境专业调剂
已经有3人回复
-
335求调剂
已经有5人回复
-
求调剂
已经有7人回复
-
一志愿吉大化学322求调剂
已经有4人回复
-
环境学硕288求调剂
已经有8人回复
-
341求调剂(一志愿湖南大学070300)
已经有6人回复
