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

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 n)，o(n*log n)22c.o(n)，o(n*log n)，o(n ) 22d.o(n )，o(n*log n)，o(n )222解析：5.数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中的( )的两趟排序后

3、的结果。【合肥工业大学 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)1547 25 84 21 (3)

4、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分)】（分数

5、：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.下列排序算法中，()排序在一趟

6、结束后不一定能选出一个元素放在其最终位置上。【南京理工大学 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.(多选)在下列排序方法中，(

7、)等方法在某趟结束后，选出一个元素到最终的位置。【华中科技大学 2007二、18(2分)】（分数：2.00）a.选择排序 b.归并排序c.冒泡排序 d.堆排序 解析：二、 填空题(总题数：5，分数：10.00)16.快速排序在_的情况下最易发挥其长处。（分数：2.00）_正确答案：(正确答案：最好每次划分能得到两个长度相等的子文件。设文件长度 n=2 1，第一遍划分k得到两个长度为 ln2j的子文件，第二遍划分得到 4个长度为n4的子文件，以此类推，总共进行 k=log(n+1)遍划分。在最后一趟划分时，各子文件长度均为 1，排序结束。)2解析：17.若一组记录的排序码为(46，79，56，3

8、8，40，84)，利用堆排序建立的初始堆是_。 (注：堆顶元素取最大值。)【东南大学 2005数据结构部分二、9(1分)】（分数：2.00）_正确答案：(正确答案：84，79，56，38，40，46)解析：18.高度为五的堆中，最多有_个元素，最少有_个元素。【哈尔滨工业大学 2005一、4(1分)】（分数：2.00）_正确答案：(正确答案：2 一 1， 2 )h-1h解析：19.堆排序的算法时间复杂度为_。【合肥工业大学 1999三、10(2分)】（分数：2.00）_正确答案：(正确答案：o(nlog n)2 解析：20.在堆排序中，首先需要进行的操作是_。【北京理工大学 2006十、5(1

9、分)】（分数：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.内排序的快速排序方法，在任何情况下均可得到最快的排序效果。(

10、)【中国海洋大学 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一、

11、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.有一大根堆，堆中任意结点的关键字均大于它的左右孩

12、子关键字，则其具有最小值的结点一定是一个叶结点并可能在堆的最后两层中。 ( )【吉林大学 2006一、10(1分)】（分数：2.00）a.正确 b.错误解析：四、 综合题(总题数：3，分数：6.00)31.简述直接插入排序、简单选择排序、2路归并排序的基本思想以及在时间复杂度和排序稳定性上的差别。【西北工业大学 1999二(8分)】（分数：2.00）_正确答案：(正确答案：直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入前面有序的子文件中。即将记录 ri(2in)插入有序子序列 r1i1中，使记的有序序列从 r1i-1变为 r1i，最终使整个文件有序。共

13、进行n一 1趟插入。最坏时间复杂度是 o(n )，平均时间复杂度是 o(n )，空间复杂度是 o(1)，是稳定排序。简单选择排序的基本思想是基22于选择，开始有序序列长度为零，第 i(1i 2)，平均时间复杂度是 o(n )，空间复杂度是 o(1)，是不稳定2排序。二路归并排序的基本思想是基于归并，开始将具有 n个待排序记录的序列看成是 n个长度为 1的有序序列，然后进行两两归并，得到n2个长度为 2的有序序列，再进行两两归并，得到n4个长度为4的有序序列。如此重复，经过log n趟归并，最终得到一个长度为 n的有序序列。最坏时间复杂度和平2均时间复杂度都是 o(nlog n)，空间复杂度是 o(n)，是稳定排序。)2解析：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