题目

二叉树是每个结点最多有两个子树的树结构，如值为9的结点有两个子树6和8，值为6的结点有两个子树5和3。若设二叉树的深度为h，则除第h层外，其它各层(1～h－1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。现要构造大根堆，堆是一棵顺序存储的完全二叉树，大根堆又是一种特殊的堆，它的特征是每个双亲结点的值都不小于其孩子结点的值。如下图所示，值为9的结点是6和8的双亲结点，而6和8分别是9的左孩子和右孩子；同理，6是5和3的双亲结点，而5和3分别是6的左孩子和右孩子…… 假如我们用数组表示上述大根堆： a(1) a(2) a(3) a(4) a(5) a(6) a(7) a(8) a(9) 9 6 8 5 3 4 7 2 1 现有一算法把一个无序数组改造成大根堆。例如：我们在上图的大根堆中再增加一个值为8的新元素，如下图所示。 数组存储为： a(2) a(3) a(4) a(5) a(6) a(7) a(8) a(9) a(10) 6 8 5 3 4 7 2 1 8 具体操作方法如下： 第一步：因为a(10)大于它的双亲结点a(5)，故需交换a(10)和a(5)的值； 数组存储为： 第二步：因为a(5)大于它的双亲结点a(2)，故需交换a(5)和a(2)(t)值； 数组存储为： a(1) a(2) a(3) a(4) a(5) a(6) a(7) a(8) a(9) a(10) 9 8 8 5 6 4 7 2 1 3 第3步：因为a(2)不大于它的双亲结点a(1)，故无需做交换操作。此时新元素已经放到了正确的位置，新的大根堆构造完成，上移行动结束。 （1） 若在图中增加值为4的新元素，则元素4将被存储在数组元素中。 （2） 小段为此编制一VB程序：在文本框Tcxt1中输入结点个数n，单击命令按钮Command1，随机产生n个[1，99]的整数作为结点值，并由此构造大根堆，结果显示在列表框List1中，程序运行界面如图所示。 实现上述功能的程序代码如下请在划线处填入合适的代码。 Dim a(1 To 100) As Integer ‘该函数功能为实现数据的对齐输出 Function pout(x As Integer, y As Integer) As String 代码略 End Function Private Sub Command1_Click() Dim tmp As Integer, Dim m As Integer Dim n As Integer, Dim s As String n = Val(Text1.Text) For i=1 To n     a(i) = Int(Rnd()*99)+ 1 Next i For i= 2 To n     p=i     f=p\2     Do While  ①           tmp = a(p): a(p)= a(f): a(f) = tmp         p=f         f=p\2         If f= 0 Then Exit Do     Loop Next i k= n Do While k >=1     m=m+1       ②   Loop k= 1 For i=0 To m- 1     s=""     For j= 1 To   ③           If k> n Then Exit For         s=s+ pout(a(k), (2^(m-1)-2^i)/2^i)         k=k+ 1     Next j     List1.AddItem s Next i ① ② ③  答案： 【1】a(5) 【1】a(p)>a(f)【2】k=int(k/2)或k=k\2【3】2^i

查看本题答案和解析