待排序记录关键字出现有序的初始排列时，快速排序的时间复杂性达到最坏情况。

题目

待排序记录关键字出现有序的初始排列时，快速排序的时间复杂性达到最坏情况。

相似考题

1.以下关于快速排序算法的描述中，错误的是( )。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12，25，30，45，52，67，85}构成，则初始排列为( )时，排序效率最高(令序列的第一个元素为基准元素)。A．快速排序算法是不稳定的排序算法B．快速排序算法在最坏情况下的时间复杂度为0(nlgn)C．快速排序算法是一种分治算法D．当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度

2.在快速排序过程中,通常取序列中的第1个记录作为枢轴,以它为“分界线”重排其余记录。但当初始记录序列按关键字有序或基本有序时,快速排序将蜕化为起泡排序,为改进之,应如何选取枢轴记录?

3.若待排序的记录数目较少且已按关键字基本有序，则宜采用______排序算法。A．快速排序B．插入排序C．选择排序D．冒泡排序

4.快速排序算法的最坏时间复杂性和平均时间复杂性函数。

更多“待排序记录关键字出现有序的初始排列时，快速排序的时间复杂性达到最坏情况。”相关问题

  • 第1题：

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

    A．归并排序

    B．插入排序

    C．选择排序

    D．冒泡排序


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

  • 第2题：

    以关键字比较为基础的排序算法在最坏情况下的计算时间下界为

    O(nlogn)。下面的排序算法中，在最坏情况下计算时间可以达到

    O(nlogn)的是( 58 )；

    A.归并排序

    B.插入排序

    C.选择排序

    D.冒泡排序


    正确答案：A
    记忆几类常见的排序算法的时间复杂度即可。

  • 第3题：

    下列排序算法中，其时间复杂度和记录的初始排列无关的是 ( )

    A．插入排序

    B．堆排序

    C．快速排序

    D．冒泡排序


    正确答案：B

  • 第4题：

    当待排序序列初始有序时，快速排序的时间复杂性为O（n）。


    正确答案:错误

  • 第5题：

    设有10000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。

    • A、快速排序
    • B、堆排序
    • C、归并排序
    • D、插入排序

    正确答案:B

  • 第6题：

    设初始记录关键字基本有序，则快速排序算法的时间复杂度为O（nlog2n）。


    正确答案:错误

  • 第7题：

    快速排序在（）情况下部利于发挥其长处或优势。

    • A、记录有相同的关键字时
    • B、记录完全乱序时
    • C、记录已经基本有序时
    • D、记录的关键字较大时

    正确答案:C

  • 第8题：

    排序中当待排序记录的关键字（数值）（）时，排序结果是惟一的，否则排序结果不惟一。

    • A、都相同
    • B、都不相同
    • C、有序
    • D、无序

    正确答案:B

  • 第9题：

    多选题
    对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是（  ）。
    A

    直接插入

    B

    二分法插入

    C

    快速排序

    D

    顺序排序


    正确答案： B
    解析：

  • 第10题：

    单选题
    设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。
    A

    快速排序

    B

    堆排序

    C

    归并排序

    D

    插入排序


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

  • 第11题：

    判断题
    当待排序序列初始有序时，快速排序的时间复杂性为O（n）。
    A

    对

    B

    错


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

  • 第12题：

    单选题
    目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态无关的是（）
    A

    插入排序

    B

    直接选择排序

    C

    快速排序

    D

    冒泡排序


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

  • 第13题：

    下列排序算法中，()算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。

    A.堆排序

    B.冒泡排序

    C.快速排序

    D.希尔排序


    正确答案：C

  • 第14题：

    若待排序记录按关键字基本有序，则直采用的排序方法是（ ）。

    A. 直接插入排序 B. 堆排序C. 快速排序 D. 简单选择排序


    正确答案：A

  • 第15题：

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


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

  • 第16题：

    对n个待排序记录序列进行快速排序，所需要的最好时间是（），最坏时间是（）。


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

  • 第17题：

    当待排序序列初始有序时，简单选择排序的时间复杂性为O（n）。


    正确答案:错误

  • 第18题：

    对n=7，给出快速排序一个最好情况和最坏情况的初始排列的实例。


    正确答案:最好情况：4，7，5，6，3，1，2
    最坏情况：7，6，5，4，3，2，1

  • 第19题：

    次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（）。

    • A、堆排序
    • B、插入排序
    • C、快速排序
    • D、归并排序

    正确答案:C

  • 第20题：

    目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态无关的是（）

    • A、插入排序
    • B、直接选择排序
    • C、快速排序
    • D、冒泡排序

    正确答案:B

  • 第21题：

    判断题
    设初始记录关键字基本有序，则快速排序算法的时间复杂度为O（nlog2n）。
    A

    对

    B

    错


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

  • 第22题：

    问答题
    对n=7，给出快速排序一个最好情况和最坏情况的初始排列的实例。

    正确答案： 最好情况：4，7，5，6，3，1，2
    最坏情况：7，6，5，4，3，2，1
    解析： 暂无解析

  • 第23题：

    填空题
    对n个待排序记录序列进行快速排序，所需要的最好时间是（），最坏时间是（）。

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

  • 第24题：

    判断题
    当待排序序列初始有序时，简单选择排序的时间复杂性为O（n）。
    A

    对

    B

    错


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

相关内容