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

计算机专业基础综合数据结构（排序）历年真题试卷汇编4(总分：66.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是( )。

[山东大学2001二、2(1分)】A.直接插入排序√B.冒泡排序C.简单选择排序D.快速排序2.在排序算法中，每次从未排序的记录中挑出最小(或最大)关键字的记录，加入到已排序记录的末尾，该排序方法是( )。

【中山大学1999一、11(1分)】A.选择√B.冒泡C.插入D.堆3.若用冒泡排序方法对序列{10，14，26，29，41，52}从大到小排序，需进行( )次比较。

【南京理工大学1999一、11(4分)】A.3B.10C.15 √D.254.采用简单选择排序，比较次数与移动次数分别为( )。

【南京理工大学2000一、18(1．5分)】A.O(n)，O(logn)B.O(logn)，O(n*n)C.O(n*n)，O(n) √D.O(nlogn)，O(n)5.对序列{15，9，7，8，20，一1，4，)用希尔排序方法排序，经一趟后序列变为{15，一1，4，8，20，9，7}，则该次采用的增量是( )。

【南京理工大学1999一、15(1分)】A.1B.4 √C.3D.26.快速排序在最坏情况下的时间复杂度与下列哪个算法最坏情况下的时间复杂度相同? ( )。

【北京交通大学2006一、7(2分)】A.Shell排序B.堆排序C.起泡排序√D.基排序7.下列排序方法中，( )在待排序的数据为有序时，花费时间反而最多。

【华中科技大学2007一、8(2分)】A.快速排序√B.插入排序C.堆排序D.冒泡排序8.快速排序算法在最好情况下的时间复杂度是( )。

【南京理工大学2005一、1(1分)】A.O(n)B.O(n 2 )C.O(nlog 2 n) √D.O(log 2 n)9.对下列关键字序列用快速排序法进行排序时，速度最快的情形是( )。

【北方交通大学2001一、18(2分)】A.{21，25，5，17，9，23，30} √B.{25，23，30，17，2l，5，9}C.{21，9，17，30，25，23，5}D.{5，9，17，21，23，25，30}10.对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是( )。

【北方交通大学2000二、5(2分)】A.每次分区后，先处理较短的部分√B.每次分区后，先处理较长的部分C.与算法每次分区后的处理顺序无关D.以上三者都不对11.快速排序在最坏情况下的时间复杂度是( )，比( )的性能差。

【山东工业大学1995二、2(4分)】A.O(NlogN)B.O(N2) √C.O(N2)D.堆排序√E.冒泡排序12.当n个整型数据是有序时，对这n个数据用快速排序算法排序，则时间复杂度是(1)，当用递归算法求n!时，算法的时间复杂度是(2)【南京理工大学1 999一、(6—7)(4分)】A.O(nlog^2n) √B.O(n) √C.O)(n*n)D.O(log^2n)13.对各种内部排序方法来说( )。

【华南理工大学2006一、3(2分)】A.快速排序时间性能最佳√B.基数排序和归并排序是稳定的排序方法C.快速排序是一种选择排序D.堆排序所用的辅助空间比较大14.在含有n个关键字的小根堆(堆顶元素最小)中，关键字最大的记录有可能存储在( )位置上。

【中科院计算所2000一、4(2分)】A.[n／2]B.[n／2]一1C.1D.[n／2]+2 √小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于[n／2]的结点上。

例子中A是最后一个分支结点，B是分支结点，C是小堆顶，值最小，D是叶子结点，所以选D。

15.若对n个元素进行堆排序，则在初始建堆的过程中需要进行( )筛选。

【北京理工大学2005一、5(1分)】A.1B.n／2 √C.(n一1)／2D.n建堆要从最后一个分支结点开始筛选，直至根结点，最后一个分支结点的编号是n／2。

二、填空题(总题数：7，分数：14.00)16.磁盘排序过程主要是先生成__________，然后对__________合并，而提高排序速度很重要的是__________，我们将采用__________方法来提高排序速度。

【山东工业大学1995一、4(4分)】__________________________________________________________________________________________ 正确答案：(正确答案：初始归并段，初始归并段，减少外存信息读写次数(即减少归并趟数)，增加归并路数和减少初始归并段个数)17.在基于关键字比较且时间为O(nlog 2 n)的排序中，若要求排序是稳定的，则可选用__________ 排序；若要求就地排序(及辅助空间为O(1))，则可选用__________排序。

【中国科学技术大学1998一、7(2分)】__________________________________________________________________________________________ 正确答案：(正确答案：归并，堆)18.外排序的基本操作过程是__________和__________。

【西安电子科技大学1998二、3(3分)】__________________________________________________________________________________________ 正确答案：(正确答案：生成有序归并段(顺串)，归并)19.外部排序的基本方法是归并排序，但在之前必须先生成__________。

【北京邮电大学2001二、6(2分)】__________________________________________________________________________________________ 正确答案：(正确答案：初始归并段(顺串))20.设工作区的容量为W，则置换一选择排序法所得到的初始归并段长度的期望值为__________。

【上海交通大学2004五、3(15／4分)】__________________________________________________________________________________________ 正确答案：(正确答案：2W)21.下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n一1]中，依次下去，直到待排序列为递增序。

(注：代表两个【南京理工大学2001三、2(10分)】【中国海洋大学2007三(12分)】void sort(SqList&r，变量的数据交换)。

int n) {i=1； While(f1) ) (min=max=i； for(J=i+1；(2) ；++j) {if((3) )min=j； elseif(r[j]key>r[max]．key)max=J；} if(i垒2 )r[min]r[i]; if(max!=n-i+1] {if((5) )r[min](一一>r In —i+1]；else((6)}；} i++； } }／／sort__________________________________________________________________________________________ 正确答案：(正确答案：(1)i≤n／2 (2)j≤n-i+1 (3)r[j]．key<-->r[n—i+1])22.下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

【北京交通大学2005七、3(6分)] #define n 10 int sDlit(int a[hi，int low，int high) {int j，k，x； k=low：J=high；x=a[k]；while(k=x&&k<=x&&k=0) { (2) ； high=stack[top][1]； top一一； k=split(a，low，high)； if(low __________________________________________________________________________________________ 正确答案：(正确答案：(1)a[j]=a[k] (2)low=stack[top][0](3)stack[top][0]=k+1)三、判断题(总题数：4，分数：8.00)23.为提高排序速度，进行外排序时，必须选用最快的内排序算法。

( )【大连海事大学2001一、4(1分)】A.正确B.错误√24.外排中使用置换选择排序的目的是增加初始归并段的长度。

( )【北京邮电大学2005二、10(1分)】A.正确√B.错误25.影响外排序的时间因素主要是内存与外设交换信息的总次数。

( )【东北大学1997二、5(2分)】A.正确√B.错误26.在外部排序中，使用选择树法可以减少初始归并段的数量。

( )【哈尔滨工业大学2005三、3(1分)】A.正确√B.错误四、综合题(总题数：4，分数：8.00)27.考虑由三个不同关键词构成的序列：{a，b，c}，试画出直接插入排序算法的二叉判定树。

【吉林大学2001一、3(4分)】__________________________________________________________________________________________正确答案：(28.设要求从大到小排序。

问在什么情况下冒泡排序算法关键字交换的次数为最大。

【南京航空航天大学1996九、1(4分)】__________________________________________________________________________________________正确答案：(正确答案：对冒泡算法而言，初始序列为反序时交换次数最多。

若要求从大到小排序，则表现为初始是上升序时交换次数最多。

)29.设与记录R 1，R 2，…，R n对应的关键字分别是K 1，K 2，…，K n。

如果存在R j和R i，使得j ij成立，试证明经过一趟起泡后，一定有记录与R i进行交换。

【吉林大学1996四、3 (20／3分)】__________________________________________________________________________________________正确答案：(正确答案：证明：起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到一个最大值或最小值(视正向排序或反向排序而定)。