题型：综合题 题类：常考题 难易度：困难
浙江省诸暨市2020届高三上学期信息技术诊断性考试试卷
假如我们用数组表示上述大根堆：
|
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)，故无需做交换操作。此时新元素已经放到了正确的位置，新的大根堆构造完成，上移行动结束。
实现上述功能的程序代码如下请在划线处填入合适的代码。
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
① ② ③
试题篮
