itgle.com

假设待排序的表长为n，那么下列排序算法中，（）排序算法需要O（n)的辅助空间。A．简单选择B．插入C．冒泡D．归并

题目

假设待排序的表长为n，那么下列排序算法中，（）排序算法需要O（n)的辅助空间。

A．简单选择

B．插入

C．冒泡

D．归并

相似考题

1.下列排序方法中,在最坏情况下算法的时间复杂度为 O(n^2)的有________。A、堆排序B、快速排序C、希尔排序D、冒泡排序

2.下列排序方法中，最好情况下，时间复杂度为O(n)的算法是______。A．选择排序B．归并排序C．快速排序D．直接插入排序

3.在下面的排序方法中,辅助空间为O(n)的是( ) 。A、希尔排序B、堆排序C、选择排序D、归并排序

4.n个元素排序问、如果只能通过元素比较交换构造算法,则n个处理器的并行排序算法达到____的运行时间才是代价最优的。A、O(logn)B、O(n)C、O(nlogn)D、O(n^2)

更多“假设待排序的表长为n，那么下列排序算法中，（）排序算法需要O（n)的辅助空间。”相关问题

  • 第1题：

    有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。

    ① 给出适用于计数排序的顺序表定义;

    ② 编写实现计数排序的算法;

    ③ 对于有n个记录的表，关键字比较次数是多少?

    ④ 与简单选择排序相比较，这种方法是否更好?为什么?


    参考答案：
    　　[算法描述]
    　　① typedef struct
    　　{int key;
    　　datatype info
    　　}RecType
    　　② void CountSort(RecType a[],b[],int n)
    　　//计数排序算法，将a中记录排序放入b中
    　　{for(i=0;i　　{for(j=0,cnt=0;j　　if(a[j].key　　b[cnt]=a[i];
    　　}
    　　}//Count_Sort
    　　③ 对于有n个记录的表，关键码比较n2次。
    　　④ 简单选择排序算法比本算法好。简单选择排序比较次数是n(n-1)/2,且只用一个交换记录的空间;而这种方法比较次数是n2，且需要另一数组空间。
    　　[算法讨论]因题目要求“针对表中的每个记录，扫描待排序的表一趟”，所以比较次数是n2次。若限制“对任意两个记录之间应该只进行一次比较”，则可把以上算法中的比较语句改为：
    　　for(i=0;i　　for(i=0;i　　for(j=i+1;j　　if(a[i].key

  • 第2题：

    对由n个记录所组成的有序关键码排序时，下列各常用排序算法的平均比较次数分别是：二路归并排序为(29)，冒泡排序(30)，快速排序为(31)。其中，归并排序和快速排序所需要的辅助存储分别是(32)和(33)。

    A．O(1)

    B．O(nlog2n)

    C．O(n)

    D．O(n2)

    E．O(n(log2n)2)


    正确答案：B

  • 第3题：

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

    A．归并排序

    B．插入排序

    C．选择排序

    D．冒泡排序


    正确答案：A
    解析：归并排序(mergesort)，是把待排序的文件分成n个已排序的子文件，将这些文件合并得到完全排序的文件。n个记录的平均运算次数是O(nlog2n)，所需的辅助存储空间是O(n)，该算法采用的设计方法是分治法。

  • 第4题：

    下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是

    A、堆排序

    B、起泡排序

    C、直接选择排序

    D、快速排序


    正确答案：C

  • 第5题：

    下列各种排序算法中平均时间复杂度为O(n)是()。

    A.快速排序
    B.堆排序
    C.归并排序
    D.冒泡排序

    答案：D
    解析：

  • 第6题：

    数据结构与算法里，以下算法时间复杂度是O（n*n）的是（）。

    • A、冒泡排序
    • B、直接插入排序
    • C、折半查找
    • D、希尔排序

    正确答案:A,B

  • 第7题：

    排序的平均时间复杂度为O（n•logn）的算法是（），为O（n•n）的算法是（）


    正确答案:快速排序、二路归并排序、堆排序；直接插入排序、简单选择排序、起泡排序

  • 第8题：

    数据结构与算法里，冒泡排序N个记录需要N-1趟排序，就可以完成排序。


    正确答案:正确

  • 第9题：

    单选题
    下列各种排序算法中平均时间复杂度为O（n2）是（）
    A

    快速排序

    B

    堆排序

    C

    归并排序

    D

    冒泡排序


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

  • 第10题：

    多选题
    数据结构与算法里，时间复杂度低于O（n*n）的排序有（）。
    A

    快速排序

    B

    冒泡排序

    C

    直接插入排序

    D

    希尔排序


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

  • 第11题：

    多选题
    数据结构与算法中，快速排序的特性描述正确的是（）。
    A

    快速排序是稳定排序

    B

    快速排序不稳定排序

    C

    快速排序的时间复杂度是O（nlog2n）

    D

    快速排序的时间复杂度是O（n*n）


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

  • 第12题：

    单选题
    对由n个记录所组成的表按关键码排序时，下列各个常用排序算法的平均比较次数分别是：二路归并排序为（ ），直接插入排序为（ ），快速排序为（ ），其中，归并排序和快速排序所需要的辅助存储分别是（ ）和（ ）。a.O（l）b.O（nlogzn）c.O（n）d.O（n2）e.O（n（logzn）2）f.O（logzn）
    A

    bdbcf

    B

    bcfed

    C

    dbecf

    D

    debfc


    正确答案： D
    解析：

  • 第13题：

    下列方法中,()算法的时间复杂度为O(n²)。

    A.堆排序

    B.希尔排序

    C.快速排序

    D.直接插入排序


    参考答案：D

  • 第14题：

    对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为（62）；若采用快速排序算法，则时间和空间复杂度分别为（63）。

    A.O（n2）和O（n）

    B.O（n）和O（n）

    C.O（n2）和O（1）

    D.O（n）和O（1）


    正确答案：C
    本题考查基本排序算法的时间复杂度与空间复杂度。

  • 第15题：

    下列排序算法中，时间复杂度为O(nlog2n)且占用额外空间最少的是(18)。

    A．堆排序

    B．冒泡排序

    C．快速排序

    D．SHELL排序


    正确答案：A
    解析：其他都不符合条件。

  • 第16题：

    快速排序算法是，在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了 （ ） 算法设计策略。已知确定着基准元素操作的时间复杂度为O(n)，则快速排序算法的最好和最坏情况下的时间复杂度为 （请作答此空） 。

    A.O(n)和O(nlgn)
    B.O(n)和O(n2)
    C.O(nlgn)和O(nlgn)
    D.O(nlgn)和O(n2)

    答案：D
    解析：
    将数据分成若干份，每份单独处理后再合并，其思想为分治。
    理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为O(nlgn)。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为O(n)，次操作的总复杂度为O(n2)。

  • 第17题：

    数据结构与算法中，快速排序的特性描述正确的是（）。

    • A、快速排序是稳定排序
    • B、快速排序不稳定排序
    • C、快速排序的时间复杂度是O（nlog2n）
    • D、快速排序的时间复杂度是O（n*n）

    正确答案:B,C

  • 第18题：

    下列各种排序算法中平均时间复杂度为O（n2）是（）

    • A、快速排序
    • B、堆排序
    • C、归并排序
    • D、冒泡排序

    正确答案:D

  • 第19题：

    下列排序算法中，（）需要的辅助存储空间最大。

    • A、快速排序
    • B、插入排序
    • C、希尔排序
    • D、基数排序

    正确答案:A

  • 第20题：

    数据结构与算法里，时间复杂度低于O（n*n）的排序有（）。

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

    正确答案:A,D

  • 第21题：

    填空题
    排序的平均时间复杂度为O（n•logn）的算法是（），为O（n•n）的算法是（）

    正确答案： 快速排序、二路归并排序、堆排序,直接插入排序、简单选择排序、起泡排序
    解析： 暂无解析

  • 第22题：

    单选题
    下列排序算法中，（）需要的辅助存储空间最大。
    A

    快速排序

    B

    插入排序

    C

    希尔排序

    D

    基数排序


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

  • 第23题：

    单选题
    在下面的排序方法中，辅助空间为O（n）的是（  ）。
    A

    希尔排序

    B

    堆排序

    C

    选择排序

    D

    归并排序


    正确答案： C
    解析：

  • 第24题：

    多选题
    数据结构与算法里，以下算法时间复杂度是O（n*n）的是（）。
    A

    冒泡排序

    B

    直接插入排序

    C

    折半查找

    D

    希尔排序


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

相关内容