1.稳定排序
1.1：_____在其最好情况下的算法时间复杂度为O(n)。
A．插入排序 B．归并排序 C．快速排序 D．堆排序
1.2：在最好和最坏的情况下的时间复杂度均为O(nlogn)且稳定的排序方法是_____。
A．基数排序 B．快速排序 C．堆排序 D．归并排序
现需要对一个基本有序的数组进行排序。此时最适宜采用的算法为_________排算法，时间复杂度为______。
1.3：A 插入 B 快速 C 归并 D 堆
1.4：A O(n) B O(nlgn) C O(n^2) D O(n^2lgn)
1.5：从未排序的序列中依次取出一个元素与排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法为______。
A 插入排序 B 选择排序 C 快速排序 D 冒泡排序
1.6：两个递增序列A和B的长度分别为m和n(m＜n)，将两者归并为一个长度为m+n的递增序列时，______，归并过程中元素的比较次数最少。
A．当A的最大元素大于B的最大元素时
B．当A的最大元素小于B的最小元素时
C．当A的最小元素大于B的最小元素时
D．当A的最小元素小于B的最大元素时
2.不稳定排序
2.1：对n个元素的数组进行______ ，其平均时间复杂度和最坏情况下的时间复杂度都是O(nlogn)。
A．希尔排序 B．快速排序 C．堆排序 D．选择排序
2.2：对n个元素进行快速排序时，最坏情况下的时间复杂度为____。
A．O(1og2n) B．O(n) C．O(nlog2n) D． O(n2)
2.3：若总是以待排序列的第一个元素作为基准元素进行快速排序，那么最好情况下的时间复杂度为 ( ) 。
A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)
3.综合
在内排序的过程中，通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法，会产生不同的排序中间结果。设要将序列
( Q 81，H 72，C 67，Y 89，P 80，A 65，M 77，S 83，R 82，D 68，F 70，X 88 )
中的关键码按字母序的升序重新排列，
则 ____ 是冒泡排序一趟扫描的结果，
____ 是初始步长为4的希尔(Shell)排序一趟扫描的结果，
____ 是两路归并(合并)排序一趟扫描的结果，
____ 是以第一个元素为分界元素的快速排序一趟扫描的结果。
3.1～3.4：
①F，H，C，D，P，A，M，Q，R，S，Y，X
②P，A，C，S，Q，D，F，X，R，H，M，Y
③A，D，C，R，F，Q，M，S，Y，P，H，X
④H，C，Q，P，A，M，S，R，D，F，X，Y
⑤H，Q，C，Y，A，P，M，S，D，R，F，X
给定结点的关键字序列
（Ｆ 70、Ｂ 66、Ｊ 74、Ｇ 71、Ｅ 69、Ａ 65、Ｉ 73、Ｄ 68、Ｃ 67、Ｈ 72）
，对它按字母的字典顺序进行排列，采用不同方法，其最终结果相同。但中间结果是不同的。
Shell排序的第一趟扫描（步长为５）结果应为____。
冒泡排序（大数下沉）的第一趟起泡的效果是____。
快速排序的第一趟结果是____。
二路归并排序的第一趟结局是____。
供选择的答案
3.5：
①（B、F、G、J、A、D、I、E、H、C）
②（B、F、G、J、A、E、D、I、C、H）
③（A、B、D、C、E、F、I、J、G、H）
④（C、B、D、A、E、F、I、G、J、H）
3.6：
①（A、B、D、C、F、E、I、J、H、G）
②（A、B、D、C、E、F、I、H、G、J）
③（B、F、G、E、A、I、D、C、H、J）
④（B、F、G、J、A、E、D、I、C、H）
3.7：
①（C、B、D、A、F、E、I、J、G、H）
②（C、B、D、A、E、F、I、G、J、H）
③（B、A、D、E、F、G、I、J、H、C）
④（B、C、D、A、E、F、I、J、G、H）
3.8：
①（B、F、G、J、A、E、D、I、G、H）
②（B、A、D、E、F、G、I、J、H、C）
③（A、B、D、C、E、F、I、J、G、H）
④（A、B、D、C、F、E、J、I、H、C）
网友评论