给定记录的关键字序列为：15，3，7，21，3，16，18，15，画出构造好的二叉排序树，并计算等概率下查找成功时平均查找长度ASL

这是一棵构造好的二叉排序树：

            15
           /  \
          3   21
           \    \
            7   30
               /  \
             16   18

ASL的计算公式为：ASL = ∑(深度×概率)

其中，深度为从根节点到目标节点的距离，概率为查找目标节点的概率。由于每个节点的查找概率相等，因此概率为1/9。

我们可以通过遍历二叉排序树来计算每个节点的深度和概率：

| 节点 | 深度 | 概率 |
| --- | --- | --- |
| 15 | 1 | 1/9 |
| 3 | 2 | 2/9 |
| 7 | 3 | 1/9 |
| 21 | 2 | 1/9 |
| 16 | 4 | 1/9 |
| 18 | 4 | 1/9 |

因此，ASL = (1×1/9) + (2×2/9) + (3×1/9) + (2×1/9) + (4×1/9) + (4×1/9) = 2.67。

答案：ASL = 2.67。

相关问题

给定结点的关键字序列为：47，7，29，11，16，92，22，8，3，哈希表的长度为11。 设散列函数为：H（K）=K %11。试画出链地址法解决冲突时所构造的哈希表，并求出其平均查找长度。

好的，我明白了。下面是您所要求的答案。

根据散列函数H（K）=K，对给定的关键字序列进行哈希，得到的哈希地址为：

47 % 11 = 3
7 % 11 = 7
29 % 11 = 7
11 % 11 = 0
16 % 11 = 5
92 % 11 = 4
22 % 11 = 0
8 % 11 = 8
3 % 11 = 3

因为哈希表的长度为11，所以我们需要构造一个长度为11的链表数组，用于存放同一个哈希地址上的所有元素。

我们可以画出以下哈希表：

0 -> 11 -> 22
1 ->
2 ->
3 -> 47 -> 3
4 -> 92
5 -> 16
6 ->
7 -> 7 -> 29
8 -> 8
9 ->
10 ->

平均查找长度指的是在查找时平均需要遍历的节点数。对于链地址法，平均查找长度为：

((n+1)/2m) + ((n+2)/2m) + ((n+3)/2m) + ... + ((n+m)/2m)

其中，n为元素的个数，m为哈希表的长度。

带入数值：

n = 9
m = 11

((9+1)/2*11) + ((9+2)/2*11) + ((9+3)/2*11) + ... + ((9+11)/2*11)
= (10/22) + (11/22) + (12/22) + (13/22) + (14/22) + (15/22) + (16/22) + (17/22) + (18/22) + (19/22) + (20/22)
= 1.136

因此，该哈希表的平均查找长度为1.136。

给定结点的关键字序列为：19，14，23，1，68，20，84，27，55，11，10，79。 设散列表的长度为13，散列函数为：H（K）=K % 13。试画出线性探测再散列解决冲突时所构造的散列表，并求出其平均查找长度

### 回答1：
散列函数为 H(K) = K % 13，散列表的长度为13，因此散列表的下标范围为0~12。

首先，将给定的关键字序列按照散列函数的结果分配到散列表中：

| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|------|---|---|---|---|---|---|---|---|---|---|----|----|----|
| 关键字 | 0 | 1 | | 19 | 14 | 55 | 27 | | 68 | 20 | 79 | 84 |

其中，空白表示该位置没有被占用。

接下来，对于发生冲突的关键字，采用线性探测再散列的方法解决冲突。具体做法是，如果散列表中的某个位置已经被占用，那么就继续往后查找，直到找到一个空白位置为止。

例如，关键字23在下标2处发生了冲突，因此需要继续往后查找。下一个位置是3，但是已经被关键字19占用了，因此继续往后查找。下一个位置是4，但是也被占用了，继续往后查找。最终，在下标7处找到了一个空白位置，将关键字23放入该位置：

| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|------|---|---|---|---|---|---|---|---|---|---|----|----|----|
| 关键字 | 0 | 1 | 23 | 19 | 14 | 55 | 27 | | 68 | 20 | 79 | 84 |

同样地，对于关键字1、11、10也需要进行线性探测再散列：

| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|------|---|---|---|---|---|---|---|---|---|---|----|----|----|
| 关键字 | 0 | 1 | 23 | 19 | 14 | 55 | 27 | 11 | 68 | 20 | 79 | 84 | 10 |

此时，所有的关键字都已经被正确地插入到了散列表中。平均查找长度为：

(1 + 2 + 3 + 4 + 5 + 6 + 7 + 1 + 1 + 1 + 1 + 1) / 12 ≈ 2.5

因此，平均查找长度为2.5。

### 回答2：
线性探测再散列是一种解决冲突的方法，当发生冲突时，按照线性的方式探测下一个位置，直到找到空闲位置为止。给定的关键字序列为：19，14，23，1，68，20，84，27，55，11，10，79。散列表长度为13，散列函数为：H（K）=K % 13。

首先，根据散列函数，计算每个关键字对应的散列地址：
19 % 13 = 6
14 % 13 = 1
23 % 13 = 10
1 % 13 = 1
68 % 13 = 7
20 % 13 = 7
84 % 13 = 4
27 % 13 = 1
55 % 13 = 3
11 % 13 = 11
10 % 13 = 10
79 % 13 = 2

然后，根据线性探测再散列方法，将关键字插入到对应的散列地址，如果该地址已经被占用，则向后探测，直到找到空闲位置：
6: 19
1: 14 1
10: 23 10
7: 68 20
4: 84
3: 55
11: 27
2: 79
5: 11
8: 27
9: 11

最终构造的散列表为：
索引 关键字
0:
1: 14 1
2: 79
3: 55
4: 84
5: 11
6: 19
7: 68 20
8: 27
9: 11
10: 23 10
11: 27
12:

平均查找长度是指在查找过程中平均需要查找的次数。根据已构造的散列表，对每个关键字进行查找并计算查找长度：
关键字 查找长度
19 1
14 1
23 1
1 1
68 1
20 2
84 1
27 1
55 1
11 1
10 1
79 1

总查找长度 = 1 + 1 + 1 + 1 + 1 + 2 + 1 + 1 + 1 + 1 + 1 = 11
平均查找长度 = 总查找长度 / 关键字个数 = 11 / 12 ≈ 0.917

因此，线性探测再散列所构造的散列表的平均查找长度约为0.917。