排列次序__________。
【南京理工大学 1997 三、5 （2分）】
13．从平均时间性能而言，__________排序最佳。【青岛大学 2001 六、5 （3分）】
14．对于7个元素的集合{1，2，3，4，5，6，7}进行快速排序，具有最小比较和交换次数的初始排列次序为_____。【长沙铁道学院 1997 二、1 (2分)】 15．快速排序在_____的情况下最易发挥其长处。【长沙铁道学院 1998 二、5 (2分)】 类似本题的另外叙述有：
(1)快速排序法在_____情况下最不利于发挥其长处，在_____情况下最易发挥其长处。
【山东大学 2001 三、5 (2分)】 16．在数据表有序时，快速排序算法的时间复杂度是____。【合肥工业大学 2001 三、10 （2分）】
17．堆排序的算法时间复杂度为：_____。【合肥工业大学 1999 三、10 （2分）】 18．PROC sift(VAR r：listtype;k,m:integer); {假设r[k+1..m]中各元素满足堆的性质，本算法调整r[k]使整个序列r[k..m]中各元素
满足堆的性质。}
i:=k; j:= (1)__; x:=r[k].key; finished:=false; t:=r[k]; WHILE (j<=m) AND NOT finished DO [IF(j ELSE [r[i]:= (4)___; i:=j; j:= (5)____] ]; r[i]:=t; ENDP;{sift} 【燕山大学 1998 四、2 （15分）】 19．设n为结点个数，datatype为结点信息类型。为了进行堆排序，定义： TYPE node=RECORD key：integer；info：datatype END； VAR heap：ARRAY[1..n] OF node l，r，i，j：0..n ;x：node； 在下面的算法描述中填入正确的内容，使其实现1964年Floyd提出的建堆筛选法，要求堆建成后便找到了最小的关键码。 筛选算法sift(l,r,heap)： 步1．[准备] i←l; j ←(1)___; x←heap[i] 步2．[过筛] 循环：当(2)____时反复执行 ⑴．若j ⑵．若(4)___则heap[i]←heap[j]; (5)____; (6)____ 否则跳出循环 步3.[结束] heap[i] ← (7)____ 【山东工业大学 1996 三、2 （7分）】 20．以下程序的功能是利用堆进行排序。请在空白处填上适当语句，使程序完整。 PROCEDURE sift(VAR r:arr;k,m:integer); VAR i,j,x:integer; t:rec; finished:boolean; BEGIN i:=k; (1)___; x:=r[i].key; (2)___; t:=r[k]; WHILE (j<=m) AND NOT finished DO BEGIN IF (j IF x<=r[j].key THEN finished:=true ELSE BEGIN(4)____; (5)____; (6)____END; END; (7)___ END; PROCEDURE heapsort(VAR r:arr); VAR i:integer; x:rec; BEGIN FOR i:=n DIV 2 DOWNTO 1 DO (8)___; FOR i:=n DOWNTO 2 DO BEGIN x:=r[1]; (9)___; r[i]:=x; (10)___ END; END; 【北方交通大学 2000 四 （20分）】 21．堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆__________。 ①16，72，31，23，94，53 ②94，53，31，72，16，23 ③16，53，23，94，31，72 ④16，31，23，94，53，72 ⑤94，31，53，23，16，72 堆排序是一种_(1)_类型的排序，它的一个基本问题是如何建堆，常用的建堆算法是1964年Floyd提出的_(2)_，对含有n个元素的序列进行排序时,堆排序的时间复杂度是_(3)_，所需要的附加结点是_(4)_。 【山东工业大学 1994 一、2 （5分）】 22．堆是一种有用的数据结构. 堆排序是一种_(1)_排序，堆实质上是一棵_(2)_结点的层次序列。对含有N个元素的序列进行排序时，堆排序的时间复杂度是_(3)_，所需的附加存储结点是_(4)_。关键码序列05，23，16，68，94，72，71，73是否满足堆的性质_(5)_。 【山东工业大学 1996 三、1 （5分）】 23．将如下的堆排序算法补写完整。说明如下： TYPE heaptype=ARRAY[1..n]OF integer； 过程heapsort的功能是将数组h中的前n个记录按关键字递减的次序排序。heapsort调用过程sift时的参数h，k，r有如下定义：以 h[k+1]，h[k+2]，?,h[r]为根的子树已经是堆；执行sift后，以h[k]，h[k+1],h[k+2],?,h[r] 为根的子树都成为堆。 PROC sift（VAR h：heaptype；k，r：integer）； VAR i，j，x：integer；finish：boolean； BEGIN i:=k；x:=h[i]；j:=2*j； ((1)____); WHILE (j<=r) AND NOT finish DO [IF (j END; PROC heapsort(VAR h:heaptype; n:integer); VAR k,r,i,j:integer; BEGIN FOR k:=n DIV 2 DOWNTO 1 DO sift ((4)____) ; FOR r:=n DOWNTO 2 DO [x:=h[1]; h[1]:=h[r]; h[r]:=x; ((5)____) ] END; 【北京工业大学 1997 五、2 (16分)】 24．设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按2路归并排序方法对该序列进行一趟扫描后的结果_______。 【北方交通大学 2001 二、7】 25. 阅读下列程序说明和PASCAL程序，把应填入其中______处的字句写在答题纸上。程序说明： 本题给出的是将数组a的元素a1，a2,?,an从大到小排序的子程序。子程序采用改进的选择排序方法，该方法基于以下思想： 在选择第一大元过程中, a1与aj(j=n,n-1,?,2)逐个比较，若发现aj1>a1，则aj1与a1变换，变换后新的aj1有性质aj1≥at(j1 设程序包含有常量和类型定义： CONST maxn=1000; TYPE vector=ARRAY[1..maxn] OF integer; index= 1..maxn; PROCEDURE sort(VAR a:vector;n:index) VAR p:vector; i,j,k,m,t:integer; BEGIN k:=0; i:=1; m:=n; WHILE i FOR j:=m DOWNTO i+1 DO IF a[i] BEGIN t:=a[i]; a[i]:=a[j]; a[j]:=t; k:=k+1;（(1)____）END; REPEAT（(2)____）; IF（(3)____）THEN（(4)____） ELSE BEGIN m:=p[k]; k:=k-1; END; UNTIL (i IF （(5)___） BEGIN t:=a[i];（(6)____）;（(7)____）END END END; 【上海海运学院 1997 七（14分）】 26．下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i,将a[i]和a[i+1]进行比较,第二趟对所有偶数的i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>a[i+1],将二者交换;以后重复上述二趟过程,直至整个数组有序。 程序.(a) PROCEDURE oesort(VAR a:ARRAY[1..n] OF integer); VAR flag:boolean; i,t:integer; BEGIN REPEAT flag:=false; FOR i:=1 TO n step 2 DO IF(a[i]>a[i+1]) THEN [flag:= (1)____; t:=a[i+1]; a[i+1]:=a[i]; (2)____] FOR i:= (3)____ DO IF (a[i]>a[i+1]) THEN [flag:= (4)____ ; t:=a[i+1];a[i+1]:=a[i]; a[i]:=t;] UNTIL (5)___ ; END; 程序（b） void oesort (int a[n]) {int flag,i,t; do {flag=0; for(i=1;i if(a[i]>a[i+1]) {flag=(1)__; t=a[i+1]; a[i+1]=a[i]; (2)____;} for (3)____ if (a[i]>a[i+1]) {flag=(4)____;t=a[i+1]; a[i+1]=a[i]; a[i]=t;} }while (5)_; } 【上海大学 2000 一、1 （10分）】 27．关键码序列（ Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_____；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。 【北京大学 1997 一、4 （4分）】 类似本题的另外叙述有： (1)设有字符序列Q、H、C、Y、P、A、M、S、R、D、F、X要求按字符升序排序，采用初始步长为４的希尔（shell）排序，一趟扫描的结果是____;采用以首元素为分界元素的快速排序，一趟扫描的结果是_____。 【北京工业大学 1999 一、7 (8分)】 28．外部排序的基本方法是归并排序，但在之前必须先生成___。【北京邮电大学2001 二、6（2分）】 29．磁盘排序过程主要是先生成 ，然后对 合并，而提高排序速度很重要的是 ，我们将采用 方法来提高排序速度。 【山东工业大学 1995 一、4（4分）】 30．设输入的关键字满足k1>k2>?>kn，缓冲区大小为m，用置换-选择排序方法可产生____个初始归并段。 【武汉大学 2000 一、9】 31．下面是一改进了的快速排序算法，请填空并简要说明支持improveqsort递归所需要的最大栈空间用量。 PROCEDURE improveqsort(VAR list:afile;m,n:integer); {设list[m].key<=list[n+1].key} VAR i,j,k:integer; BEGIN WHILE m i:=m; j:=n+1; k:=list[m].key; REPEAT REPEAT i:=i+1 UNTIL list[i].key>=k; REPEAT j:=j-1 UNTIL list[j].key<=k; IF i UNTIL i>=j; interchange(list[m],list[j]); IF n-j>=j-m THEN BEGIN improveqsort(list, (1)____); (2)____; END ELSE BEGIN improveqsort(list, (3)____); (4)____; END END; {OF WHILE} END; 【东南大学 2001 五（10分）】 四、应用题 1. 内部排序（名词解释）。 【燕山大学 1999 一、5 （2分）】 2. 在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。【大连海事大学 1996 七、3 (４分)】 类似本题的另外叙述有： (1) 举例说明堆排序是否为稳定排序法. 【西安电子科技大学 1996 三、4 （5分）】 (2) 选择排序算法是否稳定？为什么？ 【燕山大学 2001 三、3 （5分）】 (3) 举例分析堆排序方法是否稳定。 【北京邮电大学 1993 二、3 （6分）】 (4) 堆排序是稳定排序吗？举例说明。 【东南大学 1996 一、5 （6分）】 (5) 试举例分析堆排序法是否稳定。 【东南大学 1999 一、5 （5分）】 (6) 树型选择排序通常采用顺序存储结构，①试指出n个元素的原始序列一般如何在该存储结构中存放（起始存储位置，次序），请说明理由。②讨论树形选择排序的稳定性。若稳定，须说明理由；不稳定，须举反例，并尝试找出使它稳定的方法。【北京工业大学 1999 七 (10分)】 3．在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？ 【燕山大学 2001 三、4 （5分）】 4．设有5个互不相同的元素a、b、c、d、e，能否通过7次比较就将其排好序？如果能，请列出其比较过程；如果不能，则说明原因。 【北方交通大学 1996 五（10分）】 5．对一个由n个关键字不同的记录构成的序列，能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录？请说明如何实现？在最坏的情况下至少进行多少次比较？ 【东南大学 2000 一、5 （8分）】 6．利用比较的方法进行排序，在最坏的情况下，能达到的最好时间复杂性是什么？请给出详细证明。