1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 5 及答案与解析一、单项选择题1 下列序列中，( ) 是执行第一趟快速排序后所得的序列。【福州大学 1998 一、9(2 分)】（A）68 ，11，18，69 23，93，73（B） 68，11，69，23 18，93，73（C） 93，7368 ，11，69，23，18（D）68 ，11，69，23，18 93，732 适合并行处理的排序算法是( )。【西安电子科技大学 2005 一、8(1 分)】【电子科技大学 2005 一、8(1 分)】（A）选择排序（B）快速排序（C）希尔排序（D）基数排序3 一组记录的关键字为(46，79，56，3
2、8，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。【北京交通大学 2005 一、8(2 分)【燕山大学 2001 一、4(2 分)】（A）(38 ，40，46，56，79，84)（B） (40，38，46，79，56，84)（C） (40，38，46，56，79，84)（D）(40 ，38，46，84，56，79)4 下列排序算法中，( ) 算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。【中南大学 2005 一、4(2 分)】（A）快速排序（B）堆排序（C）希尔排序（D）冒泡排序5 将一组无序的数据重新排列成有序序列，其方法有：( )。【武汉
3、理工大学 2004一、8(3 分) 】（A）拓扑排序（B）快速排序（C）堆排序（D）基数排序6 就平均性能而言，目前最好的内排序方法是( )排序法。【西安电子科技大学1998 一、9(2 分) 】（A）冒泡（B）希尔插，A（C）交换（D）快速7 如果只想得到 1000 个元素组成的序列中第 5 个最小元素之前的部分排序的序列，用( )方法最快。 【清华大学 1998 一、2(2 分) 】（A）起泡排序（B）快速排列（C） Shell 排序（D）堆排序（E）简单选择排序8 若要从 1000 个元素中选出前 10 个最小的元素，( )是最适合的算法。【北京理工大学 2005 一、9(1 分) 】（
4、A）直接插入排序（B）归并排序（C）堆排序（D）快速排序9 对数据序列(8，9，10，4，5，6，20，1，2)采用(由后向前次序的)冒泡排序，需要进行的趟数(遍数) 至少是( ) 。【中国科学技术大学 2005】（A）3（B） 4（C） 5 （D）810 下列排序算法中，占用辅助空间最多的是：( )。【厦门大学 2002 五、2(8 分)】（A）归并排序（B）快速排序（C）希尔排序（D）堆排序11 在下面的排序方法中，辅助空间为 O(m)的是( )。【南京理工大学 1999 一、17(1 分 )】（A）希尔排序（B）堆排序（C）选择排序（D）归并排序12 从未排序序列中依次取出一个元素与已排
5、序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。【北京航空航天大1999 一、8(2 分) 】（A）插入（B）选择（C）希尔（D）二路归并13 在下列排序方法中，( )方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。【武汉理工大学 2003 一、10(2612 分)】（A）快速排序（B）冒泡排序（C）堆排序（D）插入排序14 用直接插入排序方法对下面四个序列进行排序(由小到大)，元素比较次数最少的是( )。【 北方交通大学 2001 一、15(2 分) 】（A）94，32，40，90，80，46，21，69（B） 32
6、，40，21，46，69，94，90，80（C） 21，32，46，40，80，69，90，94 （D）90，69，80，46，21，32，94，4015 直接插入排序在最好情况下的时间复杂度为( )。【北京邮电大学 1999 一、5(2分)】（A）O(logn)（B） O(n)（C） O(n*logn)（D）O(n 2)二、填空题16 堆是一种有用的数据结构。试判断下面的关键字序列中哪一个是堆_。16，72，31 ，23，94， 53 94，53，31，72 ，16，2316，53，23 ，94，31， 72 16，31，23，94 ，53，7294，31，53 ，23，16， 72 堆排序
7、是一种(1) 类型的排序，它的一个基本问题是如何建堆，常用的建堆算法是 1964 年 Floyd 提出的(2)，对含有 n 个元素的序列进行排序时，堆排序的时间复杂度是(3)，所需要的附加结点是(4)。【山东工业大学1994 一、2(5 分17 堆是一种有用的数据结构。堆排序是一种(1)排序，堆实质上是一棵(2)结点的层次序列。对含有 n 个元素的序列进行排序时，堆排序的时间复杂度是(3)，所需的附加存储结点是(4)。关键字序列 05，23，16，68，94，72，71，73 是否满足堆的性质(5)。【山东工业大学 1996 三、1(5 分) 】18 每次使两个有序表合并成一个有序表，这种排序
8、方法叫做_排序。【哈尔滨工业大学 2005 一、6(1 分)】19 按 LSD 进行多关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_的排序方法。【北京交通大学 2004 二、5(2 分)】20 分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，则最省时间的是_算法，最费时间的是_算法。【福州大学 1998 二、10(2 分 )】21 不受待排序初始序列的影响，时间复杂度为 O(N2)的排序算法是_，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_。 【中国人民大学 2001 一、3(2 分)】三、判断题22 归并排序要求的辅助空间最多。
9、( )【中国海洋大学 2007 二、15(1 分)】（A）正确（B）错误23 在分配排序时，最高位优先分配法比最低位优先分配法简单。( )【上海交通大学 1998 一、20(1 分) 】（A）正确（B）错误24 快速排序是排序算法中最快的一种。 ( )【暨南大学 2010 三、1(1 分)】（A）正确（B）错误25 在任何情况下，归并排序都比简单插入排序快。 ( )【北京邮电大学 2000 一、4(1 分)2002 一、 9(1 分)】（A）正确（B）错误26 基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。( )【哈尔滨工业大学 2003 二、8(1 分) 】（A）正确
10、（B）错误27 外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间 取决于内部排序的时间。( )【北京邮电大学 1998 一、8(2 分)】（A）正确（B）错误28 在外排序过程中，对长度为 n 的初始序列进行“置换一选择” 排序时，可以得到的最大初始有序段的长度不超过 n2。( )【大连海事大学 2001 一、3(1 分)】（A）正确（B）错误四、综合题28 在堆排序、快速排序和合并排序中：29 若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法?30 若只从排序结果的稳定性考虑，则应选取哪种排序方法?31 若只从平均情况下排
11、序最快考虑，则应选取哪种排序方法?32 若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法?【吉林大学 2001 一、5(6 分) 】32 已知关键字集合为32，6，50，27，97，1 5，92，29，20)，要求按关键字递增排序33 若采用快速排序，请给出第一趟、第二趟的排序结果。34 若采用(小根) 堆排序，请给出初始堆。35 若给定待排序记录的关键字基本有序时，应采用快速排序还是堆排序?为什么?36 快速排序属于稳定排序吗?堆排序属于稳定排序吗? 【厦门大学 2005 4(15 分)】计算机专业基础综合数据结构（排序）历年真题试卷汇编 5 答案与解析一、单项选择题1 【正
12、确答案】 C【试题解析】 枢轴是 73。2 【正确答案】 B3 【正确答案】 C【试题解析】 如何对一趟快速排序的结果在最短的时间内做出正确判断，这里给出建议：首先 84 应该不动，所以 D 排除了；接着 40 应调到序列首，所以 A 排除了；接着 79 应调到移走 40 的空位上，B 排除了。选择答案 C，不必再继续做了(假定确有唯一正确答案) 。4 【正确答案】 A5 【正确答案】 B,C,D6 【正确答案】 D7 【正确答案】 D【试题解析】 本题相当于从 n 个元素选取 k(kn) 个元素用什么排序方法最好。起泡排序和简单选择排序第 1 趟比较 n 一 1 次选出最小最大元素，第 2
13、趟比较n 一 2 次，选出次小次大元素，因此，这两种排序方法不予考虑。若选最小，快速排序和起泡排序差不多。希尔排序只有等排序结束才能有最后结果，这里不予考虑。堆排序建堆选出最小最大元素，比较了至多不超过 4n 次，以后每选出一个元素需要 logn 次的比较。由此，本题的答案应该选 D。但是编者还有另外的分析。若先用快速排序选出第 k 个最小元素，则比较次数在 O(n)级，算法见下面“五、27”。对前面 k-1 个记录可以采用任何简单(不使用适合大数据量的堆排序等 )排序方法，即使再用快速排序，也是可以的。这里 n 大到什么程度，k 小到什么程度，会有个阈值。8 【正确答案】 C9 【正确答案】
14、 C10 【正确答案】 A11 【正确答案】 D12 【正确答案】 A【试题解析】 是叙述直接插入排序特征的，要认真领会。13 【正确答案】 D14 【正确答案】 C15 【正确答案】 B二、填空题16 【正确答案】 是堆 (1)选择 (2)筛选法 (3)O(nlog 2n) (4)1 个17 【正确答案】 (1)选择 (2) 完全二叉树 (3)O(nlog 2n) (4)1 个 (5)满足堆的性质18 【正确答案】 归并19 【正确答案】 稳定20 【正确答案】 冒泡，快速21 【正确答案】 简单选择排序，直接插入排序(最小的元素在最后时)三、判断题22 【正确答案】 A23 【正确答案】
15、B24 【正确答案】 B25 【正确答案】 B【试题解析】 待排序序列为正序时，简单插入排序比归并排序快。26 【正确答案】 B27 【正确答案】 B【试题解析】 都是外部排序问题。外部排序指待排序文件很大，不能一次调入内存所进行的排序方法。外部排序分成生成顺串和归并顺串两个阶段。外部排序的效率主要取决于读写外存的次数，即归并的趟数。减少归并趟数就可以减少读写次数，提高效率。28 【正确答案】 B四、综合题29 【正确答案】 堆排序，快速排序，归并排序30 【正确答案】 归并排序31 【正确答案】 快速排序32 【正确答案】 堆排序33 【正确答案】 快速排序第一趟结果：20，6，29，27，1 5，32，92，97，50快速排序第二趟结果：15，6，20，27，29，32，50，92，9734 【正确答案】 建成的小根堆：6，20，15，27，97，50，92，29，3235 【正确答案】 采用堆排序。因为记录的关键字基本有序时，快速排序蜕变成起泡排序，时间复杂度为 O(n2)而堆在最坏情况下时间复杂度仍是 nlogn。36 【正确答案】 快速排序和堆排序都是不稳定排序。
