软考-算法-排序（上）

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）