发布时间 : 星期四 文章数据结构考研试题精选及答案第10章 排序更新完毕开始阅读f23476232f60ddccda38a060
该算法将会有什么变化，是否还能正确工作？【上海海运学院 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); {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．现有一文件Ｆ含有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) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 (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分）】 类似本题的另外叙述有： (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 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