设散列表的地址空间为0到10,散列函数为h(k)=k modll,用线性探查法解决碰撞。现从空的散列表开始,依次插入关键码值95,14,27,68,82,则最后—个关键码82的地址为:

admin2009-01-19  36

问题 设散列表的地址空间为0到10,散列函数为h(k)=k modll,用线性探查法解决碰撞。现从空的散列表开始,依次插入关键码值95,14,27,68,82,则最后—个关键码82的地址为:

选项 A、4
B、5
C、6
D、7

答案4

解析 本题是对散列表存储问题的考查。散列表的基本思想是:由结点的关键码值决定结点的存储地址,即以关键码值k为自变量,通过一定的函数关系h(称为散列函数),计算出对应的函数值h(k)来,把这个值解释为结点的存储地址,将结点存入该地址中。在散列表中,不同的关键码值可能对应到同一存储地址,这种现象叫碰撞,处理碰撞基本有两种方法:拉链法和线性探索法。在本题中,所采用的散列函数为h(k)=kmod11,用线性探查法解决碰撞。计算顺序如下:①h(95)=95modll=7,存在地址为7的位置;②h(14)=14modll=3,存在地址为3的位置;③h(27)=27modll=5,存在地址为5的位置;④h(68)=68modll=2,存在地址为2的位置;⑤h(82)=82modll=5,与关键码为27的存储位置发生碰撞,采用线性探索的方法解决,即将82存在5以后的首个开放位置,在本题中即为6,所以82存在地址为6的位置。因此本题正确答案为选项C。
转载请注明原文地址:https://kaotiyun.com/show/QlcZ777K
0

相关试题推荐
最新回复(0)