数据结构1800试题-第10章 排序

我下vip免费资源网 www.woxia.net 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分)】

2

5. 不受待排序初始序列的影响,时间复杂度为O(N)的排序算法是_____,在排序算法的最后一趟开始之前,所有元素都可能不在其最终位置上的排序算法是_____。【中国人民大学 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进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式: #include

typedef struct node {char data; struct node *link; }node; node *select(node *head) {node *p,*q,*r,*s;

p=(node *)malloc(sizeof(node));

我下vip免费资源网 www.woxia.net p->link=head; head=p; while(p->link!=null) {q=p->link; r=p; while ((1)____)

{ if (q->link->datalink->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则排序需__________趟,写出第一趟结束后,数组中数据的

我下vip免费资源网 www.woxia.net 排列次序__________。

【南京理工大学 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)____时反复执行

⑴.若jheap[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

我下vip免费资源网 www.woxia.net 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 (jh[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

联系客服:779662525#qq.com(#替换为@)