23 起泡排序

选择题

（1） 以下（ ）在数据序列基本有序时效率最高。 A．快速排序 B．起泡排序 C．堆排序 D．希尔排序

（2） 将记录序列{8，9，10，4，5，6，20}采用起泡排序排成升序序列，需要进行

（ ）趟（假设采用从前向后的扫描方式）。 A．3 B．4 C．5 D．8

41

24 快速排序

选择题

（1） 下列序列中，（ ）是执行一趟快速排序的结果。 A．[da，ax，eb，de，bb] ff [ha，gc] B．[cd，eb，ax，da] ff [ha，gc，bb] C．[gc，ax，eb，cd，bb] ff [da，ha] D．[ax，bb，cd，da] ff [eb，gc，ha]

（2） 快速排序在（ ）情况下最不利于发挥其长处。 A．待排序的数据量太大 B．待排序的数据中含有多个相同值 C．待排序的数据已基本有序 D．待排序的数据数量为奇数

（3） 对数列{25，84，21，47，15，27，68，35，20}进行排序，元素序列的变化情

况如下：

①25，84，21，47，15，27，68，35，20 ②20，15，21，25，47，27，68，35，84 ③15，20，21，25，35，27，47，68，84 ④15，20，21，25，27，35，47，68，84 则采用的排序方法是（ ）。 A．希尔排序 B．简单选择排序 C．快速排序 D．归并排序

（4） 一组记录的关键码为{46，79，56，38，40，84}，则利用快速排序的方法，以

第一个记录为基准得到的一次划分结果为（ ）。 A．{40，38，46，56，79，84} B．{40，38，46，79，56，84} C．{40，38，46，84，56，79} D．{84，79，56，46，40，38}

（5） 就平均时间而言，（ ）最佳。 A．起泡排序 B．直接插入排序 C．快速排序 D．简单选择排序

（6） 快速排序的最大递归深度是（ ），最小递归深度是（ ）。 A．○(1) B．○(log2n) C．○(n) D．○(nlog2n)

（7） 对以下数据序列利用快速排序进行排序，速度最快的是（ ）。 A．{21，25，5，17，9，23，30} B．{25，23，30，17，21，5，9} C．{21，9，17，30，25，23，5} D．{5，9，17，21，23，25，30}

（8） 对8个元素的线性表进行快速排序，最好情况下的比较次数为（ ）次。 A．7 B．8 C．12 D．13

应用题

（9） 对n=7，给出快速排序一个最好情况和最坏情况的初始排列的实例。

（10） 快速排序在什么情况下退化成起泡排序？如何改进？

（11） 对50个整数进行快速排序需进行的关键码之间的比较次数可能达到的最大值

和最小值分别是多少？

42

算法设计题

（12） 写出快速排序的非递归算法。

（13） 一个数组中的元素为正整数或负整数。设计算法将正整数和负整数分开，使线

性表的前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少比较次数。

（14） 设计算法将数组A[n]中所有的偶数移到奇数之前，要求不增加存储空间，且

时间复杂度为O(n)。

（15） 对给定序号j（1≤j≤n），要求在无序记录A[1]～A[n]中找到按关键码从小到

大排在第j位上的记录，试利用快速排序的划分思想设计算法实现上述查找。

（16） 荷兰国旗问题。要求重新排列一个由字符R、W、B（R代表红色，W代表白

色，B代表蓝色，这都是荷兰国旗的颜色）构成的数组，使得所有的R都排在最前面，W排在其次，B排在最后。为荷兰国旗问题设计一个算法，其时间性能是O(n)。

43

25 简单选择排序

选择题

（1） （ ）方法是从未排序序列中挑选元素，并将其放入排列序列的一端。 A．归并排序 B．插入排序 C．快速排序 D．选择排序

（2） 对数据序列{84，47，25，15，21}进行排序，数据序列的变化为：{84，47，

25，15，21}→{15，47，25，84，21}→{15，21，25，84，47}→{15，21，25，47，84}，则采用的排序方法是（ ）。 A．快速排序 B．简单选择排序 C．起泡排序 D．直接插入排序

（3） 简单选择排序的比较次数和移动次数分别为（ ）。 A．O(n)，O(log2n) B．O(log2n)，O(n2) C．O(n2)，O(n) D．O(nlog2n)，O(n)

44

26 二路归并排序

选择题

（1） 将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（ ）。 A．n B．2n-1 C．2n D．n-1

（2） 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选

择的排序方法是（ ）。 A．快速排序 B．堆排序 C．归并排序 D．希尔排序

（3） 二路归并的趟数是（ ）。 A．n B．log2n C．nlog2n D．n2

（4） （ ）在某趟排序结束后不一定能选出一个元素放到其最终位置上。 A．选择排序 B．堆排序 C．归并排序 D．起泡排序

（5） 下列排序算法中，（ ）在最坏情况下的时间复杂度不高于○（nlog2n）。 A．希尔排序 B．快速排序 C．归并排序 D．起泡排序

27 基数排序

选择题

（1） 以下排序方法中，（ ）不需要进行关键码的比较。 A．快速排序 B．归并排序 C．基数排序 D．堆排序

（2） 以下排序方法中，稳定的排序方法是（ ）。 A．快速排序 B．希尔排序 C．基数排序 D．堆排序

（3） 已知关键码序列{78，19，63，30，89，84，55，69，28，83}采用基数排序，

第一趟排序后的关键码序列为（ ）。

A．{19，28，30，55，63，69，78，83，84，89} B．{28，78，19，69，89，63，83，30，84，55} C．{30，63，83，84，55，78，28，19，89，69} D．{30，63，83，84，55，28，78，19，69，89}

（4） 将1000个英文单词进行排序，采用（ ）排序方法时间性能最好。 A．插入排序 B．快速排序 C．基数排序 D．堆排序

（5） 假设线性表中每个记录有两个数据项K1和K2，现对线性表按如下规则进行

排序：先按数据项K1由小到大排序，在K1值相同的情况下，K2值小的在前面，大的在后面，则应该采用的排序方法是（ ）。

A．先按K1值进行直接插入排序，再按K2的值进行简单选择排序 B．先按K2值进行直接插入排序，再按K1的值进行简单选择排序

45