对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。A、3B、4C、5D、6

对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。

A. 3

B. 4

C. 5

D. 6

在n个记录的有序顺序表中进行折半查找，最大的比较次数是(27)。

A．

B．

C．

D．

此题为判断题(对，错)。

在查找算法中，可用平均查找长度(记为ASL)来衡量一个查找算法的优劣，其定义为：

此处Pi为表中第i个记录被查找的概率，Ci为查找第i个记录时同关键字比较的次数，n为表中记录数。

以下叙述中均假定每一个记录被查找的概率相等，即Pi=//n(i=1，2，…，n)。当表中的记录连续存储在一个一维数组中时，可采用顺序查找与折半查找方法(折半查找要求表是按关键字有序排列的)。顺序查找时的ASL为(19)，折半查找时的ASL为(20)。记录的关键字有序时，用二叉排序树查找记录，在最坏的情况下，ASL为(21)。当二叉排序树是一棵平衡树时，ASL为(22)。在平衡树上删除一个结点后可以通过旋转使其平衡，最坏的情形下需(23)次旋转。

A．O(1)

B．O(log2n)

C．O(log2n2)

D．O(nlog2n)

E．O(n)

● 关于线性表的顺序查找、折半查找、分块查找方法的叙述中，错误的是 （47） 。

（47）

A. 顺序查找的算法非常简单但效率较低

B. 折半查找法的平均查找长度小，查找速度快

C. 分块查找的平均长度介于顺序查找和折半查找之间

D. 分块查找只能用于顺序存贮结构，且要求表中记录是有序的

设查找表为(50,60,75,85,96,98,105,110,120,130)

(1)说出进行折半查找成功查找到元素120需要进行多少次元素间的比较?

(2)为了折半查找元素95，经过多少次元素间的比较才能确定不能查到?

(3)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点)。