niusouti.com

单选题在最坏情况下（　　）。A 快速排序的时间复杂度比冒泡排序的时间复杂度要小B 快速排序的时间复杂度比希尔排序的时间复杂度要小C 希尔排序的时间复杂度比直接插入排序的时间复杂度要小D 快速排序的时间复杂度与希尔排序的时间复杂度是一样的

题目
单选题
在最坏情况下（　　）。
A

快速排序的时间复杂度比冒泡排序的时间复杂度要小

B

快速排序的时间复杂度比希尔排序的时间复杂度要小

C

希尔排序的时间复杂度比直接插入排序的时间复杂度要小

D

快速排序的时间复杂度与希尔排序的时间复杂度是一样的

相似考题

1.将7个数据进行插入排序，在最坏情况下需要比较的次数是A．42B．6C．7D．21

2.( 7 )冒泡排序在最坏情况下的比较次数是A )n(n＋1)／2 B ) nlog2 n C ) n(n－1)／2 D )n／2（ 7 ）冒泡排序在最坏情况下的比较次数是A ）ｎ(n+1)/2B ） nlog2 nC ） n(n-1)/2D ）ｎ/2

3.在堆排序和快速排序中，若只从最坏情况下排序最快并且要节省内存考虑，则应选择______方法。

4.（ 1 ）下列叙述中，正确的是A ）对长度为 n 的有序链表进行查找，最坏情况下需要的比较次数为 nB ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n/2 ）C ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ log 2 n ）D ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n log 2 n ）

更多“在最坏情况下（　　）。”相关问题

  • 第1题：

    下列叙述中正确的是( )。

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

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

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

    D．对长度为n的有序链表进行对分查找，最坏情况—卜需要的比较次数为(nlog2(下标)n)


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

  • 第2题：

    在最坏情况下，堆排序需要比较的次数为 【2】 。


    正确答案：
    正确答案:  1.(O(nlog2n)) 

  • 第3题：

    在长度为n的顺序存储结构的线性表中，插入(或删除)一个元素，在平均情况下需要移动表中的________个元素，在最坏情况下需要移动表中的________个元素。


    正确答案：
    n/2 n

  • 第4题：

    将6个数据进行冒泡排序，在最坏情况下需要比较的次数是

    A．15

    B．5

    C．6

    D．30


    正确答案：A
    解析：对长度为n的线性表进行冒泡排序，在最坏情况下需要n(n-1)/2次比较，现线性表的长度为6，在最坏情况下需要比较的次数为6(6-1)/2=15。

  • 第5题：

    对长度为n的线性表进行顺序查找,在最坏情况下需要比较的次数为( )。 A.125B.n／ZSXB

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

    A.125

    B.n／Z

    C.n

    D.n＋1


    正确答案：C
    C。【解析】对线性表进行顺序查找时，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查找到所要找的元素为止。在最坏情况下，要查找的元素是表的最后一个元素或查找失败，这两种情况都需要将这个元素与表中的所有元素进行比较，因此比较次数为n。

  • 第6题：

    在一个长度为n的线性表中插入一个元素，以下说法不正确的是( )。

    A．最好情况下需要移动的数据元素数目为0

    B．最坏情况下需要移动的数据元素数目为n

    C．在平均情况下需要移动的数据元素数目为n/2

    D．最坏情况下需要移动的数据元素数目为n/2


    正确答案：D
    解析：在一般情况下，要在第i个元素之前插入一个新元素时，首先是从最后一个元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置。最好情况指的是性表的最后的元素之后插入一个新元素，则不需要移动表中元素，A是正确的。最坏情况指的是性表的第一个元素之前插入一个新元素，则需要移动表中所有的元素，B是正确的。在平均清况下需要移动的数据元素数目为n/2，C是正确的。

  • 第7题：

    在最坏情况下，二分查找法的时间复杂度为（ ）。


    正确答案：C
    二分法查找也称拆半查找，能使用二分1法查找的线性表必须满足两个条件，用顺序存储结构以及线性f表有序。利用二分法查找元素x的过程如下：将x与线性表1的中间项比较，如果X的值与中间项的值相等，则查找成功，1结束查找；如果x小于中间项的值，则在线性表的前半部分以二分法继续查找；如果x大于中间项的值，则在线性表的后半1部分以二分法继续查找。可以证明，对于长度为n的有序线性f表，在最坏情况下，二分法查找需比较l092n次，故时间复杂度1为l092n。故选择C选项。

  • 第8题：

    在最坏情况下，下列各排序方法的比较次数正确的是 （ ）


    正确答案：D
    在最坏情况下，冒泡排序和简单插入排序的比较次数均为n(n-1)/2。

  • 第9题：

    以比较为基础的排序算法在最坏情况下的计算时间下界为()。


    答案：D
    解析：

  • 第10题：

    快速排序在平均情况下的时间复杂度为（），在最坏情况下的时间复杂度为（）。


    正确答案:O（nlog2n）；O（n2）

  • 第11题：

    填空题
    快速排序在平均情况下的空间复杂度为（），在最坏情况下的空间复杂度为（）。

    正确答案： O（log2n）,O（n）
    解析： 暂无解析

  • 第12题：

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

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

    B

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

    C

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

    D

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


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

  • 第13题：

    在最坏情况下，冒泡排序所需要的比较次数为_______。


    正确答案：

    【答案】n(n-1)/2 
    【解析】在最坏情况下，冒泡排序所需要的比较次数为n(n-1)/2。 

  • 第14题：

    （ 1 ）下列叙述中正确的是

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

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

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

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


    正确答案：C

  • 第15题：

    度为10的线性表进行冒泡排序，在最坏情况下需要比较的次数为______。


    正确答案：45
    45 解析：对于长度为n的线性表，在最坏情况下(即线性表中元素现在的顺序与目标顺序正好相反)，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。

  • 第16题：

    分治合并排序的二分归并过程在最坏情况下花费多少时间


    参考答案：分治合并排序的二分归并过程在最坏情况下需比较n-1次，花费可用cn表示。

  • 第17题：

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


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

  • 第18题：

    以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中，最坏情况下计算时间可以达到O(nlogn)的是(59)；该算法采用的设计方法是(60)。

    A．归并排序

    B．插入排序

    C．选择排序

    D．冒泡排序


    正确答案：A
    解析：直接插入排序、简单选择排序和冒泡排序最坏情况下计算时间可以达到O(n2)，而归并排序的时间最坏情况下可以达到O(nlogn)。而归并排序也是分治策略的一个典型应用。

  • 第19题：

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


    正确答案：A

  • 第20题：

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


    正确答案：
    log= n

  • 第21题：

    对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是（）。若对其进行快速排序，在最坏的情况下所需要的时间是（）。


    正确答案:O（n2）；O（n2）

  • 第22题：

    堆排序是不稳定，空间复杂度为（）。在最坏情况下，其时间复杂度也为（）


    正确答案:O（1）；O（nlog2n）

  • 第23题：

    填空题
    对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是（）。若对其进行快速排序，在最坏的情况下所需要的时间是（）。

    正确答案： O（n2）,O（n2）
    解析： 暂无解析

相关内容