名词解释题侃侃而谈kǎn kǎn ér tán

正确答案：C

正确答案：A
解析：由题可知，B[1]=T[(1-1)*n]，B[2]=T[(2-1)*n]，B[3]=T[(3-1)*n]，...，根据归纳法可得B[k]=T[(k-1)*n)。

正确答案：(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个记录的数组以及少量暂存单元。
堆排序算法是不稳定的。

答案：C

解析：