更多“需要辅助空间为O(1)的排序方法有()。”相关问题
  • 第1题:

    时间复杂性为O(nlog2n)且空间复杂性为O(1)的排序方法是()。

    A.归并排序

    B.堆排序

    C.快速排序

    D.锦标赛排序


    参考答案:B

  • 第2题:

    ●若关键字是非负整数,快速排序、归并、堆排序和基数排序 (54) 最快。若要求辅助空间为O (1) ,应选 (55) 。

    (54),(55) A.快速排序

    B.归并排序

    C.堆排序

    D.基数排序


    正确答案:A,C
    【解析】①在初始序列杂乱无序的前提下,最快的是快速排序。②若要求辅助空间为O(1),应选堆排序。③若要求排序稳定,且关键字为实数,则应选归并排序和基数排序。

  • 第3题:

    n个记录的文件进行快速排序,所需要的辅助存储空间为( )。

    A.O(1)

    B.O(log2n)

    C.O(n)

    D.O(n2)


    正确答案:B
    解析:快速排序的思想是不断对待排序的元素按指定的元素进行划分,然后对两部分再进行划分……。在划分过程中,用到递归算法,其递归算法平均深度为约为 log2n,所以其空间复杂度为O(log2n)。

  • 第4题:

    若关键字是非负整数,快速排序、归并排序、堆排序和基数排序中(54)最快。若要求辅助空间为O(1),应选(55)。

    A.快速排序

    B.归并排序

    C.堆排序

    D.基数排序


    正确答案:A

  • 第5题:

    对n个记录的文件进行起泡排序,所需要的输助存储空间为( )。

    A.O(1)

    B.O(1og2n)

    C.O(n)

    D.O(n2)


    正确答案:A
    解析:下表给出了主要排序方法的性能比较:

    根据上表,对n个记录的文件进行起泡排序,所需要的辅助存储空间为O(1)。

  • 第6题:

    对n个记录的文件进行起泡排序,所需要的辅助存储空间为

    A.O(1)

    B.O(log2n)

    C.O(n)

    D.O(n2)


    正确答案:A
    解析:本题考查起泡排序的概念。起泡排序是将排序的记录顺次两两比较,若为逆序则进行交换。不管对多少个记录的文件进行起泡排序,所需要的辅助存储空间都为 O(1)。正确答案为选项A。

  • 第7题:

    对n个记录的文件进行归并排序,所需要的辅助存储空间为

    A.O(1)

    B.O(n)

    C.O(1og2n)

    D.O(n2)


    正确答案:B
    解析:对n个记录的文件进行归并排序,所需要的辅助存储空间为O(n)。A) 选项为冒泡排序、简单选择排序、插入排序所需要的辅助存储空间。

  • 第8题:

    对n个记录的序列进行快速排序,所需的辅助存储空间为( )。

    A.O(1)

    B.O(log2n)

    C.O(n)

    D.O(n2)


    正确答案:B
    解析:快速排序对待排序序列的划分大约为log2n次,而快速排序是通过递归算法来完成的,递归深度大约为log2n,因此所需的辅助存储空间为O(log2n)。

  • 第9题:

    下面给出的四种排序方法中,辅助空间为O(n)的是()。

    A.希尔选择
    B.冒泡排序
    C.归并排序
    D.堆排序

    答案:C
    解析:
    希尔选择、冒泡排序、堆排序的辅助空间都为0(1);而归并排序中,由于每一趟都要一个TR数组来复制,因此需要与待排记录等量的辅助空间O(n)。

  • 第10题:

    对n个记录的文件进行起泡排序,所需要的输助存储空间为()。

    • A、O(1)
    • B、O(log2n)
    • C、O(n)
    • D、O(n2

    正确答案:A

  • 第11题:

    对于直接插入排序,希尔排序,冒泡排序,快速排序,直接选择排序,堆排序和归并排序等排序方法,分别写出:(1)平均时间复杂度低于O(n2)的排序方法;(2)所需辅助空间最多的排序方法;


    正确答案: (1) 希尔、快速、堆、归并
    (2) 归并

  • 第12题:

    问答题
    对于直接插入排序,希尔排序,冒泡排序,快速排序,直接选择排序,堆排序和归并排序等排序方法,分别写出:(1)平均时间复杂度低于O(n2)的排序方法;(2)所需辅助空间最多的排序方法;

    正确答案: (1) 希尔、快速、堆、归并
    (2) 归并
    解析: 暂无解析

  • 第13题:

    在下列排序方法中,空间复杂性为O(n)的方法为()。

    A.快速排序

    B.直接插入排序

    C.堆排序

    D.归并排序


    参考答案:D

  • 第14题:

    对N个记录的文件进行快速排序,所需要的辅助存储空间为

    A.O( )

    B.O

    C.O( )

    D.O( )


    正确答案:B

  • 第15题:

    在下面的排序方法中,辅助空间为O(n)的是( ) 。

    A、希尔排序

    B、堆排序

    C、选择排序

    D、归并排序


    正确答案:D

  • 第16题:

    以下关于快速排序的叙述正确的是()

    A.快速排序在所有排序方法中最快,而且所需辅助空间最少

    B.在快速排序中,不可以用队列替代栈

    C.快速排序的空间复杂度为O(n))

    D.快速排序在待排序的数据随机分布时效率最高


    参考答案:D

  • 第17题:

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

    A.O(1)

    B.O(nlog2n)

    C.O(n)

    D.O(n2)

    E.O(n(log2n)2)


    正确答案:B

  • 第18题:

    对n个记录的文件进行归并排序,所需要的辅助存储空间为

    A.O(1)

    B.O(n)

    C.O(log2n)

    D.0(n2)


    正确答案:B
    解析:对n个记录的文件进行归并排序,所需要的辅助存储空间为O(n),因为归并排序的实现过程需要两个包含n个记录的数组,每趟归并需将所有记录从一个数组移到另一数组中。本题的答案为B。

  • 第19题:

    对n个记录的文件进行归并排序,所需要的辅助存储空间为_______。

    A.O(1)

    B.0(n)

    C.O(1og2n)

    D.0(n2)


    正确答案:B
    解析:对n个记录的文件进行归并排序,所需要的辅助存储空间为O(n),因为归并排序的实现过程需要用两个包含n个记录的数组,每趟归并需将所有记录从一个数组移至另一数组中。

  • 第20题:

    对n个记录的文件进行归并排序,所需要的辅助存储空间为

    A.O

    B.O(n)

    C.O(log2n)

    D.O(n2)


    正确答案:B
    解析:对n个记录的文件进行归并排序,所需要的辅助存储空间为O(n)。A)选项为起泡排序、简单选择排序、插入排序所需要的辅助存储空间。

  • 第21题:

    对n个记录的文件进行快速排序,所需要的辅助存储空间大致为()。


    答案:C
    解析:

  • 第22题:

    下列排序算法中,()需要的辅助存储空间最大。

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

    正确答案:A

  • 第23题:

    对n个记录的文件进行快速排序,所需要的辅助存储空间大致为()。

    • A、O(1)
    • B、O(n)
    • C、O(1og2n)
    • D、O(n2)

    正确答案:C

  • 第24题:

    单选题
    在下面的排序方法中,辅助空间为O(n)的是(  )。
    A

    希尔排序

    B

    堆排序

    C

    选择排序

    D

    归并排序


    正确答案: C
    解析: