niusouti.com

53、基数排序比堆排序的空间复杂度高。

题目

53、基数排序比堆排序的空间复杂度高。

相似考题

1.插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中,不稳定的排序方法有_____、_____、______、________。

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

3.●在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是 (52) 。(52) A．快速排序B．堆排序C．归并排序D．基数排序

4.最好和最坏时间复杂度均为O(nlog2n)且稳定的排序方法是()。A.快速排序B.堆排序C.归并排序D.基数排序

参考答案和解析
错误
更多“53、基数排序比堆排序的空间复杂度高。”相关问题

  • 第1题：

    在下列排序方法中，平均时间性能为O(nlog2n)且空间性能最好的是( )。

    A．快速排序

    B．堆排序

    C．归并排序

    D．基数排序


    正确答案：B
    解析：堆排序先把序列看成一棵大根堆或小根堆，摘取最大或最小元素后再建成新的根堆，再排序。因此它的平均时间性能为O(nlog2n)且空间性能最好。

  • 第2题：

    在最好和最坏情况下的时间复杂度均为O(nlogn)，但不稳定的排序算法是(60)。

    A．堆排序

    B．快速排序

    C．归并排序

    D．基数排序


    正确答案：A
    解析：堆排序在最好和最坏情况下的时间复杂度均为O(nlogn)但不稳定。
      快速排序最好和最坏情况下的时间复杂度分别为O(n2)和O(nlogn)且不稳定。
      归并排序是在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法。
      基数排序在最好和最坏情况下的时间复杂度均为O(d(n+rd))。

  • 第3题：

    在基数排序、快速排列、堆排序、希尔排序中，排序方法稳定的是 ______。


    正确答案：基数排序
    基数排序 解析：在一个序列中相等的两个元素，在排序前后二者的相对位置没有发生变化的排序，称为稳定的，反之为不稳定的。通常排序过程中的“比较”是在相邻两个记录关键字间进行的排序方法是稳定的。

  • 第4题：

    对n个元素进行堆排序时，其空间复杂度为( )。

    A．O(log2n)

    B．O(n log2n)

    C．O(n)

    D．O(1)


    正确答案：D
    解析：堆排序每次都选出最大或最小的结点，需要的辅助空间始终只需要一个。

  • 第5题：

    对n个元素进行堆排序时，最坏情况下的时间复杂度为(53)。

    A．O(log2n)

    B．O(n)

    C．O(nlog2n)

    D．O(n2)


    正确答案：C
    解析：堆排序性能比较稳定，即使在最坏情况下的时间复杂度也是O(nlog2n)。

  • 第6题：

    在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是( )。

    A．快速排序

    B．堆排序

    C．归并排序

    D．基数排序


    正确答案：B
    解析：堆排序先把序列看成一棵大根堆或小根堆，摘取最大或最小元素后再建成新的根堆，再排序。因此它的平均时间性能为O(nlogn)且空间性能最好。

  • 第7题：

    在最好和最坏情况下的时间复杂度均为0(nlogn)且稳定的排序方法是()。

    A.基数排序
    B.归并排序
    C.快速排序
    D.堆排序

    答案：B
    解析：
    快速排序和堆排序是不稳定的，基数排序和归并排序是稳定的。基数排序的平均时间为O(d(n+rd))，最坏情况下时间复杂度为O(d(n+rd))；归并排序是一种稳定的排序方法，其最好和最坏情况下的时间复杂度为O(nlogn)。

  • 第8题：

    在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为（），整个堆排序过程的时间复杂度为（）。


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

  • 第9题：

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


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

  • 第10题：

    单选题
    在对n个元素进行堆排序的过程中，空间复杂度为（）
    A

     O（1）

    B

     O（log2n）

    C

     O（n2）

    D

     O（nlog2n）


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

  • 第11题：

    填空题
    在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为（），整个堆排序过程的时间复杂度为（）。

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

  • 第12题：

    单选题
    下面的排序算法中，不稳定的是（  ）。
    A

    起泡排序、折半插入排序、堆排序

    B

    折半插入排序、简单选择排序、堆排序

    C

    简单选择排序、希尔排序、堆排序

    D

    基数排序、堆排序、起泡排序。


    正确答案： B
    解析：

  • 第13题：

    下列内部排序方法中，稳定的排序方法是______。

    A．快速排序

    B．堆排序

    C．希尔排序

    D．基数排序


    正确答案：D
    解析：对于具有同一排序码的多个记录，若采用的排序方法使得排序后记录的相对次序不变，则此排序方法为稳定的。基数排序是一种借助多关键词排序的思想对单逻辑关键词进行排序的方法。基数排序不需要进行记录关键词间的比较，因此是一种稳定的排序方法。

  • 第14题：

    在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是(51)。

    A．基数排序

    B．快速排序

    C．堆排序

    D．归并排序


    正确答案：D
    解析：基数排序最坏的时间复杂度均为O(d(n+rd))；快速排序最好和最坏情况下F的时间复杂度分别为O(n2)和O(nlogn)且不稳定；堆排序在最好和最坏情况下的时间复杂度均为O(nlogn)但不稳定；归并排序是在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法。

  • 第15题：

    下面的排序方法中，平均时间性能为O(nlogn)且空间性能最好的是(26)。

    A．基数排序

    B．堆排序

    C．归并排序

    D．快速排序


    正确答案：B
    解析：快速排序、堆排序、归并排序的平均时间性能均为O(nlogn)，但是堆排序的空间性能最好。

  • 第16题：

    堆排序是(54)类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。

    A．插入

    B．归并

    C．基数

    D．选择


    正确答案：D

  • 第17题：

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

    A．堆排序

    B．冒泡排序

    C．快速排序

    D．SHELL排序


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

  • 第18题：

    在最坏情况下，冒泡排序的时间复杂度为________，简单插入排序的时间复杂度为________，希尔排序的时间复杂度为________，简单选择排序的时间复杂度为________，堆排序的时间复杂度为________。


    正确答案：
    O(n(n-1)/2)  O(n(n—1)/2)  O(n1.5) O(n(n—1)/2) O(nlog2n)

  • 第19题：

    占用的额外空间的空间复杂度为0(1)的排序算法是()。

    A.堆排序算法
    B.归并排序算法
    C.快速排序算法
    D.以上答案都不对

    答案：A
    解析：
    归并排序中，由于每一趟都要一个TR数组来复制，因此需要与待排记录等量的辅助空间O(n)；而快速排序中的递归所耗费的栈空间最好情况下也要O(logn)；堆排序仅在交换是需要一个记录的辅助空间。

  • 第20题：

    在对n个元素进行堆排序的过程中，空间复杂度为（）

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

    正确答案:A

  • 第21题：

    下列四种排序中（）的空间复杂度最大。

    • A、插入排序
    • B、冒泡排序
    • C、堆排序
    • D、归并排序

    正确答案:D

  • 第22题：

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

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

  • 第23题：

    单选题
    下列四种排序中（）的空间复杂度最大。
    A

    插入排序

    B

    冒泡排序

    C

    堆排序

    D

    归并排序


    正确答案： B
    解析： 归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。故归并排序的复杂度是最大的。

  • 第24题：

    单选题
    堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是（  ）。
    A

    O（n²）和O（1）

    B

    O（nlogzn）和O（1）

    C

    O（nlog₂n）和O（n）

    D

    O（n²）和O（n）


    正确答案： A
    解析：

相关内容