1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 2 及答案与解析一、单项选择题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，192 若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( )
2、。【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第三趟排序结果：
3、2，5，10，12，16，88则采用的排序方法可能是( )。 【2010 年全国试题 11(2 分)】（A）起泡排序（B）希尔排序（C）归并排序（D）基数排序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）57 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为
4、一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是( )。【20 1 2 年全国试题 10(2 分)】I简单选择排序希尔排序快速排序堆排序V二路归并排序（A）仅 I、（B）仅 I、V（C）仅 、（D）仅、V8 对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是( )。【 2012 年全国试题 11(2 分) 】（A）排序的总趟数（B）元素的移动次数（C）使用辅助空间的数量（D）元素之间的比较次数9 对给定的关键字序列 1 10，1 19，007，91 1，1 14，120，122 进行基数排序，则第 2 趟分配收集后得到的关键字序列是( )
5、。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，11910 用希尔排序方法对一个数据序列进行排序时，若第 1 趟排序结果为9，1，4，13，7，8，20，23，15，则该趟排序采用的增量(间隔)可能是( )。2014 年全国试题 10(2 分)】（A）2（B） 3（C） 4（D）511 下列选项中，不可能是快速排序第 2 趟排序结果的是( )。2014 年全国试题1
6、1(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，912 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是( )。【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）414 希尔排序的组内排序采用的是( )。2015 年全国试题 11(2 分)
7、】（A）直接插入排序（B）折半插入排序（C）快速排序（D）归并排序15 排序算法的稳定性是指( )。【北京理工大学 2005 一、10(1 分)】（A）经过排序之后，能使值相同的数据保持原顺序中的相对位置不变（B）经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变（C）算法的排序性能与被排序元素的数量关系不大（D）算法的排序性能与被排序元素的数量关系密切二、填空题16 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_和记录的_。【北京邮电大学 2001 二、7(4 分)】17 直接插入排序用监视哨的作用是_。【南京理工大学 2001 二、8(2 分)】18 对 n 个
8、元素的序列进行起泡排序时，最少的比较次数是_。【东华大学 2003 一、3(1 分) 】19 对 n 个记录的表 r1n进行简单选择排序，所需进行的关键字间的比较次数为_。【华中理工大学 2000 一、10(1 分)】【江苏大学 2004 二、9(3 分)】20 简单选择算法的最好和最坏情况时间复杂度分别为_和_。【南京邮电学院 2004 二、5(5 分)】三、判断题21 分析排序算法时间复杂性时，当待排序文件是顺序排列时，则所有排序算法对此文件执行都具有最好的时间复杂性；当待排序文件是逆序排列时，所有排序算法对此文件执行都具有最坏时间复杂性。 ( )【吉林大学 2007 一、4(1 分)】（
9、A）正确（B）错误22 内排序要求数据一定要以顺序方式存储。( )【南京理工大学 1997 二、2(2 分)】（A）正确（B）错误23 排序算法中的比较次数与初始元素序列的排列无关。( )【南京航空航天大学1997 一、8(1 分) 】（A）正确（B）错误24 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。 ( )【南京航空航天大学 1996 六、9(1 分)】（A）正确（B）错误25 拓扑排序是一种内部排序方法。( )【暨南大学 2011 三、9(1 分)】（A）正确（B）错误26 若某内排序算法不稳定，则该算法没有实用价值。( )【北京邮电大学 2006 二、9(1 分)】
10、（A）正确（B）错误27 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。( )【上海交通大学 1998 一、1 8(1 分)】（A）正确（B）错误28 时间复杂度为 O(N2)、空间复杂度为 O(1)且与文件初始状态无关的排序算法是直接插入排序。( ) 【北京交通大学 2005 三、3(2 分)】（A）正确（B）错误29 两分法插入排序所需比较次数与待排序记录的初始排列状态相关。 ( )【上海交通大学 1998 一、15(1 分)】（A）正确（B）错误30 由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。( ) 【电
11、子科技大学 2001 二、4(1 分)】【北京邮电大学 2006 二、4(1分)】（A）正确（B）错误四、综合题31 希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法，试举例说明。【吉林大学 2007 二、9(4 分)】32 设有 n 个元素采用冒泡排序法进行排序，通常需要进行多少趟排序?对于第，趟冒泡通常需要进行多少次关键字比较?在程序设计中如何设置判断条件，有可能使冒泡趟数可以减少并且能完成排序。【北京交通大学 2005 四、3(5 分)】33 设有 5 个互不相同的元素 a、b、c 、d、e，能否通过 7 次比较就将其排好序?如果能，请列出其比较过程；如果不能，则说明原因。【北
12、方交通大学 1996 五(10分)】计算机专业基础综合数据结构（排序）历年真题试卷汇编 2 答案与解析一、单项选择题1 【正确答案】 A【试题解析】 首先按所给关键字序列画出完全二叉树，关键字 3 插入结点 22 的后边。沿结点 3 到根的路径调整堆，直到满足堆的定义为止。2 【正确答案】 B【试题解析】 起泡排序的特点是待排序元素相邻两两比较，逆序交换，每趟有一个最大元素到达底部(或一个最小元素到达顶部)；插入排序的特点是先假定第一个元素有序，从第二个元素起，每趟将未排序元素的第一个元素插入的前面有序子文件中；选择排序的特点是第一趟在待排序元素中选最小(或最大)元素和第一个元素交换，第二趟在
13、未排序元素中选次小(或次大)和第二个元素交换；二路归并排序是两两归并，再四四归并，等等。3 【正确答案】 D【试题解析】 快速排序和数据的初始排列次序相关。每次划分后，先处理较短分区可以减少递归深度，递归次数和先处理哪个分区无关。4 【正确答案】 A【试题解析】 起泡排序和二路归并排序的特点见上面第 2 题。希尔排序是先按步长分组，组内进行插入排序，逐渐减少步长，最后步长为 1 进行一趟直接插入排序。根据各种排序的特点，可以分析出本题是起泡排序。5 【正确答案】 A【试题解析】 每趟排序结束时都至少能够确定一个元素最终位置的排序方法有起泡排序、快速排序、简单选择排序、堆排序。6 【正确答案】
14、B7 【正确答案】 A8 【正确答案】 D9 【正确答案】 C10 【正确答案】 B【试题解析】 使用枚举法，逐个测试，可以得出结论。11 【正确答案】 C【试题解析】 本题测试快速排序的概念。待排序序列的几种初态都可能在丽趟快速排序后变为 A、B 和 D。例如，初态是 A，经过两趟快速排序后，状态未变；B的初态可能是9 ，7，5，6，4，3，2 ；D 的初态可能是9，2，3，4，7，6，5；唯独 C 是不可能的。12 【正确答案】 C13 【正确答案】 B14 【正确答案】 A15 【正确答案】 A【试题解析】 关于稳定排序的概念，不稳定的排序有希尔排序、快速排序、简单选择排序、树形排序、堆
15、排序。二、填空题16 【正确答案】 比较，移动17 【正确答案】 免去查找过程中每一步都要检测整个查找表是否查找完毕，提高了查找效率18 【正确答案】 n 一 119 【正确答案】 n(n 一 1)220 【正确答案】 O(n 2)， O(n2)三、判断题21 【正确答案】 B【试题解析】 快速排序在待排序文件有序时具有最坏的时间复杂性。22 【正确答案】 B23 【正确答案】 B24 【正确答案】 B【试题解析】 关于稳定排序与不稳定排序的问题，稳定性是描述排序状态，指两个关键字值相同元素的相对次序在排序前、后是否发生变化。相对次序不变化的叫稳定排序，反之是不稳定排序。25 【正确答案】 B
16、【试题解析】 拓扑排序是对有向无环图顶点的一种排序方法。有向图的顶点表示活动，弧代表活动的优先关系。26 【正确答案】 B27 【正确答案】 B【试题解析】 例如，冒泡排序是稳定排序，将 4，3，2，1 按冒泡排序排成升序序列，第一趟变成 3，2，1，4，此时 3 就朝向最终位置的相反方向移动。应按稳定排序的定义去判断。题中叙述和排序中稳定性的定义无关。28 【正确答案】 B【试题解析】 叙述的情况是简单选择排序。29 【正确答案】 B【试题解析】 因为要在已有序的子文件中折半查找插入位置，这种查找都要查到外部结点(失败结点，假定排序数据互不相等)。因此，两分法插入排序的比较次数和数据的初始排
17、列没有关系。比较次数和数据的初始排列没有关系的排序方法还有简单选择排序、归并排序、基数排序等。30 【正确答案】 B【试题解析】 希尔排序的时间性能优于直接插入排序。四、综合题31 【正确答案】 各种内部排序小结如下表。32 【正确答案】 n 个元素采用冒泡排序法进行排序，最多需要进行 n1 趟排序。第 j 趟冒泡排序要进行 nj 次关键字比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排序结束，下面语句段说明了标记 flag的使用。intj=1，flag=1； flag 用作控制标记while(jri+1)(flag=1； riri+1 ；发生了交换，还要进行下趟33 【正确答案】 可以做到。取 a 与 b 进行比较，c 与 d 进行比较。设ab，cd(ad，则abd 有序；若 bdb 有序，此时已进行了 3 次比较。再把另外两个元素按折半插入排序方法，插入上述某个序列中共需 4 次比较，从而共需 7 次比较。
