56. 归并排序中，归并的趟数是( )。【南京理工大学 2000 一、19（1.5分）】 A．O（n） B．O(logn) C．O(nlogn) D．O(n*n) 类似本题的另外叙述有：
(1)归并排序的时间复杂性是（ ）。 【中山大学 1999 一、12】 A.O（N*N） B. O（N） C. O（N*LOG（N）） D. O（LOG（N）） 57． 在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该
项的位置叫( ) A．插入排序 B．枚举排序 C．选择排序 D．交换排序【北京邮电大学 2000 二、6 （20/8分）】 58．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是 （ ）
A．堆排序〈 快速排序〈归并排序 B．堆排序〈 归并排序〈 快速排序 C．堆排序〉 归并排序 〉快速排序 D．堆排序 > 快速排序 > 归并排序 E．以上答案都不对 【西安交通大学 1996 三、1 (3分)】 59．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法， 而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 【北方交通大学 1999 一、3 （5分）】 （1）--（5）: A．选择排序 B．快速排序 C．插入排序 D．起泡排序
E．归并排序 F．shell排序 G．堆排序 H．基数排序
类似本题的另外叙述有：
（1）排序的方法有很多种，（ ）法从未排序的序列中依次取出元素与已排序序列中的元素比较，将其放在已排序序列的正确位置上；（ ）法从未排序序列中挑选元素，并将其依次放入已排序序列的一端；交换排序法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换。（ ）和（ ）是基于这类方法的两种排序方法，而 ( )是比( )效率更高的方法。供选择的答案：
A. 快速排序 B. 选择排序 C. 归并排序 D．冒泡排序 E．直接插入排序
【山东大学 1998 三、2 (5分)】 【山东工业大学 2000 三、2 （7分）】 60．设要将序列（q,h,c,y,p,a,m,s,r,d,f,x） 中的关键码按字母升序重新排序，
（1）（ ）是初始步长为4的shell排序一趟扫描的结果； （2）（ ）是对排序初始建堆的结果；
（3）（ ）是以第一个元素为分界元素的快速一趟扫描的结果。
从下面供选择的答案中选出正确答案填入括号内。 【厦门大学 2000 六、3 （16%/3分）】
A. f ,h ,c ,d ,p ,a ,m ,q ,r ,s ,y ,x B. p ,a ,c ,s ,q ,d ,f ,x ,r ,h ,m ,y
C. a ,d ,c ,r ,f ,q ,m ,s ,y ,p ,h ,x D. h ,c ,q ,p ,a ,m ,s ,r ,d ,f ,x ,y E. h ,q ,c ,y ,a ,p ,m ,s ,d ,r ,f ,x 类似本题的另外叙述有：
（1）在内排序的过程中,通常需要对待排序的关键码进行多编扫描,采用不同重新排序方法,会产生不同的排序中间结果。设要将序列
【上海海运学院 1997 二、3 （5分）】
1-5:A. f,h,c,d,p,a,m,q,r,s,y,x B. p,a,c,s,q,d,f,x,r,h,m,y C. a,d,c,r,f,q,m,s,y,p,h,x
D. h,c,q,p,a,m,s,r,d,f,x,y E. h,q,c,y,a,p,m,s,d,r,f,x
61．对由n个记录所组成的表按关键码排序时,下列各个常用排序算法的平均比较次数分别是:二路归并排序为( 1 ),直接插入排序为( 2 ),快速排序为( 3 ),其中,归并排序和快速排序所需要的辅助存储分别是( 4 )和( 5 )。 【上海海运学院 1998 二、4 （5分）】
22
1-5:A. O(1) B. O（nlog2n） C. O（n） D. O（n） E. O（n(log2n)） F. O（log2n） 62．将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是( ) A．N B．2N-1 C．2N D．N-1
【中科院计算所 1998 二、7 （2分）】 【中国科技大学 1998 二、7 （2分）】 63. 基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（ ）。 A. O(nlogn) B. O(logn) C. O(n) D. O(n*n) 【南京理工大学 1996 一、2 （2分）】 64．已知待排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。
A. O(nlog2n) B. O(nlog2k) C. O(klog2n) D. O(klog2k) 【中国科技大学 1998 二、9 （2分）】
类似本题的另外叙述有：
(1)已知待排序的N个元素可分为N/K个组，每个组包含K个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( ) A. O(klog2k) B. O(klog2n) C. O(nlog2k) D. O(nlog2n) 【中科院计算所 1998 二、9 （2分）】
65．采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k （ ） A． 有关 B．无关 【北京工业大学 2000 一 、2 (3分)】
66．采用败者树进行K路平衡归并时，总的（包括访外）归并效率与K（ ）。
A．有关 B．无关 【北京工业大学 2001 一、4 (2分)】
二、判断题：
1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（ ）【长沙铁道学院 1998 一、10 (1分)】 2．内排序要求数据一定要以顺序方式存储。 （ ）【南京理工大学 1997 二、2（2分）】 3．排序算法中的比较次数与初始元素序列的排列无关。（）【南京航空航天大学 1997 一、8 （1分）】 4．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ） 【南京航空航天大学 1996 六、9 （1分）】
5．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）【上海交通大学 1998 一、18】 6．直接选择排序算法在最好情况下的时间复杂度为O（N）。（ ）【合肥工业大学 2001 二、10（1分）】 7．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（【）上海交通大学 1998 一、15】
8．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。（ ） 【合肥工业大学 2000 二、9（1分）】
9．在待排数据基本有序的情况下，快速排序效果最好。（ ）【南京理工大学 1997 二、4（2分）】
10．当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（ ）
【上海交通大学 1998 一、16】
11．快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（ ） 【北京邮电大学 1998 一、7 （2分）】 12．堆肯定是一棵平衡二叉树。（ ）【南京航空航天大学 1997 一、6 （1分）】 13．堆是满二叉树。（ ）【南京航空航天大学 1996 六、6 （1分）】
14．（101，88，46，70，34，39，45，58，66，10）是堆。（ ）【北京邮电大学 1999 二、1 （2分）】
15．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ） 【合肥工业大学 2000 二、10（1分）】
16．堆排序是稳定的排序方法。（ ）【上海交通大学 1998 一、19】
17．归并排序辅助存储为O（1）。（ ）【青岛大学 2000 四、9（1分）】 18．在分配排序时，最高位优先分配法比最低位优先分配法简单。（ ）【上海交通大学 1998 一、20】
19． 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。 （ ）
【上海海运学院 1997 一、9（1分）】 20．交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是O（n*n） ，而快速排序算法的最坏时间复杂性是O（nlog2n）；所以快速排序比冒泡排序效率更高。（ ）
【上海海运学院 1998 一、10 （1分）】【上海海运学院 1995 一、10（1分）】 21．快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。（ ） 【上海海运学院1996一、9（1分）】
22．在任何情况下，归并排序都比简单插入排序快。（ ）【北京邮电大学 2000 一、4 （1分）】 23．归并排序在任何情况下都比所有简单排序速度快。（ ）【北京邮电大学 2002 一、9（1分）】 24．快速排序总比简单排序快。（ ）【东南大学 2001 一、9 （1分）】
25. 中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（ ） 【中山大学 1994 一、4 （2分）】
26．外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。( )【北京邮电大学 1998 一、8 （2分）】 27．在外部排序时，利用选择树方法在能容纳m个记录的内存缓冲区中产生的初始归并段的平均长度为2m个记录。( )【上海海运学院 1999 一、10（1分）】 28．为提高在外排序过程中，对长度为N的初始序列进行“置换—选择”排序时，可以得到的最大初始有序段的长度不超过N/2。( )
29．排序速度，进行外排序时，必须选用最快的内排序算法。( )
30．在完成外排序过程中，每个记录的I/O次数必定相等。( )【大连海事大学 2001 一、20 (每题1分)】 31．影响外排序的时间因素主要是内存与外设交换信息的总次数。( )【东北大学 1997 二、5 (2分)】 三、填空题
1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。
【北京邮电大学 2001 二、7 （4分）】 2. 外排序的基本操作过程是_______和_______。【西安电子科技大学 1998 二、3 （3分）】
类似本题的另外叙述有： （1）外部排序中两个相对独立的阶段是___和___。【西安电子科技大学 1999软件 一、8 （2分）】
3. 属于不稳定排序的有__________。【青岛大学 2002 三、5 （2分）】
4．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。【福州大学 1998 二、10 (2分)】 类似本题的另外叙述有：
（1）设表中元素的初始状态是按健值递增的，分别用堆排序，快速排序，冒泡排序和归并排序方法对其进行排序（按递增顺序）， __排序最省时间，__排序最费时间。【厦门大学 2001 一、5 （14%/5分）】
5. 不受待排序初始序列的影响，时间复杂度为O(N)的排序算法是_____，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_____。【中国人民大学 2001 一、3 （2分）】
6．直接插入排序用监视哨的作用是_______。【南京理工大学 2001 二、8 （2分）】 7．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。
【华中理工大学 2000 一、10 （1分）】 8. 用链表表示的数据的简单选择排序，结点的域为数据域data ，指针域 next ；链表首指针为head ，链表无头结点。 selectsort(head) p=head;
while (p(1)_______) {q=p; r=(2)_______ while((3)______ )
{if ((4)_______ ) q=r;
r=(5)_______ ;
}
tmp=q->data; q->data=p->data; p->data=tmp; p= (6)_______ ; } 【南京理工大学 2000 三、2 （6分）】
9．下面的c函数实现对链表head进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式： #include
typedef struct node {char data; struct node *link; }node; node *select(node *head) {node *p,*q,*r,*s;
p=(node *)malloc(sizeof(node));
2
p->link=head; head=p;
while(p->link!=null) {q=p->link; r=p; while ((1)____)
{ if (q->link->data
}
if ((2)____) {s=r->link; r->link=s->link; s->link= ((3)_____); ((4)_____);} ((5)____) ; }
p=head; head=head->link; free(p); return(head); } 【复旦大学 1999 六（15分）】
10．下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，?,依次下去，直到待排序列为递增序。（注：<-->）代表两个变量的数据交换）。
void sort(SqList &r,int n) { i=1;
while((1)__) { min=max=1;
for (j=i+1;(2)____ ;++j)
{if((3)____) min=j; else if(r[j].key>r[max].key) max=j; }
if((4)_____) r[min] < ---- >r[j];
if(max!=n-i+1){if ((5)___) r[min] < ---- > r[n-i+1]; else ((6)__); } i++; }
}//sort 【南京理工大学 2001 三、2 （10分）】
11．表插入排序的基本思想是在结点中设一指针字段，插入Ri时Rl到Ri-1己经用指针按排序码不减次序链结起夹，这时采用顺序比较的方法找到Ri应插入的位置，做链表插入。如此反复，直到把Rn插入为止。 （1）(6分)请完成下列表插人的算法；【山东工业大学 2000 五（16分）】【山东大学 1998 五】
①. R[0].LINK←(1)___; R[N].LINK←(2)___;
②. 循环，I以-1为步长，从(3)___到(4)___执行 （1）P← R[0].LINK; Q← 0
（2）循环，当P>0且(5)__ 时，反复执行 Q←P； P←(6)___
（3）R[Q].LINK←I; R[I].LINK←P
（2）(2分) 表插入排序的最大比较次数是(7)__； （3）（2分）表插入排序的最小比较次数是(8)__； （4）（2分）记录移动的次数是(9)__； （5）（2分）需要附加的存储空间是(10)__；
（6）（2分）该排序算法是否是稳定的(11)____。
12. 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需__________趟，写出第一趟结束后，数组中数据的