假定有一个 7 个槽的散列表(槽从 0 到 6 编号)。如果使用散列函数 h(k) = k mod 7 和线性探查,作用于一组数字 3、12、9、2,给出每次插入数字后的散列表。在插入值为 2 的关键码后,列出每一个空槽作为下一个被填充槽的概率。
时间: 2023-06-06 19:06:57 浏览: 173
我理解了你的问题。这是一个计算题,很容易回答。以下是每次插入数字后的散列表:
1. 插入数字 3:[3, _, _, _, _, _, _]
2. 插入数字 12:[3, _, 12, _, _, _, _]
3. 插入数字 9:[3, 9, 12, _, _, _, _]
4. 插入数字 2:[3, 9, 12, 2, _, _, _]
在插入值为2的关键码后,空槽作为下一个被填充槽的概率分别是:
1. 槽4的概率为1/7,因为它是唯一一个空槽。
2. 其他槽的概率都为0。
希望我的回答对你有所帮助。
相关问题
假定有一个 7 个槽的散列表(槽从 0 到 6 编号)。如果使用散列函数 h(k) = k mod 7 和线性探查,在插入值为 3、12、9、2 的关键码后,列出每一个空槽作为下一个被填充槽的概率。并给出理由
散列表的大小为7,散列函数h(k) = k mod 7。在线性探查法下,依次插入关键码3, 12, 9, 2。
在插入3时,h(3) = 3 mod 7,3被存放在槽3。此时槽0、槽1、槽2、槽4、槽5、槽6均为空。
在插入12时,h(12) = 12 mod 7,12被存放在槽5。此时槽0、槽1、槽2、槽4、槽6均为空,槽3中有3,槽5中有12。
在插入9时,h(9) = 9 mod 7,9被存放在槽2。此时槽0、槽1、槽4、槽6均为空,槽3中有3,槽5中有12,槽2中有9。
在插入2时,h(2) = 2 mod 7,2被存放在槽2(发生了冲突,进行线性探查,先检查槽3,槽3已被占用,继续检查槽4,槽4为空,2被存放在槽4)。此时槽0、槽1、槽6均为空,槽3中有3,槽5中有12,槽2中有9,槽4中有2。
因此,下一个被填充的空槽分别为:
槽0:填充的概率为0,因为哈希函数h(k)对10取模所得的值为0的元素不可能再被填充进散列表。
槽1:填充的概率为0,因为哈希函数h(k)对10取模所得的值为1的元素不可能再被填充进散列表。
槽2:填充的概率为1/7,因为要填充到槽2的元素只有9和2,但是2已经占用了槽4,因此只有9能够填充到槽2。
槽3:填充的概率为0,因为槽3已经被填充了。
槽4:填充的概率为1/7,因为要填充到槽4的元素只有2,但是2已经占用了槽4,因此概率为1/7。
槽5:填充的概率为0,因为槽5已经被填充了。
槽6:填充的概率为0,因为哈希函数h(k)对10取模所得的值为6的元素不可能再被填充进散列表。
理由如上。
假定有一个 7 个槽的散列表(槽从 0 到 6 编号)。如果使用散列函数 h(k) = k mod 7 和线性探查,作用于一组数字 3、12、9、2,给出每次插入数字后的散列表,并给出示意图
好的,我理解了你的要求。下面是对于给定数字的插入过程中的散列表和示意图:
1. 插入数字 3:
散列表:
[ , , , , , ,3]
0 1 2 3 4 5 6
示意图:
| | | | | | |3|
|0 |1 |2 |3 |4 |5 |6|
2. 插入数字 12:
散列表:
[ , ,12, , , ,3]
0 1 2 3 4 5 6
示意图:
| | |12| | | |3|
|0 |1 |2 |3 |4 |5 |6|
3. 插入数字 9:
散列表:
[ ,9,12, , , ,3]
0 1 2 3 4 5 6
示意图:
| |9 |12| | | |3|
|0 |1 |2 |3 |4 |5 |6|
4. 插入数字 2:
散列表:
[2,9,12, , , ,3]
0 1 2 3 4 5 6
示意图:
|2 |9 |12| | | |3|
|0 |1 |2 |3 |4 |5 |6|
希望以上能帮到你,有什么问题可以随时向我提出。
相关推荐
![sh](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)