2018-09-07 31页 doc 373KB 34阅读
is_225574
暂无简介
中的关键码按字母序的升序排列,则( 1 )是冒泡排序一趟扫描的结果,( 2 )是初始步长为4的希尔(SHELL)排序一趟扫描的结果,( 3 ) 是合并排序一趟扫描的结果,( 4 )是以第一个元素为分界元素的快速排序一趟扫描的结果,( 5 )是堆排序初始建堆的结果。供选择的答案: 【上海海运学院 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分)】 1-5:A. O(1) B. O(nlog2n) C. O(n) D. O(n2) E. O(n(log2n)2) 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(N2)的排序算法是_____,在排序算法的最后一趟开始之前,所有元素都可能不在其最终位置上的排序算法是_____。【中国人民大学 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进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式: #includetypedef struct node {char data; struct node *link; }node; node *select(node *head) {node *p,*q,*r,*s; p=(node *)malloc(sizeof(node)); p->link=head; head=p; while(p->link!=null) {q=p->link; r=p; while ((1)____) { if (q->link->data link->data) r=q; q=q->link; } 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则排序需__________趟,写出第一趟结束后,数组中数据的排列次序__________。 【南京理工大学 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 heap[j+1].key 则(3)____ ⑵.若(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 h[j+1]) THEN j:=j+1; IF x>h[j] THEN [(2)____ ] ELSE finish:=true; (3)____ ] 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 a1 (j2 j2>…>jk>1。有了这些下标,在确定第二大元时,可只考虑a2与aj (j=jk,jk-1,…,3) 逐个比较。倘若jk=2,则可不经比较就知道它是第二大元。在选择第二大元过程中,将与a2交换过的元素下标也标记下来,可供选择其他大元使用,但在选择第二大元时,应保证与a2交换的那些位置上的新值也都满足上述性质,依次类推,顺序选择第一,第二,…,第n-1大元,实现对a的排序。 设程序包含有常量和类型定义: 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 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 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要求按字符升序排序,采用初始步长为4的希尔(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 =k; REPEAT j:=j-1 UNTIL list[j].key<=k; IF 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 (4分)】 类似本题的另外叙述有: (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].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 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=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 >k,最好采用什么排序方法?为什么?如果有这样一个序列{59,11,26,34,17,91,25},得到的部分序列是:{11,17,25},对于该例使用所选择的方法实现时,共执行多少次比较?【东北大学 2002 一、4(3分)】 类似本题的另外叙述有: (1) 如果只想得到一个序列中第K个最小元素之前的部分排序序列,那么最好应采用哪种排序算法?为什么?如由这样一个序列:57, 40, 38, 11, 13, 34, 48, 75, 25, 6, 19, 9, 7 得到其第四个最小元素之前的部分排序序列:6,7,9,11,… 用你选用算法实现时,共执行多少次比较? 【北方交通大学 1994 七(16分)】 43.写出用堆排序算法对文件F=(12,3,15,30,9,28)进行排序时,初始堆及以后每挑好一个元素重新调整后堆的状态,并指出这里的堆和败者树的一个主要区别。【东南大学 1998 二(8分)】 44.请回答下列关于堆(Heap)的一些问题:【清华大学 2000 五 (12分)】 (1)(4分) 堆的存储表示是顺序的,还是链接的? (2)(4分) 设有一个最小堆,即堆中任意结点的关键码均大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方? (3)(4分)对n个元素进行初始建堆的过程中,最多做多少次数据比较(不用大O表示法)? 45.解答问题 (1)(6分)设某文件中待排序记录的排序码为72,73,71,23,94,16,05,68,试画图表示出树形选择排序(增序)过程的前三步。 (2)(4分) 试说明树形选择排序的基本思想。 (3)(2分) 树形选择排序与直接选择排序相比较,优缺点是什么? (4)(3分) 堆排序是如何改进树形排序方法的?优点是什么? 【山东大学 1999 五(15分)】 【山东工业大学 1999 五 (15分)】 46. 若有N个元素已构成一个小根堆, 那么如果增加一个元素为Kn+1,请用文字简要说明你如何在log2n 的时间内将其重新调整为一个堆? 【中科院计算所 1999 三、2 (5分)】 47.填空并回答相关问题 (1)下面是将任意序列调整为最大堆(MAX HEAP)的算法,请将空白部分填上: 将任意序列调整为最大堆通过不断调用adjust函数,即:FOR(i=n/2;i >0;i- -)adjust(list,i,n);其中list为待调整序列所在数组(从下标1开始),n为序列元素个数,adjust函数为: void adjust(int list[],int root,int n) /*将以root为下标的对应元素作为待调整堆的根,待调整元素放在list数组中,最大元素下标为n*/ {int child,rootkey; rootkey=list[root]; child=2*root; while(child<=n) {if((child list[child]) break; else{List[(2) ]=list[child]; child*=2; } } list[child/2]=rootkey; } (2).判断下列序列能否构成最大堆:(12,70,33,65,24,56,48,92,86,33);若不能按上述算法将其调整为堆,调整后的结果为:( )。 【浙江大学 1998 七 (11分)】 48.回答问题:(1) 设待排序的结点个数是n。试问堆排序算法在完成一次sift建堆,并且取走找到的最小关键码后,是否还需要对于n-1个关键码从头开始建堆?为什么? (2) 假定采用sift建堆算法。试问堆排序算法采用了怎样的节省存储空间的措施?堆排序完成后,heap中保存了关键码值的升序排列还是降序排列? 【山东工业大学 1996 三、3 (8分)】 49.在多关键字排序时,LSD和MSD两种方法的特点是什么?【北京邮电大学 2001 三、3 (5分)】 50.内排序的过程中,通常需要对待排序的关键字集合进行多遍扫描。采用不同排序方法,会产生不同的中间结果。设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键字按字母序的升序重新排列,请分别给出对该序列进行冒泡排序,初始步长为4的希尔排序,二路归并排序及以第一个元素为分界元素的快速排序的第一趟扫描的结果,并给出对该序列作堆排序时初始建堆的结果。【长沙铁道学院 1998 四、5(6分)】 51.给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列; (1) 希尔排序(第一趟排序的增量为5) (2) 快速排序(选第一个记录为枢轴(分隔)) (3) 链式基数排序(基数为10) 【上海交通大学 1999 八 (9分)】 52. 给出一组关键字:29,18,25,47,58,12,51,10,分别写出按下列各种排序方法进行排序时的变化过程:【南开大学 1998 八 (12分)】 (1) 归并排序 每归并一次书写一个次序。 (2) 快速排序 每划分一次书写一个次序。 (3) 堆排序 先建成一个堆,然后每从堆顶取下一个元素后,将堆调整一次。 类似本题的另外叙述有: (1) 对关键字/权值序列{9,4,3,8,10,7,6,5} ① 设序列是初始归并段的长度,画出最佳归并树,并计算其对应归并排序的I/O次数(假设每次I/O读写一个记录)。 ② 设序列是关键字输入次序,画出得到的二叉排序树。 ③ 画出构造初始小根堆的过程。 ④ 画出快速排序第一趟的过程。 ⑤ 画出步长为2的一趟希尔排序结果。【华南师范大学2000 二 (20分)】 53. (1) 判定起泡排序的结束条件是什么? (2) 请简单叙述希尔排序的基本思想。 (3) 将下列序列调整成堆(堆顶为最小值) 1 2 3 4 5 6 7 8 9 10 112 70 33 65 24 56 48 92 80 13 (4)在16个关键字中选出最小的关键字至少要多少次比较?再选出次小的关键字至少要多少次比较?请简要说明选择的方法和过程。 【燕山大学 1999 九(14分)】 54.给出如下关键字序列321,156,57,46,28,7,331,33,34,63试按链式基数排序方法,列出一趟分配和收集的过程。 【北京轻工业学院 1999 九 (10分)】 类似本题的另外叙述有: (1) 已知整数数组a的10个元素为326,129,167,588,212,95,980,725,443,601,用以下排序方法进行由小到大排序。 【西南交通大学 2000 二、6】 ① 用基数排序算法时,试写出第一次分配和收集后数组a中的结果。 ② 用堆排序时,试写出将第一个选出的数据放在数组a的最后位置上,将a调整为堆之后的a中的结果。 55.请写出应填入下列叙述中( )内的正确答案。 【上海大学 2002 一(8分)】 排序有各种方法,如插入排序、快速排序、堆排序等。 设一数组中原有数据如下:15,13,20,18,12,60。下面是一组由不同排序方法进行一遍排序后的结果。 ( )排序的结果为:12,13,15,18,20,60 ( )排序的结果为:13,15,18,12,20,60 ( )排序的结果为:13,15,20,18,12,60 ( )排序的结果为:12,13,20,18,15,60 56.图: no yes no yes no no yes yes no yes no yes 注:a是整数数组,存放要排序的数组集合,n是a的长度,p,i,j,k,m,t是临时变量,p为整型数组,i,j,k,m,t为整型变量。本题给出的是将数组a的元素a1,a2,…,an从大到小排序的子程序的框图,如上图,填空完善此算法框图。该子程序采用改进的选择排序方法,该方法基于以下思想:在选择第一大元过程中:a1与aj (j=n,n-1,…,2)逐个比较,若发现aj1>a1,则aj1与a1交换,交换后新的aj1有性质aj1>= at( j1 ai(j2 =at(j2 =0)个,依次为aj1,aj2,…,ajk,则它们都满足这一性质。它们的下标满足n>=j1>j2>…>jk>1。有了这些下标,在确定第二大元时,可只考虑a2与aj(j=jk,jk-1,…,3)逐一比较。倘若jk=2,则可不经比较就知道a2就是第二大元。在选择第二大元的过程中,将与a2交换过的元素下标也记录下来,可供选择其他大元使用。但在选择第二大元时,应保证与a2交换的那些位置上的新值也都满足上述性质。依次类推,顺序选择第一,第二,…,第n-1大元,实现对a的排序。 【哈尔滨工业大学 1999 六 (14分)】 57.给定一个关键字序列{24,19,32,43,38,6,13,22},请写出快速排序第一趟的结果;堆排序时所建的初始堆;归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少?在最坏情况下那种方法的时间复杂度最差? 【西安电子科技大学 1999五(10分)】 58.奇偶交换排序如下所述:对于初始序列A[1],A[2],…,A[n],第一趟对所有奇数i(1<=i A[i+1],则将两者交换;第二趟对所有偶数i(2<=i A[i+1],则将两者交换;第三趟对所有奇数i(1<=i 方案