1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 6 及答案与解析一、单项选择题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 分)】（
2、A）3（B） 10（C） 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）1（B） 4（C） 3 （D）26 快速排序在最坏情况下的时间复杂度与下列哪个算法最坏情况下的时间复杂度相同?
3、 ( ) 。【北京交通大学 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(n2)（C） O(nlog2n)（D）O(log 2n)9 对下列关键字序列用快速排序法进行排序时，速度最快的情形是( )。【北方交通大学 2001 一、18(2 分)】（A）21 ，25 ，5，
4、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，3010 对 n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是( )。【北方交通大学 2000 二、5(2 分)】（A）每次分区后，先处理较短的部分（B）每次分区后，先处理较长的部分（C）与算法每次分区后的处理顺序无关（D）以上三者都不对11 快速排序在最坏情况下的时间复杂度是( )，比( )的性能差。【山东工业大学1995 二、2(4 分) 】（A）O(NlogN)（B） O(N2)（C） O(N2)（D）堆排序（E）冒泡排
5、序12 当 n 个整型数据是有序时，对这 n 个数据用快速排序算法排序，则时间复杂度是(1)，当用递归算法求 n!时，算法的时间复杂度是(2)，则：(1) 一(2)=( )。【南京理工大学 1 999 一、(67)(4 分) 】（A）O(n)（B） O(nlogn)（C） O)(n*n)（D）O(logn)13 对各种内部排序方法来说( )。【华南理工大学 2006 一、3(2 分)】（A）快速排序时间性能最佳（B）基数排序和归并排序是稳定的排序方法（C）快速排序是一种选择排序（D）堆排序所用的辅助空间比较大14 在含有 n 个关键字的小根堆(堆顶元素最小)中，关键字最大的记录有可能存储在(
6、)位置上。 【中科院计算所 2000 一、4(2 分) 】（A）n 2 （B） n2 一 1（C） 1 （D）n 2+215 若对 n 个元素进行堆排序，则在初始建堆的过程中需要进行( )筛选。【北京理工大学 2005 一、5(1 分)】（A）1（B） n2（C） (n 一 1)2 （D）n二、填空题16 磁盘排序过程主要是先生成_，然后对_合并，而提高排序速度很重要的是_，我们将采用_方法来提高排序速度。【山东工业大学 1995 一、4(4 分)】17 在基于关键字比较且时间为 O(nlog2n)的排序中，若要求排序是稳定的，则可选用_ 排序；若要求就地排序(及辅助空间为 O(1)，则可选用
7、_排序。【中国科学技术大学 1998 一、7(2 分)】18 外排序的基本操作过程是_和_。【西安电子科技大学 1998二、3(3 分) 】19 外部排序的基本方法是归并排序，但在之前必须先生成_。【北京邮电大学 2001 二、6(2 分) 】20 设工作区的容量为 W，则置换一选择排序法所得到的初始归并段长度的期望值为_。【上海交通大学 2004 五、3(154 分)】21 下面的排序算法的思想是：第一趟比较将最小的元素放在 r1中，最大的元素放在 rn中，第二趟比较将次小的放在 r2中，将次大的放在 rn 一 1中，依次下去，直到待排序列为递增序。(注： 代表两个变量的数据交换 )。【南京
8、理工大学 2001 三、2(10 分) 】【中国海洋大学 2007 三(12 分)】void sort(SqListif(max!=n-i+1if(5) )rmin(一一r Ini+1；else(6)；i+； sort22 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。【北京交通大学 2005 七、3(6 分)#define n 10int sDlit(int ahi，int low，int high)int j，k，x；k=low：J=high；x=ak；while(k=x&k=0) (2) ；high=stacktop1；top 一一；k=split(a，low，high)
9、；if(lowrni+122 【正确答案】 (1)aj=ak (2)low=stacktop0(3)stacktop0=k+1三、判断题23 【正确答案】 B24 【正确答案】 A25 【正确答案】 A26 【正确答案】 A四、综合题27 【正确答案】 28 【正确答案】 对冒泡算法而言，初始序列为反序时交换次数最多。若要求从大到小排序，则表现为初始是上升序时交换次数最多。29 【正确答案】 证明：起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到一个最大值或最小值(视正向排序或反向排序而定)。由题假设知 Rj 在 Ri 之前且 KjKi，即说明 Rj 和 Ri 是反序；设
10、对于 Ri 之前全部记录R1R i-1(其中包括 Kj)中关键字最大为 Kmax，则 KmaxKi，故经过起泡排序前 i一 2 次比较后，R i-1 的关键字一定为 Kmax，又因 KmaxKiR i，故 Ri-1 和 Ri 为反序，由此可知 Ri-1 和 Ri 必定交换，证毕。30 【正确答案】 采用直接插入排序算法，因为记录序列已基本有序，直接插入排序比较次数少，且由于少量次序不对的记录与正确位置不远，使直接插入排序记录移动次数也相对较少，故选直接插入排序算法。五、设计题31 【正确答案】 本题是双向起泡排序，重点是每次起泡的上下界，核心语句段如下：change=1；low=0；high=
11、n-1； 冒泡的上下界while(lowai+1)(aiai+1；change=l ； 有交换，修改标志 changehigh-一； 修改上界for(i=high； ilow；i 一一) 气泡下沉，小元素上浮 (向左)if(a(iai 一 1； change=l ； 有交换，修改标志changelow+； 修改下界 while32 【正确答案】 设 head 是带头结点的双向链表的指针， head 一next 是向下起泡的开始结点，一趟起泡排序将最大元素下沉到链表尾；再设 tail 是向上起泡的开始结点，初始 tail=null。在第一个最大元素沉到链表尾时，tail 取链表倒数第二个结点的指
12、针的值，这时向上起泡，得到最小值。如此下去，直到 head 等于 tail 或无交换为止，排序结束。核心语句段如下：exchange=1； tail=null； tail 是双向链表尾，算法过程中是向上起泡的开始结点while(exchange)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；t
13、emp 一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 【正确答案】 假定第 1 个元素有序，从第 2 个元素起，依次插入前面有序子文件中。核心语句如下：for(i：2；i ：n；i+) 假定第一个记录有序R0=Ri；j=i 一 1； 将待排序记录放进监视哨while(R0keyRj key) 从后向前查找插入位置，同时向后移动记录(Rj+1=Rj；j=j 一 1；Rj+1=R0 将待排序记录放到合适位置
