Question

数据结构第8章测试 排序

Answer 1

第一题、单项选择题（每题1分，5道题共5分）
1、一组记录的关键字序列为{46，79，56，38，40，84}，则利用快速排序方法，以第一个记录为枢轴得到的一次划分结果是＿＿＿C＿＿＿＿。
A、{38，40，46，56，79，84} B、{40，38，46，79，56，84}
C、{40，38，46，56，79，84} D、{40，38，46，84，56，79}
2、对于关键字序列{12，13，10，18，60，15，7，20，25，100}用筛选法建堆，必须从关键字为＿＿＿＿B＿＿＿的结点开始。
A、18 B、60
C、15 D、7
3、排序方法中，从未排序序列中挑选元素，将其依次放至已排序序列（初始为空）的一端的方法，称为＿＿＿＿C＿＿＿。
A、插入排序 B、交换排序
C、选择排序 D、归并排序
4、下列序列中，＿＿＿＿A＿＿＿＿是堆。
A、{12，35，20，60，40，30} B、{100，85，120，38，10，9，36}
C、{1，5，6，24，7，3，4 } D、{38，24，15，20，30，46}
5、对n个记录的序列进行堆排序，最坏情况下的时间复杂度为＿＿＿B＿＿＿。
A、O(logn) B、O(nlogn)
C、O(n) D、O(n^2)
第二题、多项选择题（每题2分，5道题共10分）
1、下列方法中，＿＿＿＿BC＿＿＿＿算法的时间复杂度为O(nlogn)。
A、希尔排序
B、堆排序
C、快速排序
D、简单选择排序
E、直接插入排序
2、下列排序方法中，＿＿＿＿BDE＿＿＿＿是稳定的排序方法。
A、简单选择排序
B、起泡排序
C、快速排序
D、直接插入排序
E、折半插入排序
3、下列序列中，＿＿＿＿AB＿＿＿＿是堆。
A、{15,30,22,93,52,71}
B、{15,22,30,52,71,93}
C、{15,52,22,93,30,71}
D、{15,52,22,71,30,93}
4、在下列排序方法中，每一趟排序结束后都能选出一个元素放在其最终位置上的是＿＿＿ABCE＿＿＿＿。
A、简单选择排序
B、起泡排序
C、快速排序
D、直接插入排序
E、堆排序
5、下列排序方法中，空间复杂度为O(1)的排序方法有＿＿＿ACD＿＿＿＿＿。
A、堆排序
B、快速排序
C、直接插入排序
D、冒泡排序
第三题、判断题（每题1分，5道题共5分）
1、快速排序的速度在所有排序方法中是最快的，而且所需的附加空间也最少。F
正确 错误
2、在一个大顶堆中，最小元素不一定在最后。T
正确 错误
3、在数据表基本有序时，冒泡排序方法的时间复杂度一定接近O(n)。T
正确 错误
4、由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。F
正确 错误
5、在初始数据表为逆序时，冒泡排序所执行的比较次数最多。T
正确 错误