NOIP一题选择题求讲解2002年初中组19.设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key%13,其中%是求余数运算.用线性探查法解决冲突,则对于序列(2,8,31,20,19,18,53,27)中,18应该放在第几号格中?
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/30 00:23:21
![NOIP一题选择题求讲解2002年初中组19.设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key%13,其中%是求余数运算.用线性探查法解决冲突,则对于序列(2,8,31,20,19,18,53,27)中,18应该放在第几号格中?](/uploads/image/z/10293821-53-1.jpg?t=NOIP%E4%B8%80%E9%A2%98%E9%80%89%E6%8B%A9%E9%A2%98%E6%B1%82%E8%AE%B2%E8%A7%A32002%E5%B9%B4%E5%88%9D%E4%B8%AD%E7%BB%8419.%E8%AE%BE%E6%9C%89%E4%B8%80%E4%B8%AA%E5%90%AB%E6%9C%8913%E4%B8%AA%E5%85%83%E7%B4%A0%E7%9A%84Hash%E8%A1%A8%280%7E12%29%2CHash%E5%87%BD%E6%95%B0%E6%98%AF%3AH%28key%29%3Dkey%2513%2C%E5%85%B6%E4%B8%AD%25%E6%98%AF%E6%B1%82%E4%BD%99%E6%95%B0%E8%BF%90%E7%AE%97.%E7%94%A8%E7%BA%BF%E6%80%A7%E6%8E%A2%E6%9F%A5%E6%B3%95%E8%A7%A3%E5%86%B3%E5%86%B2%E7%AA%81%2C%E5%88%99%E5%AF%B9%E4%BA%8E%E5%BA%8F%E5%88%97%282%2C8%2C31%2C20%2C19%2C18%2C53%2C27%29%E4%B8%AD%2C18%E5%BA%94%E8%AF%A5%E6%94%BE%E5%9C%A8%E7%AC%AC%E5%87%A0%E5%8F%B7%E6%A0%BC%E4%B8%AD%3F)
NOIP一题选择题求讲解2002年初中组19.设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key%13,其中%是求余数运算.用线性探查法解决冲突,则对于序列(2,8,31,20,19,18,53,27)中,18应该放在第几号格中?
NOIP一题选择题求讲解
2002年初中组19.设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key%13,其中%是求余数运算.用线性探查法解决冲突,则对于序列(2,8,31,20,19,18,53,27)中,18应该放在第几号格中?
A、5
B、9
C、4
D、0
NOIP一题选择题求讲解2002年初中组19.设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key%13,其中%是求余数运算.用线性探查法解决冲突,则对于序列(2,8,31,20,19,18,53,27)中,18应该放在第几号格中?
线性探查法基本思想是:将散列表T[0..m-1]看成是一个循环向量,若初始探查的地址为d(即h(key)=d),则最长的探查序列为:
d,d+l,d+2,…,m-1,0,1,…,d-1
即:探查时从地址d开始,首先探查T[d],然后依次探查T[d+1],…,直到T[m-1],此后又循环到T[0],T[1],…,直到探查到T[d-1]为止.
探查过程终止于三种情况:
(1)若当前探查的单元为空,则表示查找失败(若是插入则将key写入其中);
(2)若当前探查的单元中含有key,则查找成功,但对于插入意味着失败;
(3)若探查到T[d-1]时仍未发现空单元也未找到key,则无论是查找还是插入均意味着失败(此时表满).