设一组初始记录关键字序列为(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．设一组初始记录关键字序列为(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。

设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立 的初始堆为____

首先，我们需要将这些关键字序列转化为一个完全二叉树。然后，我们进行筛选法建立初始堆的操作，即从最后一个非叶子节点（也就是第 n/2 个节点，其中 n 为节点总数）开始，依次向上进行下滤操作，确保每个节点都满足堆的性质。

将这些关键字序列转化为完全二叉树后，得到如下的图示：

           55
         /    \
        63     44
       /  \   /  \
      38  75 80  31
     /
    56

从最后一个非叶子节点开始，也就是第 4 个节点（值为 38），进行下滤操作，得到如下的堆：

           55
         /    \
        63     44
       /  \   /  \
      56  75 80  31
     /
    38

因此，利用筛选法建立的初始堆为(55，63，44，56，75，80，31，38)。