计算机二级
在长度为 n 的有序线性表中进行顺序查找，最坏情况下需要比较的次数是A．O(n) B．O(n2) C．O(log2n) D．O(nlog2n)
题目
在长度为 n 的有序线性表中进行顺序查找，最坏情况下需要比较的次数是A．O(n) B．O(n2) C．O(log2n) D．O(nlog2n)
参考答案和解析
在有序的线性表中进行查找，最差的情况为从表头查找到表尾都没有所需要的值。长度为n的线性表从表头开始每次取出一个值比较，若不符合，再取下一个值，依次比较，一直到最后一个，需要比较n次。
相似问题和答案
第1题：
在长度为n的有序线性表中进行二分查找，在最坏的情况下需要比较的次数是( )。
A．O(n)
B．O(n2)
C．O(log2n)
D．O(nlog2n)
解析： 二分查找法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]，则找到x，算法终止；如果x2n。
第2题：
在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（ ）。
A.O(n)
B.O(n2)
C.O(log2n)
D.O(nlog2n)
C。【解析】本题考查查找的算法，对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次。
第3题：
在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（ ）。
A.O(n)
B.O(n2)
C.O(1092n)
D.0(n1092n)
当有序线性表为顺序存储时才能用：二分法查找。可以证明的是对于长度为n的有序线性表，在最坏情况下，二分法查找只需要比较l092n次，而顺序查找需要比较n次。
第4题：
在长度为z的有序线性表中进行二分查找，最坏情况下需要比较的次数是（ ）。
A.O(n)
B.O(n2)
C.O(log2n)
D.O(nlog2n)
C【解析】对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。
第5题：
在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是
A．O(n)
B．O(n2)
C．O(log2n)
D．O(nlog2n)
解析：二分法检索要求线性表结点按关键值排序且以顺序方式存储。在查找时，首先与表的中间位置上结点的关键值比较，若相等则检索成功；否则根据比较结果确定下一步在表的前半部分或后半部分继续进行。二分法检索的效率比较高，设线性表有n个元素，则最多的检索次数为大于long2n(2为底数)的最小整数，最少的检索次数为1。
第6题：
在长度为z的有序线性表中进行二分查找，最坏情况下需要比较的次数是( )
A．O(n)
B．O(n2)
C．O(log2n)
D．O(nlog2n)
解析： 对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。
第7题：
在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是______。
A．O(n)
B．O(n2)
C．O(log2n)
D．O(nlog2n)
解析：二分法检索要求线性表结点按关键值排序且以顺序方式存储。在查找时，首先与表的中间位置上结点的关键值比较，若相等则检索成功；否则根据比较结果确定下一步在表的前半部分或后半部分继续进行。二分法检索的效率比较高，设线性表有n个元素，则最多的检索次数为大于log2n的最小整数，最少的检索次数为1。
第8题：
在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是( )。
A．O(n)
B．O(n2)
C．O(log2n)
D．O(nlog2n)
解析：对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。
第9题：
在长度为n的有序线性表中进行二分查找，最坏情况下需要较的次数是（ ）
A．O(n)
B．O(n2)
C．O(log2n)
D．O(nlog2n)
对于长度为n的线性表进行顺序查找，平均要进行n/2次比较，在最坏情况下要进行n次比较；对于长度为n的线性表进行二分查找，在最坏情况下要进行l092n次比较(但二分查找要求线性表是顺序存储的有序表)。因此本题的正确答案是C。