更多“假设待排序的表长为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
    解析: 暂无解析