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 分)】 18. PROC sift(VAR r: listtype: k, m: integer/, 17.堆排序的算法时间复杂度为: 【合肥工业大学1999三、10(2分)】 {假设r[k+1.m]中各元素满足堆的性质,本算法调整r[k]使整个序列r[k..m]中各元素 满足堆的性质。} i:=k:j: =(1): x: r[k]. key: finished: =false: t: =r[k] While (j<=)AND NOT finished DO [IF(j<m) AND((2))THEN j: =j+1 IF X<=r[j]. key THen finished: =(3) ELSE[r[i]:=(4);i:=j;j:=(5)] r[i]:=t ENDP;{sift}【燕山大学1998四、2(15分)】 9.设n为结点个数, datatype为结点信息类型。为了进行堆排序,定义: TYPE node=ReCoRd key: integer: info: datatype END VAR heap: ARRAY[l. n] OF node I,r, i, j: 0. n X: node 在下面的算法描述中填入正确的内容,使其实现1964年 Floyd提出的建堆筛选法,要求堆 建成后便找到了最小的关键码 筛选算法sift(l,r,heap): 步1.[准备]i1;j←(1);x-heap[i] 步2.[过筛]循环:当(2)时反复执行 (1).若jr且heap[j].key>heap[j+1].key则(3) (2).若(4)则heap[i]←heap[j;(5 否则跳出循环 步3.[结束] 【山东工业大学1996三、2(7分)】 20.以下程序的功能是利用堆进行排序。请在空白处填上适当语句,使程序完整 PROCedURE sift(VAR r: arr: k, m: integer) VAR 1, j, x: integer: t: rec: finished: boolean: BEGIN ;x:=r[i].key;(2)_; t:=r[k]
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<m) AND ((2)__) THEN j:=j+1; IF x<=r[j].key THEN finished:=(3)__ 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<r 且 heap[j].key>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<m) anD(3) Then j: =j+1 x<=r[j]. key THEn finished:true SE BEGIN (4 PROCEDURE heapsort(VaR r: arr) VAR i: integer; x: rec: BEGIN FOR i: =n DIv 2 DOWNTO 1 D0(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,5 ②94,53,31,72,16,23③16,53,23,94, 31,72 ④16,31,23,94,53,72 ⑤94,31,53,23,16,72 堆排序是一种_()类型的排序,它的一个基本问题是如何建堆,常用的建堆算法是 1964年 Floyd提出的_(2),对含有n个元素的序列进行排序时,堆排序的时间复杂度是 (3),所需要的附加结点是 【山东工业大学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[l. nJOF integer: 过程 heapsort的功能是将数组h中的前n个记录按关键字递减的次序排序。 heapsort 调用过程sift时的参数h,k,r有如下定义:以h[k+1],h[k+2],…,h]为根的子树已 经是堆:执行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<r)AND(h[j洫h[j+1]) then j:=计+1; IF x>h[j] THEN[(2) else finish: =true: PROC heapsort(var h: heapt ype: n: integer) ar k, r,i,j: integer: BEGIN For k:=n div 2 DOWNto 1 DO
WHILE (j<=m) AND NOT finished DO BEGIN IF (j<m) AND (3)____THEN j:=j+1; 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<r) AND (h[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