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

．设有n个无序元素按非递减次序排序但只想得到前面长度为k的部分序列其中n>>k最好采用什么排序方法？为什么？如果有这样一个序列{}得到的部分序列是{}对于该例使用所选择的方法实现时共执行多少次比较？【东北大学 一(分)】

类似本题的另外叙述有

() 如果只想得到一个序列中第K个最小元素之前的部分排序序列那么最好应采用哪种排序算法？为什么？如由这样一个序列 得到其第四个最小元素之前的部分排序序列… 用你选用算法实现时共执行多少次比较？【北方交通大学 七(分)】

．写出用堆排序算法对文件F=()进行排序时初始堆及以后每挑好一个元素重新调整后堆的状态并指出这里的堆和败者树的一个主要区别【东南大学 二(分)】

．请回答下列关于堆(Heap)的一些问题【清华大学 五 (分)】

()(分) 堆的存储表示是顺序的还是链接的?

()(分) 设有一个最小堆即堆中任意结点的关键码均大于它的左子女和右子女的关键码其具有最大值的元素可能在什么地方?

()(分)对n个元素进行初始建堆的过程中最多做多少次数据比较(不用大O表示法)?

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