设哈希函数h（k）=3 k mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失

败时的平均查找长度。

方法一：线性探测法

构造哈希表：

哈希地址 1 2 3 4 5 6 7 8 9 10

关键字 - - - - 32 13 49 24 38 21 4

平均查找长度：

查找成功时：(1/11)*(1+2+3+4+5+6+7+8+9+10+11) = 6

查找失败时：(1/11)*(1+2+3+4+5+6+7+8+9+10+11) = 6

方法二：链地址法

构造哈希表：

哈希地址 1 2 3 4 5 6 7 8 9 10

关键字 - - - - 32 13 49 24 38 21 4

平均查找长度：

查找成功时：(1/11)*(1+1+1+1+2+2+1+2+2+2+1) = 1.45

查找失败时：(1/11)*(1+2+2+2+3+3+3+3+3+3+3) = 2.45

相关问题

3.设哈希函数H(K)+=3K+mod+11，哈希地址空间为0~10，对关键字序列(32，13，49，24，38，21，4，12)，按线性探测法解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和

按照线性探测法解决冲突的方法构造哈希表的步骤如下：
1. 初始化哈希表，将所有位置都置为空。
2. 对于关键字序列中的每一个关键字，计算其哈希地址。
3. 如果该地址为空，则将该关键字存入该地址中；否则，使用线性探测法解决冲突，即依次检查该地址后面的位置，直到找到一个空位置为止，将该关键字存入该位置中。
4. 如果哈希表已满，则无法再插入新的关键字。

对于关键字序列(32，13，49，24，38，21，4，12)，按照上述方法构造哈希表的过程如下：

|地址|关键字|
|----|----|
|0 | |
|1 | |
|2 | |
|3 | |
|4 |32 |
|5 |13 |
|6 |49 |
|7 |24 |
|8 |38 |
|9 |21 |
|10 |4 |

其中，哈希地址的计算公式为：H(K) = (3K + mod) % 11，mod为一个常数，这里取1。

等概率情况下查找成功的查找长度为：(1+2+3+4+5+6+7+8)/8 = 4.5。

设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。 ① 线性探测法； ② 链地址法。

好的，我会根据您的要求进行回答，下面是答案：

首先，我们需要根据哈希函数H（K）=3 K mod 11，对关键字进行哈希，得到如下哈希地址序列：

| 关键字 | 哈希地址 |
| ------ | -------- |
| 32 | 9 |
| 13 | 6 |
| 49 | 5 |
| 24 | 7 |
| 38 | 2 |
| 21 | 8 |
| 4 | 1 |
| 12 | 6 |

接下来，我们分别采用线性探测法和链地址法来构造哈希表。

1. 线性探测法

在线性探测法中，当发生冲突时，我们会顺序地往后查找空闲地址，直到找到一个空闲地址为止。

首先，我们将哈希表初始化为空表：

| 哈希地址 | 关键字 |
| -------- | ------ |
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 | |

然后，我们将第一个关键字32插入哈希表中，并计算它的哈希地址为9，将32插入哈希表的第9个位置，得到：

| 哈希地址 | 关键字 |
| -------- | ------ |
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | 32 |
| 10 | |

接着，我们将第二个关键字13插入哈希表中，并计算它的哈希地址为6，发现哈希表的第6个位置已经被32占用了，因此我们需要顺序地往后查找空闲地址。在查找过程中，我们发现第7个位置为空，因此将13插入哈希表的第7个位置，得到：

| 哈希地址 | 关键字 |
| -------- | ------ |
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | 32 |
| 7 | 13 |
| 8 | |
| 9 | 32 |
| 10 | |

接下来，我们继续插入其他的关键字，直到哈希表被填满。最终的哈希表如下：

| 哈希地址 | 关键字 |
| -------- | ------ |
| 0 | |
| 1 | 38 |
| 2 | 24 |
| 3 | |
| 4 | 4 |
| 5 | 49 |
| 6 | 32 |
| 7 | 13 |
| 8 | 21 |
| 9 | 32 |
| 10 | 12 |

在线性探测法中，查找关键字时，如果关键字的哈希地址被占用了，那么我们就顺序地往后查找，直到找到一个空闲地址或者找遍整个哈希表为止。因此，等概率下查找成功时的平均查找长度ASLsucc和查找失败时的平均查找长度ASLunsucc分别为：

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

ASLunsucc = (1/11)*(1+2+3+4+5+6+7+8+9+10+11) = 6

2. 链地址法

在链地址法中，当发生冲突时，我们将哈希地址相同的所有关键字都放到同一个链表中。

首先，我们将哈希表初始化为空表，并创建一个链表头数组，用来存放链表的头指针：

| 哈希地址 | 关键字 | 链表头 |
| -------- | ------ | ------ |
| 0 | | |
| 1 | | |
| 2 | | |
| 3 | | |
| 4 | | |
| 5 | | |
| 6 | | |
| 7 | | |
| 8 | | |
| 9 | | |
| 10 | | |

然后，我们将第一个关键字32插入哈希表中，并计算它的哈希地址为9，将32插入哈希地址为9的链表中，得到：

| 哈希地址 | 关键字 | 链表头 |
| -------- | ------ | ------ |
| 0 | | |
| 1 | | |
| 2 | | |
| 3 | | |
| 4 | | |
| 5 | | |
| 6 | | |
| 7 | | |
| 8 | | |
| 9 | 32 | -> |
| 10 | | |

接着，我们将第二个关键字13插入哈希表中，并计算它的哈希地址为6，将13插入哈希地址为6的链表中，得到：

| 哈希地址 | 关键字 | 链表头 |
| -------- | ------ | ------ |
| 0 | | |
| 1 | | |
| 2 | | |
| 3 | | |
| 4 | | |
| 5 | | |
| 6 | 13 | -> |
| 7 | | |
| 8 | | |
| 9 | 32 | -> |
| 10 | | |

接下来，我们继续插入其他的关键字，直到哈希表被填满。最终的哈希表如下：

| 哈希地址 | 关键字 | 链表头 |
| -------- | --------------- | ------ |
| 0 | | |
| 1 | 38 | -> |
| 2 | 24 | -> |
| 3 | | |
| 4 | 4 | -> |
| 5 | 49 | -> |
| 6 | 13 | -> |
| 7 | | |
| 8 | 21 | -> |
| 9 | 32 -> 12 | -> |
| 10 | | |

在链地址法中，查找关键字时，我们首先根据哈希函数计算关键字的哈希地址，然后在对应的链表中查找。因此，等概率下查找成功时的平均查找长度ASLsucc和查找失败时的平均查找长度ASLunsucc分别为：

ASLsucc = (1/8)*(1+1+1+2+1+2+2+2) = 1.375

ASLunsucc = (1/11)*(1+1+1+1+1+1+1+1+1+1+1) = 1