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
时间: 2024-04-21 10:26:09 浏览: 200
首先,我们根据散列函数将关键字散列到对应的槽中:
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 是正确答案。
相关问题
9.设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链接法构造散列表,散列函数为H(key)=key MOD 13,散列地址为1的链中有()个记录。
首先,按照散列函数将每个关键字映射到散列表中的位置,得到以下结果:
|位置|关键字|
|---|---|
|0|14|
|1|1 -> 27|
|2|19|
|3|55|
|4|20|
|5|11|
|6|23|
|7|68|
|8|84|
|9||
|10|10|
|11|79|
|12|
其中,散列地址为1的链中有2个记录,即1和27。
设有一组关键字{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
这样,我们就成功地构造出了一个散列表,其中每个关键字都被正确地插入到了对应的散列地址处。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)