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

．如果只要找出一个具有n个元素的集合的第k(≤k≤n)个最小元素你所学过的排序方法中哪种最适合？给出实现的思想【北方交通大学 六 (分)】

．已知快速排序和归并排序的算法分别如下所示

PROCEDURE qksort(VAR r:listtype; st:integer);

BEGIN

IF s<t THEN BEGIN

qkpass(rstk);

qksort(rsk);

qksortd(rk+t)

END

END;

PROCEDURE mergesort(VAR rr:listtype;st:integer);

BEGIN

IF s=t THEN r[s]:=r[s] ELSE

BEGIN

MERGESORT(rrs(s+t)DIV );

MERGESORT(rr(S+t)DIV +t);

MERGE(rs(s+t)DIV trl)

END

END;

若对下列关键字序列进行快速排序和归并排序分别写出三次调用过程qkpass和过程merge后的结果

()【清华大学 六 】

．已知一关键码序列为试根据堆排序原理填写完整下示各步骤结果【首都经贸大学 二 (分)】

建立堆结构_____________

交换与调整

() ;()____________________;

() ;()____________________;

() ;()____________________;

() ;

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