单选题在长度为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）

相似考题

1.在长度为 n 的有序线性表中进行二分查找，最坏情况下需要比较的次数是A ) O( n )B ) O( n2)C ) O(log 2 n )D ) O( n log 2 n )

2.（ 3 ）在长度为 n 的有序线性表中进行二分查找，最坏情况下需要比较的次数是A ） O( n )B ） O( n2)C ） O(log 2 n )D ） O( n log 2 n )

3.在长度为n的有序线性表中进行二分查找，最坏情况下需要较的次数是（ ）A．O(n)B．O(n2)C．O(log2n)D．O(nlog2n)

4.采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为()。A、O(n2)B、O(nlog2n)C、O(n)D、O(log2n)

更多“单选题在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（　　）。A O（n）B O（n2）C O（log2n）D O（nlog2n）”相关问题

  • 第1题：

    采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为()。

    A.O（n2）

    B.O（nlog2n）

    C.O（n）

    D.O（log2n）


    正确答案：D

  • 第2题：

    （3）在长度为 n 的有序线性表中进行二分查找，最坏情况下需要比较的次数是

    A）O(n)

    B）O(n2)

    C）O(log2n)

    D）O(nlog2n)


    正确答案：C

    （3）【答案】C)
    【解析】二分查找法也称折半查找法，它的基本思想是：将n个元素分成个数相同的两组，取a[n/2]与欲查找的X作比较。如果X=a[n/2],刚找到x，算法终止。如果x<a[n/2],则只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列）；如果x>a[n/2]则只要在数组a的右半部继续搜索x。每次余下n/(2r)个元素待比较时，即n/(2r)=1.故，n=2i,i=long2n.

  • 第3题：

    用二分查找法对具有n个节点的线性表查找一个节点所需的平均比较次数为( )。

    A．O(n2)

    B．O(nlog2n)

    C．O(n)

    D．O(log2n)


    正确答案：D
    解析：二分查找对应的判定树为平衡树，其树的高度达到最小，因此其平均比较次数为O(log2n)。

  • 第4题：

    下列叙述中，正确的是

    A．对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n

    B．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（n／2）

    C．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（log2n）

    D．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（nlog2n）


    正确答案：A
    解析：对长度为n的有序链表进行查找，最坏情况是从最小值开始查找最大值(或从最大值开始查找最小值)，这个过程需要比较的次数为n，故选项A正确。对分查找只能针对随机存取的有序表进行，而有序链表只能进行顺序存取，不能进行随机存取，在有序链表上不能进行对分查找，故B、C、D选项都错误。

  • 第5题：

    在长度为n的有序线性表中进行二分法查找，最坏情况下需要比较的次数是( )。

    A.O(n)

    B.0(n2)

    C.O(1092n)

    D.O(nl092n)


    正确答案：C
    当有序线性表为顺序存储时才能用二分法查找。可以证明的是，对于长度为n的有序线性表，在最坏情况下，二分法查找只需要比较l092n次，而顺序查找需要比较n次，因此本题答案为C)。

  • 第6题：

    在长度为 n 的有序线性表中进行顺序查找，最坏情况下需要比较的次数是A．O(n) B．O(n2) C．O(log2n) D．O(nlog2n)


    正确答案：A
    在有序的线性表中进行查找，最差的情况为从表头查找到表尾都没有所需要的值。长度为n的线性表从表头开始每次取出一个值比较，若不符合，再取下一个值，依次比较，一直到最后一个，需要比较n次。

  • 第7题：

    在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（ ）。

    A.0（n）

    B.D（n2）

    C.O（1092n）

    D.0（nl092n）


    正确答案：C
    当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为n的有序线性表，在最坏情况下，二分法查找只需要比较l092n次，而顺序查找需要比较n次。

  • 第8题：

    二分查找一个具有n个元素的有序表，其时间复杂度为______。

    A．O(n)

    B．O(n2)

    C．O(log2n)

    D．(nlog2n)


    正确答案：C
    解析：二分法中查找时间t与查找次数m呈比例关系，2m=n(n为极限查找个数)，m=log2n，所以查找时间复杂度与log2n相关。

  • 第9题：

    在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（ ）。

    A.O(n)

    B.O(n2)

    C.O(1092n)

    D.0(n1092n)


    正确答案：C
    当有序线性表为顺序存储时才能用：二分法查找。可以证明的是对于长度为n的有序线性表，在最坏情况下，二分法查找只需要比较l092n次，而顺序查找需要比较n次。

  • 第10题：

    （ 3 ）在长度为 n 的有序线性表中进行二分查找，最坏情况下需要比较的次数是

    A ） O( n )

    B ） O( n 2)

    C ） O(log 2 n )

    D ） O( n log 2 n )


    正确答案：C

  • 第11题：

    采用简单选择排序，比较次数与移动次数分别是（）

    • A、O（n），O（log2n）
    • B、O（log2n），O（n2）
    • C、O（n2），O（n）
    • D、O（nlog2n），O（n）

    正确答案:C

  • 第12题：

    单选题
    下列叙述中正确的是（　　）。
    A

    对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n

    B

    对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（n/2）

    C

    对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（log2n）

    D

    对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（nlog2n）


    正确答案： B
    解析：
    对于顺序查找，在最坏的情况下查找的是链表的最后一个元素，或者查找的元素不在表中，此时需要比较n次，A项正确。对分查找只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n次，BCD三项错误。答案选择A选项。

  • 第13题：

    在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是( )。

    A．O(n)

    B．O(n2)

    C．O(log2n)

    D．O(nlog2n)


    正确答案：C
    解析：对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。

  • 第14题：

    用顺序查找法对具有n个节点的线性表查找一个节点所需的平均比较次数为( )。

    A．O(n2)

    B．O(nlog2n)

    C．O(n)

    D．O(log2n)


    正确答案：C
    解析：根据要找的元素存在的位置，其比较次数依次为1、2…n，所以平均比较次数为(1+n)n/2/n=(1+n)/2，所以其时间复杂度为O(n)。

  • 第15题：

    在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是

    A．O(n)

    B．o(n2)

    C．O(10g2n)

    D．O(nlog2n)


    正确答案：C
    解析：二分查找法也称为折半查找法。它的基本思想是：将n个元素分成个数大致相同的两组，取a[n／2]与欲查找的x作比较。如果x=a[／2]，则找到x，算法终止；如果xa[n／2]，则只耍在数组a的右半部继续搜索x。每次余下n／(2i)个元素待比较，当最后剩下一个时，即n／(2i)=1。故，n=2i，i=log22n。

  • 第16题：

    在长度为z的有序线性表中进行二分查找，最坏情况下需要比较的次数是( )

    A．O(n)

    B．O(n2)

    C．O(log2n)

    D．O(nlog2n)


    正确答案：C
    解析： 对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。

  • 第17题：

    采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为______。

    A．O(log2n)

    B．O(n)

    C．O(nlog2n)

    D．O(n2)


    正确答案：A

  • 第18题：

    顺序查找一个具有n个元素的线性表，二分查找一个具有n个元素的有序表，其时间复杂性为______。

    A．O(n)

    B．O(log2n)

    C．O(n2)

    D．O(nlog2n)


    正确答案：B

  • 第19题：

    在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（ ）。

    A.0（n）

    B.O（n2）

    C.O（1092n）

    D.O（nl092n）


    正确答案：C
    暂无解析，请参考用户分享笔记

  • 第20题：

    在长度为z的有序线性表中进行二分查找，最坏情况下需要比较的次数是（ ）。

    A.（ ）(n)

    B.（ ）(n2)

    C.（ ）(log2n)

    D.（ ）(nlog2n)


    正确答案：C
    对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。

  • 第21题：

    在长度为n的有序线性表中进行二分查找，在最坏的情况下需要比较的次数是( )。

    A．O(n)

    B．O(n2)

    C．O(log2n)

    D．O(nlog2n)


    正确答案：C
    解析： 二分查找法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]，则找到x，算法终止；如果x2n。

  • 第22题：

    对n个元素进行快速排序时，最坏情况下的时间复杂度为______。

    A．O(log2n)

    B．O(n)

    C．O(nlog2n)

    D．O(n2)


    正确答案：D
    解析：最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。其时间复杂度为0(n2)。

  • 第23题：

    单选题
    在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（　　）。
    A

    O（n）

    B

    O（n2）

    C

    O（log2n）

    D

    O（nlog2n）


    正确答案： D
    解析：
    二分查找的最坏情况是不断的二分直至无法再分时，仍然没有查找成功。对于有序的线性表，二分查找法只需比较log2n次。答案选择C选项。

  • 第24题：

    单选题
    采用简单选择排序，比较次数与移动次数分别是（）
    A

    O（n），O（log2n）

    B

    O（log2n），O（n2）

    C

    O（n2），O（n）

    D

    O（nlog2n），O（n）


    正确答案： A
    解析： 暂无解析

相关内容