题15

题15

题目

Q:下列关于查找的说法中, 正确的是 ( ). (注, 涉及下节内容)
A. 若数据元素保持有序, 则查找时就可以采用折半查找法
B. 折半查找与二叉查找树的时间性能在最坏情况下是相同的
C. 折半查找法的平均查找长度一定小于顺序查找法
D. 折半查找法查找一个元素大约需要 次关键字比较

分析

A:二分查找，或者叫折半查找，要求序列本身是有序的
对于数据量比较小的情况，顺序查找的效率可能比折半查找高
对于二分查找树和折半查找，这两者的对比我还比较模糊

解

折半查找法不仅要求数据元素有序, 而且要求必须为顺序存储, A 错误。
折半查找法在最坏情况下的时间性能为 ，二叉查找树在最坏情况下的时间性能为 ，B 错误。
在每个元素查找概率不同的情况下, 折半查找法的平均查找长度可能大于顺序查找法, C 错误。