阅读以下说明,将应填入(n)处的字句写在答卷纸的对应栏内。【说明】 下面的程序为堆排序程序,其中函

Question

阅读以下说明，将应填入(n)处的字句写在答卷纸的对应栏内。

【说明】

下面的程序为堆排序程序，其中函数adjust(i,n)是把以R[i](1≤i≤┕i/2┙)为根的二叉树调整成堆的函数，假定R[i]的左、右子树已经是堆，程序中的，是在主函数中说明的结构数组，它含有要排序的n个记录。

【程序】

Void adjust(i，n)

Int i，n；

{

iht k,j;

element extr;

extr=r[i];

k=i;

j=2*i;

while (j＜=n )

{if ((j＜n) && (r[j].key＜r[j+1].key))

(1);

if (extr. key＜r[j].key)

{

r[k]=r[j];

k=j;

(2);

}

else

(3);

}

r[k]=extr;

}

/*让i从┗i/2┛逐步减到1, 反复调用函数adjust, 便完成建立初始堆的过程。*/

void heapsort (r,n)

list r;

int n;

{

int i,1;

element extr;

for (i=n/2;i＞=1;- -i)

(4); /* 建立初始堆*/

for (k--n;k＞=2;k- -)

{

extr=r[1];

r[1]=r[k];

r[k]=extr;

(5);

}

}

Answer 1

正确答案：(1)j++ (2)j*=2或j=k*2 (3)j=n+1或break (4)adjust(in) (5)adjust(1k-1)
(1)j++ (2)j*=2或j=k*2 (3)j=n+1或break (4)adjust(i,n) (5)adjust(1,k-1) 解析：函数adjust(i,n)是把以R[i](1≤i≤┗i/2┛)为根的二叉树调整成堆的函数，假定R[i]的左、右子树已经是堆，程序中的r是在主函数中说明的结构数组，它含有要排序的n个记录。
Void adjust(i,n)
Int i,n；
{
int k,j;
element extr;
extr=r[i];
k=i;
j=2*i;
while(j=n)
{if((jn)&&(r[j].keyr[j+ 1].key))
j++;
if(extr.keyr[j].key)
{
r[k]=r[j];
k=j;
j*=2;
}
else
j=n+1;
}
r[k]=extr;
}
/* 让i从┗i/2 ┛逐步减到1, 反复调用函数adjust, 便完成建立初始堆的过程。堆排序程序heapsort 如下*/
void heapsort(r,n)
list r;
int n;
{
int i,l;
element extr;
for (i=n/2;i＞= 1 ;--i)
adjust(i,n); /*建立初始堆*/
for(k=n;k＞=2;k--)
{
extr=r[1];
r[1]=r[k];
r[k]=extr;
adjust(1,k-1);
}
}
函数heapsoff的第一个for循环建立初始化。没待排序的n个记录组成—棵深度为h的完全二叉树，因此有2h-1n≤2h+1-1，即2h≤n2h+1。完全二叉树的第i层(设根结点的层次为0)上最多有2i个结点，对每个非叶结点，都要调用过程adjust，同时可能移动结点(向下移动)，第i层上的结点可能要移动的最大距离为h-i，若设向下移动一层花费的时间为c，则第i层2i个结点调整的时间最多为c*(h-i)*2i建立初始堆的全部时间应是：
令j=h-1，则i=h-j，所以有：
对第二个for循环，调用adjust函数n-1次，每次总是由根向下调整，调整的最大距离为log2n(实际上，调整的距离是逐渐变小的)，所以总的时间不多于c*(n-1)log2n＝O(log2n)．堆排序总的时间为：
O(n)+O(nlog2n)=O(max(n,n log2n))=O(n log2n)
算法需要的存储空间是存储n个记录的数组以及少量暂存单元。
堆排序算法是不稳定的。