题8
题目
Q:折半查找和二叉排序树的时间性能 ( ).
A. 相同
B. 有时不相同
C. 完全不同
D. 无法比较
分析
A:二叉排序树是指一棵二叉树, 它的每个结点都有一个关键字, 并满足以下性质: 若任意结点的左子树不空, 则左子树上所有结点的关键字均小于它的根结点的关键字;
若任意结点的右子树不空, 则右子树上所有结点的关键字均大于它的根结点的关键字;
左、右子树也分别为二叉排序树。
折半查找是一种高效的查找方式, 但是在一些特殊情况下, 比如 n 很小的时候, 顺序查找可能会更快, 所以不能说二分查找必然快。
解
B
折半查找的性能分析可以用二叉判定树来衡量,平均查找长度和最大查找长度都是
二叉排序树的查找性能与数据的输入顺序有关, 最好情况下的平均查找长度与折半查找相同, 但最坏情况即形成单支树时,其查找长度为