问题
单项选择题
设散列表的地址空间为0到10,散列函数为h(k)=k mod 11,用线性探查法解决碰撞。现从空的散列表开始,依次插入关键码值95,14,27,68,82,则最后一个关键码 82的地址为( )。
A.4
B.5
C.6
D.7
答案
参考答案:C
解析:
用线性探查法处理碰撞就是当碰撞发生时形成一个探查序列,沿着这个序列逐个地址探查,直到找到一个开放的地址(即未被占用的单元),将发生碰撞的关键码放入该地址中。即若发生碰撞的地址为d,则探查的地址序列为:
d+1, d+2…,m-1,0,1,…,d-1
其中m是散列表存储区域的大小。
依题意即处理方法,95 mod 11=7,故关键码95存储于地址7; 14 mod 11=3,故关键码14存储于地址3,27 mod 11=5,故关键码 27存储于地址13;68 mod 11=2,故关键码68存储在地址2;82 mod 11=6,故关键码82存储于地址6中。各关键码存储地址如下表。
地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Key | 68 | 14 | 27 | 82 | 95 |