在关键字随机分布的情况下，用二分查找树的方法进行查找，其平均查找长度与（ ）量级相当。

A. 顺序查找 B. 折半查找 C. 分块查找 D. 散列查找

数组查找 平均查找长度

[tag_link]

正确答案：B

在关键字随机分布的情况下，构建的二分查找树（BST）通常趋于平衡，树的高度平均为 O(log n)，其中 n 是关键字的数量。 因此，使用二分查找树进行查找的平均查找长度（ASL）量级为 O(log n)。 折半查找（即二分查找）在有序数组上进行，每次比较后将搜索范围减半，其平均查找长度也是 O(log n) 量级。 顺序查找的 ASL 为 O(n)，分块查找的 ASL 介于顺序查找和折半查找之间，通常优于 O(n) 但不如 O(log n)，而散列查找在理想情况下 ASL 为 O(1)。 因此，二分查找树在随机分布下的平均查找长度与折半查找同属于对数量级。