对于输入30,20,56,75,31,19和散列函数h(k)=k mod 11 构造它们的闭散列表(没有元素的位置请写NULL) 0 1 2 3 4 5 6 7 8 9 10
时间: 2024-03-31 10:37:23 浏览: 36
首先,根据散列函数h(k)=k mod 11,我们可以将输入的数字映射到0到10的整数范围内。然后,我们可以使用闭散列法(也叫拉链法)将它们插入到散列表中,如果发生冲突,则将它们放在同一个链表中。
下面是该算法的具体步骤:
1. 创建一个长度为11的散列表,每个位置都初始化为NULL。
2. 针对输入的每个数字,计算其散列值h(k)。
3. 将数字插入到散列表中对应的位置,如果该位置已经有元素,则将其放在该位置对应的链表的末尾。
4. 重复步骤2和3,直到所有数字都插入到散列表中。
按照上述算法,我们可以得到以下闭散列表:
0: 75
1: 20 -> NULL
2: NULL
3: 31
4: 56
5: NULL
6: NULL
7: NULL
8: 30
9: 19
10: NULL
其中,数字20和19发生了冲突,它们被放在了同一个链表中。
相关问题
对于输入30,20,56,75,31,19和散列函数h(K)=Kmod11,做以 a.构造它们的闭散列表。" b.求在本表中成功查找的最大键值比较次数。 c.求本表中成功查找的平均键值比较次数
a. 首先根据散列函数 h(K)=Kmod11,求出每个关键字的散列地址:
- h(30) = 8
- h(20) = 9
- h(56) = 1
- h(75) = 10
- h(31) = 9 (发生了冲突)
- h(19) = 8 (发生了冲突)
为了解决冲突,我们可以采用闭散列法,具体方法是将冲突的关键字放到散列表中的下一个空位置上(如果下一个位置也被占用,则继续往后找,直到找到一个空位置为止)。
- h(30) = 8
- h(20) = 9
- h(56) = 1
- h(75) = 10
- h(31) = 9 (放到下一个空位置,即位置10)
- h(19) = 8 (放到下一个空位置,即位置9)
最终得到的闭散列表为:
| 槽位 | 关键字 |
| --- | --- |
| 0 | |
| 1 | 56 |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | 30<br>19 |
| 9 | 20<br>31 |
| 10 | 75 |
b. 成功查找的最大键值比较次数取决于查找的关键字所在的槽位,因此最大键值比较次数为2(对应槽位8和9的关键字)。
c. 成功查找的平均键值比较次数可以通过所有成功查找的键值比较次数之和除以总的成功查找次数来计算。假设我们要查找的关键字是等概率地分布在各个槽位上的,则成功查找的概率为 $p=\frac{6}{11}$,失败查找的概率为 $q=1-p=\frac{5}{11}$。对于成功查找的情况,需要比较的键值次数为1或2,因此平均键值比较次数为:
$$\frac{1}{6}\cdot1+\frac{5}{6}\cdot\left(\frac{2}{6}\cdot1+\frac{4}{6}\cdot2\right)=\frac{11}{6}\approx1.83$$
因此,在本表中成功查找的平均键值比较次数为约1.83。
设散列表的长度为8,散列函数h(k)=kmod7
散列表的长度为8意味着散列表中有8个存储位置。散列函数h(k)=kmod7表示对关键字k进行取模运算并将结果作为存储位置的索引值。
具体来说,当我们向散列表中插入一个关键字时,我们首先对关键字进行散列函数计算,得到的结果为k对7取模的值。例如,如果关键字k=15,那么h(k)=15mod7=1,意味着关键字15会被存储在散列表的第1个位置上。
散列表的长度为8,散列函数h(k)=kmod7,意味着散列表中的存储位置索引值的范围是0到7。实际上,对于当前的散列函数和散列表长度,任意关键字经过散列函数计算后得到的结果都在0到6之间,这样就可以保证插入时能够找到对应的存储位置。
在使用散列函数h(k)=kmod7时,需要注意关键字的选择和散列表的大小,以保证散列函数计算的结果能够均匀地分布在散列表中,从而避免发生过多的冲突。当发生冲突时,可以采用开放定址法、链地址法等方法进行解决。
总而言之,散列表的长度为8,散列函数h(k)=kmod7,通过合理的关键字选择和冲突解决方法,可以有效地进行散列表的插入、查找和删除等操作。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)