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

设一组初始记录关键字序列(6,3,10,5,7.4,8),以关键字6为基准进行第一趟快速排序的结果为

在以关键字6为基准进行第一趟快速排序中，我们需要将比6小的关键字放在6的左边，比6大的关键字放在6的右边。具体步骤如下：

1. 以第一个记录3作为初始枢轴（也可以随机选择一个作为枢轴），记录6暂时空出来。
2. 从右向左扫描，找到第一个比3小的记录5，将5填入6的位置（即空位），同时将6记录到5的位置。
3. 从左向右扫描，找到第一个比3大的记录10，将10填入刚才6的位置（即5的位置），同时将5记录到10的位置。
4. 重复步骤2和步骤3，直到左右两个指针相遇。
5. 将枢轴3填入最后相遇的位置，此时以3为枢轴的第一趟快速排序就完成了。

最终得到的关键字序列为(3,5,6,10,7.4,8)。