1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 6 及答案解析(总分：108.00，做题时间：90 分钟)一、单项选择题(总题数：44，分数：88.00)1.某内部排序方法的稳定性是指_。【南京理工大学 1997 年】（分数：2.00）A.该排序算法不允许有相同的关键字记录B.该排序算法允许有相同的关键字记录C.平均时间为 O(nlogn)的排序方法D.以上都不对2.若要求尽可能快地对序列进行稳定的排序，则应选_。【北京邮电大学 2001 年】（分数：2.00）A.快速排序B.归并排序C.冒泡排序D.根排序3.下列排序方法中，_是稳定的排序方法。【北方交通大学 2001】（分数：2.00）
2、A.直接选择排序B.二分法插入排序C.希尔排序D.快速排序4.对有 n 个记录的表做直接插入排序，在最好情况下，需比较_次关键字。【华中科技大学 2006 年】（分数：2.00）A.n-1B.n+1C.n2D.n(n-1)25.对 n 个不同的数据利用冒泡法从小到大排序，在下列哪种情况下元素交换的次数最多_。【北京交通大学 2007 年】（分数：2.00）A.从大到小排列好的B.从小到大排列好的C.元素无序D.元素基本有序6.采用简单选择排序，比较次数与移动次数分别为_。【南京理工大学 2000 年】（分数：2.00）A.O(n)，O(10gn)B.O(logn)，O(n*n)C.O(n*n)
3、，O(n)D.O(nlogn)，O(n)7.希尔排序属于_。【太原科技大学 2006 年】（分数：2.00）A.插入排序B.交换排序C.选择排序D.归并排序8.对序列15，9，7，8，20，一 1，4用希尔排序方法排序，经一趟后序列变为15，一1，4，8，20，9，7则该次采用的增量是_。【南京理工大学 1999 年】（分数：2.00）A.1B.4C.3D.29.有些排序算法在每趟排序过程中，都会有一个元素被放置到其最终位置上，下列算法不会出现此种情况的是_。【北京交通大学 2005 年】（分数：2.00）A.希尔排序B.堆排序C.冒泡排序D.快速排序10.从未排序序列中选择一个元素，该元素将
4、当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于等于所选元素，而所选元素处在排序的最终位置。这种排序法称为_。【北京航空航天大学 2005 年】（分数：2.00）A.插入排序法B.冒泡排序法C.希尔排序法D.快速排序法11.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_。【北京交通大学 2005 年】（分数：2.00）A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84)D.(40，38，46，8
5、4，56，79)12.对下列 4 个序列，以第一个关键字为基础用快速排序算法进行排序，在第一趟过程中移动记录次数最多的是_。【电子科技大学 2007 年】（分数：2.00）A.92，96，100，110，42，35，30，88B.92，96，88，42，30，35，110，100C.100，96，92，35，30，110，88，42D.42，30，35，92，100，96，88，11013.快速排序方法在_情况下最不利于发挥其长处。【华南理工大学 2007 年】（分数：2.00）A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序14.对
6、n 个元素的表做快速排序，最坏情况下，算法的时间复杂度为_。【华中科技大学 2006 年】（分数：2.00）A.O(log 2 n)B.O(nlog 2 n)C.O(n 2 )D.O(2 n )15.对以下关键字序列用快速排序算法进行排序，速度最慢的是_。【北京交通大学 2002 年】（分数：2.00）A.20，24，4，16，22，29B.24，22，29，16，20，4，8C.20，8，16，29，24，22，4D.4，8，16，20，24，2916.快速排序在最坏的情况下的时间复杂度与下面哪个算法的最坏情况下的时间复杂度相同_。【北京交通大学 2006 年】（分数：2.00）A.希尔排序
7、B.堆排序C.冒泡排序D.基数排序17.根据堆的定义，下面 4 个序列中，构成堆的是_。【广东工业大学 2002 年】（分数：2.00）A.77，67，32，17，27，47，22，12B.77，67，47，12，32，27，22，17C.77，47，67，32，17，27，22，12D.77，47，67，12，27，32，22，1718.有组数据(15，9，7，8，20，一 1，7，4)，用堆排序的筛选方法建立的初始堆为_。【南京理工大学 1996 年】（分数：2.00）A.一 1，4，8，9，20，7，15，7B.一 1，7，15，7，4，8，20，9C.一 1，4，7，8，20，15，7
8、，9D.A，B，C 均不对。19.构建 n 个记录的初始堆，其时间复杂度为_。【华中科技大学 2006 年】（分数：2.00）A.O(n)B.O(n 2 )C.O(log 2 n)D.O(nlog 2 n)20.在对 n 个元素的序列进行排序时，堆排序所需要的附加存储空间是_。【西安电子科技大学 2001 年】（分数：2.00）A.O(log 2 n)B.O(1)C.O(n)D.O(nlog 2 n)21.对 n 个记录的文件进行堆排序，最坏情况下的执行时间是_。【北京交通大学 2001 年（分数：2.00）A.O(log 2 n)B.O(n)C.O(nlog 2 n)D.O(n 2 )22.
9、归并排序中，归并趟数的数量级是_。【南京理工大学 2000 年】（分数：2.00）A.O(n)B.O(log 2 n)C.O(nlog 2 n)D.O(n 2 )23.对具有 n 个元素的序列采用二路归并排序算法排序，算法的空间复杂度是_。【北京航空航天大学2007 年】（分数：2.00）A.O(n)B.O(2n)C.O(n 2 )D.O(log 2 n)24.若需在 O(nlog 2 n)的时间内完成对数组的排序，且要求排序是：稳定的，则可选择的排序方法是_。【北京交通大学 2004 年】【太原科技大学 2007 年】（分数：2.00）A.快速排序B.堆排序C.归并排序D.直接插入排序25.
10、排序趟数与序列的原始状态有关的排序方法是_排序法。【北京航空航天大学 1999 年】（分数：2.00）A.插入B.选择C.冒泡D.基数26.下列排序方法中，_在待排序的数据为有序时，花费时间反而最多。【华中科技大学 2007 年】（分数：2.00）A.快速排序B.插入排序C.堆排序D.冒泡排序27.当待排序序列基本有序时，下列方法中_最好。【北京邮电大学 2005 年】（分数：2.00）A.直接插入排序B.快速排序C.堆排序D.归并排序28.下面给出的 4 种排序方法中，排序过程中的比较次数与序列初始状态无关的是_。【北京航空航天大学 2000 年】（分数：2.00）A.选择排序法B.插入排序
11、法C.快速排序法D.堆积排序法29.用直接插入排序方法对下面 4 个序列进行排序(由小到大)，元素比较次数最少的是_。【北方交通大学 2001 年】（分数：2.00）A.94，32，40，90，80，46，21，69B.32，40，21，46，69，94，90，80C.21，32，46，40，80，69，90，94D.90，69，80，46，21，32，94，4030.数据序列(2，1，4，9，8，10，6，20)只能是下列排序算法中的_的两趟排序后的结果。【合肥工业大学 2000 年】（分数：2.00）A.快速排序B.冒泡排序C.选择排序D.插入排序31.对一组数据(84，47，25，15，
12、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.00）A.选择B.冒泡C.快速D.插入32.下列排序算法中，_算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。【南开大学 2000 年】【西北大学 2001 年】（分数：2.00）A.堆排序B.冒泡排序C.快速排序D.插入排序33.用某种排序方法对关键字序列(25，84，21，47，15，27，68，35，20)进行排序时，
13、序列的变化情况如下：20，15，21，25，47，27，68，35，84,15，20，21，25，35，27，47，68，84,15，20，21，25，27，35，47，68，84 则所采用的排序方法是_。【北京交通大学 2003 年】（分数：2.00）A.选择排序B.希尔排序C.归并排序D.快速排序34.若序列的原始状态为 1，2，3，4，5，10，6，7，8，9，要想使得排序过程中元素比较次数最少，则应该采用_方法。【北京航空航天大学 2004 年】（分数：2.00）A.插入排序B.选择排序C.希尔排序D.冒泡排序35.下列排序算法中_排序在一趟结束后不一定能选出一个元素放在其最终位置上。
14、【南京理工大学2001 年】【哈尔滨工业大学 2001 年】（分数：2.00）A.选择B.冒泡C.归并D.堆36.在下面的排序方法中，辅助空间为 O(n)的是_。【南京理工大学 1999 年】（分数：2.00）A.希尔排序B.堆排序C.选择排序D.归并排序37.下列排序算法中，占用辅助空间最多的是_。【厦门大学 2002 年】（分数：2.00）A.归并排序B.快速排序C.希尔排序D.堆排序38.对初始状态为递增序列的表按递增顺序排序，最省时间的是_算法，最费时间的是_算法。【南开大学 2000 年】（分数：2.00）A.堆排序B.快速排序C.插入排序D.归并排序39.就平均性能而言，目前最好的
15、内部排序方法是_排序法。【西安电子科技大学 1998 年】（分数：2.00）A.冒泡B.希尔插入C.交换D.快速40.如果只想得到 1000 个元素组成的序列中第 lO 个最小元素之前的部分排序的序列，用_方法最快。【北京交通大学 2003 年】（分数：2.00）A.冒泡排序B.快速排列C.希尔排序D.堆排序41.基于比较方法的 n 个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是_。【南京理工大学 1996 年】（分数：2.00）A.O(nlog 2 n)B.O(log 2 n)C.O(n)D.O(n 2 )42.基于比较的排序算法时间复杂度最好的是 O(_)。【北京邮电大学 20
16、07 年】（分数：2.00）A.log 2 nB.nC.nlog 2 nD.n 243.在最好情况下，对 n 个记录的顺序表作_排序，其时间复杂度为 O(n)。【华中科技大学 2006 年】（分数：2.00）A.归并排序B.快速排序C.堆排序D.直接插入排序44.对各种内部排序方法来说，_。【华南理工大学 2006 年】（分数：2.00）A.快速排序时间性能最佳B.基数排序和归并排序是稳定的排序方法C.快速排序是一种选择排序D.堆排序所用的辅助空间比较大二、综合题(总题数：6，分数：20.00)45.冒泡排序算法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)请给出上浮和
17、下沉过程交替的冒泡排序算法。【吉林大学 2001 年】（分数：2.00）_46.有 50 个学生的记录(每个学生的记录包括学号和成绩)，组成记录数组，按成绩由高到低的次序输出(每行 10 个记录)。排序方法采用选择排序。【北京师范大学 1999 年】（分数：2.00）_有一种简单的排序算法，叫做计数排序(CountSorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值
18、为 c，那么，这个记录在新的有序表中的合适的存放位置即为C。（分数：8.00）(1).给出适用于计数排序的数据表定义。（分数：2.00）_(2).使用 C 语言编写实现计数排序的算法。（分数：2.00）_(3).对于有 n 个记录的表，关键码比较次数是多少?（分数：2.00）_(4).与简单选择排序相比较，这种方法是否更好?为什么?【清华大学 2000 年】（分数：2.00）_47.设有一个数组中存放了一个无序的关键序列 K 1 、K 2 、K n 。现要求将 Kn 放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 n。【南京航空航天大学 1997 年】（分数：
19、2.00）_已知关键字序列(K 1 ，K 2 ，K 3 ，K n-1 )是大根堆。（分数：4.00）(1).试写出一算法将(K 1 ，K 2 ，K 3 ，K n-1 ,K n )调整为大根堆。（分数：2.00）_(2).利用 1)的算法写一个建大根堆的算法。【中科院软件所 1999 年】（分数：2.00）_48.设有顺序放置的 n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。【上海大学 1999 年】（分数：2.00）_计算机
20、专业基础综合数据结构（排序）历年真题试卷汇编 6 答案解析(总分：108.00，做题时间：90 分钟)一、单项选择题(总题数：44，分数：88.00)1.某内部排序方法的稳定性是指_。【南京理工大学 1997 年】（分数：2.00）A.该排序算法不允许有相同的关键字记录B.该排序算法允许有相同的关键字记录C.平均时间为 O(nlogn)的排序方法D.以上都不对 解析：解析：考查排序算法的稳定性。如果排序前后有相同关键字的记录的前后顺序不变，则称此排序是稳定的。2.若要求尽可能快地对序列进行稳定的排序，则应选_。【北京邮电大学 2001 年】（分数：2.00）A.快速排序B.归并排序 C.冒泡排
21、序D.根排序解析：解析：考查排序算法的稳定性及算法效率。归并排序和冒泡排序是稳定的，冒泡排序的平均时间复杂度为 O(n 2 )，归并排序的平均时间复杂度为 O(nlog 2 n)。3.下列排序方法中，_是稳定的排序方法。【北方交通大学 2001】（分数：2.00）A.直接选择排序B.二分法插入排序 C.希尔排序D.快速排序解析：解析：考查稳定的排序算法有哪些。插入排序、冒泡排序、二路归并排序、基数排序是稳定的排序算法，选择排序、希尔排序、快速排序、堆排序属于不稳定排序。4.对有 n 个记录的表做直接插入排序，在最好情况下，需比较_次关键字。【华中科技大学 2006 年】（分数：2.00）A.n
22、-1 B.n+1C.n2D.n(n-1)2解析：解析：考查最好情况下直接插入排序比较次数。在最好的情况下，即初始序列有序列，则每次循环只需与前一个元素比较 1 次，且不需要移动，总的比较次数为 n1。5.对 n 个不同的数据利用冒泡法从小到大排序，在下列哪种情况下元素交换的次数最多_。【北京交通大学 2007 年】（分数：2.00）A.从大到小排列好的 B.从小到大排列好的C.元素无序D.元素基本有序解析：解析：考查冒泡排序最差的情况。一般情况下冒泡排序最多进行 n1 次冒泡。若初始序列为逆序时，则需进行 n 一 1 次冒泡，并且需要交换次数最多。6.采用简单选择排序，比较次数与移动次数分别为
23、_。【南京理工大学 2000 年】（分数：2.00）A.O(n)，O(10gn)B.O(logn)，O(n*n)C.O(n*n)，O(n) D.O(nlogn)，O(n)解析：解析：考查简单选择排序的比较次数和移动次数。简单选择排序过程共需选择 n1 次，第 i 趟选择具有最小元素所需的比较次数总是 ni 次，与初始排列无关，总共比较次数为 n(n 一 1)2 次。最多交换次数为 n 一 1 次。7.希尔排序属于_。【太原科技大学 2006 年】（分数：2.00）A.插入排序 B.交换排序C.选择排序D.归并排序解析：解析：考查希尔排序的概念。希尔排序又称“缩小增量排序”，它也是一种属于插入排
24、序类的方法。8.对序列15，9，7，8，20，一 1，4用希尔排序方法排序，经一趟后序列变为15，一1，4，8，20，9，7则该次采用的增量是_。【南京理工大学 1999 年】（分数：2.00）A.1B.4 C.3D.2解析：解析：考查希尔排序的过程。希尔排序将序列分成若干个组，只在组内进行交换。由观察可知，经过一趟后 9 和一 1 交换7 和 4 交换，可得增量为 4。9.有些排序算法在每趟排序过程中，都会有一个元素被放置到其最终位置上，下列算法不会出现此种情况的是_。【北京交通大学 2005 年】（分数：2.00）A.希尔排序 B.堆排序C.冒泡排序D.快速排序解析：解析：考查希尔排序的性
25、质。在希尔排序中，序列被分成了组，组内的排序并不能保证一定有元素被放置到其最终位置上。10.从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于等于所选元素，而所选元素处在排序的最终位置。这种排序法称为_。【北京航空航天大学 2005 年】（分数：2.00）A.插入排序法B.冒泡排序法C.希尔排序法D.快速排序法 解析：解析：考查快速排序的概念。快速排序是基于分治的思想，将序列分为两个部分递归的实现排序。11.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得
26、到的一次划分结果为_。【北京交通大学 2005 年】（分数：2.00）A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84) D.(40，38，46，84，56，79)解析：解析：考查快速排序的过程。以第一个记录 46 为基准，先从后向前查找比它小的，找到 40，交换两者位置，序列变为(40，79，56，38，46，84)，然后从前向后找比 46 大的，找到 79，交换位置，46 到了第二个位置，继续从后面找比 46 小的元素，找到 38，交换。再次从前向后找比 46 大的元素，找到56，交换。一趟划分完成。12.对下列
27、4 个序列，以第一个关键字为基础用快速排序算法进行排序，在第一趟过程中移动记录次数最多的是_。【电子科技大学 2007 年】（分数：2.00）A.92，96，100，110，42，35，30，88 B.92，96，88，42，30，35，110，100C.100，96，92，35，30，110，88，42D.42，30，35，92，100，96，88，110解析：解析：考查快速排序移动的过程。分别对 4 个选项进行一趟快速排序，可得 A 选项需要移动 7 个记录，次数最多。13.快速排序方法在_情况下最不利于发挥其长处。【华南理工大学 2007 年】（分数：2.00）A.要排序的数据量太大B.
28、要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序 解析：解析：考查快速排序的最坏情况。每次分组时，分成的两个组大小平衡，快速排序处于最优状态。当待排序序列基本有序时，快速排序法性能最差。14.对 n 个元素的表做快速排序，最坏情况下，算法的时间复杂度为_。【华中科技大学 2006 年】（分数：2.00）A.O(log 2 n)B.O(nlog 2 n)C.O(n 2 ) D.O(2 n )解析：解析：考查快速排序的最坏情况。快速排序的最坏情况发生在两个区域分别包含 n1 个元素和 0个元素时，这种最大程度的不对称性若发生在每一层递归上时，就得到时间复杂度为 O(
29、n 2 )。15.对以下关键字序列用快速排序算法进行排序，速度最慢的是_。【北京交通大学 2002 年】（分数：2.00）A.20，24，4，16，22，29B.24，22，29，16，20，4，8C.20，8，16，29，24，22，4D.4，8，16，20，24，29 解析：解析：考查快速排序的最坏情况。当待排序序列有序时，快速排序最慢。16.快速排序在最坏的情况下的时间复杂度与下面哪个算法的最坏情况下的时间复杂度相同_。【北京交通大学 2006 年】（分数：2.00）A.希尔排序B.堆排序C.冒泡排序 D.基数排序解析：解析：考查各类排序算法最坏情况下的时间复杂度。希尔排序时间复杂度无法
30、进行详细比较，堆排序最坏情况和最好情况时间复杂度都为 0(n10g2n)，冒泡排序最坏时间复杂度为 O(n 2 )，基数排序最坏情况下的时间复杂度为 O(d(n+r)。快速排序最坏情况下的时间复杂度为 O(n 2 )。17.根据堆的定义，下面 4 个序列中，构成堆的是_。【广东工业大学 2002 年】（分数：2.00）A.77，67，32，17，27，47，22，12B.77，67，47，12，32，27，22，17C.77，47，67，32，17，27，22，12 D.77，47，67，12，27，32，22，17解析：解析：考查堆的定义。堆有两种形式：大顶堆和小顶堆。在大顶堆中，树中任一非
31、叶结点的关键字均不小于其左、右孩子(若存在)结点的关键字。显然，大顶堆中最大元素存放在根结点中，并且对其任一非根结点，它的值小于或等于其双亲结点。小顶堆的定义则刚好相反，其根结点是最小元素。18.有组数据(15，9，7，8，20，一 1，7，4)，用堆排序的筛选方法建立的初始堆为_。【南京理工大学 1996 年】（分数：2.00）A.一 1，4，8，9，20，7，15，7B.一 1，7，15，7，4，8，20，9C.一 1，4，7，8，20，15，7，9 D.A，B，C 均不对。解析：解析：考查建立堆的过程。本题中，建堆操作是将一个输入数组 ALn变为一个小顶堆的过程。从树中最后一个非叶结点(
32、最后一个元素的父结点)开始，向前对各个元素进行调整。看每个结点值是否小于其左、右子结点的值，若不是，将左、右子结点中较小值与之交换，并对交换后的子树结点继续向下调整。19.构建 n 个记录的初始堆，其时间复杂度为_。【华中科技大学 2006 年】（分数：2.00）A.O(n) B.O(n 2 )C.O(log 2 n)D.O(nlog 2 n)解析：解析：考查建堆的时间复杂度。建堆过程中，向下调整的时间与树高有关，为 O(h)。建堆过程中每次向下调整时，大部分结点的高度都较小。因此，可以证明在元素个数为 n 的序列上建堆，其时间复杂度为 O(n)。20.在对 n 个元素的序列进行排序时，堆排序
33、所需要的附加存储空间是_。【西安电子科技大学 2001 年】（分数：2.00）A.O(log 2 n)B.O(1) C.O(n)D.O(nlog 2 n)解析：解析：考查堆排序的空间复杂度。堆排序只需要一个辅助空间。21.对 n 个记录的文件进行堆排序，最坏情况下的执行时间是_。【北京交通大学 2001 年（分数：2.00）A.O(log 2 n)B.O(n)C.O(nlog 2 n) D.O(n 2 )解析：解析：考查堆排序最坏的时间复杂度。堆排序在最好、平均、晟坏情况下的时间复杂度都为O(nlog 2 n)。22.归并排序中，归并趟数的数量级是_。【南京理工大学 2000 年】（分数：2.
34、00）A.O(n)B.O(log 2 n) C.O(nlog 2 n)D.O(n 2 )解析：解析：考查归并排序的趟数。归并排序将序列一分为二，将问题范围缩小到原来的一半递归地加以解决，最终归并的趟数应该为 O(log 2 n)。23.对具有 n 个元素的序列采用二路归并排序算法排序，算法的空间复杂度是_。【北京航空航天大学2007 年】（分数：2.00）A.O(n) B.O(2n)C.O(n 2 )D.O(log 2 n)解析：解析：考查二路归并排序的空间复杂度。24.若需在 O(nlog 2 n)的时间内完成对数组的排序，且要求排序是：稳定的，则可选择的排序方法是_。【北京交通大学 200
35、4 年】【太原科技大学 2007 年】（分数：2.00）A.快速排序B.堆排序C.归并排序 D.直接插入排序解析：解析：考查排序算法效率以及稳定性。各类排序算法的性能比较见表 6-1。25.排序趟数与序列的原始状态有关的排序方法是_排序法。【北京航空航天大学 1999 年】（分数：2.00）A.插入B.选择C.冒泡 D.基数解析：解析：考查原始序列状态对排序算法的影响。当待排序序列有序时，冒泡排序只需要比较 n1 次，而不需要移动元素：当待排序序列逆序时，需要进行 n1 次冒泡。26.下列排序方法中，_在待排序的数据为有序时，花费时间反而最多。【华中科技大学 2007 年】（分数：2.00）A
36、.快速排序 B.插入排序C.堆排序D.冒泡排序解析：解析：考查各排序算法对于初始序列的敏感性。当待排序序列有序时，快速排序退化为冒泡排序。时间复杂度为 O(n 2 )。27.当待排序序列基本有序时，下列方法中_最好。【北京邮电大学 2005 年】（分数：2.00）A.直接插入排序 B.快速排序C.堆排序D.归并排序解析：解析：考查各类排序算法对初始序列的敏感性。当待排序序列基本有序时，直接插入排序只需要比较 n1 次，算法性能最好。28.下面给出的 4 种排序方法中，排序过程中的比较次数与序列初始状态无关的是_。【北京航空航天大学 2000 年】（分数：2.00）A.选择排序法 B.插入排序法
37、C.快速排序法D.堆积排序法解析：解析：考查比较次数和序列初始状态的关系。选择排序法整个排序过程共需选择 n 一 1 次，第 i 趟选择具有最小元素所需的比较次数总为 ni 次，总共比较次数为 n(n 一 1)2 次。29.用直接插入排序方法对下面 4 个序列进行排序(由小到大)，元素比较次数最少的是_。【北方交通大学 2001 年】（分数：2.00）A.94，32，40，90，80，46，21，69B.32，40，21，46，69，94，90，80C.21，32，46，40，80，69，90，94 D.90，69，80，46，21，32，94，40解析：解析：考查直接插入排序元素比较次数最少
38、的条件。当初始序列有序时，直接插入排序的比较次数最少。观察可知，C 选项基本有序，所以比较次数最少。30.数据序列(2，1，4，9，8，10，6，20)只能是下列排序算法中的_的两趟排序后的结果。【合肥工业大学 2000 年】（分数：2.00）A.快速排序 B.冒泡排序C.选择排序D.插入排序解析：解析：考查各类排序算法的过程。冒泡排序和选择排序两趟之后必然有两个最小值有序的排在序列头部，插入排序两趟之后前 3 个元素应该有序。31.对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为：(1)84,47,25,15,21(2)15,47,25,84,21(3)1
39、5,21,25,84,47(4)15,21,25,47,84 则采用的排序是_。【南京理工大学 1997 年】（分数：2.00）A.选择 B.冒泡C.快速D.插入解析：解析：考查各类排序算法的过程。通过观察发现每次排序都是从未排序序列中选择一个最小的元素放到其最终的位置。正是选择排序的特征。32.下列排序算法中，_算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。【南开大学 2000 年】【西北大学 2001 年】（分数：2.00）A.堆排序B.冒泡排序C.快速排序D.插入排序 解析：解析：考查各类排序的过程。堆排序、冒泡排序、快速排序每一趟排序后总有一个元素是在其最终
40、位置上。插入排序有可能出现最小的元素在最后面，最后一个元素插入到前面之后，各个元素才各就各位。33.用某种排序方法对关键字序列(25，84，21，47，15，27，68，35，20)进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，84,15，20，21，25，35，27，47，68，84,15，20，21，25，27，35，47，68，84 则所采用的排序方法是_。【北京交通大学 2003 年】（分数：2.00）A.选择排序B.希尔排序C.归并排序D.快速排序 解析：解析：考查各种排序方法的过程。观察序列变化，发现第一趟排序序列位置变化很大，所以不可能是选择排序
41、和归并排序。又发现第二趟排序 15 和 20 交换了位置，所以不可能是希尔排序。所采用的排序算法正是快速排序。34.若序列的原始状态为 1，2，3，4，5，10，6，7，8，9，要想使得排序过程中元素比较次数最少，则应该采用_方法。【北京航空航天大学 2004 年】（分数：2.00）A.插入排序 B.选择排序C.希尔排序D.冒泡排序解析：解析：考查各类排序算法的过程。当初始序列基本有序时，插入排序比较次数最少(13 次)，冒泡排序(17 次)。35.下列排序算法中_排序在一趟结束后不一定能选出一个元素放在其最终位置上。【南京理工大学2001 年】【哈尔滨工业大学 2001 年】（分数：2.00
42、）A.选择B.冒泡C.归并 D.堆解析：解析：考查排序算法能否将元素放在最终位置。选择排序、冒泡排序、堆排序在一趟结束后都可以选出一个元素放在最终位置上。归并排序是递归进行的，某一趟排序只是在各个局部进行排序，不一定能选出一个元素将其放在最终位置上。36.在下面的排序方法中，辅助空间为 O(n)的是_。【南京理工大学 1999 年】（分数：2.00）A.希尔排序B.堆排序C.选择排序D.归并排序 解析：解析：考查各类排序的空间复杂度。从空间复杂度来讲，希尔排序、堆排序、选择排序都为 O(1)，只有归并排序为 O(n)。37.下列排序算法中，占用辅助空间最多的是_。【厦门大学 2002 年】（分
43、数：2.00）A.归并排序 B.快速排序C.希尔排序D.堆排序解析：解析：考查各类排序算法所需辅助空间。快速排序是递归的，需要一个栈来存放每一层递归调用的必要信息，其最大容量应与递归调用的深度一致，最好情况下为 O(log 2 n)；最坏情况下，因为要进行 n一 1 次递归调用，所以，栈的深度为 O(n)；希尔排序、堆排序空间复杂度都为 O(1)。38.对初始状态为递增序列的表按递增顺序排序，最省时间的是_算法，最费时间的是_算法。【南开大学 2000 年】（分数：2.00）A.堆排序B.快速排序C.插入排序 D.归并排序解析：解析：B。考查各种排序当序列有序时的效率。当序列已经为递增时，插入
44、排序只需要比较 n 一 1次，不需移动，而快速排序此时需要比较 n(n1)次。堆排序、归并排序不受初始序列影响，算法时间复杂度为 O(nlog 2 n)。39.就平均性能而言，目前最好的内部排序方法是_排序法。【西安电子科技大学 1998 年】（分数：2.00）A.冒泡B.希尔插入C.交换D.快速 解析：解析：考查平均性能最好的排序算法。虽然快速排序算法在初始序列有序时性能变差，但是就平均性能而言，快速排序仍然是最好的排序算法。40.如果只想得到 1000 个元素组成的序列中第 lO 个最小元素之前的部分排序的序列，用_方法最快。【北京交通大学 2003 年】（分数：2.00）A.冒泡排序B.
45、快速排列C.希尔排序D.堆排序 解析：解析：考查灵活运用各种排序算法的能力。希尔排序和快速排序要等排序全部完成之后才能确定最小的 10 个元素，冒泡排序需要从头到尾冒 10 趟才能得到 10 个最小的元素，而堆排序只需要调整 10 次小根堆，调整时间与树高成正比。显然堆排序所需时间更短。41.基于比较方法的 n 个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是_。【南京理工大学 1996 年】（分数：2.00）A.O(nlog 2 n) B.O(log 2 n)C.O(n)D.O(n 2 )解析：解析：考查基于比较的排序算法的时间复杂度。最好下界即是最低的时间复杂度，归并排序在最坏情况下时间复杂度为 O(nlog 2 n)。42.基于比较的排序算法时间复杂度最好的是 O(_)。【北京邮电大学 2007 年】（分数：2.00）A.log 2 nB.nC.nlog 2 n D.n 2解析：解析：考查基于比较的排序算法的时间复杂度。此处应按平均复杂度来比较。43.在最好情况下，对 n 个记录的顺序表作_排序，其时间复杂度为 O(n)。【华中科技大学 2006 年】（分数：2.00）A.归并排序B.快速排序C.堆排序D.直接插入排序 解析：解析：考查最好情况下时间复杂度为 O(n)的算法。归并排序最好和最坏
