数据结构1800试题-第10章 排序 下载本文

我下vip免费资源网 www.woxia.net 该算法将会有什么变化,是否还能正确工作?【上海海运学院 1998 六 (10分)】 17.下面是冒泡排序算法,请阅读并完成该程序,并回答以下问题:

PROCEDURE bubblesort (r,n) BEGIN

i:=1; m:=n-1; flag:=1;

WHILE (i<=(1)___)AND(flag=(2)____) DO BEGIN

flag:= (3)___; FOR j:=1 TO m DO

IF r[j].key>r[j+1].key THEN

BEGIN flag:= (4)___; t:=r[j]; r[j]:=r[j+1]; r[j+1]:=t END; i:=i+1;m:=m-1

END; END.

(1) 请在上面横线上填上适当的语句,完成该算法程序。 (2) 设计标志flag的作用是什么?

(3) 该算法结点的最大比较次数和最大移动次数是多少?

(4) 该分类算法稳定吗? 【上海海运学院 1996 六(12分) 1999 六(16分)】 18.仔细阅读下面的过程,并回答有关的问题

PROCEDURE unknownname(VAR A:array[1..500] OF integer;n:integer); VAR i,j,x:integer; b:boolean; BEGIN

b:=true; i:=1;

WHILE (i

b:=false;

FOR j:=1 TO(1)___DO IF(2)___

THEN BEGIN

x:=A[j]; A[j]:=A[j+1]; A[j+1]:=x; (3)___ END; i:=i+1; END

END; 【西安电子科技大学 2001计应用 六 (14分)】

(1) 在 中填上正确的语句,使该过程能完成预期的功能。 (2) 该过程使用的是什么排序方法?

(3) 当数组A的元素初始时已按值递增排序,该过程执行中会进行多少次比较?多少次交换?

(4) 当数组A的元素初始时已按值递减排序,该过程执行中会进行多少次比较?多少次交换?

19.写出下列排序算法的基本思想,并写出对序列(23,12,35,47,16,25,36,19,21,16)进行排序时每一趟的结果。

PROC bbsort(VAR r: sequence; n: integer);

我下vip免费资源网 www.woxia.net {r是一个数组}

d:=1; pos[-1]:=1; pos[1]:=n; i:=1; exchanged:= true; WHILE exchanged DO [ exchanged:= false; WHILE i<>pos[d] DO

[IF (r[i]-r[i+d])*d>0 THEN [r[i]与r[i+d]交换;

exchanged:=true;];

i:=i+d; ]

pos[d]:=pos[d]-d; i:=pos[d]; d:=-d; ]

ENDP; 【山东科技大学 2002 五 (12分)】

20.设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最大。

【南京航空航天大学 1996 九、1 (4分)】

21.设与记录R1,R2,?,Rn对应的关键词分别是K1,K2,?,Kn。如果存在Ri和Rj使得j

22.现有一文件F含有1000个记录,其中只有少量记录次序不对,且它们距离正确位置不远;如果以比较和移动次数作为度量,那末将其排序最好采用什么方法?为什么?【北方交通大学 1997 四(8分)】 23.分析下面排序算法中各带标号语句的频度及此算法的时间复杂度,并指出该算法是属于哪一种排序方法。 【北京邮电大学 1996 一、2 (7分)】 PROCEDURE sort (VAR a: ARRAY [1..n] OF integer); BEGIN

1 FOR i:=1 TO n-1 DO 2 [j:=i;

3 FOR k:=j+1 TO n DO 4 IF a[k]

] END;

24. 设待排序的关键码分别为28,13,72,85,39,41,6,20。按二分法插入排序算法已使前七个记录有序,中间结果如下: 【山东工业大学 1996 七 (10分)】

6 13 28 39 41 72 85 20

i=1 m=4 r=7 试在此基础上,沿用上述表达方式,给出继续采用二分法插入第八个记录的比较过程。 (1) 使用二分法插入排序所要进行的比较次数,是否与待排序的记录的初始状态有关? (2) 在一些特殊情况下,二分法插入排序比直接插入排序要执行更多的比较。这句话对吗?

25.算法模拟(15分,问题1,2各6分,问题3占3分) 设待排序的记录共7个,排序码分别为8,3,2,5,9,1,6。

(1) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。

我下vip免费资源网 www.woxia.net (2) 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。

(3) 直接插入排序算法和直接选择排序算法的稳定性如何?【山东工业大学 1997 四 (15分)】

26.在执行某个排序算法过程中,出现了排序关键字朝着最终排序序列相反的方向的移动,从而认为该算法是不稳定的。这种说法对么?为什么? 【东北大学 2001 一、1( 4分)】 类似本题的另外叙述有: (1) (冒泡)排序过程中,有的关键字在某趟排序中可能朝着与最终排序相反的方向移动,试举例说明之。快速排序过程中有没有这种现象? 【东北大学 2000 一 、5 (4分)】 27. 对下面数据表,写出采用SHELL排序算法排序的每一趟的结果,并标出数据移动情况。(125,11,22, 34,15,44,76,66,100,8,14,20,2,5,1)。【合肥工业大学 1999 四、4 (5分)】

28.快速排序的最大递归深度是多少?最小递归深度是多少?【清华大学 1999 一、1 (2分)】

29. 已知某文件的记录关键字集为{50,10,50,40,45,85,80},选择一种从平均性能而言是最佳的排序方法进行排序,且说明其稳定性。【西安电子科技大学 1996 五 (10分)】 30. 在内排序算法中,待排序的数据已基本有序时,花费时间反而最多的排序方法是哪种?

【西安电子科技大学 2000计应用 一、1 (5分)】

31.我们知道,对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: 【西安电子科技大学 2001计应用 五(12分)】【中国矿业大学 2000 六 (10分)】

(1) 当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2) 当n=7时,给出一个最好情况的初始排序的实例。

(3) 当n=7时,在最坏情况下需进行多少次比较?请说明理由。 (4) 当n=7时,给出一个最坏情况的初始排序的实例。 类似本题的另外叙述有:

(1) 快速排序(quick sorting)的效率与原始序列有关,现用快速排序算法对关键字分别为1—15的15 个元素进行排序

① 在最好情况下要进行几遍比较,给出一种原始序列实例; ② 在最坏情况下要进行几遍比较,给出一种原始序列实例。【浙江大学 1995 七(12分)】

(2) 对N个元素组成的线性表进行快速排序时,所需进行的比较次数依赖于这N个元素的初始排列。对N=7,给出快速排序的一个最好情况的初始排列实例(7个元素可取自集合{l,2,3,4,5,6,7})。

【西北大学 2000 二、5(5分)】 32.有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下, 则该排序方法是什么? 【武汉交通科技大学 1996 二、5 (6分)】

初 始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84 第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,84 33.快速排序是在所有情况下,排序速度最快吗?为什么?在何种情况下使用此排序法最好?

【北京邮电大学 1993 一、1 (5分)】

34.对给定文件(28,07,39,10,65,14,61,17,50,21)选择第一个元素28进行划分,写出其快速排序第一遍的排序过程。【厦门大学 1998 七、1 (8分)】

我下vip免费资源网 www.woxia.net 类似本题的另外叙述有:

(1) 对下列关键字序列进行快速排序(从小至大) (48, 38, 65, 95, 73, 13, 27, 50)要求给出快速排序的算法思想,并画出排序过程示意图。 【南京航空航天大学 1999 五 (10分)】

(2) 设记录的关键字集合K={23,9,39,5,68,12,62,48,33},给定的增量序列D={4,2,1},请写出对K按“SHELL方法”排序时各趟排序结束时的结果;若每次以表的第一元素为基准(或枢轴),写出对K按“快速排序方法”排序时,各趟排序结束时的结果。 【北京科技大学 1999 七(10分) 2000 七(10分)】 35.下面是一改进了的快速分类算法

1. PROCEDURE qsort1(VAR list:afile;m,n:integer); 2 (设list[m].key

5 WHILE m

7 i:=m;j:=n+1; k:=list[m].key; 8 REPEAT

9 REPEAT i:=i+1 UNTIL list[i].key>=k; 10 REPEAT j:=j-1 UNTIL list[j].key<=k;

11 IF i=j;

13 interchange( list[m],list[j]);

14 IF n-j>=j-m

15 THEN BEGIN qsort1(list,m,j+1);m:=j+1;END 16 ELSE BEGIN qsort1(list,j+1,n);n:=j-1;END 17 END;(OF WHILE) 18 END. 问:

(1) 将第9、10行中的>=,<=分别改成>,<行吗?为什么? (5分) (2) 该排序算法稳定否?举例说明 (5分)

(3) 对输入文件(22,3,30,4,60,11,58,18,40,16),列表表示该文件在每次调用qsort1时的状态及相应m、n值。(5分)

(4) 若输入文件有n个记录,简要说明支持qsort1递归所需最大栈空间用量(设一层递归用一个单位栈空间)。(5分) 【东南大学 1998 四 (20分)】

36.如果只要找出一个具有n个元素的集合的第k(1≤k≤n)个最小元素,你所学过的排序方法中哪种最适合?给出实现的思想。【北方交通大学 1998 六 (10分)】 37.已知快速排序和归并排序的算法分别如下所示:

PROCEDURE qksort(VAR r:listtype; s,t:integer); BEGIN

IF s

qkpass(r,s,t,k); qksort(r,s,k-1);

qksortd(r,k+1,t)

END