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

(1) 构造哈希表过程如下：

| 位置 | 关键字 |
|------|--------|
| 0 | 44 |
| 1 | 54 |
| 2 | 32 |
| 3 | |
| 4 | 87 |
| 5 | 49 |
| 6 | 27 |
| 7 | |
| 8 | |
| 9 | |
| 10 | |
| 11 | |

注意，第一个关键字 32 映射到位置 10，但该位置已经被关键字 87 占用，因此需要线性探测，依次尝试位置 11、0、1，最终插入到位置 1。

(2) 等概率下查找成功时的平均查找长度为 (1/6) * (1 + 2 + 3 + 4 + 5 + 6) = 3.5。其中，1/6 表示每个关键字被查找的概率相等，1、2、3、4、5、6 表示查找成功时需要探测的位置数。

相关问题

已知关键字序列为{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。

已知哈希函数为：H(k)=k%11，表长为11，采用线性探测再散列解决冲突，对下列关键字序列{21,66,99,98,2,49} (1)构造哈希表； (2)求出等概率下查找成功时的平均查找长度。

好的，我来回答你的问题。

首先，根据给出的哈希函数和表长，我们可以得到哈希表的下标范围为0~10。

(1) 接下来，我们按照线性探测再散列的方法，将关键字序列插入哈希表中。

首先，将21插入哈希表中，计算其哈希值为10，将其插入哈希表中的第10个位置。

然后，将66插入哈希表中，计算其哈希值为0，但是0位置已经有了关键字21，因此需要进行线性探测再散列。按照线性探测的规则，依次往后查找，直到找到一个空位置插入。因此，将66插入哈希表中的第1个位置。

接下来，将99插入哈希表中，计算其哈希值为10，但是10位置已经有了关键字21和66，因此需要进行线性探测再散列。依次往后查找，直到找到一个空位置插入。因此，将99插入哈希表中的第2个位置。

然后，将98插入哈希表中，计算其哈希值为9，将其插入哈希表中的第9个位置。

接着，将2插入哈希表中，计算其哈希值为2，将其插入哈希表中的第2个位置。

最后，将49插入哈希表中，计算其哈希值为5，将其插入哈希表中的第5个位置。

因此，构造出的哈希表如下所示：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|----|
|66 |99 |2 | | |49 |21 | | |98 |21 |

(2) 接下来，我们需要求出等概率下查找成功时的平均查找长度。这里我们可以采用公式ASL = (1/λ)*Σ(pi*(1+di))，其中λ为填入表中的记录数与表长的比值，pi为查找表中第i个记录的概率，di为查找表中第i个记录的查找长度减1。

由于等概率下每个关键字被查找的概率都相等，因此pi=1/6。

计算λ的值为n/m，其中n为填入表中的记录数，m为表长。由于填入表中的记录数为6，表长为11，因此λ=6/11。

接下来，我们需要计算每个关键字的查找长度。以关键字21为例，它在哈希表中的位置为10和0，因此它的查找长度为(1+1)/2=1。同理，我们可以求出其他关键字的查找长度。

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|----|
|66 |99 |2 | | |49 |21 | | |98 |21 |
|1 |1 |1 | | |1 |1 | | |1 |1 |

最后，代入公式ASL = (1/λ)*Σ(pi*(1+di))中，我们可以得到等概率下查找成功时的平均查找长度为(1/6)*[(1+1)+(1+1)+(1+1)+(1+1)+(1+1)+(1+1)]=2。

因此，该哈希表等概率下查找成功时的平均查找长度为2。