题型：综合题 题类：真题 难易度：困难
浙江省普通高等学校招生2021年1月信息技术选考试卷
1）整体放置。按格子编号由小到大的次序查找第一个可放置该组全部物品的空区域（空区域是指从某个空格子开始的同层连续的所有空格子），若找到，则在该空区域居中、连续放置该组全部物品，如图a所示。
2） 零散放置。若所有空区域格子数都小于该组物品数，则将该组每个物品依次放置在当前编号最小的空格子中，如图b所示。
编写VB程序，模拟物品放置。运行程序，在列表框List1中显示每组物品的组号和数量，单击“放置”按钮Command1，在列表框List2中显示每组物品放置结果。程序运行界面如图c所示。
图c
Constm ＝ 50 'm表示物品柜的格子数
Const w ＝ 10 'w表示物品柜每层的格子数
Const n ＝ 9 'n表示物品的组数
'f（i）存储第i个格子开始的同层连续的所有空格子数。f（i）为0表示第i个格子不是空格子
Dim f（m）As Integer
Dim a（n）As Integer
Private Sub Form_Load( )
'读取各组物品的个数依次存入数组a，并在List1中显示
'代码略
End Sub
Function getpos（r As Integer As Integer
'按格子编号从小到大的次序，查找空格子数≥r的第一个空区域
'若找到，返回该空区域的起始编号，否则返回 -1
'代码略
End Function
Private Sub Command1_Click( )
Dim i As Integer，j As Integer， k As Integer，p As Integer，v As Integer
Dim s As String
For i ＝ 1 To m
f（i） ＝ w -（i -1）Mod w 'w为10，表示每层的格子数
Next i
v ＝ 1
For i ＝ 1 To n
s ＝ ""
p ＝
If p ＝ - 1 Then
j ＝ 1
Do While j ＜ ＝ a（i）
If f（v） ＜＞ 0 Then
s ＝ s ＋ Str（v）
f（v）＝
j ＝ j ＋ 1
End If
Loop
Else
k ＝（f（p）- a（i）） \ 2
For j ＝ k To 1 Step - 1
f（p） ＝ j
p ＝ p ＋ 1
Next j
For j ＝
f（j） ＝ 0
s ＝ s ＋ Str（j）
Next j
End If
List2. AddItem "第" ＋ Str（i） ＋ "组：" ＋ s
Next i
End Sub
假如我们用数组表示上述大根堆：
|
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)，故无需做交换操作。此时新元素已经放到了正确的位置，新的大根堆构造完成，上移行动结束。
试题篮
