2022届高三信息技术选考总复习 专题24 桶排序、计数排序和索引排序 课件-（62张PPT）

(共62张PPT)
专题24 桶排序、计数排序和索引排序
1.语句t＝t＋1表示的是计数语句，若要统计0－9或a－z各元素的数量，分别需要10个和26个计数器，定义数组a(0 To 9)和a(1 To 26)来表示各元素的数量，这些数组元素可以看成是桶，数组元素的下标对应了元素的编号，如a(1)分别表示1和a的个数，而字母a可能通过其ASCII码值减去96达到与下标的联系。
2.简单桶排序算法采用以空间换时间的策略，可以对数组进行高效排序。(1)根据数组a中元素最值，确定申请的桶个数(下标上下界之差加1)，并将桶全部清空；(2)统计待排序序列中每个值为i的元素出现的次数，存入编号为i的桶；(3)依次把数据从桶里倒出来，存储到原序列中，获得一个已排序序列。
3.桶排序的原理是桶的编号，即数组元素的下标是有序，从最小编号的桶开始遍历到最大编号的桶，依次输出该桶编号对应的内容。注意，当桶中数量大于1时，要不断地取出编号对应的内容，同时把桶中数量减少一个。
4.计数排序是一种特殊的桶排序，它是一种稳定排序。(1)根据待排序序列中元素最值，确定申请的桶个数(下标界限)，并将桶全部清空；(2)统计待排序序列中每个值为i的元素出现的次数，存入编号为i的桶；(3)依次求出每个桶的前缀和；(4)反向填充目标数组，每放一个元素就将对应桶的元素值减1；(5)复制目标数组到原数组。
5.索引排序是指增加一个索引数组，用一个数组元素记录原数组的下标，不对原始数组进行排序，而是对索引数组进行排序。可以使用冒泡排序、插入排序和计数排序等算法对索引数组进行排序，确保排序的稳定性。
考点一　桶排序
先根据需要，确定桶的数量，如要统计字母的个数，可以用26只桶，要统计0－100分之间的人数，可以定义101只桶。桶的操作有三步，洗桶、装桶和数桶。
【例1】 若有11个桶，编号从0～10，每出现一个数时， 就在以该数编号的桶中放一面小旗子，最后只要按顺序数每个桶中有几面小旗子，就能得到这几个整数的有序排列。例如2号桶中有1个小旗子，表示2出现了一次；3号桶中有1个小旗子，表示3出现了一次；5号桶中有2个小旗子，表示5出现了两次；8号桶中有1个小旗子，表示8出现了一次，最后只要按桶的编号顺序逐次输出非空的桶的编号即可实现排序功能，为“2，3，5，5，8”。
实现程序如下，将空白处填写完整
Dim a(5) As Integer　　′数组a存储产生的随机整数
Dim b(10) As Integer　 ′数组b即桶
For i＝0 To 10　　′将数组初始化为0　　b(i)＝0
Next i
For i＝1 To 5　　′产生5个[0，10]的随机数
a(i)＝Int(Rnd*10)
____①____ ′第a(i)号桶中小旗子数量加1
List1.AddItem Str(a(i))
Next i
For i＝0 To 10
For j＝1 To b(i)
List2.AddItem____②______
Next j
Next i
答案　①b(a(i))＝b(a(i))＋1　②Str(i)
解析　数a(i)作为桶的编号，在相应桶下标元素进行计数。在输出时，桶的编号是有序的，桶的编号就是原来存储的数据。
【变式1】 有如下程序段：
Dim a(0 To 127) As Integer，ch As Integer
s＝Text1.Text
For i＝1 To Len(s)
ch＝Asc(Mid(s，i，1))
a(ch)＝a(ch)＋1
Next i
Text2.Text＝””
For i＝0 To 127
For j＝1 To a(i)
Text2.Text＝Text2.Text＋Chr(i)
Next j
Next i
A
数组a各个元素初始值为0，文本框Text1中输入的内容为“Text1”。执行该程序段后，文本框Text2中显示的第5个字符为(　　)
A.x B.1 C.T D.e
解析　程序的功能是桶排序，取出字符，并按ASCII值计数。接着按ASCII值从小到大输出，当a(i)＝0时，不循环。
【例2】 借助一个新数组，存储待排序元素在数组中名次号，把该名次号作为桶的编号，将待排序数据赋值给对应编号的桶数组元素中。下列VB程序段的功能为：先计算数组a中各个整数的降序排序的名次存入数组c中，然后根据名次进行排序，排序结果存入数组b中。如数组元素a(1)～a(5)的各元素值为“2，3，1，0，8”，程序运行后c(1)～c(5)各元素的值为“3，2，4，5，1”，b(1)～b(5)各元素的值为“8，3，2，1，0”。
For i＝1 To n
Next i
For i＝1 To n － 1
For j＝i ＋ 1 To n
　　　　c(i)＝c(i) ＋ 1
Else
　　　　c(j)＝c(j) ＋ 1
End If
Next j
Next i
For i＝1 To n
A
为完成如题所述功能，上述程序段3个方框处的代码分别为(　　)
A.(1)c(i)＝1　(2)a(j)>a(i)　(3)b(c(i))＝a(i)
B.(1)c(i)＝1　(2)a(j)C.(1)c(i)＝i　(2)a(j)>a(i)　(3)b(c(i))＝a(i)
D.(1)c(i)＝i　(2)a(j)解析　本题主要考查桶排序的算法思想，定义两个新数组，一个数组用于存储待排序数组元素在数组中名次号，另一个是桶数组，将待排序的数据赋值给名次号对应的桶中，桶编号是有序的，桶中数据也是有序的。c(i)表示数组a第i位置元素降序排序的名次，即降序排序后的位置。数组c各元素的初值为1，
为保证数组a中的元素两两比较一次，则i的范围：1→n－1，j的范围：i＋1→n。由于是降序排序，若a(j)>a(i)，则a(i)对应的名次号c(i)加1；否则a(j)对应的名次号c(j)加1，故(1)处代码为“c(i)＝1”，(2)处代码为“a(j)>a(i)”。c(i)表示数组a第i位置元素降序排序在数组b中的位置，依次处理数组a第1到n位置元素，即c数组存储a数组中各元素的1－n的名次号，该名次号作为桶的编号，把b数组看成是一个桶。把a(i)赋值给b(c(i))，c(i)是a(i)在数组a中名次号，即把a(i)放在b数组c(i)位置。如c(1)的值为3，则把a(1)的名次号是放在3号桶中，b(3)的值为2。桶的编号是有序的，桶中数据也是有序的。通过赋值语句“b(c(i))＝a(i)”存入数组b，故(3)处代码为“b(c(i))＝a(i)”。
考点二　桶经常用作标志
若有多个元素的状态，用桶的思想来描述，桶的值为True或False。
【例3】 对随机生成n 个互不相同的正整数(正整数的最大值不超过 m)进行排序，排序要求如下：①偶数在前，奇数在后；②奇数降序排序；③偶数升序排序。部分程序如下所示，划线处的正确语句是(　　)
Const n＝15
Const m＝100　　 ′整数的最大值
Dim a(1 To n) As Integer
′本过程产生 n 个不同随机整数，区间在[1，m]之间，存储在数组 a 中，代码略
Private Sub Command1_Click()
Dim i As Integer
Dim flag(1 To m) As Boolean
For i＝1 To n
____①____＝True
Next i
For i＝2 To m step 2
If flag(i) Then List2.AddItem ____②____
Next i
For i＝____③____ To 1 Step －2
If flag(i) Then List2.AddItem Str(i)
Next i
A.①flag(i)　 　②Str(a(i))　③m－1 　B.①flag(a(i))　②Str(i)　 　③m－1
C.①flag(a(i))　②Str(i)　 　③m 　D.①flag(i)　 　②Str(a(i))　③m
答案　B
解析　根据下面出现flag(i)，下标i范围是[2，m]的偶数，所以①是初始化语句，由i下标范围为 [1，n]，说明i是数组a的下标，所以①处应填flag(a(i))，即数组flag以产生的n个随机整数为下标，值置为True，这样②处显示产生过的偶数i，所以应填str(i)，那么③处遍历奇数[1，m－1]。
【变式2】 有如下VB程序：
For i＝1 To 10
f(i)＝False
Next i
For i＝2 To 10
If d(i)－d(i－1)>0 Then
f(i)＝True
d(i)＝d(i)－d(i－1)
End If
Next i
B
ans＝0
For i＝1 To 10
If f(i) Then ans＝ans＋1
Next i
Label1.Caption＝Str(ans)
程序运行时，数组元素d(1)～d(10)的值分别为25、15、10、8、1、7、8、11、16、9，则标签Label1中显示的内容为(　　)
A.6 B.5 C.4 D.3
解析　从第2个数组元素开始，如果他大于前面一个数组元素，编号i的桶为True，同时该数减去前面一个数的值存放在该数中。
考点三　计数排序
利用桶排序以空间换时间的思想，以及桶排序装入再倒出数据的过程，设计一个稳定的排序方法——计数排序。
Const n＝10
Dim a(1 To n) As Integer，tong(0 To 9) As Integer，b(1 To n) As Integer
For i＝0 To 9　　′把桶清空
tong(i)＝0
Next i
For i＝1 To n　　　　　　 ′将数据装入桶中
tong(a(i))＝tong(a(i))＋1
Next i
For i＝1 To 9　 ′从第2个桶开始依次求出每个桶的前缀和
tong(i)＝tong(i)＋tong(i－1)
Next i
For i＝n To 1 Step －1 ′逆序扫描原数组，反向填充目标数组
b(tong(a(i)))＝a(i)
tong(a(i))＝tong(a(i))－1　 ′该桶的前缀和减一
Next i
For i＝1 Ton　 ′顺序取出b数组里的值，实现升序排列
List1.Additem str(b(i))
Next i
【例4】 (2020·1月浙江选考)某省举办大型活动，面向省内城市招募有志愿服务工作经历的志愿者，每个志愿者的报名数据包含城市序号、姓名(字母缩写)和参加志愿服务的次数。现需整理报名数据，要求是：先按城市序号从小到大排列；然后，同一城市的志愿者按参加志愿服务的次数从多到少排列。 按上述要求，编写一个VB程序，功能如下：在列表框List1中显示整理前的数据，单击“整理”按钮Command1，整理结果显示在列表框List2中，程序运行界面如图所示。
(1)将数组元素q(1)到q(200)分为10段，如果每段恰好包含20个元素，采用选择排序算法分别对每段中的元素进行排序，整个排序过程中，数组元素之间的比较次数是________(单选，填字母：A.200×199/2次/B.10×20×19/2次/C.20×10×9/2次)。
(2)请在划线处填入合适的代码。
Const n＝200 　　′报名总人数
Const nc＝10 　　′城市数
Dim city(1 To n) As Integer，pname(1 To n) As String，times(1 To n) As Integer
Dim b(1 To nc) As Integer　　′存储每个城市的报名人数
Dim c(1 To nc) As Integer
Dim q(1 To n) As Integer
Private Sub Form_Load()
′本过程读取城市序号、姓名和参加次数的数据分别存储在数组city，pname和 times中并在List1中显示，代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer，j As Integer，k As Integer，t As Integer，pos As Integer
For i＝1 To nc
b(i)＝0
Next i
For i＝1 To n　　　　　　′统计每个城市报名人数
____①____
b(k)＝b(k)＋1
Next i
k＝1
For i＝1 To nc
c(i)＝k
k＝k＋b(i)
Next i
For i＝1 To n
k＝city(i)
____②____
c(k)＝c(k)＋1
Next i
pos＝1
For i＝1 To nc　　　　′对各城市报名数据按参加志愿服务的次数进行排序
For j＝pos To pos＋b(i)－2
k＝fp(j，pos＋b(i)－1)
t＝q(k): q(k)＝q(j): q(j)＝t
Next j
pos＝pos＋b(i)
Next i
For i＝1 To n
List2.AddItem ” ” & city(q(i)) & ”　” & pname(q(i)) & ” ” & times(q(i))
Next i
End Sub
Function fp(head As Integer，tail As Integer) As Integer
Dim i As Integer，k As Integer
k＝head
For i＝____③____
If times(q(i))>times(q(k)) Then k＝i
Next i
fp＝k
End Function
答案　(1)B　(2)①k＝city(i)　②q ( c( k ) )＝i　③head＋1 To tail 或 k＋1 To tail
解析　(1)冒泡排序算法和选择排序算法比较次数都是n(n－1)/2 次，所以每段比较次数为 20×19/2 次，总 10 段比较次数为 10×20×19/2 次。(2)根据注释语句数组b 存储每个城市的报名人数，联系下一条语句b(k)＝b(k)＋1，得知变量 k 为城市序号，所以第①空答案为 k＝city(i)。程序要求按照双关键字排序，其中主要关键字是城市序号。次要关键字是服务次数，分别对每一个城市的志愿者按照服务次数进行选择排序，q(k)＝i表示排名为k的志愿者序号为i，其所在城市序号为city(i)，姓名为pname(i)，服务次数为times(i)。对各城市报名数据按参加志愿服务的次数进行排序，j表示城市i中当前排名最靠前的位置，程序找到服务次数最多的志愿者(其序号为q(k))，将q(k)交换到排名为j的位置，使得times(q(j))是当前最大值。在自定义函数中，实现位置head到tail之间的选择排序。
【变式3】 小明编写了一个VB程序对成绩数据进行排序。为保证相同分数的同学相对位置(指原数据中的前后关系)不发生改变，他试着采用一种新的排序算法来解决。为便于描述算法的实现过程，假定有如下数组a：
第一步：统计数组a中每个值a(i)出现的次数，存入b(a(i))，统计完成后数组b的情况如下：
下标 1 2 3 4 5
值 5 3 3 2 4
下标 1 2 3 4 5
值 0 1 2 1 1
第二步：从前向后，依次使数组b中的每个值等于其与前一项之和，这样数组b(a(i))就代表了数组a中小于或等于a(i)的元素个数，完成第二步后数组b如下：
下标 1 2 3 4 5
值 0 1 3 4 5
第三步：从后往前，依次将数组a中元素填入数组c中，将数组元素a(i)放在数组c的第b(a(i))项，如元素a(1)＝5，应该放在数组c的b(5)位(即c(5))。每放一个元素就将b(a(i))递减；完成第三步后，数组c如下所示，已经完成升序排序，且相对位置不变，即原来a(2)的值3仍然在a(3)的值3前面。
下标 1 2 3 4 5
值 2 3 3 4 5
程序运行界面如下图所示：
实现上述功能的 VB 程序如下，请在划线处填上相应代码。
Dim a(1 To 50) As Integer 　′存放学生的成绩
Dim s name(1 To 50) As String 　′存放学生姓名
Dim n As Integer
Private Sub Form_Load()
′从数据库中读取相关数据并存入数组中
End Sub Private Sub Command1_Click()
Dim i As Integer，k As Integer
Dim b(0 To 100) As Integer
Dim c(1 To 50) As Integer，c1(1 To 50) As String　　′c和c1作为临时数组
For i＝1 To n
b(a(i))＝____①____
Next
For i＝1 To 100
b(i)＝____②____
Next
For i＝n To 1 Step －1
c(b(a(i)))＝a(i)
c1(b(a(i)))＝sname(i)
____③____
Next
For i＝1 To n 　′把临时数组 c 和 c1 中的数据放入 a 和 sname 数组
a(i)＝c(i)
sname(i)＝c1(i)
Next
List2.AddItem ”姓　 名” & ” ” & ”成绩”
For i＝1 To n
List2.AddItem sname(i) & ”　” & Str(a(i))
Next i
End Sub
答案　①b(a(i))＋1　②b(i)＋b(i－1)　③b(a(i))＝b(a(i))－1
考点四　索引排序
　　排序前后，序列的值是存储在数组a中还是数组c中。如何用排序后数组c来表示数组a中元素的值，如a(1)＝17，用a(c(1))还是用a(c(3))来表示。
原序列a 17 19 23 21 38 5 12
索引前c 1 2 3 4 5 6 7
索引后c 6 7 1 2 4 3 5
【例5】 编写一个VB程序实现以下功能：产生10个1～100之间的随机整数存数组a中，引入一个数组q，使得a(q(i))升序，即a(q(1) )≤a(q(2) ) ≤a(q(3) )……≤a(q(9) )≤a(q(10) )。
For i＝1 To 10
a(i)＝Int(Rnd()*100)＋1
Next i
For i＝1 To 9
k＝i
For j＝i＋1 To 10
Next j
If i <>k Then
t＝q(i): q(i)＝q(k): q(k)＝t
End If
Next i
上述程序段(1)(2)个方框处的代码分别为(　　)
A.(1)q(i)＝i　(2)a(q(j))C.(1)q(i)＝1　(2)a(q(j))解析　本题考核索引排序的基本方法。q数组中存储的是索引号，因此初值为i。q数组下标为k的元素存储a数组最值的位置，因此a(q(k))表示最值的值。
A
【变式4】 索引排序是近年来各类模拟考试中的新宠，而“索引排序”是和“物理排序”相对应的概念，所谓物理排序就是改变数组元素存储的物理位置，即直接对数组进行排序；而索引排序通过增加一个索引数组来存储各数组元素的下标，在排序时不需要对原数组进行排序，只需对索引数组排序即可。小明为了探究索引排序，编写VB程序演示索引排序算法，功能如下：在文本框Text1中输入各个数据(用“，”隔开和结尾)，单击“读取”按钮Command1，将各个数据依次存储到数组a中；单击“排序”按钮Command2，则对索引数组b重新排列，使得数组a中的元素按升序存储到数组c中，分别将处理后的索引数组b和有序数组c显示在标签Label1和Label2中。部分运行界面如图所示。
请回答下列问题：
(1)下列对象中，无Caption属性的是________(单选，填字母：A.Command1/B.Text1/C.Form1)。
(2)实现上述功能的VB程序如下，请在划线处填入合适的代码。
(3)程序加框处代码有错，请改正。
Dim n As Integer
Dim a(1 To 20) As Integer, b(1 To 20) As Integer, c(1 To 20) As Integer
Private Sub Command1_Click()
Dim i As Integer, t As String, ch As String
n＝0: t＝””
i＝1
Do While i <＝ Len(Text1.Text)
ch＝Mid(Text1.Text, i, 1)
If ch＝”，” Then
n＝n ＋ 1
　　____①____
b(n)＝n
t＝””
Else
t＝t ＋ ch
End If
i＝i ＋ 1
Loop
End Sub
Private Sub Command2_Click()
Dim i As Integer, j As Integer, t As Integer
For i＝1 To n － 1
For j＝n To i ＋ 1 Step －1
t＝b(j): b(j)＝b(j － 1): b(j － 1)＝t
End If
Next j
Next i
For i＝1 To n
____②____
Label1.Caption＝Label1.Caption ＋ Str(b(i))
Labe12.Caption＝Labe12.Caption ＋ Str(c(i))
Next i
End Sub
答案　(1)B　(2)①a(n)＝Val(t)　②a(b(i))　(3)a(b(j))解析　本题属于索引和冒泡排序的算法思想。(1)略。(2)读取文本框Text1中字符ch，当ch＝”，”时，表示一个数字串结束，将这个数字转换成文本后存储到数组a中，因此①的答案为a(n)＝Val(t)，变量n记录数的个数，数组b记录数据在原来数组a中的位置。采用索引排序，因此原数据不需求进行交换，只需交换记录其位置的数据即可。数组b用于记录数据在数组a中位置，比较和交换过程中，需用a(b(j))在交换中交换了数组b的值，因此数组b用于记录第n大(小)的数据在原来数组中的位置。具体排序过程如下表所示。
原始数据 第1趟排序 结果 第2趟排序 结果 第3趟排序 结果 第4趟排序 结果 i a(i) b(i) b(i) a(b(i)) b(i) a(b(i)) b(i) a(b(i)) b(i) a(b(i))
1 73 1 4 36 4 36 4 36 4 36
2 58 2 1 73 5 37 5 37 5 37
3 62 3 2 58 1 73 2 58 2 58
4 36 4 3 62 2 58 1 73 3 62
5 37 5 5 37 3 62 3 62 1 73
6 79 6 6 49 6 79 6 79 6 79
第一趟排序完成后，排序的区域并不是a(2)至a(6)，而是a(b(2))至a(b(6))，有序的是数组b(1)。因此在b(1)中用于记录最小数据所在的位置。故在改错处将条件改成a(b(j))【例6】 学生的班级、学号和成绩分别存储在数组bj、xh和cj中，要求按班级升序、成绩降序排列，且不能改变原来数组中值。编写VB程序实现上述功能，程序运行时，在列表框List1中输出每位学生的信息，单击“排序”按钮Command1，在列表框List2中输出排序后的信息。程序运行的界面如图所示。
(1)程序代码“List2.Clear”中的Clear是列表框类ListBox对象的__________(单选，填字母：A.属性名/B.过程名/C.方法名/D.事件名)。
(2)实现上述功能的VB程序如下，请在划线处填入合适的代码。
(3)程序中加框处代码有错，请改正。
Const n＝200
Dim xh(1 To n) As String，bj(n) As String　′存储学号和班级
Dim cj(1 To n) As Integer　　 ′存储成绩
Private Sub Command1_Click()
Dim index(1 To n) As Integer，t As Integer，begin As Integer
Dim i As Integer，j As Integer，k As Integer
List2.Clear
For i＝1 To n
index(i)＝i
Next i
begin＝1
For i＝1 To n
k＝i
For j＝i＋1 To n
If ____①____ Then k＝j
Next j
If k <>i Then t＝index(k): index(k)＝index(i): index(i)＝t
For j＝i To begin＋1 Step －1
　　　　If cj(index(j))>cj(index(j－1)) Then
　　　　　　t＝index(j): index(j)＝index(j－1): index(j－1)＝t
　　　　End If
Next j
Else
　　____②____
End If
Next i
′输出排序后的班级、学号和成绩信息，代码略
Next i
End Sub
答案　(1)C　(2)①bj(index(j))解析　(1)Clear是一种动作行为，因此属于方法。(2)程序首先采用选择排序，第i趟排序实现第1个位置至第i位置的班级从小到大排列，再采用从后往前冒泡排序，实现第i个位置前面的同一班级按成绩降序排列。在程序中引入一个索引数组index，给1至n个学生分配了一个索引号index(i)，表示他们在bj、xh、cj数组元素中位置。以图中所给数据为例，排序是从第1个位置到第n个位置i中，找到一个班级号最小位置k，比较的学生成绩的下标是该位置k在数组index中的索引号，即cj(index(k))，因此①的答案是bj(index(j))1.有如下程序段：
Const s＝”3123abc21d64”
For i＝1 To Len(s)
c＝Mid(s，i，1)
If c>＝”0” And c <＝”9” Then flag(Val(c))＝flag(Val(c))＋1
Next i
For i＝0 To 9
If flag(i)>0 Then n＝n＋1
t＝t＋flag(i)
Next i
flag数组中各元素的初值均为0，程序运行后，n和t的值分别是________和________ 。
答案　5　8
解析　Val(c)是把字符c转换成数字，将该数字作为下标的数组元素进行计数，因此flag数组可以看成是桶，flag(i)表示数字i的数量，字符串s中有1，2，3，4，6各2，2，2，1，1，因此n的值为5，t的值为8。
2.有如下VB程序段：
a(1)＝7: a(2)＝5: a(3)＝9: a(4)＝4: a(5)＝3
For i＝1 To 5
b(a(i))＝b(a(i))＋1
Next i
pa＝0
For j＝1 To 10
For k＝1 To b(j)
pa＝pa＋1
a(pa)＝j
Next k
Next j
数组元素a(1)到a(10)的值依次是7，4，9，4，3，执行程序段，数组元素a(1)到a(5)的数据依次是(　　)
A.7，9，4，4，3 B.3，4，4，7，9
C.4，4，7，9，3 D.9，7，4，4，3
解析　本题考查桶排序。第一个For循环中，语句b(a(i))＝b(a(i))＋1的功能是：利用桶对数组a中数据进行计数。桶的下标是有序的，对应数的值，按桶的编号输出各个桶中的数。
B
3.有如下VB程序段：
inS＝Text1.Text: n＝0
For i＝1 To Len(inS)
c＝Mid(inS，i，1)
m＝0
If c>＝”a” And c <＝”z” Then
m＝1
ElseIf c>＝”A” And c <＝”Z” Then
m＝2
ElseIf c>＝”0” And c <＝”9” Then
m＝3
End If
b(m)＝b(m)＋1
If b(m)＝2 Then n＝n＋1
Next i
已知数组b各元素初始值都为0，文本框Text1中的内容为“Welcome，2020！”，执行该程序段后，变量n的值为(　　)
A.1 B.2 C.3 D.4
解析　判断字符的种类，如果大于或等于2个，进行计数，大写字母只有一个，m的值默认为0，当条件均不满足时，即是标点符号时，统计个数并存储在a(0)中。
C
4.有如下VB程序段：
A
t＝””
For i＝1 To 10
b(a(i) Mod 10)＝b(a(i) Mod 10)＋1
b(a(i)\10)＝b(a(i)\10)＋1
Next i
c＝2
For i＝0 To 9
　If b(i)>c Then t＝t＋Str(i)
Next i
Label1.Caption＝t
数组b各元素初始值为0，数组元素a(1)到a(10)的值依次是65，99，12，34，40，74，56，88，30，45，执行程序段，标签Label1上显示的内容是(　　)
A.4 5 B.4 3 C.5 6 D.3 5
解析　a(i) Mod 10 和a(i)\10分别取出a(i)的个位数和十位数。
5.某VB程序段功能为：数组a顺序不变，输出升序结果。例如a数组各元素的值分别为”53，9，71，45，10，41”，最终a数组保持不变，而列表框List2输出”9，10，41，45，53，71”。
Const n＝6
Dim a(1 To n) As Integer
Private Sub Command1_Click()
Dim b(1 To n) As Integer，t As Integer，i As Intager，i As Intager
For i＝1 To n
b(i)＝i
Next i
For i＝1 To____①____
For j＝____②____ To n
If____③____T hen
　　　　t＝b(i): b(i)＝b(j): b(j)＝t
End If
Next j
Next i
For i＝1 To n
List2.AddItem a(b(i))
Next i
End Sub
上述程序段3处下划线的表达式分别为(　　)
A.①n－1　②i＋1　③b(i)>b(j) B.①n－1　②i＋1　③a(b(i))>a(b(j))
C.①n　　 ②1　　 ③b (i)>b(j) D.①n　　 ②1　　 ③a(b(i))>a(b(j))
B
解析　通过输出语句List2.AddItem a(b(i))得知最终数组a(b(i))是升序排序的。通过选择排序实现索引有序，n个元素排序最多需要n－1趟。排序本质上是交换索引数组b。当i＝1时，内循环j从2到n将最小值交换到a(b(1))，当i＝2时，内循环j从3到n将最小值交换到a(b(2))……，内循环j从i＋1到n，比较的数组a的值，即a(b(i))>a(b(j))。所以本题选择B选项。
6.根据成绩算名次。已知数组a存储了n个学生的成绩，成绩为40到100之间的整数。请编写程序输出各学生的名次，其中最高分为第1名，成绩相同则名次也相同。
下面的代码能实现上述程序功能，请将缺失的代码补充完整。
Const n＝20，minimum＝40，maximum＝100
Dim a(1 To n) As Integer
Dim c(minimum To maximum) As Integer
Private Sub Form_Load()
′产生n个介于minimum 和 maximum之间的数并显示在文本框Text1中，代码略！
End Sub
Private Sub Command1_Click()
Dim i As Integer
For i＝minimum To maximum ′把所有的桶均清空
c(i)＝____①____
Next i
For i＝1 To n　′把数据装入对应的桶中
c(a(i))＝____②____
Next i
For i＝maximum－1 To minimum Step －1′逆序求出每个桶的前缀和
c(i)＝c(i)＋c(i＋1)′此时c(i)表示最后一个入桶的元素在已排序数组中的索引值
Next i
For i＝minimum To maximum－1　　′依次求出每个分数对应的排名
c(i)＝c(i＋1)＋1 　　′此时c(i)表示第一个入桶的元素在已排序数组中的索引值
Next i
c(maximum)＝____③____
For i＝1 To n 　　′输出各学生的名次
　　　　Text2.Text＝Text2.Text＋Str(c(a(i)))
Next i
End Sub
答案　①0　②c(a(i))＋1　③1
解析　①中代码是把桶清空，因此将0赋值给c(i)。数组c表示计minimum 和 maximum之间的各个数的个数，这些数作为c数组的下标，对应的数组增加1，就把数据装入对应的桶中，因此②处应填入c(a(i))＋1。最大数maximum排在最大的前c(maximum)个位置，从第二大的数即maximum－1开始，找到多个相同数的最后一个数的位置，如100，100，99，99，99，99，那么最后一个99排在第6个位置，即该数在已排序数组中的索引值。无论有多少相同的最大数，他的排名是1，第二个数的名次取决于比他大数的个数，名次为比他大的个数加1。