计算机技术与软件专业技术资格考试(初级程序员)
对n个元素的有序表A［1..n］进行二分（折半）查找，则成功查找到表中的任意一个元素时，最多与A中的（）元素进行比较。A、n-1B、n/2C、（log2n）-1D、（log2n）+1
题目
对n个元素的有序表A［1..n］进行二分（折半）查找，则成功查找到表中的任意一个元素时，最多与A中的（）元素进行比较。
- A、n-1
- B、n/2
- C、（log2n）-1
- D、（log2n）+1
相似问题和答案
第1题：
线性表L=(a1，a2,...，an)用数组表示，假定删除表中任一个元素的概率相同，则删除一个元素平均需要移动的元素个数是
A．n
B．n/2
C．log2n
D．n log2n
第2题：
对具有n个元素的有序序列进行二分查找时，(61)。
A．元素位置越靠近序列前端，查找该元素所需的比较次数越少
B．查找序列中任何一个元素所需要的比较次数不超过[log2(n+1)]
C．查找元素所需的比较次数与元素的位置无关
D．元素位置越靠近序列后端，查找该元素所需的比较次数越少
解析：二分查找过程是：以处于中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或查找区间的大小为零时(表明查找不成功)为止。对于有11个元素的有序表进行二分查找的过程可用一个二叉树表示，如图6-12所示(结点中的数字表示元素在序列中的序号)。
图6-12所示二叉树表明，若需要查找序列中的第6个元素，则仅需一次元素间的比较。若需查找第3个或第9个元素，则分别需要两次比较。依此类推，查找第1、4、7、10个元素时，分别需要三次比较，查找第2、5、 8、11个元素时，分别需要四次比较。因此，查找元素所需的比较次数与元素在序列中的位置是有关的。显然，选项A或D的说法也是错误的。若序列中有n个元素，则根据二分查找法构造的二叉树的高度不会超过[log2(n+1)]，因此选项B是正确的。
第3题：
A、O(n2)
B、O(nlog2n)
C、O(n)
D、O(log2n)
第4题：
若对大小为N的有序顺序表进行顺序查找，当查找不成功时，平均查找长度为(59)；当查找成功且表中仅有一个关键字等于欲查找的元素时，平均查找长度为(60)。
A．N
B．N+1
C．N/2
D．(N+1)/2
解析：当查找不成功时，会查找至最后一个元素，故平均查找长度为N。
第5题：
An
Bn/2
C(n+1)/2
D(n-1)/2
第6题：
对于长度为11的顺序存储的有序表，若采用折半查找(向下取整)，则找到第5个元素需要与表中的(39)个元素进行比较操作(包括与第5个元素的比较)。
A．5
B．4
C．3
D．2
解析：本题考查折半(二分)查找。折半查找判定树可以用于描述折半查找过程，在有11个元素的有序顺序表中进行折半查找的判定树如下图所示，结点中的数字表示元素的序号。该判定树表示，首先将待查找的元素与表中的中间元素比较(第6个元素)，若相等，则找到，若大于中间位置元素，则下一步到后半个子表进行折半查找，否则，下一步到前半个子表进行折半查找。因此，要找表中的第5个元素，需要与第6、3、4和5个元素依次比较，查找成功。
第7题：
设查找表为(50,60,75,85,96,98,105,110,120,130)
(1)说出进行折半查找成功查找到元素120需要进行多少次元素间的比较?
(2)为了折半查找元素95，经过多少次元素间的比较才能确定不能查到?
(3)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点)。
(2 )4次
(3)
第8题：
采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为()。
A.O（n2）
B.O（nlog2n）
C.O（n）
D.O（log2n）
第9题：
对于长度为11的顺序存储的有序表，若采用折半查找(向下取整)，则找到第5个元素需要与表中的______个元素进行比较操作(包括与第5个元素的比较)。
A．5
B．4
C．3
D．2
A．
B．
C．
D．
第10题：
从具有n个结点的二叉查找树中查找一个元素时，在最坏情况下进行成功查找的时间复杂度为(51)。
A．O(n)
B．O(1)
C．O(log2n)
D．O(n2)
解析：当二叉查找树严重不平衡时，二叉查找树有n层，最坏情况就是把n个结点都比较一遍才查找成功。