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