设哈希表长为m=13,散列函数为H(k)=k mod 11,关键字序列为5,7,16,12,11,21,31,51,17,81;试求:散列后的表中关键字分布(假定解决冲突的方法为线性探测再散列法);求

散列后的表中关键字分布如下：

| 槽位 | 关键字 |
| --- | --- |
| 0 | 16 |
| 1 | 81 |
| 2 | 7 |
| 3 | 11 |
| 4 | 12 |
| 5 | 51 |
| 6 | 17 |
| 7 | 5 |
| 8 | 21 |
| 9 | 31 |
| 10 | - |
| 11 | - |
| 12 | - |

其中，槽位10, 11, 12因为线性探测再散列法造成的冲突，无法插入关键字，因此为空。

相关问题

4. (共15分)设哈希表长为m=13,散列函数为H(k)=k mod 11,关键字序列为5,7,16,12,11,21,31,51,17,81;试求:散列后的表中关键字分布(假定解决冲突的方法为线性探测再散列法);求平均查找长度ASL;计算

首先，将关键字序列散列到哈希表中，使用线性探测再散列法解决冲突：

|位置|关键字|
|---|---|
|0|17|
|1|81|
|2|11|
|3|31|
|4|12|
|5|5|
|6|16|
|7|7|
|8|51|
|9|21|
|10||
|11||
|12||

其中，第10个位置发生了冲突，需要再散列。由于哈希表长为13，因此再散列的散列函数为H'(k) = k mod 13。将10号位置的关键字再次散列：

|位置|关键字|
|---|---|
|0|17|
|1|81|
|2|11|
|3|31|
|4|12|
|5|5|
|6|16|
|7|7|
|8|51|
|9|21|
|10|1|
|11||
|12||

现在所有关键字都能够插入到哈希表中了。关键字分布如下：

|位置|关键字|
|---|---|
|0|17|
|1|81|
|2|11|
|3|31|
|4|12|
|5|5|
|6|16|
|7|7|
|8|51|
|9|21|
|10|1|
|11|16|
|12|31|

平均查找长度ASL的计算公式为：ASL = (查找成功的关键字的比较次数之和 + 查找失败的关键字的比较次数之和) / 关键字总数。

对于查找成功的关键字，比较次数为1，因此查找成功的关键字的比较次数之和为：1+1+1+1+1+1+1+1+1+1 = 10。

对于查找失败的关键字，需要按照散列函数和线性探测的规则进行查找，直到找到空位置或者找到该关键字。因此，查找失败的关键字的比较次数之和为：

- 16：1（位置6）+1（位置7）+1（位置8）+1（位置9）+1（位置10）= 5
- 51：1（位置8）+1（位置9）+1（位置10）+1（位置11）+1（位置12）= 5

因此，查找失败的关键字的比较次数之和为10。

综上，ASL = (10 + 10) / 10 = 2。

已知关键字序列为：（75, 33, 52, 41, 12, 88, 66, 27）哈希表长为10，哈希函数为： H(k)=K MOD 7, 解决冲突用线性探测再散列法，构造哈希表，求等概率下查找成功的平均查找长度。

首先，我们需要用哈希函数将关键字映射到哈希表中的位置。根据题目给定的哈希函数，得到以下结果：

- 75 → H(75) = 75 mod 7 = 3
- 33 → H(33) = 33 mod 7 = 5
- 52 → H(52) = 52 mod 7 = 3 （冲突，需要线性探测）
- 41 → H(41) = 41 mod 7 = 6
- 12 → H(12) = 12 mod 7 = 5 （冲突，需要线性探测）
- 88 → H(88) = 88 mod 7 = 4
- 66 → H(66) = 66 mod 7 = 3 （冲突，需要线性探测）
- 27 → H(27) = 27 mod 7 = 6 （冲突，需要线性探测）

接下来，我们使用线性探测再散列法来解决冲突。具体方法是，当发生冲突时，在哈希表中查找下一个可用位置，直到找到一个空闲位置为止。在这个例子中，我们得到以下哈希表：

| 位置 | 关键字 |
| ---- | ------ |
| 0 | |
| 1 | |
| 2 | |
| 3 | 75 |
| 4 | 88 |
| 5 | 33 |
| 6 | 52 |
| 7 | 41 |
| 8 | 12 |
| 9 | 27 |

接下来，我们可以计算等概率下查找成功的平均查找长度。假设哈希表中有n个关键字，每个位置被查找的概率相等，即为1/n。设查找成功的平均查找长度为ASL，那么：

ASL = (1/n) * (1 + 2 + ... + n-1 + n/m)

其中，m为哈希表长度，n为关键字个数。在这个例子中，m=10，n=8，因此：

ASL = (1/8) * (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8/10)
= 4.375

因此，等概率下查找成功的平均查找长度为4.375。