发布时间 : 星期一 文章计算机专业基础综合数据结构(排序)历年真题试卷汇编3更新完毕开始阅读cc8125e6640e52ea551810a6f524ccbff021caeb
计算机专业基础综合数据结构（排序）历年真题试卷汇编3
(总分：72.00，做题时间：90分钟)
一、 单项选择题(总题数：15，分数：36.00)
1.下面给出的四种排序法中，( )排序法是不稳定性排序法。【北京航空航天大学1999一、10(2分)】 （分数：2.00） A.插入 B.冒泡 C.二路归并 D.堆 √ 解析：
2.下列排序算法中，其中( )是稳定的。【福州大学1998一、3(2分)】 （分数：2.00） A.堆排序，冒泡排序 B.快速排序，堆排序 C.直接选择排序，归并排序 D.归并排序，冒泡排序 √ 解析：
3.稳定的排序方法是( )。【北方交通大学2000二、3(2分)】 （分数：2.00）
A.直接插入排序和快速排序 B.折半插入排序和起泡排序 √ C.简单选择排序和四路归并排序 D.树形选择排序和Shell排序 解析：
4.下列排序方法中，哪一个是稳定的排序方法?( )。【北方交通大学2001一、8(2分)】 （分数：2.00） A.直接选择排序 B.二分法插入排序 √ C.希尔排序 D.快速排序 解析：
5.下列排序算法中，( )是稳定排序。【北京理工大学2007一、10(1分)】 （分数：2.00） A.希尔排序 B.快速排序 C.堆排序
D.直接插入排序 √ 解析：
6.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。( )就是不稳定的排序方法。【清华大学1998一、3(2分)】 （分数：2.00） A.起泡排序 B.归并排序 C.Shell排序 √ D.直接插入排序 E.简单选择排序 √ 解析：
7.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选( )排序为宜。【中科院计算所2000一、5(2分)】 （分数：2.00） A.直接插入 √ B.直接选择 C.堆 D.快速 E.基数 解析：
8.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )。【中国科技大学1998二、4(2分)】【中科院计算所1998二、4(2分)】 （分数：2.00） A.快速排序 B.堆排序 C.归并排序 √ D.直接插入排序 解析：
9.下面的排序算法中，不稳定的是( )。【北京工业大学1999一、2(2分)】 （分数：2.00） A.起泡排序 B.折半插入排序 C.简单选择排序 √ D.希尔排序 √ E.基数排序 解析：
下列内部排序算法中：【北京工业大学2000一、1(10分每问2分)】A．快速排序B．直接插入排序C．二路归并排序D．简单选择排序E．起泡排序（分数：8.00） (1).其比较次数与序列初态无关的算法是( )（分数：2.00） A. B. C. √ D. √ E. 解析：
(2).不稳定的排序算法是( )（分数：2.00） A. √ B. C. D. √ E. 解析：
(3).在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序，k< A. B. √ C. D. E. 解析：
(4).排序的平均时间复杂度为O(n*10gn)的算法是( )，为O(n*n)的算法是( )（分数：2.00）
A. √ B. √ C. √ D. √ E. √ 解析：
10.排序趟数与序列的原始状态有关的排序方法是( )排序法。【北京航空航天大学1999一、9(2分)】 （分数：2.00） A.插入 B.选择 C.冒泡 √ D.快速 √
解析：解析：排序趟数和序列的初始状态无关的排序方法有：直接插入排序，折半插入排序，希尔排序，简单选择排序，归并排序，基数排序。而元素的比较次数和序列的初始状态无关的排序方法有：折半插入排序，简单选择排序，归并排序，基数排序。
11.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是( )。【北京航空航天大学2000一、10(2分)】 （分数：2.00） A.选择排序法 √ B.插入排序法 C.快速排序法 D.堆排序法 解析：
12.排序方法中，关键字比较的次数与记录的初始排列无关的是( )。【北京交通大学2013 二、14(2分)】 （分数：2.00） A.简单选择排序 √ B.快速排序 C.直接插入排序 D.Shell排序 解析：
13.对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。【南京理工大学2000一、7(1．5分)】 （分数：2.00） A.直接插入 B.二分法插入 √ C.快速排序 D.归并排序 √ 解析：
14.在下列排序算法中，哪一个算法的时间复杂度与初始排序无关? ( )【北京理工大学2001六、4(2)】【北京工业大学2005一、4(2分)】 （分数：2.00） A.直接插入排序 B.气泡排序 C.快速排序 D.直接选择排序 √ 解析：
二、 填空题(总题数：5，分数：10.00)
15.直接选择排序算法在最好情况下所做的交换元素次数为__________。【中南大学2005二、5(2分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：0) 解析：
16.一组记录的排序码为(25，48，16，35，79，82，23，40，36，72)，其中含有5个长度为2的有序表，按2路归并排序的方法对该序列进行一趟归并后的结果__________。【北京交通大学2005二、8(2分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：16，25，35，48，23，40，79，82，36，72。两组(四个)长度为2的有序表进行归并，第5个长度为2的有序表不动，等待和前面长度为8的有序表归并。) 解析：
17.设用希尔排序对数组{98，36，一9，0，47，23，1，8，10，7)进行排序，给出的步长(也称增量序列)依次是4，2，1，则排序需__________趟，写出第一趟结束后，数组中数据的排列次序__________。【南京理工大学1997三、5(2分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：3，(10，7，一9，0，47，23，1，8，98，36)) 解析：
18.设要将线性表(45，86，99，76，43，19，67，26，65，72，85，14)从小到大进行排序，则使用冒泡排序、初始步长为4的Shell排序、归并排序和以第一个元素为分界元素的快速排序进行第一趟扫描的结果分别为(1)，(2)，(3)，(4)。【上海海事大学2005二、5(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：初态：45，86，99，76，43，19，67，26，65，72，85，14 (1)45，86，76，43，19，67，26，65，72，85，14，99 (2)43，19，67，14，45，72，85，26，65，86，99，76 (3)45，86，76，99，19，49，26，67，65，72，14，85 (4) 14，26，19，43，45，76，67，99，65，72，85，86) 解析：
19.关键字序列(Q，H C，Y, Q，A，M,S,R，D，E,X)，要按照关键字值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是__________；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是__________。【北京大学1997一、4(4分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(Q，A，C，S,Q，D，F,X,R，H M,Y)，(F,E,H,C,D，Q，A，M,Q，R,S,Y,X)) 解析：
三、 判断题(总题数：10，分数：20.00)
20.用希尔(Shell)方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。( )【中国海洋大学2005二、12(1分)】 （分数：2.00） A.正确 B.错误 √ 解析：
21.起泡排序的排序趟数与参加排序的序列原始状态有关。( )【兰州大学2000一、5(1分)】 （分数：2.00） A.正确 √ B.错误 解析：
22.对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是O(n )。( )【中国海洋大学2006二、15(1分)】 （分数：2.00） A.正确 √
2