发布时间 : 星期四 文章数据结构考研试题精选及答案第10章 排序更新完毕开始阅读f23476232f60ddccda38a060
[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 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 {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 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．利用比较的方法进行排序，在最坏的情况下，能达到的最好时间复杂性是什么？请给出详细证明。 【上海交通大学 2000 六 （8分）】 7．以下概念的区别：拓扑排序与冒泡排序。 【大连海事大学 1996 三、 2（3） (2分)】 8．简述直接插入排序，简单选择排序，2-路归并排序的基本思想以及在时间复杂度和排序稳定性上的差别。 【西北工业大学 1999 二 (8分)】 9．快速排序，堆排序和希尔排序是时间性能较好的排序方法，也是稳定的排序方法。判断正误并改错。 【燕山大学 1998 二、5 （2分）】 10. 设LS是一个线性表，LS=(a1,a2,?,an),若采用顺序存储结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是多少？若元素插在ai与ai+1之间(0<=i<=n-1)的概率为(n-i)/(n*(n+1)/2)，则插入一个元素需要平均移动的元素个数又是多少？【西安电子科技大学 2001软件 二、3 （5分）】 11．对于堆积排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？若仅考虑排序结果的稳定性，则应该选取其中哪种方法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？【北京航空航天大学 1998 一、10 （4分）】 12． 在堆排序、快速排序和合并排序中： 【吉林大学 2001 一、5 (6分)】 (1)．若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选 取哪种排序方法？ (2)．若只从排序结果的稳定性考虑，则应选取哪种排序方法？ (3)．若只从平均情况下排序最快考虑，则应选取哪种排序方法？ (4)．若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ 13. 快排序、堆排序、合并排序、Shell排序中哪种排序平均比较次数最少，哪种排序占用空间最多，哪几种排序算法是不稳定的？ 【首都经贸大学 1997 一、3 （4分）】 14．欲求前k个最大元素，用什么分类方法好？为什么？什么是稳定分类？分别指出下列算法是否是稳定分类算法，或易于改成稳定分类算法？ A． 插入分类 B．快速分类 C．合并分类 D．堆分类 E．基数分类【东南大学 1994 一、3 （8分）】 15．考虑由三个不同关键词构成的序列：｛a,b,c｝，试画出直接插入排序算法的二叉判定树。 【吉林大学 2001 一、3 (4分)】 16. 请阅读下列算法，回答问题 PROCEDURE sort（r，n） BEGIN FOR i:=2 TO n DO BEGIN x:=r(i)；r(O):=x；j:=i-1； WHILE x.key r(j+1):=r(j); j:=j-1 END; r(j+1):=x END END; 问题一：这是什么类型的排序算法，该排序算法稳定吗？ 问题二：设置r(O)的作用是什么？若将WHILE—DO 语句中判断条件改为x.key<=r(j).KEY,