已知一组初始记录关键字序列为（35,20,33,48,59,47,62,50,48)。其哈希函数为H（key)=key%13处理中突的方法为排地址 法。 试求：（1)画出哈希表。 （2)计算等概率查找时查找成功的平均查找长度。

(1) 哈希表：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ----- | --- | --- | --- | --- | ----- | --- | --- | ----- |
| | 35 | 33 | 62 | | 47,20 | | | 50,48 |
| | | | 48 | | 59 | | | |

(2) 计算等概率查找时查找成功的平均查找长度：

- 对于已经存储的记录：
- 35：在哈希表的位置0，平均查找长度为1。
- 20、33、47、48、50、59、62：在哈希表的位置5或8，平均查找长度为1。
- 对于不在哈希表中的记录：
- 34：哈希函数为H(34)=34%9=7，但位置7为空，平均查找长度为1。
- 60：哈希函数为H(60)=60%9=6，但位置6为空，平均查找长度为1。

因此，等概率查找时查找成功的平均查找长度为：
$$\frac{1+7\times 1+2\times 1}{9}=1.22$$

相关问题

已知关键字序列为{17，77，76，66，10 , 98}，采用线性探测再散列解决冲突， 哈希函数为H（K）= K %11，表长为12。 (1)构造哈希表 (2)求出等概率下查找成功时的平均查找长度。

好的，问题已经记录下来了。现在回答你的问题：

(1) 构造哈希表：

首先，我们需要创建一个12个元素的哈希表，初始状态下所有元素都为空。然后，我们按照哈希函数H(K) = K % 11的规则，将关键字序列中的每个关键字插入到哈希表中。

具体的插入过程如下：

- 17 % 11 = 6，将17插入到哈希表的第6个位置；
- 77 % 11 = 0，将77插入到哈希表的第0个位置；
- 76 % 11 = 1，将76插入到哈希表的第1个位置；
- 66 % 11 = 0，发生冲突，采用线性探测再散列的方法，将66插入到哈希表的第1 + 1 = 2个位置；
- 10 % 11 = 10，将10插入到哈希表的第10个位置；
- 98 % 11 = 3，将98插入到哈希表的第3个位置。

最终得到的哈希表为：

|0|1|2|3|4|5|6|7|8|9|10|11|
|---|---|---|---|---|---|---|---|---|---|---|---|
|77|76|66|98|||17||||10|

(2) 求出等概率下查找成功时的平均查找长度：

假设哈希表中有n个关键字，m个哈希桶，平均查找长度为ASL。由于这是等概率的情况，我们可以采用公式ASL = (1 + (1/1-p))/2来计算。

其中，p为填装因子，即哈希表中已有关键字数目n与哈希桶数目m的比值。在这个例子中，n = 6，m = 12，因此p = n/m = 0.5。

带入公式ASL = (1 + (1/1-p))/2，可得ASL = 1.67。因此，等概率下查找成功时的平均查找长度为1.67。

已知一个列表长为12，关键字的线性序列为53 17 19 61 98 75 79 63 46 49，假定采用h（key）=key%11，若采用线性探测法处理冲突，构造出该散列表

根据给定的哈希函数h(key)=key%11和线性探测法，可以按照以下步骤构造该散列表：

1. 创建一个长度为11的数组，用于存放关键字。
2. 将数组中所有元素初始化为空位（null）。
3. 依次将线性序列中的关键字插入到散列表中。对于每个关键字，计算其哈希值h(key)，如果对应的数组位置为空，则将关键字插入到该位置；否则，按照线性探测法，依次检查下一个位置，直到找到一个空位。
4. 插入完所有关键字后，散列表的构造就完成了。

根据上述步骤，可以得到以下散列表（其中“-”表示空位）：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|53 |17 |46 |79 |98 |75 |19 |63 |- |- |49 |

其中，关键字53、17、46、79、98、75、19、63、和49分别对应数组下标0、1、2、3、4、5、6、7、10，而关键字61和关键字46都发生了冲突，需要按照线性探测法依次往后查找空位，最终关键字61插入到了下标8的位置。