6．设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。

根据这些记录关键字构造的二叉排序树如下所示：

        20
       /  \
     12   42
    / \   /
  18  14 31
       \
       28

二叉排序树的平均查找长度与树的形态有关，一般情况下难以计算出精确值，但可以通过公式进行估算。假设有 $n$ 个节点，则平均查找长度为：

$$ASL=\frac{1}{n}\sum_{i=1}^{n}{l_i}$$

其中 $l_i$ 表示第 $i$ 个节点的查找长度。对于一棵随机构造的二叉排序树，每个节点被访问到的概率是相等的，因此可以用节点的深度作为节点的查找长度。假设节点深度为 $d_i$，则 $l_i = d_i + 1$，因为在访问到节点后还需要比较一次才能确定查找成功。因此有：

$$ASL=\frac{1}{n}\sum_{i=1}^{n}{(d_i+1)}$$

对于一组随机的数据，期望的二叉排序树的深度为 $O(\log{n})$，因此可以估算出平均查找长度的数量级。但是，由于这组数据的初始序列并不是随机的，因此无法直接使用上述结论。不过，可以通过计算这棵树的深度来估算平均查找长度的数量级。

这棵树的深度为 4，因此平均查找长度的数量级为 $O(\log{n})$。具体的数值为：

$$ASL \approx \frac{1}{7}(3+2+3+2+3+3+4) \approx 2.71$$

因此，根据这些记录关键字构造的二叉排序树的平均查找长度约为 2.71。

相关问题

设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字： 1.构造的二叉排序树 2.计算ASL成功 3.计算ASL不成功 要求列出计算式子。

1. 构造的二叉排序树如下图所示：

        20
       /  \
     12   42
    /  \    \
  18  14   31
          /
        28

2. 计算ASL成功：

- 20: 1 * 0 = 0
- 12: 2 * 1/2 = 1
- 18: 3 * 1/3 = 1
- 14: 4 * 2/4 = 2
- 28: 5 * 1/3 = 5/3
- 31: 6 * 1/2 = 3
- 42: 7 * 0 = 0

ASL = (0 + 1 + 1 + 2 + 5/3 + 3 + 0) / 7 = 2.19

3. 计算ASL不成功：

- 20: 1 * 0 = 0
- 12: 2 * 1/2 = 1
- 42: 3 * 2/3 = 2
- 31: 4 * 1/2 = 2
- 18: 5 * 2/5 = 2
- 14: 6 * 3/6 = 3
- 28: 7 * 3/4 = 5.25

ASL = (0 + 1 + 2 + 2 + 2 + 3 + 5.25) / 7 = 2.08

设一组初始记录关键字序列为（25，50，15，35，80，85，20，40），其中含有4个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为

根据题目所给的信息，关键字序列中含有4个长度为2的有序子表，可以将其分为4个子序列：（25，50）、（15，35）、（80，85）和（20，40）。接下来，我们可以使用归并排序的方法，对这4个子序列进行归并操作。

首先，将第一对子序列（25，50）归并为有序序列（25，50）。然后，将第二对子序列（15，35）归并为有序序列（15，35）。将第三对子序列（80，85）归并为有序序列（80，85）。最后，将第四对子序列（20，40）归并为有序序列（20，40）。

接下来，将归并后的4个子序列进行合并。首先，将前两个子序列（25，50）和（15，35）合并为有序序列（15，25，35，50）。然后，将后两个子序列（80，85）和（20，40）合并为有序序列（20，40，80，85）。

最后，将上述两个有序序列合并为最终的有序序列。具体步骤如下：

- 比较两个序列的第一个元素，取较小的元素放入最终序列中，并将该元素所在序列的指针后移一位；
- 重复上述步骤，直到一个序列中的所有元素都被取出；
- 将另一个序列中剩余的元素全部放入最终序列中。

根据上述步骤，将有序序列（15，25，35，50）和（20，40，80，85）合并为最终的有序序列（15，20，25，35，40，50，80，85）。

因此，一趟归并后的结果为（15，20，25，35，40，50，80，85）。