1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 4 及答案与解析一、单项选择题1 下述几种排序方法中，要求内存量最大的是( )。【中南大学 2005 一、6(2 分)】（A）归并排序（B）快速排序（C）插入排序（D）选择排序2 快速排序方法在( ) 情况下最不利于发挥其长处。【华南理工大学 2007】（A）要排序的数据量太大（B）要排序的数据中含有多个相同值（C）要排序的数据个数为奇数（D）要排序的数据已基本有序3 当待排序列基本有序时，下列排序方法中( )最好。【北京邮电大学 2005 一、10 (2 分 )】（A）直接插入排序（B）快速排序（C）堆排序（D）归并排序4 设被排序的结点序
2、列共有 N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为( )。【 上海交通大学 2005 四、5(2 分) 】（A）O(N) ， O(N)，O(N)（B） O(N)，O(N*log 2N)，O(N*log 2N)（C） O(N)，O(N*log 2N)，O(N 2)（D）O(N 2)， O(N*log2N)，O(N 2)5 数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中的( )的两趟排序后的结果。【合肥工业大学 1999 一、3(2 分)】（A）选择排序（B）冒泡排序（C）插入排序（D）堆排序
3、6 一个排序算法的时间复杂度与( )有关。【华中科技大学 2004 一、8(1 分)】（A）排序算法的稳定性（B）所需比较关键字的次数（C）所采用的存储结构（D）所需辅助存储空间的大小7 对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为(1)84 47 25 15 21 (2)15 47 25 84 21 (3)15 21 25 84 47 (4)15 21 25 47 84 则采用的排序是( ) 。 【南京理工大学 1997 一、2(2 分) 】（A）选择（B）冒泡（C）快速（D）插入8 对序列15，9，7，8， 20，一 1，4)进行排序，进行一趟后数据
4、的排列变为4，9，一 1， 8，20，7， 15)，则采用的是( )排序。 【南京理工大学 1998 一、8(2 分)】（A）选择（B）快速（C）希尔（D）冒泡9 若上题的数据经一趟排序后的排列为9，15，7，8，20，一 1，4 ，则采用的是( )排序。【 南京理工大学 1998 一、9(2 分) 】（A）选择（B）堆（C）直接插入（D）冒泡10 ( )占用的额外空间的空间复杂性为 O(1)。【上海交通大学 2005 四、4(2 分)】（A）堆排序算法（B）归并排序算法（C）快速排序算法（D）以上答案都不对11 有些排序算法在每趟排序过程中，都会有一个元素被放置在其最终的位置上，下列算法不会
5、出现此情况的是( )。【北京交通大学 2005 一、7(2 分)】（A）Shell 排序（B）堆排序（C）冒泡排序（D）快速排序12 下列排序算法中，( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。【南京理工大学 2005 一、10(1 分)】（A）希尔（B）冒泡（C）选择（D）直接插入13 下列排序算法中( ) 排序在一趟结束后不一定能选出一个元素放在其最终位置上。【南京理工大学 2001 一、7(15 分)】【哈尔滨工业大学 2001 二、4(2 分)】（A）选择（B）冒泡（C）归并（D）堆14 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。【电子科
6、技大学 2005 一、2(1 分)】（A）堆排序（B）起泡排序（C）快速排序（D）直接插入排序15 (多选 )在下列排序方法中，( ) 等方法在某趟结束后，选出一个元素到最终的位置。【华中科技大学 2007 二、18(2 分)】（A）选择排序（B）归并排序（C）冒泡排序（D）堆排序二、填空题16 快速排序在_的情况下最易发挥其长处。17 若一组记录的排序码为(46，79，56，38，40，84)，利用堆排序建立的初始堆是_。 (注：堆顶元素取最大值。)【东南大学 2005 数据结构部分二、9(1分)】18 高度为五的堆中，最多有_个元素，最少有_个元素。【哈尔滨工业大学 2005 一、4(1
7、分)】19 堆排序的算法时间复杂度为_。【合肥工业大学 1999 三、10(2 分)】20 在堆排序中，首先需要进行的操作是_。【北京理工大学 2006 十、5(1 分)】三、判断题21 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。 ( ) 【上海交通大学 1998 一、16(1 分) 】（A）正确（B）错误22 快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。( )【北京邮电大学 1998 一、7(2 分)】【吉林大学 2007 一、8(1 分)2006 一、9(1 分)】【中国海洋大学 2005 二、1(1 分)】（A）正确（B）错误23 内排
8、序的快速排序方法，在任何情况下均可得到最快的排序效果。( )【中国海洋大学 2007 二、14(1 分)】（A）正确（B）错误24 堆肯定是一棵平衡二叉树。( )【南京航空航天大学 1997 一、6(1 分)】（A）正确（B）错误25 堆是满二叉树。 ( ) 【南京航空航天大学 1996 六、6(1 分)】（A）正确（B）错误26 给定序列(100，86，48，73，35，39，42，57，66，21】，按堆结构的定义，它一定是堆。 ( ) 【吉林大学 2006 一、3(1 分) 】（A）正确（B）错误27 (101，88，46，70，34，39，45，58，66，10)是堆。( )【北京邮电
9、大学 1999二、1(2 分) 】【 上海海事大学 2005 一、8(2 分) 】（A）正确（B）错误28 在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆” 。( )【合肥工业大学 2000 二、10(1 分)】（A）正确（B）错误29 堆排序是稳定的排序方法。 ( ) 【上海交通大学 1998 一、19(1 分)】（A）正确（B）错误30 有一大根堆，堆中任意结点的关键字均大于它的左右孩子关键字，则其具有最小值的结点一定是一个叶结点并可能在堆的最后两层中。 ( )【吉林大学 2006 一、10(1 分 )】（A）正确（B）错误四、综合题31 简述直接插入排序、简单选择排序、2
10、路归并排序的基本思想以及在时间复杂度和排序稳定性上的差别。【西北工业大学 1999 二(8 分)】32 对下列数据表，写出采用希尔排序算法的每一趟排序结果。 (100， 12，20，31，1，5，44，66，61，200，30，80，150，4，8)设增量序列为：D=-5，3，1)【中国海洋大学 2007 一、4(8 分)】33 采用希尔排序法，对以下关键字序列按递增次序排序，使用的增量序列为5、3、1，请给出每趟排序的结果。【北京理工大学 2006 十一、6(5 分)】(8，6， 3，4，2，9，7，5，1，0)计算机专业基础综合数据结构（排序）历年真题试卷汇编 4 答案与解析一、单项选择题
11、1 【正确答案】 A2 【正确答案】 D3 【正确答案】 A4 【正确答案】 C5 【正确答案】 C【试题解析】 对于 A、B 和 D 三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。6 【正确答案】 B7 【正确答案】 A8 【正确答案】 C【试题解析】 本题为步长为 3 的一趟希尔排序。9 【正确答案】 C10 【正确答案】 A11 【正确答案】 A【试题解析】 每趟排序都会有一个元素被放置到最终位置上的排序方法有：冒泡排序，快速排序，直接选择排序，堆排序。12 【正确答案】 A13 【正确答案】 C14 【正确答案】 D15 【正确答案】 A,
12、C,D二、填空题16 【正确答案】 最好每次划分能得到两个长度相等的子文件。设文件长度n=2k 1，第一遍划分得到两个长度为 Ln2j 的子文件，第二遍划分得到 4 个长度为n 4的子文件，以此类推，总共进行 k=log2(n+1)遍划分。在最后一趟划分时，各子文件长度均为 1，排序结束。17 【正确答案】 84，79，56，38，40，4618 【正确答案】 2 h 一 1， 2 h-119 【正确答案】 O(nlog 2n)20 【正确答案】 建堆三、判断题21 【正确答案】 B22 【正确答案】 B23 【正确答案】 B24 【正确答案】 B【试题解析】 堆是 n 个元素的序列，可以看作
13、是完全二叉树，但并无(根) 结点大于左子树而小于右子树的要求，故其既不是二叉排序树，更不会是平衡二叉树。25 【正确答案】 B26 【正确答案】 A27 【正确答案】 A28 【正确答案】 A29 【正确答案】 B30 【正确答案】 A四、综合题31 【正确答案】 直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入前面有序的子文件中。即将记录 Ri(2in)插入有序子序列 R1i1中，使记的有序序列从 R1i-1 变为 R1i，最终使整个文件有序。共进行 n 一 1 趟插入。最坏时间复杂度是 O(n2)，平均时间复杂度是 O(n2)，空间复杂度是 O(1)
14、，是稳定排序。简单选择排序的基本思想是基于选择，开始有序序列长度为零，第 i(1i2)，平均时间复杂度是 O(n2)，空间复杂度是O(1)，是不稳定排序。二路归并排序的基本思想是基于归并，开始将具有 n 个待排序记录的序列看成是 n 个长度为 1 的有序序列，然后进行两两归并，得到n2个长度为 2 的有序序列，再进行两两归并，得到n4个长度为 4 的有序序列。如此重复，经过log 2n趟归并，最终得到一个长度为 n 的有序序列。最坏时间复杂度和平均时间复杂度都是 O(nlog2n)，空间复杂度是 O(n)，是稳定排序。32 【正确答案】 数据表初态：100，12，20，31，1，5，44，66，61，200，30，80，150，4，8第 1 趟后：5，12，20，4，1，30，44，66，31，8，100，80，150，61，200第 2 趟后：4，1，20，5，12，30，8，61，31，44，66，80，150，1 00，200第 3 趟后：1，4，5，8，12，20，30，31，44，61，66，80，100，1 50，20033 【正确答案】 排序第一趟结果：6，2，10，4，8，12，28，30，20，16，18
