1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 4 及答案解析(总分：66.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是( )。山东大学 2001 二、2(1分)】（分数：2.00）A.直接插入排序B.冒泡排序C.简单选择排序D.快速排序2.在排序算法中，每次从未排序的记录中挑出最小(或最大)关键字的记录，加入到已排序记录的末尾，该排序方法是( )。【中山大学 1999 一、11(1 分)】（分数：2.00）A.选择B.冒泡C.插入D.堆3.若用冒泡排序方法对序列10，14，26，29，41，
2、52从大到小排序，需进行( )次比较。【南京理工大学 1999 一、11(4 分)】（分数：2.00）A.3B.10C.15D.254.采用简单选择排序，比较次数与移动次数分别为( )。【南京理工大学 2000 一、18(15 分)】（分数：2.00）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 分)】（分数：2.00）A.1B.4C.3D.2
3、6.快速排序在最坏情况下的时间复杂度与下列哪个算法最坏情况下的时间复杂度相同? ( )。【北京交通大学 2006 一、7(2 分)】（分数：2.00）A.Shell 排序B.堆排序C.起泡排序D.基排序7.下列排序方法中，( )在待排序的数据为有序时，花费时间反而最多。【华中科技大学 2007 一、8(2 分)】（分数：2.00）A.快速排序B.插入排序C.堆排序D.冒泡排序8.快速排序算法在最好情况下的时间复杂度是( )。【南京理工大学 2005 一、1(1 分)】（分数：2.00）A.O(n)B.O(n 2 )C.O(nlog 2 n)D.O(log 2 n)9.对下列关键字序列用快速排序
4、法进行排序时，速度最快的情形是( )。【北方交通大学 2001 一、18(2分)】（分数：2.00）A.21，25，5，17，9，23，30B.25，23，30，17，2l，5，9C.21，9，17，30，25，23，5D.5，9，17，21，23，25，3010.对 n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是( )。【北方交通大学2000 二、5(2 分)】（分数：2.00）A.每次分区后，先处理较短的部分B.每次分区后，先处理较长的部分C.与算法每次分区后的处理顺序无关D.以上三者都不对11.快速排序在最坏情况下的时间复杂度是( )，比( )的性能差。【山东工业大
5、学 1995 二、2(4 分)】（分数：2.00）A.O(NlogN)B.O(N2)C.O(N2)D.堆排序E.冒泡排序12.当 n 个整型数据是有序时，对这 n 个数据用快速排序算法排序，则时间复杂度是(1)，当用递归算法求n!时，算法的时间复杂度是(2)【南京理工大学 1 999 一、(67)(4 分)】（分数：2.00）A.O(nlog2n)B.O(n)C.O)(n*n)D.O(log2n)13.对各种内部排序方法来说( )。【华南理工大学 2006 一、3(2 分)】（分数：2.00）A.快速排序时间性能最佳B.基数排序和归并排序是稳定的排序方法C.快速排序是一种选择排序D.堆排序所用
6、的辅助空间比较大14.在含有 n 个关键字的小根堆(堆顶元素最小)中，关键字最大的记录有可能存储在( )位置上。【中科院计算所 2000 一、4(2 分)】（分数：2.00）A.n2B.n2一 1C.1D.n2+215.若对 n 个元素进行堆排序，则在初始建堆的过程中需要进行( )筛选。【北京理工大学 2005 一、5(1分)】（分数：2.00）A.1B.n2C.(n 一 1)2D.n二、填空题(总题数：7，分数：14.00)16.磁盘排序过程主要是先生成_，然后对_合并，而提高排序速度很重要的是_，我们将采用_方法来提高排序速度。【山东工业大学 1995 一、4(4 分)】（分数：2.00）
7、_17.在基于关键字比较且时间为 O(nlog 2 n)的排序中，若要求排序是稳定的，则可选用_ 排序；若要求就地排序(及辅助空间为 O(1)，则可选用_排序。【中国科学技术大学 1998 一、7(2 分)】（分数：2.00）_18.外排序的基本操作过程是_和_。【西安电子科技大学 1998 二、3(3 分)】（分数：2.00）_19.外部排序的基本方法是归并排序，但在之前必须先生成_。【北京邮电大学 2001 二、6(2 分)】（分数：2.00）_20.设工作区的容量为 W，则置换一选择排序法所得到的初始归并段长度的期望值为_。【上海交通大学 2004 五、3(154 分)】（分数：2.00
8、）_21.下面的排序算法的思想是：第一趟比较将最小的元素放在 r1中，最大的元素放在 rn中，第二趟比较将次小的放在 r2中，将次大的放在 rn 一 1中，依次下去，直到待排序列为递增序。(注：代表两个变量的数据交换)。【南京理工大学 2001 三、2(10 分)】【中国海洋大学 2007 三(12 分)】 void sort(SqList if(max!=n-i+1 if(5) )rmin(一一r Ini+1；else(6)； i+； sort（分数：2.00）_22.下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。【北京交通大学 2005 七、3(6分) #define n
9、10 int sDlit(int ahi，int low，int high) int j，k，x； k=low：J=high；x=ak；while(k=x if(max!=n-i+1 if(5) )rmin(一一r Ini+1；else(6)； i+； sort（分数：2.00）_正确答案：(正确答案：(1)in2 (2)jn-i+1 (3)rjkeyrni+1)解析：22.下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。【北京交通大学 2005 七、3(6分) #define n 10 int sDlit(int ahi，int low，int high) int j，k，x；
10、 k=low：J=high；x=ak；while(k=x&kK i ，即说明 R j 和 R i 是反序；设对于 R i 之前全部记录 R 1 R i-1 (其中包括 K j )中关键字最大为 Kmax，则 KmaxK i ，故经过起泡排序前 i 一 2 次比较后，R i-1 的关键字一定为 Kmax，又因 KmaxK i R i ，故 R i-1 和 R i 为反序，由此可知 R i-1 和 R i 必定交换，证毕。)解析：30.现有一文件 F 含有 1000 个记录，其中只有少量记录次序不对，且它们距离正确位置不远；如果以比较和移动次数作为度量，那么将其排序最好采用什么方法?为什么? 【北
11、方交通大学 1997 四(8 分)】（分数：2.00）_正确答案：(正确答案：采用直接插入排序算法，因为记录序列已基本有序，直接插入排序比较次数少，且由于少量次序不对的记录与正确位置不远，使直接插入排序记录移动次数也相对较少，故选直接插入排序算法。)解析：五、设计题(总题数：3，分数：6.00)31.冒泡排序算法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法。【吉林大学 2001 二、3(9 分)】【北京邮电大学 1992 六(10 分)】（分数：2.00）_正确答案：(正确答案：本题是双向起泡排序，重点是每次起泡的上下界，核心语句
12、段如下： change=1；low=0；high=n-1； 冒泡的上下界 while(lowlow；i 一一) 气泡下沉，小元素上浮(向左) if(a(inext 是向下起泡的开始结点，一趟起泡排序将最大元素下沉到链表尾；再设 tail 是向上起泡的开始结点，初始 tail=null。在第一个最大元素沉到链表尾时，tail 取链表倒数第二个结点的指针的值，这时向上起泡，得到最小值。如此下去，直到 head 等于 tail 或无交换为止，排序结束。核心语句段如下： exchange=1； tail=null； tail是双向链表尾，算法过程中是向上起泡的开始结点 while(exchange)
13、fp=head 一next； P 是工作指针，指向当前结点 exchange=0； 假定本趟无交换 while(p 一next!=tail) 向下(右)起泡，一趟有一最大元素沉底 if(p 一datap 一next 一data) 交换两结点指针，涉及 6 条链 (temp=p 一next；exchange=1； 有交换 P 一next=temp 一next；temp 一next 一prior=p 先将结点从链表上摘下 temp 一next=p； P 一prior 一next=temp； 将 temp 插到 P 结点前 temp 一prior=p 一prior；P 一prior=temp； else p=p 一next； 无交换，指针后移 tail=p； 准备向上起泡 p=tail 一prior； while(exchange&P 一prior!=head) 向上起泡，一趟有一最小元素冒出 head=P；准备向下起泡 while(exchange)解析：33.请编写直接插入排序算法。【北京工商大学 1998 七(10 分)】（分数：2.00）_正确答案：(正确答案：假定第 1 个元素有序，从第 2 个元素起，依次插入前面有序子文件中。核心语句如下： for(i：2；i解析：
