对于输入30,20,56,75,31,19和散列函数 h ( K )=Kmod11,做以下练习。 a .构造它们的开散列表。 b .求在本表中成功查找的最大键值比较次数。 c .求在本表中成功查找的平均键值比较次数。
时间: 2024-05-27 14:09:17 浏览: 19
a. 首先根据散列函数将数值映射到散列表的桶中:
| 桶 | 值 |
|---|---|
| 0 | |
| 1 | 31|
| 2 | 20|
| 3 | 75|
| 4 | 56|
| 5 | |
| 6 | |
| 7 | |
| 8 | 19|
| 9 | |
| 10| 30|
b. 成功查找的最大键值比较次数取决于查找的元素在散列表中的位置。在本例中,最大键值比较次数为3,对应查找元素31。
c. 成功查找的平均键值比较次数可以通过以下公式计算:
$Ave=\frac{1}{n}\sum_{i=1}^{n}c_i$
其中,$n$为散列表中元素的总数,$c_i$为查找第$i$个元素时所需的键值比较次数。
在本例中,$n=6$。
对于每个元素,它的键值比较次数等于它所在桶中元素的个数。因此,$c_1=0$, $c_2=1$, $c_3=1$, $c_4=1$, $c_5=0$, $c_6=0$。
将$c_i$代入公式得到:
$Ave=\frac{1}{6}(0+1+1+1+0+0)=\frac{3}{6}=0.5$
因此,在本表中成功查找的平均键值比较次数为0.5。
相关问题
对于输入30,20,56,75,31,19和散列函数h(k)=k mod 11 构造它们的闭散列表(没有元素的位置请写NULL) 0 1 2 3 4 5 6 7 8 9 10
首先,根据散列函数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。
相关推荐
![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)