设散列函数H(k)=key mod 7, 散列表的地址空间为0到6，对关键字序列{14，21,24, 31，39，6，40}，请按照线性探测再散列构造散列表，并计算查找成功的平均查找长度。

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

首先，按照散列函数H(k)=key mod 7，对关键字序列{14，21,24, 31，39，6，40}进行散列，得到的散列地址分别为{0，0，3，3，4，6，5}。其中，14和21的散列地址都是0，因此需要进行线性探测再散列。

根据线性探测再散列的方法，当出现冲突时，将关键字向后移动一位，重新计算散列地址，直到找到一个空闲位置为止。具体地，14的散列地址为0，但是位置已经被占用，因此需要向后查找。经过一次探测后，14被移到了位置1。21的散列地址也为0，但是位置已经被占用，需要向后查找。经过两次探测后，21被移到了位置2。

此时散列表的情况如下：

0: 21 14
1: 24
2: 31
3: 39 6
4: 40
5:
6:

以此类推，依次将关键字插入散列表中。最终得到的散列表为：

0: 21 14
1: 24
2: 31
3: 39 6
4: 40
5:
6:

查找成功的平均查找长度ASL为：

ASL = (1/7) * [(1+2+1+2+1+1+1)] = 1.29

因此，查找成功的平均查找长度为1.29。

相关问题

设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用散列函数H(key)=key%13，采用开放地址法的二次探测再散列方法解决冲突，试在0~18的散列地址空间中对该关键字序列构造散列表。

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

根据题目中所给的关键字和散列函数，我们可以得到以下散列地址：

- 19 -> 6
- 01 -> 1
- 23 -> 10
- 14 -> 1
- 55 -> 3
- 20 -> 7
- 84 -> 11
- 27 -> 1
- 68 -> 4
- 11 -> 11
- 10 -> 10
- 77 -> 5

其中，关键字14和27的散列地址与关键字01相同，发生了冲突。我们可以采用开放地址法中的二次探测再散列方法解决冲突。具体地，如果第一次散列地址为h，冲突解决的第i步散列地址为：

$h_i = (h + c_1i + c_2i^2) \mod m$

其中，c1和c2是正整数，m是散列表的大小。

在本题中，我们可以取c1=1，c2=3，m=13。则，关键字14的散列地址为2，关键字27的散列地址为12。最终的散列表如下：

- 0:
- 1: 01
- 2: 14
- 3: 55
- 4: 68
- 5: 77
- 6: 19
- 7: 20
- 8:
- 9: 23
- 10: 10
- 11: 84, 11
- 12: 27

这样，我们就成功地构造出了一个散列表，其中每个关键字都被正确地插入到了对应的散列地址处。

设关键字序列是(19，24，23，17，38，27，51，34)，散列表长度是11，散列函数是 H(key)=key MOD 11，计算等概率情况下查找成功的平均查找长度ASLsucc。

根据散列函数 H(key)=key MOD 11，可以将关键字序列散列到如下的散列表中：

0:
1: 51
2: 23
3: 34
4: 24
5: 38
6:
7: 17
8:
9: 19
10:27

接下来，我们可以使用公式 ASLsucc = (Σ(di+1)) / n 来计算等概率情况下查找成功的平均查找长度，其中 n 是关键字序列的长度，di 是第 i 个关键字在散列表中的查找长度。

因此，我们需要先通过散列函数计算出每个关键字在散列表中的位置，然后计算出每个关键字的查找长度 di，最后求和并除以 n。

对于关键字序列中的每一个关键字，我们可以通过 H(key) 计算出它在散列表中的位置：

H(19) = 8
H(24) = 2
H(23) = 1
H(17) = 7
H(38) = 5
H(27) = 5
H(51) = 1
H(34) = 3

因此，关键字的散列表位置和查找长度如下：

key H(key) di
19 8 1
24 2 1
23 1 1
17 7 1
38 5 1
27 5 2
51 1 2
34 3 1

接下来，我们可以计算出 ASLsucc：

ASLsucc = (Σ(di+1)) / n
= (1+1+1+1+1+2+2+1+1) / 8
= 1.375

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