发布时间 : 星期四 文章数据结构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->data
}
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)____时反复执行 ⑴．若j ⑵．若(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 (j 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