02331数据结构
对于长度为n的顺序存储的有序表，若采用二分查找法，则对所有元素的最长查找长度为（）的值向下取整再加1。A、log2（n+1）B、n／2C、log2nD、（n+1）／2
题目
对于长度为n的顺序存储的有序表，若采用二分查找法，则对所有元素的最长查找长度为（）的值向下取整再加1。
- A、log2（n+1）
- B、n／2
- C、log2n
- D、（n+1）／2
相似问题和答案
第1题：
对于长度为11的顺序存储的有序表，若采用折半查找(向下取整)，则找到第5个元素需要与表中的______个元素进行比较操作(包括与第5个元素的比较)。
A．5
B．4
C．3
D．2
A．
B．
C．
D．
第2题：
折半(二分)查找方法对查找表的要求是( )。
A．链表存储结构，元素有序排列
B．链表存储结构，元素无序排列
C．顺序存储结构，元素有序排列
D．顺序存储结构，元素无序排列
解析：二分查找也叫折半查找，其基本思想是：以处于中间位置元素的关键字和给定值比较，如果相等，则查找成功。如果给定值大于中间位置元素，则下一次在后半个子表进行二分查找。如果给定值小于中间位置元素，则下一次在前半个子表进行二分查找。这样通过逐步缩小范围，直到查找成功或子表为空时失败为止。显然，如果要查找的表是无序排列，则查找就没有意义。另外，查找需要能直接定位表中间位置的元素，即实现随即访问，因此只有顺序存储结构能满足此要求，在链表上只能顺序查找。【总结与扩展】二分查找在查找成功时和给定值进行比较的关键字格式至多为[log2n]+1。二分查找在查找不成功时和给定值进行比较的关键字格式最多也不会超过[log2n]+l。当查找的表元素值较大时，二分查找的平均查找长度为log2(n+1)-1。二分查找要求查找表进行顺序存储并且按照关键字有序排列，因此当对表进行元素插入或删除时，需要移动大量的元素。所以二分查找适用于表不易变动，且又经常进行查找的情况。
第3题：
● 折半（二分）查找方法对查找表的要求是（42）。
（42）
A.链表存储结构，元素有序排列
B.链表存储结构，元素无序排列
C.顺序存储结构，元素有序排列
D.顺序存储结构，元素无序排列
第4题：
对于长度为8的顺序存储结构的有序表，若采用二分查找法查找，在等概率的情况下，平均查找长度为______的值除以8。
A．17
B．19
C．21
D．20
第5题：
对长度为n的单链有序表，若查找每个元素的概率相等，则查找任一元素的平均查找长度为
A．n/2
B． (n+1) /2
C． (n-1) /2
D． n/4
解析： 因为查找每个元素的概率相等，所以对长度为n的单链有序表，查找任一元素的平均查找长度为(n+1)/2。
第6题：
若对大小为N的有序顺序表进行顺序查找，当查找不成功时，平均查找长度为(59)；当查找成功且表中仅有一个关键字等于欲查找的元素时，平均查找长度为(60)。
A．N
B．N+1
C．N/2
D．(N+1)/2
解析：当查找不成功时，会查找至最后一个元素，故平均查找长度为N。
第7题：
对于长度为8的顺序存储结构的有序表，若采用二分查找法查找，在等概率的情况下的平均查找长度为______除以8的值。
A．17
B．19
C．21
D．20
第8题：
对于长度为11的顺序存储的有序表，若采用折半查找(向下取整)，则找到第5个元素需要与表中的(39)个元素进行比较操作(包括与第5个元素的比较)。
A．5
B．4
C．3
D．2
解析：本题考查折半(二分)查找。折半查找判定树可以用于描述折半查找过程，在有11个元素的有序顺序表中进行折半查找的判定树如下图所示，结点中的数字表示元素的序号。该判定树表示，首先将待查找的元素与表中的中间元素比较(第6个元素)，若相等，则找到，若大于中间位置元素，则下一步到后半个子表进行折半查找，否则，下一步到前半个子表进行折半查找。因此，要找表中的第5个元素，需要与第6、3、4和5个元素依次比较，查找成功。
第9题：
对于长度为n的线性表，若进行顺序查找，时间复杂性为【 】；若进行二分查找，则时间复杂性为【 】。
O(n),O(10g2n)
第10题：
性表中采用折半查找法(二分查找法)查找一个数据元素，线性表应(54)。
A．数据元素按值有序
B．采用顺序存储结构
C．据元素按值有序，并且采用顺序存储结构
D．据元素按值有序，并且采用链式存储结构
解析：只有当线性表中数据元素按值大小有序排列，并且采用顺序存储结构时才能使用折半查找方法查找元素。即使线性表中数据元素按值大小有序排列，但采用的不是顺序存储结构(如链式)，仍然不能够采用折半查找方法。本题应选C。