数据结构考研分类复习真题 第十章 排序[30]

．堆是一种有用的数据结构试判断下面的关键码序列中哪一个是堆_____

① ② ③④ ⑤

堆排序是一种___()___类型的排序它的一个基本问题是如何建堆常用的建堆算法是年Floyd提出的___()___对含有n个元素的序列进行排序时堆排序的时间复杂度是___()___所需要的附加结点是___()___【山东工业大学 一 (分)】

．堆是一种有用的数据结构 堆排序是一种___()___排序堆实质上是一棵___()___结点的层次序列对含有N个元素的序列进行排序时堆排序的时间复杂度是___()___所需的附加存储结点是___()___关键码序列是否满足堆的性质___()___ 【山东工业大学 三 (分)】

．将如下的堆排序算法补写完整说明如下

TYPE heaptype=ARRAY[n]OF integer;

过程heapsort的功能是将数组h中的前n个记录按关键字递减的次序排序heapsort调用过程sift时的参数hkr有如下定义以 h[k+]h[k+]…h[r]为根的子树已经是堆;执行sift后以h[k]h[k+]h[k+]…h[r] 为根的子树都成为堆

PROC sift(VAR hheaptype;krinteger);

VAR ijxinteger;finishboolean;

BEGIN i:=k;x:=h[i];j:=*j;

(____()____);

WHILE (j<=r) AND NOT finish DO

[IF (j<r) AND (h[j]>h[j+]) THEN j:=j+;

IF x>h[j] THEN [____()____]

ELSE finish:=true;

____()____]

END;

PROC heapsort(VAR h:heaptype; n:integer);

VAR krij:integer;

BEGIN

FOR k:=n DIV DOWNTO DO

sift (____()____) ;

FOR r:=n DOWNTO DO

[x:=h[]; h[]:=h[r]; h[r]:=x; (____()____)]

END;【北京工业大学 五 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []