计算机专业基础综合数据结构(排序)历年真题试卷汇编7

计算机专业基础综合数据结构（排序）历年真题试卷汇编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.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)只能是下列排序算法中的( )的两趟排序后的结果。【合肥工业大学1999一、3(2分)】

（分数：2.00）

A.选择排序

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则采用的排序是( )。【南京理工大学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.冒泡

解析：

10.( )占用的额外空间的空间复杂性为O(1)。【上海交通大学2005四、4(2分)】

（分数：2.00）

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(1．5分)】【哈尔滨工业大学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）

__________________________________________________________________________________________ 正确答案：(正确答案：最好每次划分能得到两个长度相等的子文件。设文件长度n=2 k－1，第一遍划分得到两个长度为Ln／2j的子文件，第二遍划分得到4个长度为[n／4]的子文件，以此类推，总共进行k=log 2 (n+1)遍划分。在最后一趟划分时，各子文件长度均为1，排序结束。)

解析：

17.若一组记录的排序码为(46，79，56，38，40，84)，利用堆排序建立的初始堆是__________。(注：堆顶元素取最大值。)【东南大学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分)】

（分数：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.内排序的快速排序方法，在任何情况下均可得到最快的排序效果。( )【中国海洋大学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】，按堆结构的定义，它一定是堆。( )【吉林大学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.有一大根堆，堆中任意结点的关键字均大于它的左右孩子关键字，则其具有最小值的结点一定是一个叶结点并可能在堆的最后两层中。 ( )【吉林大学2006一、10(1分)】

（分数：2.00）

A.正确√

B.错误

解析：

四、综合题(总题数：3，分数：6.00)

31.简述直接插入排序、简单选择排序、2路归并排序的基本思想以及在时间复杂度和排序稳定性上的差别。【西北工业大学1999二(8分)】

（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入前面有序的子文件中。即将记录R[i](2≤i≤n)插入有序子序列R[1．．i—1]中，使记的有序序列从R[1．．i-1]变为R[1．．i]，最终使整个文件有序。共进行n一1趟插入。最坏时间复杂度是O(n 2 )，平均时间复杂度是O(n 2 )，空间复杂度是O(1)，是稳定排序。简单选择排序的基本思想是基于选择，开始有序序列长度为零，第i(1≤i2)，平均时间复杂度是O(n2)，空间复杂度是O(1)，是不稳定排序。二路归并排序的基本思想是基于归并，开始将具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到[n／2]个长度为2的有序序列，再进行两两归并，得到[n／4]个长度为4的有序序列。如此重复，经过[log2n]趟归并，最终得到一个长度为n的有序序列。最坏时间复杂度和平均时间复杂度都是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)

解析：