已知键值序列{11,2,13,26,5,18,4,9},设散列表表长为13,散列函数H(key)=key mod 13,处理冲突的方法为线性探测法,请给出散列表。

已知键值序列{11,2,13,26,5,18,4,9},设散列表表长为13,散列函数H(key)=key mod 13,处理冲突的方法为线性探测法,请给出散列表。


【正确答案】:



【题目解析】:

应用线性探测法解决冲突时,是在散列函数H得出的地址基础上+1,若仍然冲突,继续找+2的地址,直到不冲突为止。

首先根据散列函数计算散列地址:
H(11)=11,H(2)=2,H(13)=0,H(26)=0,H(5)=5,H(18)=5,H(4)=4,H(9)=9。
可以将关键字11,2,13,5,4,9分别插入到开放地址11、2、0、5、4、9中。
剩余关键字26和18。
当插入关键字26时,地址0已经被关键字13占用,于是探查地址1,未被占用,故将26插入地址1。
当插入关键字18时,地址5已经被关键字5占用,于是探查地址6,未被占用,故将18插入地址6。


Top