将键值key分别为{16,74,60,43,54,90,46,31,29,88,77}的记录存入哈希表A[0..12],哈希函数为H(k)=key%13,采用线性探查法解决冲突。画出所有记录存放在哈希表A中位置的示意图(或写出表示上述序列关键字存放位置的哈希地址序列)。
时间: 2023-09-17 13:12:52 浏览: 48
好的,我来给你解答这个问题。
根据哈希函数 $H(k)=key\%13$,我们可以计算出每个记录的哈希地址:
| key | H(key) |
| ---- | ------ |
| 16 | 3 |
| 74 | 11 |
| 60 | 8 |
| 43 | 4 |
| 54 | 2 |
| 90 | 0 |
| 46 | 7 |
| 31 | 5 |
| 29 | 3 |
| 88 | 1 |
| 77 | 11 |
其中,哈希地址冲突的有两组:{16, 29} 和 {74, 77}。
按照线性探查法,我们将第一个哈希地址为 $i$ 的记录存入哈希表的位置 $A[i]$,如果 $A[i]$ 已经被占用,则继续往下找,直到找到一个空闲位置为止。因此,我们可以按照如下的方式将这些记录存入哈希表中:
| A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] | A[8] | A[9] | A[10] | A[11] | A[12] |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- | ----- | ----- |
| 90 | 88 | 54 | 16 | 43 | 31 | 46 | 29 | 60 | 77 | 74 | | |
最终的哈希表中,这些记录的存放位置示意图如下:
```
0 1 2 3 4 5 6 7 8 9 10 11 12
+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 90| 88| 54| 16| 43| 31| 46| 29| 60| 77| 74| | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
```