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

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

22•对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是0(n2)。()【中国海洋大学2006二、15(1分)】正确丿错误23•直接选择排序算法的时间复杂度为0(n2)，不受数据初始排列的影响。()【北京邮电大学2006二、3(1分)】正确丿错误直接选择排序算法在最好情况下的时间复杂度为O(N)。()【合肥工业大学2001二、10(1分)】【北京交通大学2005三、7(2分)】正确错误丿直接选择排序是不稳定排序。()【北京邮电大学2006二、10(1分)】正确丿错误交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是O(n*n)，而快速排序算法的最坏时间复杂性是0(nlogn)；所以快速排序比冒泡排序效率更高。()【上海海事大学1998—、10(1分)19972一、9(1分)1995一、10(1分)】正确错误丿在初始数据表已经有序时，快速排序算法的时间复杂度为0(nlogn)o()【合肥工业大学2000二、29(1分)】正确错误丿在数据基本有序时，快速排序蜕变为起泡排序，时间复杂度是0(n2)。在待排数据基本有序的情况下，快速排序效果最好。()【南京理工大学1997二、4(2分)】正确错误丿快速排序总比简单排序快。()【东南大学2001一、9(1分)】正确错误V四、 综合题(总题数：3，分数：6.00)对一个由n个关键字不同的记录构成的序列，能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少进行多少次比较?【东南大学2000一、5(8分)】正确答案：(正确答案：本题答案之一请参见第9章的四、8题，这里用分治法求解再给出另一参考答案。对于两个数x和y，经一次比较可得到最大值和最小值；对于三个数x、y、z，最多经3次比较可得最大值和最小值;对于n(n>3)个数，将分成长为n一2和2的前后两部分A和B,分别找出最大者和最小者:MaXA、MinA、MaxB、MinB，最后Max={MaXA，MaxB)和Min={MinA，MinB)。对A使用同样的方法求出最大值和最小|3n上值，直到元素个数不超过3。设C(n)是所需的最多比较次数，根据上述原则，当n>3时有如下关系式：通过逐步递推，可以得到：C(n)==|3n/2|一2。显然，当n三3时，2，z一3>3n/2—2。事实上，/2|一|3n上利用比较的方法进行排序，在最坏的情况下，能达到的最好时间复杂性是什么?请给出详细证明海交通大学2000六(8分)】正确答案：(正确答案：假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二叉树高度是h，则叶子结点个数最多为2k-i；反之，若有u个叶子结点，则二叉树的高度至少为丨logu|+1。这就是说，描述n个记录排序的判定树必定存在一条长度为丨log(n!)|的22路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是|log2(n!)|。2根据斯特林公式，有Ilog(n!)I=0(nlogn)。即借助于“比较”进