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