上题中 ，构造散列表时使用链地址法处理冲突，重新构造散列表，画出该表，并计算在等概率的情况下，查找成功时的平均查找长度。

好的，我可以回答你的问题。

如果使用链地址法处理冲突，我们可以将具有相同散列值的数据放在同一个链表中。具体地，对于每个散列值，我们都维护一个链表，将具有该散列值的数据插入到对应的链表中。如果发生冲突，就直接将数据插入到链表的末尾。

按照上述方法，将数据插入散列表中，得到的散列表如下所示：

散列值   数据
0       33 -> 1
1       34
2       13 -> 12
3
4       38
5       27
6       22
7
8
9
10

其中，箭头表示链表中的指针关系。

接下来，我们计算在等概率的情况下，查找成功时的平均查找长度。由于散列表的大小为11，因此查找成功的概率为 $p = 1/8$。查找成功时的平均查找长度为：

$$
ASL = \frac{1}{p} \sum_{i=1}^{8} i \cdot p_i = 8\left(\frac{1}{8}\cdot1 + \frac{1}{8}\cdot\frac{1}{2}\cdot2 + \frac{1}{8}\cdot\frac{2}{3}\cdot3 + \frac{1}{8}\cdot\frac{1}{4}\cdot4\right) = 1.875
$$

其中，$p_i$ 表示查找成功时，需要查找 $i$ 个位置的概率。

因此，在等概率的情况下，查找成功时的平均查找长度为1.875。

相关问题

使用散列函数H(x)=x mod 11把一个整数值转换成散列表下标，现要把数据1，13，12，34，38，33，27，22插入到散列表中。使用线性探测再散列处理冲突，画出构造的散列表，并计算在等概率的情况下，查找成功时的平均查找长度。

好的，我可以回答你的问题。

首先，我们使用散列函数 $H(x) = x \mod 11$ 将数据插入散列表中。如果发生冲突，我们使用线性探测再散列法解决冲突。具体地，如果散列到的位置已经被占用，就依次向后查找，直到找到一个空位置为止。再次散列时，我们使用另一个散列函数 $H'(x) = (x+1) \mod 11$。

按照上述方法，将数据插入散列表中，得到的散列表如下所示：

散列值   数据
0       33
1       34
2       13
3       12
4       38
5       27
6       22
7       1
8       -
9       -
10      -

其中，空位置用“-”表示。

接下来，我们计算在等概率的情况下，查找成功时的平均查找长度。由于散列表的大小为11，因此查找成功的概率为 $p = 1/8$。查找成功时的平均查找长度为：

$$
ASL = \frac{1}{p} \sum_{i=1}^{8} i \cdot p_i = 8\left(\frac{1}{8}\cdot1 + \frac{1}{8}\cdot2 + \frac{1}{8}\cdot3 + \frac{1}{8}\cdot4\right) = 2.5
$$

其中，$p_i$ 表示查找成功时，需要查找 $i$ 个位置的概率。

因此，在等概率的情况下，查找成功时的平均查找长度为2.5。

已知散列表的表长为12（0~11），散列函数为H(k)=k%11，采用拉链法处理冲突，将关键字序列20,30，70，15,8,12，18，63，19依次存储到散列表中，试构造出该散列表，并求出在等概率情况下的平均查找长度。

首先根据散列函数 H(k)=k%11，计算出关键字的散列地址：

- 20%11=9
- 30%11=8
- 70%11=5
- 15%11=4
- 8%11=8
- 12%11=1
- 18%11=7
- 63%11=8
- 19%11=8

然后将关键字插入到散列表中，按照拉链法处理冲突：

- 下标为0的链表：无元素
- 下标为1的链表：12
- 下标为2的链表：无元素
- 下标为3的链表：无元素
- 下标为4的链表：15
- 下标为5的链表：70
- 下标为6的链表：无元素
- 下标为7的链表：18
- 下标为8的链表：30 -> 8 -> 63 -> 19
- 下标为9的链表：20

这样得到的散列表如下：

0:
1: 12
2:
3:
4: 15
5: 70
6:
7: 18
8: 30 -> 8 -> 63 -> 19
9: 20
10:
11:

在等概率情况下的平均查找长度可以通过以下公式计算：

$ASL=\sum_{i=0}^{m-1}p_i(s_i+1)$

其中，$m$ 是散列表的长度，$p_i$ 是查找表中第 $i$ 个元素的概率，$s_i$ 是查找第 $i$ 个元素时需要遍历的链表长度。

在这个问题中，每个元素被查找的概率是相等的，为 $\frac{1}{9}$。对于每个下标上的链表，我们可以计算出它的长度 $s_i$：

- 下标为0的链表：$s_0=0$
- 下标为1的链表：$s_1=1$
- 下标为2的链表：$s_2=0$
- 下标为3的链表：$s_3=0$
- 下标为4的链表：$s_4=1$
- 下标为5的链表：$s_5=1$
- 下标为6的链表：$s_6=0$
- 下标为7的链表：$s_7=1$
- 下标为8的链表：$s_8=3$
- 下标为9的链表：$s_9=1$

然后代入公式计算平均查找长度：

$ASL=\frac{1}{9}[(0+1)+(1+1)+(0+1)+(0+1)+(1+1)+(1+1)+(0+1)+(1+1)+(3+1)]$

$ASL=\frac{16}{9}$

因此，在等概率情况下，该散列表的平均查找长度是 $\frac{16}{9}$。