1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 3 及答案解析(总分：72.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：36.00)1.下面给出的四种排序法中，( )排序法是不稳定性排序法。【北京航空航天大学 1999 一、10(2 分)】（分数：2.00）A.插入B.冒泡C.二路归并D.堆2.下列排序算法中，其中( )是稳定的。【福州大学 1998 一、3(2 分)】（分数：2.00）A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序3.稳定的排序方法是( )。【北方交通大学 2000 二、3(2 分)】（分数：2.00）A.直接
2、插入排序和快速排序B.折半插入排序和起泡排序C.简单选择排序和四路归并排序D.树形选择排序和 Shell 排序4.下列排序方法中，哪一个是稳定的排序方法?( )。【北方交通大学 2001 一、8(2 分)】（分数：2.00）A.直接选择排序B.二分法插入排序C.希尔排序D.快速排序5.下列排序算法中，( )是稳定排序。【北京理工大学 2007 一、10(1 分)】（分数：2.00）A.希尔排序B.快速排序C.堆排序D.直接插入排序6.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。( )就是不稳定的排序方法。【清华大学 1998 一、3(2
3、 分)】（分数：2.00）A.起泡排序B.归并排序C.Shell 排序D.直接插入排序E.简单选择排序7.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选( )排序为宜。【中科院计算所 2000一、5(2 分)】（分数：2.00）A.直接插入B.直接选择C.堆D.快速E.基数8.若需在 O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )。【中国科技大学 1998 二、4(2 分)】【中科院计算所 1998 二、4(2 分)】（分数：2.00）A.快速排序B.堆排序C.归并排序D.直接插入排序9.下面的排序算法中，不稳定的是( )。【北京工业大学
4、 1999 一、2(2 分)】（分数：2.00）A.起泡排序B.折半插入排序C.简单选择排序D.希尔排序E.基数排序下列内部排序算法中：【北京工业大学 2000 一、1(10 分每问 2 分)】A快速排序 B直接插入排序C二路归并排序 D简单选择排序 E起泡排序（分数：8.00）(1).其比较次数与序列初态无关的算法是( )（分数：2.00）A.B.C.D.E.(2).不稳定的排序算法是( )（分数：2.00）A.B.C.D.E.(3).在初始序列已基本有序(除去 n 个元素中的某 k 个元素后即呈有序，k3)个数，将分成长为 n 一 2 和 2 的前后两部分 A 和 B，分别找出最大者和最小
5、者：MaXA、MinA、MaxB、MinB，最后 Max=MaXA，MaxB)和 Min=MinA，MinB)。对 A 使用同样的方法求出最大值和最小值，直到元素个数不超过 3。设 C(n)是所需的最多比较次数，根据上述原则，当 n3 时有如下关系式： )解析：31.利用比较的方法进行排序，在最坏的情况下，能达到的最好时间复杂性是什么?请给出详细证明。【上海交通大学 2000 六(8 分)】（分数：2.00）_正确答案：(正确答案：假定待排序的记录有 n 个。由于含 n 个记录的序列可能出现的状态有 n!个，则描述 n 个记录排序过程的判定树必须有 n!个叶子结点。因为若少一个叶子，则说明尚有
6、两种状态没有分辨出来。我们知道，若二叉树高度是 h，则叶子结点个数最多为 2 k-1 ；反之，若有 u 个叶子结点，则二叉树的高度至少为log 2 u+1。这就是说，描述 n 个记录排序的判定树必定存在一条长度为log 2 (n!)的路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log 2 (n!)。根据斯特林公式，有log 2 (n!)I=O(nlog 2 n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为 O(nlog 2 n)。证毕。)解析：32.以下概念的区别：拓扑排序与冒泡排序。【大连海事大学 1996 三、2(3)(2 分)】（分数：2.00）_正确答案：(正确答案：拓扑排序和冒泡排序是两个完全不同的概念，前者是由某个集合上的偏序得到集合上的全序的操作，是对有向图的顶点的排序，主要解决一个工程能否顺利进行的问题；后者是借助交换思想通过比较相邻结点关键字大小进行排序的算法，用于解决无序记录的排序问题。)解析：
