9.设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链接法构造散列表,散列函数为H(key)=key MOD 13,散列地址为1的链中有()个记录。
时间: 2024-05-20 09:15:19 浏览: 17
将关键字用散列函数H(key)=key MOD 13计算散列地址,得到的散列地址如下:
| key | H(key) |
| --- | --- |
| 19 | 6 |
| 14 | 1 |
| 23 | 10 |
| 1 | 1 |
| 68 | 5 |
| 20 | 7 |
| 84 | 4 |
| 27 | 1 |
| 55 | 3 |
| 11 | 11 |
| 10 | 10 |
| 79 | 12 |
其中,散列地址为1的链中有3个记录,即14、1、27。
相关问题
9.设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链地址法构造散列表,散列函数为H(key)=key MOD 13,散列地址为1的链中有( )个记录。 A.1 B. 2 C. 3 D. 4
首先,我们根据散列函数将关键字散列到对应的槽中:
0: 14
1: 1 -> 27
2: 55
3: 23
4:
5: 19 -> 84
6: 20
7:
8: 68
9: 10 -> 79
10: 11
11:
12:
可以看出散列地址为1的链中有两个记录,即1和27,所以选项B. 2 是正确答案。
设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用散列函数H(key)=key%13,采用开放地址法的二次探测再散列方法解决冲突,试在0~18的散列地址空间中对该关键字序列构造散列表。
好的,让我来回答你的问题。
根据题目中所给的关键字和散列函数,我们可以得到以下散列地址:
- 19 -> 6
- 01 -> 1
- 23 -> 10
- 14 -> 1
- 55 -> 3
- 20 -> 7
- 84 -> 11
- 27 -> 1
- 68 -> 4
- 11 -> 11
- 10 -> 10
- 77 -> 5
其中,关键字14和27的散列地址与关键字01相同,发生了冲突。我们可以采用开放地址法中的二次探测再散列方法解决冲突。具体地,如果第一次散列地址为h,冲突解决的第i步散列地址为:
$h_i = (h + c_1i + c_2i^2) \mod m$
其中,c1和c2是正整数,m是散列表的大小。
在本题中,我们可以取c1=1,c2=3,m=13。则,关键字14的散列地址为2,关键字27的散列地址为12。最终的散列表如下:
- 0:
- 1: 01
- 2: 14
- 3: 55
- 4: 68
- 5: 77
- 6: 19
- 7: 20
- 8:
- 9: 23
- 10: 10
- 11: 84, 11
- 12: 27
这样,我们就成功地构造出了一个散列表,其中每个关键字都被正确地插入到了对应的散列地址处。