MOOC数据结构与算法Python版-第七周测验

本文主要是介绍MOOC数据结构与算法Python版-第七周测验，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 单选(2分)

以下关于冒泡和选择排序算法的叙述何者正确？B

A.

平均时间复杂度上，冒泡排序的复杂度较低
B.

其它选项皆不正确。
C.

平均时间复杂度上，选择排序的复杂度较低
D.

空间复杂度上，选择排序的复杂度较低

解析： B、两者均有O（N^2）的时间复杂度和O（1）的空间复杂度。

2 单选(2分)

以下关于归并和快速排序算法的叙述何者正确？D

A.

空间复杂度上，归并排序的复杂度较低
B.

平均时间复杂度上，快速排序的复杂度较低
C.

平均时间复杂度上，归并排序的复杂度较低
D.

空间复杂度上，快速排序的复杂度较低

解析： D、空间复杂度上，归并排序的复杂度是O（N），快速排序是O（logN）；时间复杂度上均是O（N logN）

3 单选(2分)

设一组初始记录关键字序列(5，2，6，3，8)，利用冒泡排序进行升序排序，则第一趟冒泡排序的结果为以下何者？B

A.

2，3，5，6，8
B.

2，5，3，6，8
C.

2，3，6，5，8
D.

2，5，6，3，8

解析： B、第一趟冒泡后，2和5易位，3和6易位

4 单选(2分)

设一组初始记录关键字序列(5，2，6，3，8)，利用插入排序进行升序排序，则第二次插入排序的结果为以下何者？C

A.

2，5，3，6，8
B.

2，3，5，6，8
C.

2，5，6，3，8
D.

5，2，3，6，8

解析： C、第一次将2插入到5前面，序列变成2，5，6，3，8；第二次将6插入到5后面，序列还是2，5，6，3，8。

5 单选(2分)

给定两个顺序列表mylst1, mylst2，两者的长度分别为m<n为已知，现要查找其中位数，问最好的查找方式的时间复杂度？D

A.

O(m^2)
B.

O(m logn)
C.

O(mn)
D.

O(logm)

解析： D、先取两者各自的中位数进行比较，并对mylst1进行二分查找，以mylst2对应的反向shift下标取得的值作为比较基准。

6 多选(3分)

所谓排序算法的稳定性是指：排序前2个相等的数，其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。以下哪些排序算法是稳定的？CD

A.

选择排序
B.

希尔排序
C.

归并排序
D.

插入排序

7 多选(3分)

现在有一个几乎顺序排列的，非常大的列表。问以下哪些算法有可能得到时间复杂度O(N)? BCD

A.

快速排序
B.

插入排序
C.

冒泡排序
D.

归并排序

解析： A、快速排序的比较次数有O(n logn） B、对于列表 mylst = [100000]+[i for i in range(100000)]+[i for i in range(100001, 200000)]，若总是从已排序完成的列表末尾开始检查，那么前100000个插入各要两次比较，后面各要一次比较，比较次数与赋值操作次数均为O(n）。 C、对于列表 mylst = [100000]+[i for i in range(100000)]+[i for i in range(100001, 200000)]，第二趟冒泡列表无变动，可判定冒泡排序完成。 D、排序过程中可检测，如果前段序列的最大值小于等于后段序列最小值，则说明序列可以直接形成一段有序序列不需要再归并。

8 多选(3分)

以下哪些排序方式，其最坏情况的时间复杂度O(N^2)的？ABD