首页有序关键字序列{13, 18, 25, 39, 42, 55, 62, 87}，画出其二分查找判定树，并计算查找成功的平均查找长度（ASL）。

有序关键字序列{13, 18, 25, 39, 42, 55, 62, 87}，画出其二分查找判定树，并计算查找成功的平均查找长度（ASL）。

时间: 2023-08-13 20:04:56 浏览: 93

好的，以下是这个有序关键字序列的二分查找判定树： ``` 42 / \ 25 62 / \ / \ 18 39 55 87 / 13 ``` 其中，根节点是中间的数 42，左子树的中间数是 25，右子树的中间数是 62。依此类推，对于每个节点，左子树是小于等于该节点的数，右子树是大于该节点的数。接下来计算查找成功的平均查找长度（ASL）。二分查找的平均查找长度公式为： $ASL = \sum_{i=1}^{n}\frac{c_i}{n}d_i$ 其中，$c_i$ 表示查找第 $i$ 个元素时经过的节点数，$d_i$ 表示查找第 $i$ 个元素的概率，$n$ 表示元素个数。对于这个有序关键字序列，$n=8$。对于每个元素，其概率都是 $1/8=0.125$。我们逐个计算 $c_i$ 值： - 查找 13，经过节点 42、25、18、13。$c_1=4$。 - 查找 18，经过节点 42、25、18。$c_2=3$。 - 查找 25，经过节点 42、25。$c_3=2$。 - 查找 39，经过节点 42、62、55、39。$c_4=4$。 - 查找 42，经过节点 42。$c_5=1$。 - 查找 55，经过节点 42、62、55。$c_6=3$。 - 查找 62，经过节点 42、62。$c_7=2$。 - 查找 87，经过节点 42、62、87。$c_8=3$。接下来计算 $ASL$： $ASL = \frac{1}{8}(4\times0.125+3\times0.125+2\times0.125+4\times0.125+1\times0.125+3\times0.125+2\times0.125+3\times0.125) = 2.375$ 因此，这个有序关键字序列的二分查找成功的平均查找长度（ASL）为 2.375。

阅读全文