在堆排序的过程中，对n个记录建立初始堆需要进行(①)次调整运算，由初始堆到堆排序结束，需要对树根结点进行(②)次调整运算。

假定一组记录的排序码为（46，79，56，38，40，84)，则利用堆排序方法建立的初始堆为（)。

在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为（①)，整个堆排序过程的时间复杂度为（②)。

手工跟踪对以下各序列进行堆排序的过程，给出形成初始堆及每选出一个排序码后堆的变化。（1)按字

手工跟踪对以下各序列进行堆排序的过程，给出形成初始堆及每选出一个排序码后堆的变化。

(1)按字母顺序排序：Tim，Dot，Eva，Rom，Kim，guy，Ann，Jim，Kay，Ron，Jan。

(2)按数值递增顺序排序：26，33，35，29，19，12，22。

(3)同样7个数字，换一个初始排列，再按数值的递增顺序排序：12，19，33，26，29，35，22。

在向一个有n个元素的最小堆中插入一个具有最小值的结点时，该结点需要逐层向上调整，直到被调整到堆顶位置为止。为此，需要做（)次关键码比较，移动（)个元素。

A、

B、

C、

D、

内存工作区可容纳的记录数。方法实现的步骤

(1)建立初始堆.

①从输入文件中输入p个记录，建立大小为p的堆。

②为第一个初始归并段选择一个适当的磁盘文件作为输出文件。

(2)置换-选择。

内存工作区存在两个堆：当前堆和新堆，新堆紧接在当前堆后存放，总大小为p。

①输出当前堆的堆顶记录到选定的输出文件。

②从输入文件中输入下一个记录。若该记录排序码的值不小于刚输出记录排序码的值，则由它取代堆顶记录，并调整当前堆。若该记录排序码的值小于刚输出记录的排序码的值，则由当前堆的堆底记录取代堆顶记录，当前堆的大小减1。新输入的记录存放在当前堆的原堆底记录的位置上，成为新堆的一个记录。

③如果新堆的记录个数大于「p/2，应着手调整新堆;如果新堆中已有p个记录，表示当前堆已输出完毕，当前的初始归并段结束、应开始创建下一个初始归并段，因此必须另为新堆选择一个磁盘文件作为输出文件。

④重复步骤②~③，直到输入文件输入完毕。

(3)输出剩余记录。

①输出当前堆中的剩余记录，并对输出边调整。

②将内存工作区中的新堆作为最后一个初始归并段输出。

设p=5，排序码序列为(54，15，62，10，77，24，29，20，59，43，69，31，47，38，12，18，51，27)，执行置换选择排序的结果如图10-19(a)~图10-19(g)所示.

生成的3个初始归并段为(10，15，24，29，54，59，62，69，77)，(20、31，38，43，47，51)，(12，18，27)。编写一个算法，实现上述利用堆的置换-选择排序.

按排序策略分类，起泡排序属于（①)。对n个元素的序列进行排序时，如果待排序元素序列的初始排列已

经全部有序，则起泡排序过程中需进行(②)次元素值的比较，(③)次元素值的交换。如果待排序元素序列的初始排列完全逆序，则起泡排序过程中需进行(④)次元素值的比较，(⑤)次元素的交换。(1)供选择的答案：A、插入排序;B、选择排序;C、交换排序;D、分配排序;E、归并排序.

A.1

B.n

C.nlog2n

D.log2n

当从一个有n个元素的最小堆中删除一个结点时，需要进行调整以重新形成最小堆。为此，需要做（)次关键码比较，移动（)元素。

A、

B、

C、

D、

请回答以下关于堆的问题: （1)堆的存储结构是顺序的，还是链式的？ （2)设有一个大顶堆，即堆中任意结点的关键码均大于它的左孩子和右孩子的关键码。其具有最大值的元素可能在什么地方？ （3)对n个元素进行初始建堆的过程中，最多做多少次数据比较？