二路归并排序中每一趟排序都要开辟O（n)的辅助空间，共需élog2nù趟排序，为什么总的辅助空间仍为O（n)？

题目

二路归并排序中每一趟排序都要开辟O（n)的辅助空间，共需élog2nù趟排序，为什么总的辅助空间仍为O（n)？

相似考题

1.对n个记录的文件进行归并排序，所需要的辅助存储空间为A．O（1）B．O（n）C．O（log2n）D．O（n2）

2.在对n个元素的序列进行排序时,堆排序所需要的附加存储空间是()A、O(log2n)B、O(1)C、O(n)D、O(nlog2n)

3.（5）对 n 个记录的文件进行二路归并排序，所需要的辅助存储空间为___________。

4.（15）对 n 个记录的文件进行起泡排序，所需要的辅助存储空间为A）O(1)B）O(log2n)C）O(n)D）O(n2)

参考答案和解析
错误
更多“二路归并排序中每一趟排序都要开辟O（n)的辅助空间，共需élog2nù趟排序，为什么总的辅助空间仍为O（n)？”相关问题

  • 第1题：

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

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(n2)


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

  • 第2题：

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

    A、希尔排序

    B、堆排序

    C、选择排序

    D、归并排序


    正确答案:D

  • 第3题：

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

    A．O(1)

    B．O(nlog2n)

    C．O(n)

    D．O(n2)

    E．O(n(log2n)2)


    正确答案：B

  • 第4题：

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

    A．O(1)

    B．O(n)

    C．O(log2n)

    D．0(n2)


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

  • 第5题：

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

    A．O(log2n)

    B．O(n log2n)

    C．O(n)

    D．O(1)


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

  • 第6题：

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

    A．O

    B．O(n)

    C．O(log2n)

    D．O(n2)


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

  • 第7题：

    对n个记录的文件进行二路归并排序，所需要的辅助存储空间为（）。


    正确答案:O(n)

  • 第8题：

    简单选择排序算法里，每一趟选择最小的记录的过程，则每一趟排序的时间复杂度是（）。

    • A、O（n）
    • B、O（n*n）
    • C、O（1）
    • D、O（n*log2n）

    正确答案:A

  • 第9题：

    在对n个元素进行快速排序的过程中，平均情况下的空间复杂性为（）

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

    正确答案:D

  • 第10题：

    若对n个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（）

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

    正确答案:B

  • 第11题：

    填空题
    对n个记录的文件进行二路归并排序，所需要的辅助存储空间为（）。

    正确答案： O(n)
    解析： 暂无解析

  • 第12题：

    单选题
    简单选择排序算法中，每一趟选择最小的记录的过程，则每一趟排序的时间复杂度是（）
    A

    O（n）

    B

    O（n*n）

    C

    O（1）

    D

    O（n*log2n）


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

  • 第13题：

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

    A ） O( 1 )

    B ） O (log 2 n )

    C ） O(n)

    D ） O(n2）


    正确答案：C

  • 第14题：

    对长度为n的关键字序列进行堆排序的空间复杂度为 ( )

    A．O(log2n)

    B．O(1)

    C．O(n)

    D．O(n*log2n)


    正确答案：B
    解析：由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为0(1)，但它是不稳定的。

  • 第15题：

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

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(n2)


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

  • 第16题：

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

    A．O(1)

    B．O(n)

    C．O(1og2n)

    D．O(n2)


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

  • 第17题：

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

    A．O(1)

    B．0(n)

    C．O(1og2n)

    D．0(n2)


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

  • 第18题：

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

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

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

  • 第19题：

    简单选择排序算法中，每一趟选择最小的记录的过程，则每一趟排序的时间复杂度是（）

    • A、O（n）
    • B、O（n*n）
    • C、O（1）
    • D、O（n*log2n）

    正确答案:A

  • 第20题：

    归并排序中，归并的趟数是（）。

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

    正确答案:B

  • 第21题：

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


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

  • 第22题：

    单选题
    简单选择排序算法里，每一趟选择最小的记录的过程，则每一趟排序的时间复杂度是（）。
    A

    O（n）

    B

    O（n*n）

    C

    O（1）

    D

    O（n*log2n）


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

  • 第23题：

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

    希尔排序

    B

    堆排序

    C

    选择排序

    D

    归并排序


    正确答案： C
    解析：

  • 第24题：

    单选题
    对由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
    解析：

相关内容