假定有一个 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|

希望以上能帮到你，有什么问题可以随时向我提出。

. 算法设计题 已知待散列的线性表为（45，16，40，69，23，33，48，96，13，38），散列用的一维地址空间为[0..12]，假定选用的散列函数是H(K)= K mod 7，若发生冲突采用链地址法处理。（1）图形化展示线性表在散列表中的数据布局。（2）假设每一个元素的查找概率相等，求该散列表的平均查找长度。

(1) 线性表在散列表中的数据布局如下：

0：
1： 38 -> 16
2： 33 -> 69 -> 23
3：
4： 45 -> 48
5： 40 -> 96
6： 13

(2) 平均查找长度的计算公式为：ASL = (n + sum(len[i])) / n，其中n为关键字个数，len[i]为第i个链表的长度。
根据散列函数H(K)= K mod 7，每个元素的散列地址为：

45： 3
16： 2
40： 5
69： 2
23： 2
33： 2
48： 6
96： 5
13： 6
38： 3

根据散列地址将元素插入散列表中，得到的链表长度为：

0： 0
1： 2
2： 4
3： 2
4： 2
5： 2
6： 2

因此，平均查找长度ASL = (10 + 14) / 10 = 2.4。