《数据结构》第08章在线测试

《数据结构》第08章在线测试

《数据结构》第08章在线测试 剩余时间：- 54:0-23 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(n^2)。 A、直接插入排序 C、快速排序 B、希尔排序 D、堆排序 2、在待排序的元素序列基本有序的前提下，效率最高的排序方法是＿＿＿＿＿＿＿。 A、直接插入排序 C、快速排序 B、起泡排序 D、堆排序 3、一组记录的关键字序列为{46，79，56，38，40，84}，则利用快速排序方法，以第一个记录为枢轴得到的一次划分结果是＿＿＿＿＿＿＿。 A、{38，40，46，56，79，84} C、{40，38，46，56，79，84} B、{40，38，46，79，56，84} D、{40，38，46，84，56，79} 4、在下列排序方法中，平均情况下占用内存量最大的是＿＿＿＿＿＿＿方法。 A、快速排序 C、冒泡排序 B、插入排序 D、堆排序 5、对n个记录的序列进行堆排序，最坏情况下的时间复杂度为＿＿＿＿＿＿。 A、O(logn) C、O(n) B、O(nlogn) D、O(n^2) 第二题、多项选择题（每题2分，5道题共10分） 1、下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(nlogn)。 A、希尔排序 B、堆排序 C、快速排序 D、简单选择排序 E、直接插入排序

2、下列排序方法中，＿＿＿＿＿＿＿＿是稳定的排序方法。

A、简单选择排序 B、起泡排序 C、快速排序 D、直接插入排序 E、折半插入排序

3、在下列排序方法中，每一趟排序结束后都能选出一个元素放在其最终位置上的是＿＿＿＿＿＿＿。

A、简单选择排序 B、起泡排序 C、快速排序 D、直接插入排序 E、堆排序

4、下列排序方法中，空间复杂度为O(1)的排序方法有＿＿＿＿＿＿＿＿。

A、堆排序 B、快速排序 C、直接插入排序 D、冒泡排序

5、下列排序方法中，在最坏情况下算法的时间复杂度为O(n^2)的有＿＿＿＿＿＿＿＿。

A、堆排序 B、快速排序 C、希尔排序 D、冒泡排序

第三题、判断题（每题1分，5道题共5分）

1、快速排序算法在待排序数据有序时最不利于发挥其长处。 正确 错误 2、对一个堆按层次遍历，一定能得到一个有序序列。 正确 错误 3、在数据表基本有序时，冒泡排序方法的时间复杂度一定接近O(n)。 正确 错误 4、由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。 正确 错误 5、快速排序算法在每趟排序结束时都能找到一个元素放到其最终位置上。 正确 错误 交卷