设散列函数H(K)=3K%11,散列地址[1]空间为0~10，对关键字序列(32,13,49,24,38,21,4,12)，按下述两种解决冲突的方法构造散列表，并分别求出等概率下查找成功时和查找失败时的平均查找长度[2]ASLsucc和ASLunsucc。(1)线性探测法;(2)链地址法。
设散列函数H(K)=3K%11,散列地址[1]空间为0~10，对关键字序列(32,13,49,24,38,21,4,12)，按下述两种解决冲突的方法构造散列表，并分别求出等概率下查找成功时和查找失败时的平均查找长度[2]ASLsucc和ASLunsucc。
(1)线性探测法;
(2)链地址法。
题目解答
答案
(1) 线性探测法：
线性探测法是一种解决冲突的方法，当发生冲突时，线性探测法会逐个探测下一个可用的散列地址，直到找到空槽或者遍历完整个散列表。
首先，我们创建一个大小为11的散列表，并初始化所有槽位为空。
关键字序列为 (32, 13, 49, 24, 38, 21, 4, 12)。
按照散列函数 H(K) = 3K % 11，将关键字插入散列表中。
步骤如下：
1. 插入关键字 32：
- 计算散列地址：H(32) = 3 * 32 % 11 = 9
- 槽位9为空，插入关键字 32。
2. 插入关键字 13：
- 计算散列地址：H(13) = 3 * 13 % 11 = 7
- 槽位7为空，插入关键字 13。
3. 插入关键字 49：
- 计算散列地址：H(49) = 3 * 49 % 11 = 4
- 槽位4为空，插入关键字 49。
4. 插入关键字 24：
- 计算散列地址：H(24) = 3 * 24 % 11 = 10
- 槽位10为空，插入关键字 24。
5. 插入关键字 38：
- 计算散列地址：H(38) = 3 * 38 % 11 = 4
- 发生冲突，线性探测下一个槽位。
- 计算下一个散列地址：H(38) + 1 = 4 + 1 = 5
- 槽位5为空，插入关键字 38。
6. 插入关键字 21：
- 计算散列地址：H(21) = 3 * 21 % 11 = 9
- 发生冲突，线性探测下一个槽位。
- 计算下一个散列地址：H(21) + 1 = 9 + 1 = 10
- 发生冲突，线性探测下一个槽位。
- 计算下一个散列地址：H(21) + 2 = 9 + 2 = 0
- 槽位0为空，插入关键字 21。
7. 插入关键字 4：
- 计算散列地址：H(4) = 3 * 4 % 11 = 1
- 槽位1为空，插入关键字 4。
8. 插入关键字 12：
- 计算散列地址：H(12) = 3 * 12 % 11 = 3
- 槽位3为空，插入关键字 12。
插入完成后的散列表如下：
```
[ _, 4, _, 12, _, 38, _, 13, _, 32, 24 ]
```
对于查找成功时的平均查找长度（ASLsucc）和查找失败时的平均查找长度（ASLunsucc），我们需要根据散列表中的元素和散列函数进行计算。在线性探测法中，ASLsucc 和 ASLunsucc 的计算公式如下：
ASLsucc = (查找成功时的平均查找长度)
= (查找成功时的查找长度之和) / (查找成功的关键字个数)
ASLunsucc = (查找失败时的平均查找长度)
= (查找失败时的查找长度之和) / (查找失败的关键字个数)
在这个例子中，我们需要对关键字序列进行查找并计算查找长度之和。
根据线性探测法，插入关键字时，如果发生冲突，会依次探测下一个槽位，直到找到空槽位。
查找成功时的查找长度之和 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8
查找失败时的查找长度之和 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36
查找成功的关键字个数 = 8
查找失败的关键字个数 = 0 （因为所有关键字都存在于散列表中）
ASLsucc = 查找成功时的查找长度之和 / 查找成功的关键字个数 = 8 / 8 = 1
ASLunsucc = 查找失败时的查找长度之和 / 查找失败的关键字个数 = 0 / 0 (未发生查找失败)
所以，线性探测法下的等概率下查找成功时的平均查找长度ASLsucc为1。
(2) 链地址法：
链地址法是一种解决冲突的方法，使用一个链表来存储散列到同一个槽位的所有关键字。
同样地，我们创建一个大小为11的散列表，并初始化所有槽位为空链表。
关键字序列为 (32, 13, 49, 24, 38, 21, 4, 12)。
按照散列函数 H(K) = 3K % 11，将关键字插入散列表中。
步骤如下：
1. 插入关键字 32：
- 计算散列地址：H(32) = 3 * 32 % 11 = 9
- 槽位9为空链表，插入关键字 32。
2. 插入关键字 13：
- 计算散列地址：H(13) = 3 * 13 % 11 = 7
- 槽位7为空链表，插入关键字 13。
3. 插入关键字 49：
- 计算散列地址：H(49) = 3 * 49 % 11 = 4
- 槽位4为空链表，插入关键字 49。
4. 插入关键字 24：
- 计算散列地址：H(24) = 3 * 24 % 11 = 10
- 槽位10为空链表，插入关键字 24。
5. 插入关键字 38：
- 计算散列地址：H(38) = 3 * 38 % 11 = 4
- 槽位4非空，将关键字 38 插入槽位4的链表末尾。
6. 插入关键字 21：
- 计算散列地址：H(21) = 3 * 21 % 11 =
7. 插入关键字 4：
- 计算散列地址：H(4) = 3 * 4 % 11 = 1
- 槽位1为空链表，插入关键字 4。
8. 插入关键字 12：
- 计算散列地址：H(12) = 3 * 12 % 11 = 3
- 槽位3为空链表，插入关键字 12。
插入完成后的散列表如下：
```
[ _, (4, 12), _, (13, 32), (21), (38), _, (49), _, _, (24) ]
```
其中括号内表示链表中的关键字。
对于链地址法，查找成功时的平均查找长度（ASLsucc）和查找失败时的平均查找长度（ASLunsucc）的计算如下：
ASLsucc = (查找成功时的平均查找长度)
= (查找成功时的查找长度之和) / (查找成功的关键字个数)
ASLunsucc = (查找失败时的平均查找长度)
= (查找失败时的查找长度之和) / (查找失败的关键字个数)
对于查找成功时的平均查找长度（ASLsucc）和查找失败时的平均查找长度（ASLunsucc），同样需要计算查找长度之和并除以关键字个数。
查找成功时的查找长度之和 = 2 + 2 + 2 + 2 + 1 + 1 + 2 + 2 = 14
查找失败时的查找长度之和 = 1 + 2 + 2 + 2 + 3 + 3 + 3 + 3 = 19
查找成功的关键字个数 = 8
查找失败的关键字个数 = 0 （因为所有关键字都存在于散列表中）
ASLsucc = 查找成功时的查找长度之和 / 查找成功的关键字个数 = 14 / 8 = 1.75
ASLunsucc = 查找失败时的查找长度之和 / 查找失败的关键字个数 = 0 / 0 (未发生查找失败)
所以，链地址法下的等概率下查找成功时的平均查找长度ASLsucc为1.75。