内容发布更新时间 : 2024/5/21 1:18:51星期一 下面是文章的全部内容请认真阅读。
计算机专业基础综合数据结构（排序）历年真题试卷汇编5
(总分：66.00，做题时间：90分钟)
一、 单项选择题(总题数：15，分数：30.00)
1.已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。【2009年全国试题9(2分)】 A.3，5，12，8，28，20，15，22，19 √ B.3，5，12，19，20，1 5，22，8，28 C.3，8，12，5，20，15，22，28，19 D.3，12，5，8，28，20，1 5，22，19
首先按所给关键字序列画出完全二叉树，关键字3插入结点22的后边。沿结点3到根的路径调整堆，直到满足堆的定义为止。
2.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( )。【2009年全国试题10(2分)】 A.起泡排序 B.插入排序 √ C.选择排序 D.二路归并排序
起泡排序的特点是待排序元素相邻两两比较，逆序交换，每趟有一个最大元素到达底部(或一个最小元素到达顶部)；插入排序的特点是先假定第一个元素有序，从第二个元素起，每趟将未排序元素的第一个元素插入的前面有序子文件中；选择排序的特点是第一趟在待排序元素中选最小(或最大)元素和第一个元素交换，第二趟在未排序元素中选次小(或次大)和第二个元素交换；二路归并排序是两两归并，再四四归并，等等。 3.采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是( )。【2010年全国试题10(2分)】
A.递归次数与初始数据的排列次序无关
B.每次划分后，先处理较长的分区可以减少递归次数 C.每次划分后，先处理较短的分区可以减少递归次数 D.递归次数与每次划分后得到的分区的处理顺序无关 √
快速排序和数据的初始排列次序相关。每次划分后，先处理较短分区可以减少递归深度，递归次数和先处理哪个分区无关。
4.对一组数据(2，12，1 6，88，5，10)进行排序，若前三趟排序结果如下： 第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88则采用的排序方法可能是( )。 【2010年全国试题11(2分)】 A.起泡排序 √ B.希尔排序 C.归并排序 D.基数排序
起泡排序和二路归并排序的特点见上面第2题。希尔排序是先按步长分组，组内进行插入排序，逐渐减少步长，最后步长为1进行一趟直接插入排序。根据各种排序的特点，可以分析出本题是起泡排序。 5.为实现快速排序算法，待排序序列宜采用的存储方式是( )。 【2011年全国试题10(2分)】 A.顺序存储 √ B.散列存储 C.链式存储 D.索引存储
每趟排序结束时都至少能够确定一个元素最终位置的排序方法有起泡排序、快速排序、简单选择排序、堆排序。
6.已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是( )。 【2011年全国试题11(2分)】
A.1 B.2 √ C.4 D.5
7.排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是( )。【20 1 2年全国试题10(2分)】I．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排序V．二路归并排序 A.仅I、Ⅲ、Ⅳ √ B.仅I、Ⅲ、V C.仅Ⅱ、Ⅲ、Ⅳ D.仅Ⅲ、Ⅳ、V
8.对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是( )。【2012年全国试题11(2分)】 A.排序的总趟数 B.元素的移动次数 C.使用辅助空间的数量 D.元素之间的比较次数 √
9.对给定的关键字序列1 10，1 19，007，91 1，1 14，120，122进行基数排序，则第2趟分配收集后得到的关键字序列是( )。[201 3年全国试题11(2分)】 A.007，110，119，114，911，120，122 B.007，110，119，114，911，122，120 C.007，110，911，114，119，120，122 √ D.110，120，911，122，114，007，119
10.用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9，1，4，13，7，8，20，23，15，则该趟排序采用的增量(间隔)可能是( )。[2014年全国试题10(2分)】 A.2 B.3 √ C.4 D.5
使用枚举法，逐个测试，可以得出结论。
11.下列选项中，不可能是快速排序第2趟排序结果的是( )。[2014年全国试题11(2分)】 A.2，3，5，4，6，7，9 B.2，7，5，6，4，3，9 C.3，2，5，4，7，6，9 √ D.4，2，3，5，7，6，9
本题测试快速排序的概念。待排序序列的几种初态都可能在丽趟快速排序后变为A、B和D。例如，初态是A，经过两趟快速排序后，状态未变；B的初态可能是{9，7，5，6，4，3，2}；D的初态可能是{9，2，3，4，7，6，5}；唯独C是不可能的。
12.下列排序算法中元素的移动次数和关键字的初始排列次序无关的是( )。【2015年全国试题9(2分)】 A.直接插入排序 B.起泡排序 C.基数排序 √ D.快速排序
13.已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是( )。[2015年全国试题10(2分)】 A.1 B.2 √ C.3 D.4
14.希尔排序的组内排序采用的是( )。[2015年全国试题11(2分)】 A.直接插入排序 √ B.折半插入排序 C.快速排序 D.归并排序
15.排序算法的稳定性是指( )。【北京理工大学2005一、10(1分)】 A.经过排序之后，能使值相同的数据保持原顺序中的相对位置不变 √ B.经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变 C.算法的排序性能与被排序元素的数量关系不大 D.算法的排序性能与被排序元素的数量关系密切
关于稳定排序的概念，不稳定的排序有希尔排序、快速排序、简单选择排序、树形排序、堆排序。
二、 填空题(总题数：5，分数：10.00)
16.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__________和记录的__________。【北京邮电大学2001二、7(4分)】
__________________________________________________________________________________________ 正确答案：(正确答案：比较，移动)
17.直接插入排序用监视哨的作用是__________。【南京理工大学2001二、8(2分)】
__________________________________________________________________________________________ 正确答案：(正确答案：免去查找过程中每一步都要检测整个查找表是否查找完毕，提高了查找效率) 18.对n个元素的序列进行起泡排序时，最少的比较次数是__________。【东华大学2003一、3(1分)】 __________________________________________________________________________________________ 正确答案：(正确答案：n一1)
19.对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为__________。【华中理工大学2000一、10(1分)】【江苏大学2004二、9(3分)】
__________________________________________________________________________________________ 正确答案：(正确答案：n(n一1)／2)
20.简单选择算法的最好和最坏情况时间复杂度分别为__________和__________。【南京邮电学院2004二、5(5分)】
__________________________________________________________________________________________ 正确答案：(正确答案：O(n )，O(n ))
2
2
三、 判断题(总题数：10，分数：20.00)
21.分析排序算法时间复杂性时，当待排序文件是顺序排列时，则所有排序算法对此文件执行都具有最好的时间复杂性；当待排序文件是逆序排列时，所有排序算法对此文件执行都具有最坏时间复杂性。 ( )【吉林大学2007一、4(1分)】 A.正确 B.错误 √
快速排序在待排序文件有序时具有最坏的时间复杂性。
22.内排序要求数据一定要以顺序方式存储。( )【南京理工大学1997二、2(2分)】 A.正确 B.错误 √
23.排序算法中的比较次数与初始元素序列的排列无关。( )【南京航空航天大学1997一、8(1分)】 A.正确 B.错误 √
24.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。 ( )【南京航空航天大学1996六、9(1分)】 A.正确 B.错误 √
关于稳定排序与不稳定排序的问题，稳定性是描述排序状态，指两个关键字值相同元素的相对次序在排序前、后是否发生变化。相对次序不变化的叫稳定排序，反之是不稳定排序。