(共98张PPT)
考点一????解析算法及程序实现
考向基础
1.解析算法的基本思想
用解析的方法找出表示问题的前提条件与所求结果之间关系的数学表达
式,并通过数学表达式的计算来实现问题的求解。
如:已知圆的半径为r,求圆的面积s,则可通过公式s=3.14*r*r计算得到。
2.解析算法的程序实现
(1)分析问题,建立正确的数学模型,找到数学计算式或数学算法。要注意
的是,有些问题能找到一个明确的公式,但是有些问题可能是一个运算过
程,比如除二倒取余法求二进制,辗转相除法求最大公约数等问题。
考点清单
(2)将数学计算或数学算法转化为VB运算过程。
考向突破
解析算法一般难度不大,重点题型是各种进制之间的相互转换。
例1 将十进制数转化为二进制数的VB 程序段如下:
Dim y As Integer, s As String, r As Integer
y=Val(Text1.Text) ’输入十进制数
s="" ????
Do While y <> 0
Loop
Text2.Text=s ’显示二进制数
方框中的代码由以下三部分组成:
①s=Str(r)+s
②y=y\2
③r=y Mod 2
代码顺序正确的选项是?( )
A.②③① B.②①③
C.①③② D.③②①
解析 本题采用“除2取余法”将十进制转换成二进制,先求余数(Mod运
算)并保存,再求商(整除 \),商用来下一次求余数。重复执行该过程直到商
为0。
答案????D
例2 辗转相除法是数学史中著名的算法,用于计算两个正整数a和b的最
大公约数。步骤如下:
现编写程序,在文本框Text1和Text2中输入a和b,在文本框Text3中输出
两数的最大公约数。代码如下:
Private Sub Command1_Click()
Dim a As Integer, b As Integer, r As Integer
变量 a b 余数
初始值 24 15 9
第一次辗转 15 9 6
第二次辗转 9 6 3
第三次辗转 6 3 0
余数为0时终止,最大公约数为3
a=Val(Text1.Text)
b=Val(Text2.Text)
r=a Mod b
Do While ①????
a=b
b=r
r=a Mod b
Loop
Text3.Text= ②????
End Sub
解析 ①循环结束条件是r=0,因此循环条件是r>0 或 r<>0。②退出循环
后,结果存在变量b中。
答案 ①r>0 ②str(b)
考点二????枚举算法及程序实现
考向基础
1.枚举算法的基本思想
将问题的可能解一一列举,逐个判断,找到所有符合条件的解。即使中途找
到符合的解也要继续找下去,要将所有可能解找完才结束。设计枚举算法
时要尽量减小罗列范围(提高算法的效率),不能遗漏,也不能重复。
2.枚举算法的程序实现
根据枚举算法的主要思想:一一列举,逐个判断。因此一般情况下枚举算法
的代码具有以下特点:
(1)用循环语句在一定范围内列举所有可能的解。
(2)用选择语句判断和选择真正的解。
枚举算法的一般格式:
For(列举所有可能的解)
If 可能解是正确解 Then 输出该解或计数
Next
注意:循环语句不一定用For语句,也可用Do语句。
3.多变量列举
某些枚举算法的问题比较复杂,可能有多个变量需要列举,此时就需要多重
循环,也即循环嵌套。格式如下:
For(列举变量1所有可能的解)
For(列举变量2所有可能的解)
????……
If 该组解是正确解 Then 输出该组解或计数
????……
Next
Next
如鸡兔同笼问题、百鸡百钱问题等。在设定多个变量的列举范围时,可以
利用验证条件,尽可能缩小列举范围,减少列举变量,从而减少循环的嵌
套。如百鸡百钱问题:100元钱买100只鸡,公鸡5元一只,母鸡3元一只,小鸡1
元3只。则代码如下:
For x=1 To 100
For y=1 To 100
For z=1 To 100
If x+y+z=100 And 5*x+3*y+z/3=100 Then 输出该组解或计数
Next z
Next y
Next x
利用验证条件,代码可优化为:
For x=1 To 20 ’公鸡最多不超过20只
For y=1 To 33 ’母鸡最多不超过33只
z=100-x-y
If 5*x+3*y+z/3=100 Then 输出该组解或计数
Next y
Next x
例 寻找3位的水仙花数。什么是水仙花数?水仙花数是指一个 n 位数(n
≥3),它的每一位上的数字的 n 次幂之和等于它本身。例如153是水仙花
数,因为13+53+33=153。
解决此问题的Visual Basic程序如下,程序界面如图所示,在列表框List1中
输出结果。
?
在(1)和(2)划线处,填入合适的语句或表达式,把程序补充完整。
Private Sub Command1_Click()
Dim i As Integer
Dim a,b,c As Integer
For (1)????
a=i\100
b=i\10 Mod 10
c=i Mod 10
If (2) ???? Then List1.AddItem Str(i)
Next
End Sub
(1)程序中划线处(1)应填入 ????。
(2)程序中划线处(2)应填入 ????。
解析 (1)枚举算法在列举的过程中,不能遗漏任何一个可能的解,寻找3位
的水仙花数,100到999都是可能解。因此列举所有可能解的语句应该是
For i=100 To 999。
(2)If语句用于检验当前列举的可能解i是不是正确解。水仙花数的验证条
件:它的每一位上的数字的n次幂之和等于它本身,本程序要求找出3位的水
仙花数,因此n=3,变量a、b、c是i的百位、十位和个位上的数字,因此验证
条件是a^3+b^3+c^3=i。
答案 (1)i=100 To 999 (2)a^3+b^3+c^3=i
考向突破
从目前出现的真题看,直接考枚举算法的不多,常考字符串的处理,一般题
型为:输入一串字符串,字符串中有一些特殊字符做为间隔符号,利用该间
隔符号,将字符串中的字符提取,并作进一步的数据分析或处理。从代码特
点和思想方法上分析,该类问题也利用了枚举算法的思想。
一、字符串问题相关知识
1.字符大小的比较
字符(包括字符串)在计算机中存储的是每个字符的内码值。字符比大小
实际上是比较字符的ASCII码值。如“a”<“b”,“ab”<“abc”,
“abc”<“abd”,“acde”<“ad”,比较方法是先比较第一个字符,如果相
同,则比较第二个字符,依次类推。几个常用字符的内码值:
字符 “0” “9” “A” “Z” “a” “z” “0”~
“9”按顺
序编码。
“A”~
“Z”、
“a”~
“z”按字
母顺序编
码
十进制值 48 57 65 90 97 122
十六进制
值 30 39 41 5A 61 7A
2.字符相加
(1)用“+”号:运算符两边必须都是字符串型,如“1”+“2”=“12”,而1
+“2”则出错。
(2)用“&”号:会自动将两边的数据转成字符串型再拼接。如“1”&
“2”=“12”,1&“2”=“12”。
注意:字符相加前后位置对调,结果不一样,“1”+“2” =“12”,而“2”+
“1” =“21”。利用这一点,可达到字符反串的效果,比如在除二倒取余
法中的应用。
3.不同类型字符的判断
功能 表达式
小写字母 ch>=“a” And ch<=“z”
大写字母 ch>=“A” And ch<=“Z”
数字字符 ch>=“0” And ch<=“9”
字母 ch>=“A” And ch<=“Z” Or ch>=“a” And
ch<=“z”
非字母 Not(ch>=“A” And ch<=“Z” Or ch>=“a”
And ch<=“z”)
4.字符转换
二、字符串基本操作
1.判断是否对称
f=true
n=Len(s)
For i=1 To n\2
If Mid(s,i,1)<>Mid(s,n-i+1,1) Then
功能 表达式
大写转小写 Chr(Asc(ch)+32)
小写转大写 Chr(Asc(ch)-32)
求字母的字母序 小写字母:Asc(ch)-96或Asc(ch)- Asc(“a”)+1
大写字母:Asc(ch)-64或 Asc(ch)- Asc(“A”)+1
f=false:Exit For
End If
Next i
最后判断f的值,如果是true,则对称,否则不对称。
2.字符串反转
n=Len(s)
For i=1 To n
s1=Mid(s,i,1)+s1
Next i
得到的字符串s1是s的反串。
3.插入字符串
在字符串s中,在第n个位置插入字符串c:
s1=Mid(s,1,n-1)+c+Mid(s,n,Len(s)-n+1)
如s=“hppynewyear”,n=2,c=“aa”,则s1=“haappynewyear”。
4.删除字符串
在字符串s中,删除子串s1:
i=1
Do While i<= Len(s)-Len(s1)+1
If Mid(s,i,Len(s1))=s1 Then
s=Mid(s,1,i-1)+Mid(s,i+Len(s1),Len(s)-i-Len(s1)+1)
Else
i=i+1
End If
Loop
5. 删除重复字符
删除字符串s中重复的字符。
s1=Mid(s,1,1)
For i=2 To Len(s)
f=0
For j= 1 To Len(s1)
If Mid(s,i,1)=Mid(s1,j,1) Then f=1:Exit For
Next j
If f=0 Then s1=s1+Mid(s,i,1)
Next i
6. 单词个数统计
f=0
For i=1 To Len(s)
ch=Mid(s,i,1)
If ch>="A" And ch<="Z" Or ch>="a" And ch<="z" ’ch是字母
If f=0 Then c=c+1:f=1
Else
f=0
End If
Next
例 用VB编写一个“加减法运算”程序,实现如下功能:在文本框Text1中
输入多个正整数加减算式(只包含数字和“+ ”“-”字符,以“=”为结束
符),单击“计算”按钮Command1,计算结果在标签Label1上显示。程序运
行界面如图所示。
?
(1)程序运行时清空Label1上的内容,则可在Form_Load事件过程中添加语
句 ????(单选,填字母:A.Form1.Caption= “”/ B.Form1.Text=“”/C.La-
bel1.Caption=“”/D.Label1. Text=“”)。
(2)实现上述功能的VB程序如下,请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim s As String, t As Integer
s = Text1.Text
t = 0: p = 0: flag = 1
For i = 1 To Len(s)
ch = Mid(s, i, 1)
If ch >="0" And ch <= "9" Then
p = ① ????
Else
t= ② ????
p = 0
If ch = "-" Then
flag = -1
Else If ch = "+" Then
flag = 1
End If
End If
Next i
Label1.Caption = Str(t)
End Sub
(3)若文本框Text1中输入内容的结束符“=”缺失(即输入内容为12+28-15
+50),单击“计算”按钮后, 标签Label1上显示的内容是 ????。
解析 本题的解题关键在于理解非数字字符的操作。For语句遍历字符串
值,If语句判断字符类型。(1)略。(2)①分析判断条件可知,要执行数字相
连。原值p乘10加新出现的值Val(ch)组成新值。②非数字符号出现,要把
前值放入累加器t中,flag存放前值符号,因此要累加flag*p。(3)由于“=”
缺失,造成最后一个数50没有被累加。
答案 (1)C (2)①p*10 + Val(ch) ②t + flag*p (3)25
考点三????排序算法及程序实现
考向基础
1.冒泡排序的基本思想
把待排序的n个元素的数组看成是垂直堆放的一列数据,从最下面的一个
元素起,自下而上地比较相邻的两个元素中的数据,将较小的数据换到上
面。重复这一过程,直到处理完最后两个元素中的数据,称为一遍加工。第
一遍加工完成后,最小的数据已经上升到第一个元素的位置。然后对余下
的n-1个元素重复上述处理过程,直至最后进行余下两个数据的比较和交
换。n个数需要n-1遍排序。
以数据130,20,98,15,67,3为例,从小到大冒泡排序的操作过程如下:
原始数据 130 20 98 15 67 3
第1遍排序
后 3 130 20 98 15 67
第2遍排序
后 3 15 130 20 98 67
第3遍排序
后 3 15 20 130 67 98
第4遍排序
后 3 15 20 67 130 98
第5遍排序
后 3 15 20 67 98 130
2.冒泡排序的程序实现
For i=1 To n-1 ’n个数需要n-1遍排序
For j=n To i+1 Step -1 ’从后往前,两两比较,直到a(i+1)和a(i)比较完
If a(j)
temp=a(j-1):a(j-1)=a(j):a(j)=temp ’小的数在后面,则交换
End If
Next j
Next i
①外循环“For i=1 To n-1”中的变量i表示第i遍冒泡排序,n个数需要n-1
遍排序。
②由内循环“For j=n To i+1 Step -1”可看出,冒泡比较的方向是从后往前,
两两比较,第i遍的比较次数是n-i次,交换次数最多是n-i次,交换次数最少是0次。
③从小到大排序(升序),If语句中条件表达式为:a(j)(降序),If语句中条件表达式为:a(j)>a(j-1)。
例1 有如下程序段:
For i=1 To 2
For j=5 To i+1 Step -1
If a(j) Next j
Next i
数组元素a(1)到a(5)的值依次为“95,88,66,80,75”,经过该程序段“加工”
后,数组元素a(1)到a(5)的值依次为?( )
A.66,75,95,88,80 B.66,75,80,95,88
C.95,88,66,80,75 D.95,88,80,75,66
解析 此题为冒泡排序,升序排序,排序两遍。答案为A。
答案????A
3.选择排序的基本思想
在所有的元素中选出最小(大)的数据,把它与第一个数据交换,然后在其余
的元素中再选出最小(大)的数据与第二个数据交换。以此类推,直至所有
数据排序完成。n个数需要n-1遍排序。
以数据130,20,98,15,67,3为例,从小到大选择排序的操作过程如下:
原始数据 130 20 98 15 67 3
第1遍排序
后 3 20 98 15 67 130
第2遍排序
后 3 15 98 20 67 130
第3遍排序
后 3 15 20 98 67 130
第4遍排序
后 3 15 20 67 98 130
第5遍排序
后 3 15 20 67 98 130
4.选择排序的程序实现
选择排序的代码如下:
For i=1 To n-1
k=i
For j=i+1 To n
If a(j)Next j
If k<>i Then
temp=a(i):a(i)=a(k):a(k)=temp
End If
Next i
①外循环“For i=1 To n-1”中的变量i表示第i遍选择排序,n个数需要n-1遍排序。
②矩形框内代码用于寻找数据元素a(i)到a(n)的最小值,变量k记录当前找
到的最小值的位置,即数组元素的下标,则a(k)就是当前找到的最小的数组
元素。它的思想方法是先假设数组的第i项是最小的(第i遍排序),因此k记
为i,然后把从第i+1项开始的所有数组元素跟a(k)进行比较,如果比a(k)小,
则用k记录该元素的下标。这样循环结束后,变量k中存储的就是数组中从
第i项至第n项的最小元素的下标,a(k)就是第i项至第n项中的最小元素。
③从小到大排序(升序),If语句中条件表达式为:a(j)序),If语句中条件表达式为:a(j)>a(k)。
例2 对下列一组原始数组:13,15,2,11,8,18 进行选择排序,第一遍排序结
束,数组的状态不可能是?( )
A.2,15,13,11,8,18 B.18,15,2,11,8,13
C.13,15,2,11,18,8 D.13,15,18,11,8,2
解析 本题考查选择排序的思想方法。选择排序算法第一遍一定会把最
大或最小的数交换到最前或最后,其他数据不动。因此答案为C。
答案????C
例3 用选择排序法对一组学生的身高数据进行升序排序,已知第一遍排
序结束后的数据序列为165,168,178,175,171,则下列选项中可能是原始数
据序列的是?( )
A.175,178,168,165,171 B.178,168,165,175,171
C.165,178,168,175,171 D.165,168,171,175,178
解析 第一遍排序后排第一位的165有5种可能的来源,①原来就在第一位,
不需要数据互换,那么原始数据就是165,168,178,175,171;②从第二位换来,
那么原始数据就是168,165,178,175,171;③从第三位换来,那么原始数据就
是178,168,165,175,171;④从第四位换来,那么原始数据就是175,168,178,16
5,171;⑤从第五位换来,那么原始数据就是171,168,178,175,165。
答案????B
5.冒泡排序与选择排序的比较
冒泡排序 选择排序
思想方法 一边比较,一边交换 先选出最大值或最小值,再交换
相同点 ①n个数都需要n-1遍排序,其中变量i控制排序的遍数
②比较的次数一样多,都是(n-1)+(n-2)+…+3+2+1次
③最好的情况下,交换的次数一样,都是0次
不同点 边比较边交换,最坏的情况下交
换的次数是(n-1)+(n-2)+…+3+2
+1次 先选择再交换,最坏的情况下交
换的次数是n-1次
如何区分 交换两个变量的代码在内层循
环内 交换两个变量的代码在内层循
环后,外层循环内
例4 某校通过政府招投标中心采购一套多媒体教学设备,有5家单位参加
竞标,竞标价分别为19万、15万、21万、13万、12万元人民币。若采用选
择排序算法对标价从大到小排序,需要进行数据互换的次数是?( )
A.1 B.2 C.3 D.4
解析 原始数据为19、15、21、13、12,第一遍排序19与21互换,得到21,1
5,19,13,12;第二遍排序15与19互换,得到21,19,15,13,12;第三遍排序与第四
遍排序都不需要数据互换。因此总共是2次数据互换。
答案????B
例5 有如下VB程序段:
a(1)=44: a(2)=36: a(3)=58: a(4)=65: a(5)=12
b=0:c=0
For i=1 To 4
k=i
For j=i+1 To 5
If a(j) < a(k) Then k=j: b=b+1
Next j
If k <> i Then
t=a(i): a(i)=a(k): a(k)=t:c=c+1
End If
Next i
Text1.Text=Str(b)+Str(c)
该程序段执行后,文本框Text1显示的内容是?( )
A.53 B.44 C.43 D.34
解析 本题首先要理解变量 b和变量 c的含义。变量 b 表示每遍排序a(j)
值比a(k)小的次数,变量 c 表示数据交换的次数。
第一遍排序 k=1,a(2)第二遍排序 k=2,后面没有数比a(k)小,也没有数据交换。
第三、四遍排序同理,最终b=4,c=3。
答案????C
考向突破
1.冒泡排序算法的变形
标准写法:
For i=1 To n-1 ’n个数需要n-1遍排序
For j=n To i+1 Step -1’从后往前,两两比较,一直到第i+1个数
If a(j) temp=a(j-1):a(j-1)=a(j):a(j)=temp
’小的数在后面,则交换
End If
Next j
Next i
排序思想解析:n个数需要n-1遍排序;每一遍排序都是从最后一个数开始,
两两比较,小的数换到前面,大的数换到后面;第一遍把最小数推到了第一
个位置,第二遍把第二小的数推到了第二个位置,……。因此排序过程中,
数据是从前往后依次排好的。
(1)变形一
For i=1 To n-1
For j=n-1 To i Step -1
If a(j+1) temp=a(j+1):a(j+1)=a(j):a(j)=temp
End If
Next j
Next i
排序思想解析:与标准形唯一的差异就是两个比较项从a(j-1)和a(j)变成a(j+
1)和a(j),因此循环语句也从“For j=n To i+1 Step -1”变成了“For j=n-1
To i Step -1”,而程序在执行过程中没有任何差别,与标准形是完全一样
的。
(2)变形二
For i=1 To n-1
For j=1 To n-i
If a(j+1) temp=a(j+1):a(j+1)=a(j):a(j)=temp
End If
Next j
Next i
排序思想解析:跟标准形不一样的是本代码中每一遍冒泡是从前往后两两
比较的,因此每一遍排序达到的效果是把最大值推到了最后面。第一遍排
序后,最大值就到了最后位置,第二遍后,次大值就到了倒数第二个位置,…
…。因此排序过程中,数据是从后往前依次排好的。
(3)变形三
For i=1 To n-1
For j=i+1 To 2 Step -1
If a(j) temp=a(j):a(j)=a(j-1):a(j-1)=temp
End If
Next j
Next i
排序思想解析:第一遍,2号和1号元素比较并交换;第二遍,从3号元素开始
往前比较并交换,直到1号元素;第三遍,从4号元素开始往前比较并交换,直
到1号元素;……。最后同样达到排序效果。如有5个数:4、3、1、5、2,第
一遍后为:3、4、1、5、2;第二遍后为:1、3、4、5、2;第三遍后为:1、3、
4、5、2;第四遍后为:1、2、3、4、5。需要注意的是,当某一遍排序过程
中没有数据交换时,不代表所有数据已经有序,这点跟标准冒泡排序不同。
(4)变形四
For i=1 To n-1
For j=i+1 To n
If a(j) temp=a(j):a(j)=a(i):a(i)=temp
End If
Next j
Next i
排序思想解析:在第i遍排序中,把第i+1到第n个数依次与a(i)比较,如果比a
(i)小,则交换。它的最大特点是:所有数据跟某个位置上的数去比较。如第
1遍排序时,所有数都跟a(1)比较;第2遍排序时,所有数都跟a(2)比较;以此类
推。排序过程中,数据是从前往后依次排好。
(5)冒泡排序的错误变形
For i=1 To n-1
For j=i To n-1
If a(j+1) temp=a(j+1):a(j+1)=a(j):a(j)=temp
End If
Next j
Next i
错误原因解析:从语句“For j=i To n-1”可看出每一遍的冒泡过程是把最
大值从前往后推,因此排序过程中,是后面的数据先排好,前面的数据是乱
的,但是第i遍的冒泡过程是从第i个数开始的,因此i位置前面的数据不能参
与排序。而后面的数据已经排好,其实是不需要参与排序的。因此要改成
“For j=1 To n-i”。
例1????(2019浙江五校联考)有如下 VB 程序段:
For i = 2 To 4
j = i: flag = False
Do While j >= 2 And Not flag
If a(j) < a(j - 1) Then
t = a(j): a(j) = a(j - 1): a(j - 1) = t
flag = True
End If
j = j - 1
Loop
Next i
数组元素 a(1)到 a(8)的初值依次为“8,2,7,10,6,9,5,3”,则程序运行后,元素
a(1)到 a(8)的值依次为?( )
A.2,7,8,10,6,9,5,3 B.10,8,7,2,6,9,5,3
C.2,3,5,8,6,7,10,9 D.2,3,5,6,7,8,9,10
解析 程序用了第3种冒泡排序的变形,数组中只有前4个数参与了排序,从
小到大升序,后4个数不动,程序运行后元素为:2,7,8,10,6,9,5,3。
答案????A
2.选择排序算法的变形
选择排序的变形考法较少。
①选择排序的变形:
For i=1 To n-1
k=I
For j=n To i+1 Step -1
If a(j) Next j
If k<>i Then
temp=a(i):a(i)=a(k):a(k)=temp
End If
Next i
排序思想解释:在每一遍找最小值时,从前往后的比较改为从后往前的比
较,其他没有变化。
②选择排序的错误变形:
For i=1 To n-1
k=i
For j=i+1 To n
If a(j) Next j
If k<>i Then
temp=a(i):a(i)=a(k):a(k)=temp
End If
Next i
错误原因分析:在选择最小值的过程中把第i+1到第n个数依次与a(i)比较,
“If a(j)与a(i)并未交换。这种方法是找不到最小值的位置的。比如有如下数据:5,
2,1,3,4,第一遍排序i=1时比较过程如下:a(2)=3;a(4)找到最小值所在的位置(最小值位置应该是3),原因就是a(1)的值没有变过。
3.冒泡排序算法的优化
当某一遍排序过程中没有数据交换,说明数据已经有序,无需进行下一遍排序。
代码如下:
Dim flag As Boolean ’flag值为True表示某遍排序中发生过交换
i = 1
flag = True
Do While i <= n - 1 Or flag = True
flag = False
For j = n To i + 1 Step -1
If a(j) < a(j - 1) Then
k = a(j): a(j) = a(j - 1): a(j - 1) = k
flag = True
End If
Next j
i = i + 1
Loop
思想解析:用一个逻辑变量flag标记某一遍排序过程中是否有数据交换,如
果没有,则无需再进行下一遍排序。排序遍数是i-1遍。
另一种写法:
Dim flag As Boolean
For i=1 To n-1
flag=False
For j=n To i+1 Step -1
If a(j) k=a(j):a(j)=a(j-1):a(j-1)=k
flag=True
End If
Next j
If flag=False Then Exit For
Next i
注意这种写法的排序遍数是i,因为程序从中间跳出循环,不执行“Next i”
指令,因此没有多加一次。
4.选择排序算法的优化
在数组的所有元素中同时找出最小和最大的元素,然后将这两个元素分别
与第一个和最后一个元素交换数据,在余下的元素中找出最小和最大数据
的元素,分别与第二个和倒数第二个元素交换数据,以此类推,直到所有元
素的数据按升序排列。代码如下:
p = 1: q = 10
Do While p < q
iMin = p:iMax = p
For i = p + 1 To q
If a(i) < a(iMin) Then iMin = i
If a(i) > a(iMax) Then iMax = i
Next i
t = a(iMin): a(iMin) = a(p): a(p) = t
If iMax = p Then iMax = iMin
t = a(iMax): a(iMax) = a(q): a(q) = t
p = p + 1
q = q - 1
Loop
普通的选择排序是从头到尾一个方向的,优化后的排序是从两端往中间同
时进行,一端从小到大排,另一端从大到小排,变量p和q表示本次排序的范
围(p前和q后的数据已经完成排序)。For语句找出本次排序的最小数a
(iMin)和最大数a(iMax),然后将a(iMin)与a(p)交换,将a(iMax)与a(q)交换。
由于找最小数和最大数时,一开始都假定了p位置上的数是最小值和最大
值,如果本次找到的最大值在p位置,那么当a(p)和a(iMin)交换以后,最大值a
(p)就被换到iMin的位置。因此当iMax=p时,在最小值交换完毕后,再给i-
Max赋值iMin。
5.奇数偶数分开排序、素数合数分开排序、男生女生分开排序等问题
解决这类排序问题的关键点是分析出需要交换的情况有哪些,比如要求奇数在前升序,偶数在后升序,则需要交换的情况有:①小奇数在大奇数的后面;②奇数在偶数的后面;③小偶数在大偶数的后面。
其他类似的排序问题也是同样的思路。
例2????(2018稽阳联谊学校联考,16,3分)有一组正整数,基于冒泡排序对其中
的数进行升序排序。排序后奇数在前,偶数在后。排序示例如下:
实现上述功能的VB程序如下,但加框处代码有误,请改正。
Const n=10
Dim d(1 To n) As Integer
Private Sub Command1_Click()
Dim i As Integer, j As Integer, t As Integer
’读取一组正整数,存储在数组d中,代码略
i=1
Do While i <=n-1
排序前 78 30 64 39 49 4 8 32 18 32
排序后 39 49 83 4 8 18 30 32 64 78
For j=n To i + 1 Step -1
If d(j) Mod 2=d(j - 1) Mod 2 Then
If d(j) > d(i)Then ’(1)
t=d(j): d(j) =d(j - 1): d(j - 1)=t
End If
Else ’(2)
t=d(j): d(j) =d(j - 1): d(j - 1)=t
End If
Next j
i=i + 1
Loop
’依次输出排序后的数据,代码略
End Sub
解析 本题考查冒泡排序的应用。与普通的冒泡排序不同之处在于,本题
把奇数偶数分开从小到大升序排序。(1) If d(j) Mod 2=d(j-1) Mod 2表示d
(j)和d(j-1)的奇偶性相同,此时如果d(j)(j)和d(j-1)的奇偶性不相同,由于奇数偶数分开排序,奇数在前,偶数在后,因
此只有当 d(j-1)是偶数而d(j)是奇数时,才需要交换两数的位置。因此此处
条件设置为ElseIf d(j) Mod 2=1 And d(j-1) Mod 2=0 Then。当d(j-1)是奇数
而d(j)是偶数时是不需要交换的。
答案????(1)d(j) < d(j-1) (2)ElseIf d(j) Mod 2=1 And d(j-1) Mod 2=0 Then或
其他等价的答案
6.隔位排序
偶数位置和奇数位置上的元素分别排序。
例3 有如下程序段:
For i=1 To 9
For j=10 To i+2 Step -1
If a(j) < a(j-2) Then
t=a(j): a(j)=a(j-2): a(j-2)=t
End If
Next j
Next i
数组元素a(1)到a(10)的值依次为“10,9,8,7,6,5,4,3,2,1”,执行该程序段后,
数组元素a(8)中的值为?( )
A.7 B.8 C.9 D.10
解析 本题考查冒泡排序。排序时隔位比较并交换,由“If a(j) < a(j-2)
Then”可知程序实现隔位递增排序,也即奇数位置的数和偶数位置的数分
别从小到大排序,排序结果为“2,1,4,3,6,5,8,7,10,9”,答案为A。
答案????A
考点四????查找算法及程序实现
考向基础
1.顺序查找的基本思想
顺序查找的基本思想是从第一个数据开始,按顺序逐个将数据与查找关键
词进行比较。若某个数据和关键词相等,则查找成功;如果所有的数据都比
较过,没有一个数据和关键词相等,则查找不成功。
2.顺序查找的程序实现
假定在数组a中有n个数据,查找关键词是key。则顺序查找的代码如下:
For i = 1 To n
If a(i)=key Then Exit For
Next i
说明:
①For语句用于遍历整个数据源,从开始位置到结束位置。
②If 语句用于判断当前访问的元素是不是等于关键词。
③一旦某个位置的数据等于关键词,查找任务结束,通常用语句 Exit For 退
出循环。
④退出循环后,如果i的值大于n,则表示未找到。i<=n是找到的情况,i的值
就是关键词所在的位置。
⑤顺序查找不要求数据源是有序的。
3.对分查找的基本思想
在有序的数据列中,首先将要查找的数据与有序数组内处于中间位置的数
据进行比较,如果两者相等,则查找成功;否则根据数组元素的有序性,可确
定该数据在数组的前半部分还是后半部分。在新确定的范围内,继续按上
述方法进行查找,直到找到要查找的数据,则查找成功,或直到子表不存在,
则查找不成功。对分查找要求数据源必须是有序的。
4.对分查找的程序实现
对分查找的代码如下:
key=Text1.Text ’输入关键词
i=1:j=n ’设置首次查找的范围
f=False ’f标志是否已经找到关键词
Do While(i<=j)And Not f’未找到并且查找范围还存在
m=Fix((i+j)/2)’计算中间位置
If key=a(m) Then
f=True ’相等表示找到了,将f设为True
ElseIf key j=m-1 ’下一次查找范围是前半部分
Else
i=m+1 ’下一次查找范围是后半部分
End If
Loop
说明:
①变量i和j记录每一次查找的起始位置和结束位置,变量m记录中间位
置。如果key果key>a(m),则下一次查找的范围是后半部分,因此j不变,i=m+1。
②退出Do循环有两种可能:第一种是f为True,说明已经找到关键词,此时结
束查找;第二种是i>j,查找的起始位置超过结束位置,说明已经找遍数据源,
但是找不到关键词,此时结束查找。
例 7位学生的身高(单位:cm)从高到低依次为:178,177,175,172,170,165,16
2。用对分查找法找到178的过程中,依次被访问到的数据是?( )
A.178 B.172,175,178
C.172,177,178 D.172,175,177,178
解析 本题主要考查对对分查找算法基本思想的理解。将7个数据从1到7
进行编号。第一次访问到的数据是第4个,即172(中间位置m=Fix((1+7)/2)=
4),178>172,因此下一次查找的范围是前半部分,即第1个到第3个。因此第
二次访问的数据应该是第2个,即177(中间位置m=Fix((1+3)/2)=2),178>177,
因此下一次查找的范围是前半部分,即第1个,因此第三次访问的数据是178。
答案????C
考向突破
1.对分查找的效率问题
(1)对分查找的每一次查找,要么找到了目标,结束任务;要么通过比较中间
值与关键词,将下一次的查找范围缩小一半,因此对分查找的效率往往高于
顺序查找。对n个数据查找某个值,最多需要查找Int(log2n)+1次。
(2)找不到关键词的情况下,最后一遍查找时,i=j=m,若key>a(m),则i=m+1;若
key该遍查找结束后会退出循环。
(3)计算中间值位置的式子有多种写法,不同写法,查找过程可能不同。
实例:a(1)到a(10)的值依次为2,7,8,10,12,13,16,18,19,20。
公式 查找过程
m=(i+j)\2
m=Int((i+j)/2)
m=Fix((i+j)/2)
m=Int((i+j+1)/2)
m=Int((i+j)/2+0.5)
m=(i+j)\2
If (i+j) Mod 2=1 Then m=m+1
表中序号表示第几次找到该数。如果“If (i+j) Mod 2=1 Then m=m+
1”写成“If j Mod 2=0 Then m=m+1”,查找过程可能也不同,要根据实际
情况分析。
例1 有一个由4000个整数构成的顺序表,假定表中的元素已经按升序排
列,采用对分查找查找一个元素,则最多需要 ????次比较就能确定是否存在
所查找的元素。?( )
A.11 B.12 C.13 D.14
解析 本题主要考查对分查找的效率问题。根据对分查找的思想方法,每
一次查找的结果要么是找到,要么是找不到,如果找不到则将下一次的查找
范围缩小一半。最差的情况是数据源中没有查找对象,每次查找都将查找
范围缩小一半。规模为n个数的数据源,使用对分查找时,最多经过Int(log
2n)+1次查找。Int(log24000)+1=11+1=12。
答案????B
例2 使用对分查找算法在包含某个有序元素的数组中查找某值,下列说
法错误的是(中括号[]表示向下取整)?( )
A.第一次查找的位置一般是[(1+n)/2]
B.在某连续的三次查找中,不可能是三个相邻的元素
C.如果找不到,那么最少需要查找[log2n]次
D.如果找得到,那么最多需要查找[log2n]+1次
解析 比如5个元素的查找,第一次查找3号位置,第二、三次分别查找1号
和2号位置,三者相邻。对分查找在找不到的情况下,最少也需要[log2n]次
查找,相当于每次都在元素个数较少的一半中查找;选项D刚好相反,每次都
在元素个数较多的一半中查找,但总次数不会超过[log2n]+1次。
答案????B
2.对分查找中各个变量值的变化规律
例3 对数组a 中6 个有序数据“11,22,33,44,55,66”,用下面的程序代码查
找数据“23”,程序执行完毕后,下列各变量值正确的是?( )
Dim a(1 To 6)As Integer
Dim i As Integer,j As Integer,Key As Integer,m As Integer
a(1)= 11:a(2)= 22:a(3)= 33: a(4)= 44:a(5)= 55:a(6)= 66
i= 1:j= 6:p= 0:Key= 23
Do While i<=j
p=p+1
m=(i+j) \2
If j Mod 2=0 Then m=m+1
If a(m)= Key Then Exit Do
If KeyLoop
A.i=5 B.j=4 C.m=3 D.p=2
解析 本题主要考查对分查找。变量p是查找次数。第一次查找,i=1,j=6,
m=(i+j)\2=3,而j Mod 2=0,因此m=m+1=4,23<44,因此j=m-1=3;第二次查找,
m=(i+j)\2=2,23>22因此i=m+1=3;第三次查找,m=(i+j)\2=3,23<33,因此i=m+
1=4,此时i=4,m=3,j=3,p=3,i>j,整个查找过程结束,故C正确。
答案????C
例4 用对分查找算法在含有100个元素的无重复有序数组中查找某元素,
已知第3次查找位置是62号元素,则第4次查找不可能是?( )
A.第43号元素 B.第56号元素
C.第68号元素 D.无需第4次查找
解析 本题考查对分查找算法的原理。100个有序元素中,第1次查找位置
是50,第2次查找位置是25或75,根据题意第3次查找位置是62,说明关键词
大于第50号元素,因此第4次不可能再去找50之前的元素,A不可能。第4次
查找位置是62左右两段区间:[51,61]或[63,74],因此B和C可能。如果第3次
找到的第62号元素就是关键词,则无需第4次查找,因此D可能。
答案????A
3.在有相同项的数据源中找关键字
找到最先出现的位置,代码如下:
i = 1: j = n
Do While i<= j
m = (i + j) \ 2
If key>a(m) Then
i = m + 1
Else
j = m - 1
End If
Loop
说明:当key>a(m)时,往后半部分查找;当keykey=a(m)时,仍然往前半部分查找,因此可以理解成是找到最先出现key的
位置。退出循环时,如果key在序列中,则key等于最后一次的a(m),此时i=j=
m,然后执行j=m-1,因此退出循环后,最先出现key的位置是i。如果key不在
序列中,则退出循环时a(j)上述代码如果将key>a(m)写成key>=a(m),则当key=a(m)时,仍然往后半部
分查找,因此是找到最后出现key的位置,退出循环时,j的位置是最后出现的
位置。
例5????(2018 浙江“七彩阳光 ”联盟期初联考,11,2分)某对分查找算法的
VB 程序段如下:
L = 1: R = 10: Key = 21
Do While L <= R
m = (L + R) \ 2
If a(m) <= Key Then
L = m + 1
Else
R = m - 1
End If
Loop
数组元素 a(1)到 a(10)的值依次为“3,9,21,21,21,21,27,28,39,40”,执行该
程序段,变量 R、a(R)的值分别是?( )
A.2,9 B.3,21 C.6,21 D.7,27
答案????C 本题考查对分查找。由于数列中有相同项,代码If a(m) <= Key
Then L=m+1,也即往后找相同项,直到找到最后一个相同项,因此Key=21
时,找到第6项a(6)。
例6 有序(非降序)数组a有n个元素,用对分查找算法在数组a中查找key值
所在的位置,如果有重复的元素,则显示最早出现该key值的位置。相应的
VB程序段如下:
key =Val(Text1.Text)
i=1:j=n
Do While i <= j
m = (i + j) \2
If a(m) > key Then
j = m-1
Elself a(m) < key Then
i = m + 1
Else
If ???? Then
j =m-1
Else
s = Str(key) + "的起始位置是"+Str(m)
Exit Do
End If
End If
Loop
If i > j Then s ="找不到"+ Str(key)
Label2.Caption=s
要使程序实现上述算法,划线处的语句是?( )
A.a(m -1) = key
B.a(m) = key
C.m-1 >= 0 And a(m-1) = key
D.m-1 >= 0 And a(m) = key
解析 Else这一支隐含的条件是:a(m)=key,因此此处判断的是当a(m)=key
时,是否前面有重复值,同时要保证m-1>=0,如果成立则继续往前找,所以答
案为 C。
答案????C
4.非简单有序序列的对分查找
例7 循环升序数组指的是将一个升序数组循环向右移动若干距离之后变
成的数组。如[1,2,3,4,5]循环右移1位,就成为[5,1,2,3,4],再右移1位,就成为
[4,5,1,2,3],……,其中[5,1,2,3,4]和[4,5,1,2,3]都是循环升序数组。该数组的
特点是:将循环升序数组从中间分开,肯定有一边是有序数组,另外一边是
循环有序数组。小杜研究发现对分查找算法适当优化后也适用于循环升
序数组。在文本框输入被查找的数据Key,查找循环升序数组a中是否有相
同的元素存在。编写的VB程序段如下:
i=1: j = n ’数组a下标从1到n
Key = Val(Text1.Text)
Do While i <= j
m = (i + j) \ 2
If a(m) = Key Then Exit Do
If a(i) < a(m) Then
If ????Then j = m -1 Else i = m + 1
Else
If Key > a(m) And Key <= a(j) Then i = m + 1 Else j = m - 1
End If
Loop
If i <= j Then Text2.Text ="查找成功" Else Text2.Text ="查找失败"
要使程序实现对分查找过程,则方框中的语句是?( )
A.Key >= a(i) And Key < a(m)
B.Key <= a(i) And Key > a(m)
C.Key >= a(i) And Key <= a(j)
D.Key > a(i) And Key <= a(m)
解析 本题考查对分查找。a(i)如果Key处于这一段,并且Key=a(i) And Key答案????A
5.随机数与可能性问题
例8 有以下VB程序段:
i = 1:j=10 : flag=True : cs=0
Key = Int(Rnd()* 10) + 28
Do While i <= j And flag = True
m =(i+ j)\2:cs=cs+l
If a(m)=Key Then
flag=False
ElseIf a(m)< Key Then
i= m+1
Else
j=m-1
End If
Loop
数组元素a(1)到a(10)依次是3,10,17,23,27,30,35,40,45,50,变量cs的值可能
是?( )
A.1 或 2 B.2或3 C.3或4 D.4或5
解析 本题考查对分查找。Key = Int(Rnd() * 10) + 28 即产生[28,37]的随
机整数,cs表示查找次数,10个数,最多查找4次,D错。第1次查找,m=5,a(5)=
27,而Key的范围是[28,37],因此1次是不可能的,A错。第2次查找,m=8,a(8)
=40,因此2次也是不可能的,B错。
答案????C
考点五????递归算法及程序实现
考向基础
1.递归算法的基本思想
函数或过程调用它本身,称为递归。递归算法的基本思想是把规模较大
的、较难解决的问题变成规模较小的、容易解决的同一问题,规模较小的
问题又变成规模更小的问题,当问题小到一定程度时,可以直接得出它的
解,从而得到原来问题的解。即采用“大事化小、小事化无”的基本思
想。比如著名的汉诺塔问题、八皇后问题、斐波那契数列、猴子吃桃问
题等。
在自定义函数中调用自己,这样的函数叫递归函数。
2.递归算法的前提条件
(1)每一步解决问题的方法要一致;
(2)在使用递归策略时,必须有一个明确的结束条件(也称边界条件),称为递
归出口。
示例:年龄问题1
有A、B、C、D四个人,问A的年龄,A说:我的年龄是B的两倍;问B的年龄,B
说:我比C大3岁;问C的年龄,C说:我的年龄是D的两倍减15岁;问D的年龄,D
说:我17岁。请问A的年龄是多少?在这个问题中,虽然有递归出口(D的年
龄),但是每一步解决问题的方法不一致,因此不能使用递归算法。
示例:年龄问题2
有A、B、C、D四个人,问A的年龄,A说:我比B大5岁;问B的年龄,B说:我比
C大5岁;问C的年龄,C说:我比D大5岁;问D的年龄,D说:我17岁。请问A的年
龄是多少?在这个问题中,不但有递归出口(D的年龄),而且每一步解决问题
的方法是相同的(前一人比后一个大5岁),因此可以用递归算法。
3.递归算法的程序实现
求阶乘(n!)的代码。
Private Sub Command1_Click()
Dim n As Integer
Dim m As Long
n = Val(Text1.Text)
m = f(n)
Text2.Text = Str(m)
End Sub
Function f(a As Integer)
If a = 1 Then ’边界条件
f = 1 ’递归出口
Else
f = f(a - 1) * a ’递归调用
End If
End Function
注:递归算法的代码通常比较简洁,但事实上递归算法的运行效率较低。
4.递归算法的设计难点
(1)找到边界条件,设置递归出口。
(2)推导递归公式。如阶乘问题的递归公式是:n!=(n-1)!*n。斐波那契数列
的递归公式是:f(n)=f(n-1)+f(n-2)。
5.递归算法的调用过程
例 有以下程序段:
Dim a(4) As Integer
Private Sub Command1_Click()
Dim s As String
a(1)= 10:a(2)= 30:a(3)= 20:a(4)= 40
s = doit(4)
Label1.Caption = s
End Sub
Function doit(k As Integer) As String
If k = 1 Then
doit = Str(a(1))
Else
doit = doit(k - 1) & Str(a(k))
End If
End Function
程序运行后,标签Label1 中显示的内容是?( )
A.10 20 30 40 B.10 30 20 40
C.40 30 20 10 D.40 20 30 10
解析 本题的递归调用过程如下:
?
答案????B
考点六????算法在数据管理中的应用
考向基础
在VB程序中使用ADO对象,必须先引用ADO的对象库。方法是点击
“工程”菜单中的 “引用”命令,弹出“引用”对话框,勾选ADO选项,如
图所示。
?
说明:不同环境下ADO的版本号可能不同。
1.通过Connection对象连接数据库的一般过程(右边是对应的代码):
?
说明:
①conn是定义的Connection对象的名字,取名规则同变量名。
②ConnectionString是连接字符串,它主要有两个参数:provider是数据库引
擎的名称;data source指定连接的数据库文件, "& App.Path &"表示相对路
径,"mydb.accdb"是数据库文件名。因此该程序连接的是跟工程文件同一
个文件夹下的名为mydb.accdb的一个数据库文件。
③Open和Close是Connection对象的方法,表示打开数据库连接和关闭数据
库连接,使用数据库应该在打开数据库连接后,关闭数据库连接前。
2.通过Recordset对象获取数据表中的数据,步骤如下(右边是对应的代码):
?
说明:
①rs是定义的Recordset对象的名字。
②SELECT语句是结构化查询语言 SQL 中常见的语句,主要用于从数据表
中查询数据。“SELECT*FROM info”表示从“info”这张表中读取所有
的记录(通配符“*”表示所有,即All)。
③“info”是表名。
④打开 Recordset 时,若 Recordset 非空,则默认指向第一条记录。
⑤EOF 属性:若当前记录的位置在最后的记录之后,则返回True,否则返回
False。 EOF 相当于读取记录的结束标志。
⑥rs.Fields(“xh”)返回当前记录中“xh”字段的值。 rs.Fields(0)返回当前
记录中第一个字段的值,如果第一个字段名为“xh”,则 rs.Fields(0) 与rs.
Fields(“xh”) 返回值相同。依此类推,rs.Fields(1)表示返回第2个字段的值。
⑦MoveNext 方法:指针移到下一条记录。
⑧本段代码应该在连接数据库后,关闭数据库前。
下表是Recordset对象的常用方法和属性。
方法 例 说明
Open rs.open 打开记录集
Close rs.close 关闭记录集
Move rs.MoveFirst 移到第一条记录
rs.MoveLast 移到最后一条记录
rs.MoveNext 移到下一条记录
rs.MovePrevious 移到上一条记录
属性 例 说明
BOF If rs.BOF=
True 若当前位置在第一条记录之前,
则BOF值为True,否则为False
EOF Do While Not rs.EOF 若当前位置在最后一条记录之
后,则EOF值为True,否则为False
3.数据库访问的标准代码如下:
?
Dim conn As New ADODB.Connection
Dim rs As New ADODB.Recordset
conn.ConnectionString="provider=Microsoft.ACE.OLEDB.12.0;data source=
"& App.Path & "\computer.accdb "
’数据库文件名为computer.accdb
conn.Open
set rs.ActiveConnection=conn
rs.Open "SELECT * FROM info" ’数据表名为info
n=0
Do While Not rs.EOF
n=n+1
a(n)=rs.Fields(“xh”) ’Fields(“xh”)表示读取“xh”字段的值,此
处等同于Fields(0)
b(n)=rs.Fields(“jg”) ’Fields(“jg”)表示读取“jg”字段的值,此处
等同于Fields(2)
rs.MoveNext
Loop
rs.Close
conn.close
set rs=nothing
set conn=nothing
说明:此段代码连接了数据库文件computer.accdb,并从该数据库的info表中
读取了第1个字段“xh”和第3个字段“jg”的值,依次存储在数组a和数组
b中,变量n是info表的记录数。读取数据后,关闭数据库连接,接下来程序对
数组a和数组b进行后续的处理,如排序、查找等,目前考纲对数据库的操作
只要求连接数据库和读取表中数据并存储到数组中,接下来的数据处理跟
数据库无关,也不要求处理后的数据重新写回数据库中。由于读取数据库
的代码较长,而后续的算法与数据库又毫无关系,限于篇幅关系,考查数据
库的概率较低,到目前为止,只在2016浙江10月选考中考过一次。考生务必
要掌握读取数据的标准代码,以及几个容易考到的考点:从代码中分析数据
库文件名、表名;读取记录时,循环结束条件的设置;读完一条记录后,如何
指向下一条记录;关闭数据库连接等。目前一种新的考法,可能是用选择题
形式考本段代码。
专题六 算法的程序实现
探考情 悟真题
【考情探究】
考点 考试内容 考试要求 5年考情 预测热度
考题示例 考向 难度
解析算 法及程 序实现 解析算法的思想方法 c 2016浙江4月选考,14,5分; 2017浙江4月选考,14,5分; 2019浙江1月学考,11,5分; 2019浙江6月学考,11,5分 进制转换、质数问题及其他数论问题、数学猜想等 ★☆☆ ★★☆
解析算法的程序实现
枚举算 法及程 序实现 枚举算法的思想方法 c 2016浙江10月选考,14,5分; 2017浙江11月选考,14,5分; 2018浙江4月选考,14,5分; 2018浙江11月选考,14,5分 字符串处理问题是考试热点,如在字符串中利用逗号、空格、数字等特殊符号,完成一些统计或计算功能 ★★☆ ★★★
枚举算法的程序实现
排序算 法及程 序实现 冒泡排序的思想方法 c 2015浙江10月选考,16,4分; 2016浙江4月选考,11,2分; 2016浙江10月选考,16,3分; 2017浙江11月选考,16,3分; 2019浙江4月选考,16,3分 排序算法优化;冒泡排序变形,如双向排序、奇偶分开排序、素数合数分开排序、去重复数排序等 ★★★ ★★★
冒泡排序的程序实现
选择排序的思想方法 c 2017浙江4月选考,12,2分; 2018浙江4月选考,16,3分 排序变形,如双向排序、奇偶分开排序、素数合数分开排序等 ★★☆ ★★☆
选择排序的程序实现
查找算 法及程 序实现 顺序查找的思想方法 c 2017浙江4月选考,16,3分 顺序查找比较简单,一般不单独考,会结合其他知识点,比如在数列中插入数、删除数列中的重复数、查找替换等 ★★☆ ★★☆
顺序查找的程序实现
查找算 法及程 序实现 对分查找的思想方法 c 2015浙江10月选考,11,2分; 2016浙江4月选考,12,2分; 2016浙江10月选考,12,2分; 2017浙江4月选考,11,2分; 2017浙江11月选考,12,2分; 2018浙江4月选考,12,2分; 2018浙江11月选考,16,3分; 2019浙江4月选考,12,2分 一类题是考查对分查找的运用:如查找次数、查找中各个变量值的变化;另一类题是将数据源序列由单一的从小到大变成如奇偶分开数列、循环有序数列、左右交替上升序列等,此类数列往往是分成前后两个有序数列,查找过程中,对分的主要思想不变,无非是增加了一些条件设置 ★★★ ★★★
对分查找的程序实现
递归算 法及程 序实现 递归算法的思想方法 b 递归算法本质上是自定义函数的应用,到目前为止,未在真题中出现 ★☆☆ ☆☆☆
递归算法的程序实现
算法在 数据管 理中的 应用 通过Connection对象连接数据库 a 2016浙江10月选考,17,6分 目前关于数据库一种新的考法是选择题形式,只要掌握连接数据库并读取数据库的标准代码即可。此外要学会分析数组变量中存储的数据内容和类型,并掌握数组下标的灵活运用 ★★☆ ★☆☆
通过Recordset对象读取数据表中的数据 a
算法在数据管理中的应用 c
分析解读 本专题主要考查几大算法的思想方法和程序实现,包括枚举、解析、排序、查找、递归,题型有选择题和非选择题。选择题为第11和12题、非选择题为第15和16题,这几题考查排序算法与对分查找的频度较高,难度为中等或较难。
纵观几次真题,程序题有逐年加难的趋势。试题中对于算法的考查不再局限于算法的基本形,而是在基本形的基础上做了许多变形,比如冒泡排序的几种变式,对分查找的变式等。还有一种变化是,在基本形的基础上增加程序的功能,比如对排序算法进行改进从而提高排序的效率、记录排序中数据的移动过程,利用查找算法查找并删除数列中的重复数据等。
还有一个重要变化是,最近几次的真题对几个经典算法的考查相对弱化,开始加强对数组的考查。往往在选择题最后2个题中有一个是考查数组的综合运用,该题往往难度较大。一般选择题中保留一题考查排序或对分查找,考对分查找的概率较高。
数据库程序题一般难度不大,可能是篇幅太长的缘故,大题中考数据库的概率并不高,有很多题都是一句话带过:从数据库中读取了什么数据存储到什么数组变量中。读取数据并存储到数组变量中后,对数组的综合运用相对难度大一些,要学会分析题中各数组变量的作用,分别存储了什么类型的数据,以及数组下标的灵活运用。目前数据库可能会有一种新的考法,以选择题的形式,考查连接数据库和读取数据库的基本方法和代码。要掌握从代码中分析数据库文件的名称、数据表的名称,以及数据表中字段的读取方法、记录集的移动方法等基础知识。
破考点 练考向
【考点集训】
考点一 解析算法及程序实现
1.(2018宁波“十校联考”,16,3分)在VB的算术运算中,最大的实数类型Double有效位数也只有15位。为了实现除法运算保留任意位数,小明根据除法原理,编写了如下程序,功能如下:在文本框Text1中输入被除数(正整数),在文本框Text2中输入除数(正整数),在文本框Text3中输入保留小数位数,单击按钮Command1,在标签Label1中显示除法运算的商。程序运行界面如图所示,但加框处代码有错,请改正。
Private Sub Command1_Click()
Dim x, y As Integer
Dim n As Integer
Dim s As String
x= Val(Text1.Text): y = Val(Text2.Text)
n= Val(Text3.Text)
s = s + Str(x \ y)
s = s + "."
k = x Mod y
For i = 1 To n
x =x+k * 10 ’(1)
s=Str(x \ y) ’(2)
k = x Mod y
Next i
Label1.Caption = "商为:" + s
End Sub
答案 (1) x=k*10 (2) s=s+Str(x\y)
2.(2018浙江十校联盟选考适应性考试,14,5分)编写“二进制数转换为十六进制数”程序,实现如下功能:在文本框 Text1中输入一个二进制数,单击“转换”按钮 Command1,将二进制数转换为十六进制数并在文本框 Text2 中显示。程序运行界面如图所示。
(1)设计如图所示的程序界面,至少要使用 个类(填数字)。?
(2)实现上述功能的VB程序如下,请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim s1 As String, s2 As String
Dim i As Integer, x As Integer
Const code = "0123456789ABCDEF"
s1 = Text1.Text : s2 = ""
Do While Len(s1) Mod 4 <> 0
s1 = "0" + s1
Loop
x = 0: i =1
Do While i <= Len(s1)
x = x*2+Val(Mid(s1,i,1))
i=i+1
If ① Then?
s2 = s2 +Mid(code,x+1,1)
② ?
End If
Loop
Text2.Text = s2
End Sub
(3)若文本框 Text1 中输入的内容为“101101”,单击“转换”按钮后,文本框 Text2 中显示的内容是 。?
答案 (1)4 (2)① i Mod 4=1 或(i-1) Mod 4=0 (或其他等价答案) ② x=0 (3)2D
考点二 枚举算法及程序实现
1.(2019宁波新高考适应性考试)得分问题:给出一个由A和X组成的字符串,统计字符的得分之和。每个A的得分为已经连续出现的A的个数,X得分为0。例如,AAXXAXXAAA的得分为1+2+0+0+1+0+0+1+2+3。现编写一个程序,功能如下:在文本框Text1中输入字符串,单击“统计”按钮Cmd_Sta后,程序计算得分,结果显示在Text2中。
(1)Cmd_Sta对象属于 类(单选,填字母:A.Form / B.Label / C.TextBox /D.CommandButton)。?
(2)实现上述功能的VB程序如下,请在程序划线处填入合适的代码。
Private Sub Cmd_Sta_Click()
Dim sum As Integer, i As Integer, cnt As Integer
Dim c As String, sz As String
sz = Text1.Text
cnt = 0: sum = 0
For i = 1 To Len(sz)
① ?
If c = "A" Then
② ?
sum = sum + cnt
Else
cnt = 0
End If
Next i
Text2.Text = Str(sum)
End Sub
(3)运行该程序,输入数据如上图所示,程序执行到循环结束时,变量cnt的值为 。?
答案 (1) D (2)① c = Mid(sz,i,1) 或 c=Mid(Text1.Text,i,1) ②cnt = cnt + 1 (3)3
2.珠心算是在大脑中以算盘表象作为载体,运用珠算法则所进行的计算。某学校的珠心算老师采用一种快速考查珠心算加法能力的测验方法。他随机给出一个正整数集合,集合中的数各不相同,然后要求学生回答:其中共有多少个数恰好等于集合中另外两个(不同的)数之和?例如对于集合{1,2,3,4},一共有2个数等于集合中另外两个数之和,它们是3、4(4=3+1,3=2+1)。将上述算法编写成程序,其功能如下:程序运行时产生n个范围在[1,100]内的不同的随机整数存储在数组a中,并在列表框List1中显示。单击按钮Command1后,在标签Label1上输出结果,如图所示。
(1)对于集合{1,2,3,4,5,6},一共有 个数等于集合中另外两个数之和。?
(2)实现上述功能的VB程序如下,请在划线处填入合适代码。
Const n=12
Dim a(1 To n) As Integer
Dim flag(1 To 100) As Boolean
Private Sub Form_Load()
Dim i As Integer, t As Integer
For i=1 To 100
flag(i)=False
Next i
i=1
Do While i <=n
t=Int(Rnd * 100)+1
If Not flag(t) Then
① ?
List1.AddItem Str(t)
flag(t)=True
i=i+1
End If
Loop
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, ans As Integer
ans=0
For i=1 To n
For j=i+1 To n
If a(i)+a(j) <=100 Then
If ② Then ?
ans=ans+1
flag(a(i)+a(j))=False
End If
③ ?
Next j
Next i
Label1.Caption="共有"+Str(ans)+"个数!"
End Sub
答案 (1)4 (2)①a(i)=t ②flag(a(i)+a(j))或flag(a(i)+a(j))=True ③End If
考点三 排序算法及程序实现
1.(2019金华十校第一学期调研考试,11,2分)有一个数组,采用冒泡排序,第一遍排序后的结果为3,18,5,35,8,9,11,13,32,那么该数组的原始顺序不可能是( )
A.18,5,35,8,9,11,13,32,3
B.18,5,35,8,9,11,3,13,32
C.18,5,35,3,8,9,11,13,32
D.3,18,5,35,13,11,32,8,9
答案 D
2.(2020届名校协作体信息技术试题)某排序算法的VB程序段如下:
k = 1
For i = 1 To 2
For j = 1 To 6 - 2 * i
If k * a(j) < k * a(j + 2) Then
t = a(j): a(j) = a(j + 2): a(j + 2) = t
End If
k = -k
Next j
Next i
数组元素a(1)到a(6)的初始值依次为“15,11,58,38,26,9”,该程序段执行后,数组元素a(1)到a(6) 的值分别为 ( )
A.58,9,26,11,15,38 B.58,38,26,11,15,9
C.15,38,26,11,58,9 D.58,38,26,15,11,9
答案 A
3.(2018温州新力量联盟期末)有如下 VB 程序段:
Const n = 8
Dim a(1 To n) As Integer
For i = 1 To n
a(i) = Int(Rnd * 20)
Next i
x = n \ 2
For i = x To 2 Step -1
For j = 1 To i - 1
If a(j) < a(i) Then
t = a(j): a(j) = a(i): a(i) = t
End If
Next j
Next i
i = n
Do While i > x + 1
k = i
For j = i - 1 To x + 1 Step -1
If a(j) > a(k) Then k = j
Next j
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
End If
i = i - 1
Loop
执行完这段代码后,数组 a 中各个元素的值可能的是( )
A.2,8,9,11,16,16,7,3 B.19,19,18,12,9,8,6,6
C.20,17,10,10,5,11,13,16 D.14,11,10,5,0,6,15,15
答案 D
4.(2018宁波“十校联考”期末)若有以下数据:64, 57, 22, 96, 71,分别存储在a(1)至a(5)中,经过以下程序段处理后的数据依次为( )
Dim a(1 To 6) As Integer
s = 0
For i = 1 To 5
If a(i) Mod 2 = 1 Then s = s + 1
Next i
For i = 1 To 4
If a(i) Mod 2 = 0 Then
For j = 5 To i + 1 Step -1
If a(j) Mod 2 = 1 Then
a(6) = a(i): a(i) = a(j): a(j) = a(6): Exit For
End If
Next j
End If
Next i
For i = s + 2 To 5
k = i - 1
For j = i To 5
If a(k) > a(j) Then k = j
Next j
If k <> i - 1 Then
a(6) = a(i - 1): a(i - 1) = a(k): a(k) = a(6)
End If
Next i
A.22, 57, 64, 71, 96 B.71, 57, 22, 96, 64
C.71, 57, 22, 64, 96 D.57, 71, 22, 64, 96
答案 C
考点四 查找算法及程序实现
1.(2019浙江“七彩阳光”联盟期初联考)某对分查找算法部分代码如下:
i = 1: j = 1000: flag = True: p = 0
key = Val(Text1.Text)
Do While i <= j And flag
m = (i + j) \2
p = p + 1
If a(m) = key Then flag = False
If a(m) > key Then j = m -1 Else i = m + 1
Loop
数组元素a(1)到a(1000)中存放着升序排列的数据。下列说法正确的是( )
A.若key的值小于a(1),则执行该段程序后,变量j的值等于1
B.若key的值等于a(1),则执行该段程序后,变量p的值等于10
C.若key的值等于a(1000),则执行该段程序后,变量i的值等于1001
D.无论key的值是否在数组a中,执行该段程序后,变量i的值均不可能等于m
答案 C
2.(2018温州九校联考,12,2分)有如下 VB 程序段:
i=1:j=10:p=0
f=False
k=Int(Rnd*100)+0.5
Do While i<=j And Not f
m=Fix((i+j)/2+0.5)
If k=a(m) Then
f=True
ElseIf k j=m-1:p=p+1
Else
i=m+1:p=p-1
End If
Loop
Label1.Caption=Str(p)
数组元素a(1)到a(10)的值依次为“5,16,22,28,35,43,52,67,78,89”,执行该程序段后,Label1的值不可能是( )
A.-3 B.-1 C.1 D.3
答案 D
3.某对分查找算法的VB程序段如下:
k=Val(Text1.Text)
i=1: j=6: Label1.Caption="": f=False
Do While i <=j And Not f
m=(i+j) \ 2
If a(m)=k Then f=True
If a(m) > a(i) Then
If a(i) <=k And k < a(m) Then j=m-1 Else i=i+1
Else
If a(m) < k And k <=a(j) Then i=i+1 Else j=j-1
End If
Label1.Caption=Label1.Caption+Str(a(m))
Loop
数组元素a(1)到a(6)的值依次为“58,66,72,24,35,40”,在文本框Text1中输入的值为35,执行该程序段,标签Label1中显示的值是( )
A.72 35 B.24 35
C.72 24 35 D.72 24 24 35
答案 D
4.(2019五校联考)某对分查找算法的 VB 程序段如下:
Key = Int(Rnd * 49) * 2 + 1
s = 0: i = 1: j = 10
Do While i <= j
m = (i + j) \ 2
If Key = a(m) Then Exit Do
If Key < a(m) Then
j = m - 1: s = 2 * s
Else
i = m + 1: s = 2 * s + 1
End If
Loop
数组 a(1)到 a(10)的值依次为“2,6,7,15,20,24,27,43,52,63”,执行该程序段后,s 的值不可能为( )
A.2 B.3 C.5 D.15
答案 A
考点五 递归算法及程序实现
1.某同学用VB编码如下程序:
Private Sub Command1_Click()
Dim k As Integer, a As Integer, b As Integer
a = Val (Text1.Text) : b = Val (Text2.Text)
Label1.Caption = trans(a, b)
End Sub
Function trans(m As Integer, n As Integer) As String
If m<> 0 Then
r =m Mod n
trans = trans (m \ n, n) + Str(r)
Else
trans="0"
End If
End Function
程序运行时,在文本框Text1和Text2中分别输入11和2,则Label1中的输出结果是( )
A.01011 B.1011 C.01101 D.11010
答案 A
2. 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶, 探究共有多少种不同的走法。
(1)完善程序:
Private Sub Command1_Click()
Dim n As Integer
n = Val(Text1.Text)
Text2.Text = Str(f(n))
End Sub
Function f(a As Integer)
If a = 1 Then
f = 1
ElseIf a = 2 Then
f = ① ?
Else
f = ② ?
End If
End Function
(2)若有10阶台阶,共有 种走法。?
答案 (1)①2 ②f(a - 1) + f(a - 2) (2)89
考点六 算法在数据管理中的应用
小林编写了一个统计高三16个班级选考技术人数占比的VB程序。运行界面如图所示,窗体加载时,从数据库中(其中“选考三”字段中存储了“技术”选考信息)调用数据,统计各班选考技术的人数占比,并在列表框List1中显示“班级”和“选技术占比”。单击“排序”按钮Command1,数据按选技术占比降序排序,在List2中显示排序结果。
实现上述功能的VB程序如下,请回答下列问题:
(1)分析程序,可知调用的数据表的名称为 。?
(2)请在划线处填入合适的代码。
Dim n As Integer, i As Integer, j As Integer’变量n用于统计学生总数
Dim rate(1 To 16) As Integer, num(1 To 16) As Integer, class (1 To 16) As Integer
Dim tech(1 To 50) As Integer, cinfo(1 To 5000) As Integer, subj(1 To 5000) As String
Private Sub Form_Load()
Dim conn As New ADODB.Connection, rs As New ADODB.Recordset
conn.Connectionstring = "Provider = Microsoft.ACE.OLEDB.12.0;DATA Source="& App.Path &"\stuimfo.accdb"
conn.Open
Set rs.ActiveConnection = conn
rs.Open "SELECT * FROM xkqk"
’此处代码略,实现将每个学生班级存储到数组cinfo中,选考三科目存储到数组subj中
For i = 1 To n
① ’统计各班人数存储到数组num中,num(1)存储1班的人数?
Next i
For i = 1 To 16
class(i) = i
For j = 1 To n
If class(cinfo(j)) = i Then
If subj(j)="技术"Then ② ?
End If
Next j
rate(i) = tech(i) / num(i) * 100
List1.AddItem ads(class(i), 3) +" "+ ads(rate(i), 7) + "%"
Next i
End Sub
Private Sub Command1_Click()
Dim i As Integer, t As Integer, s As Integer
For i = 1 To 15
For j = 16 To i + 1 Step -1
If ③ Then?
t=rate(j) : rate(j) = rate(j-1) : rate(j-1) = t
s=class(j): class(j)=class(j-1):class(j-1)=s
End If
Next j
Next i
List2.AddItem "班级" + " " + "选技术占比"
For i = 1 To 16
List2.AddItem Str(class(i))+ " " + Str(rate(i)) + "%"
Next i
End Sub
答案 (1)xkqk (2)①num(cinfo(i))=num(cinfo(i))+1
② tech(i)=tech(i)+1 ③ rate(j)>rate(j - 1)
【五年高考】
考点一 解析算法及程序实现
2015—2019年真题·提升题组
1.(2019浙江6月学考,11,5分)小宇为选定班级参赛作品编了一个VB程序,设计如下:在文本框Text1中输入5位评委对3个作品的评分依据(评委对作品的评分数据由3位十进制数组成,第1位对应作品编号,第2、3位对应作品得分,分值范围为[60,99]。如“275”表示2号作品得分75)。单击“计分”按钮后,在标签Label1中输出3个作品的平均分,在Label2中输出参赛的作品(选择最高平均分作品参赛,若最高平均分存在并列,则从并列作品中随机抽取)。程序运行界面如图所示。
(1)“计分”按钮的对象名为 。?
(2)程序部分代码如下,请在划线处填入合适的代码。
Private Sub jf_Click()
Dim s As String, d As String, i As Integer
Dim f1 As Single, f2 As Single, f3 As Single
s = Text1.Text
i = 1
Do While ① ?
d = Mid(s, i, 3)
If Mid(d, 1, 1) = "1" Then
f1 = f1 + Val(Mid(d, 2, 2))
ElseIf Mid(d, 1, 1) = "2" Then
f2 = f2 + Val(Mid(d, 2, 2))
Else
f3 = f3 + Val(Mid(d, 2, 2))
End If
② ?
Loop
Label1.Caption = "作品1平均分为:"+Str(f1/5)+"作品2平均分为:"+Str(f2/5)+"作品3平均分为:"+Str(f3/5)
’以下省略“处理并列最高平均分,并在 Label2 中输出选取的参赛作品”的代码
End Sub
(3)运行该程序时,在文本框 Text1 中以不同的顺序输入原评分数据:380/295/283/170/180/385/372/285/190/180/390/384/272/170/276,单击“计分”按钮,则 Label1中显示的结果 (选填:会/不会)发生改变。?
答案 (1)jf (2)①i<=Len(s) 或 i
2.(2019浙江1月学考,11,5分)小红编写了一个将 5 位以内的十六进制正整数转化成十进制数的 VB 程序,功能如下:在文本框 Text1 中输入一个十六进制正整数,单击“转换”按钮 Command1,在标签 Label3 中显示结果。程序运行界面如图所示。
(1)要使窗体 Form1 标题显示“数制转换”,则需修改窗体的 (单选,填字母:A.Font/B.Caption/C.BackColor)属性。?
(2)实现上述功能的 VB 程序如下,请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim x As String, ch As String
Dim flag As Boolean, i As Integer, result As Long
x = ① ?
i = 1
result = 0
flag = True
ch = Mid(x, 1, 1)
Do While i <= Len(x) And flag = True
If ch >= "0" And ch <= "9" Then
result = result * 16 + Val(ch)
ElseIf ch >= "A" And ch <= "Z" Then
result = result * 16 + (Asc(ch) - Asc("A") + 10)
ElseIf ch >= "a" And ch <= "z" Then
result = result * 16 + (Asc(ch) - Asc("a") + 10)
Else
flag = False
End If
i = i + 1
ch = ② ?
Loop
If flag = True Then
Label3.Caption = Str(result)
Else
Label3.Caption = "输入错误"
End If
End Sub
(3)若在文本框 Text1 中输入 5+9,单击“转换”按钮后,标签Label3 中显示的内容是 (单选,填字母:A.14 / B.E / C.输入错误)。?
答案 (1)B (2)①Text1.Text或其他等价表达式 ②Mid (x,i,1)或 Mid(Text1.Text,i,1)或其他等价表达式 (3)C
3.(2017浙江4月选考,14,5分)奇偶校验是一种校验数据传输正确性的方法。其中奇校验方法:统计二进制数据的数位中“1”的个数,若个数为奇数,则校验位值为0,否则校验位值为1。小李编写了一个计算奇校验位值的VB程序,功能如下:在文本框Text1中输入1~255间的十进制待校验数,单击“计算”按钮Command1后,在文本框Text2中显示该数对应的二进制值,并在标签Label3中显示该数的校验位值。程序运行界面如图所示。
(1)在设计程序界面时,要清空文本框中的显示内容,应修改该文本框中的 属性。?
(2)实现上述功能的VB程序如下,请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim a As Integer, s As String
Dim n As Integer, t As Integer, v As Integer
n = Val(Text1.Text)
t = 0
s = ""
Do While n > 0
a = n Mod 2
n = n \ 2
t = ① ?
s = Str(a) + s
Loop
v = t Mod 2
Text2.Text = s
Label3.Caption = "校验位值:" + ② ?
End Sub
(3)运行该程序,在文本框Text1中输入22,单击“计算”按钮,则显示的校验位值是 。?
答案 (1)Text (2)①t+a ②Str(1-v) (3)0
考点二 枚举算法及程序实现
2015—2019年真题·提升题组
1.(2018 浙江 11 月选考,14,5 分)在平面坐标系中,给定一组有序的点。从原点出发,依次用线段连接这些点,构成一条折线。要求编写一个“计算折线长度”的程序,功能如下:在文本框Text1中依次输入这些点的坐标值(数据都用逗号分隔并以逗号结尾),单击“计算”按钮Cmd后,程序计算这条折线的长度,结果显示在Label1中。例如,三个点的坐标为(5,10),(8,12),(6,17),输入格式如图所示。
(1)Cmd对象属于 类(单选,填字母:A.Form / B.Label/C.TextBox/D.CommandButton)。?
(2)实现上述功能的VB程序如下,请在划线处填入合适的代码。
Private Sub Cmd_Click()
Dim i As Integer,j As Integer,k As Integer
Dim x1 As Single,y1 As Single,x2 As Single,y2 As Single
Dim d As Single,Totald As Single,v As Single,s As String
s= ① ?
x1=0∶y1=0 ’出发点为坐标原点
k=1∶j=1∶Totald=0
For i=1 To Len(s)
If Mid(s,i,1)="," Then
v=Val(Mid(s,j,i-j))’提取坐标值,保存在变量v中
j=i+1
If ② Then?
x2=v
Else
y2=v
d=Sqr((x2-x1)^2+(y2-y1)^2)
Totald=Totald+d
x1=x2:y1=y2
End If
k=k+1
End If
Next i
Label1.Caption=Str(Totald)
End Sub
(3)运行该程序,输入题干中的数据,程序执行到循环结束时,变量k为 。?
答案 (1)D (2)①Text1.Text ②k Mod 2=1 (3)7
2.(2018浙江4月选考,14,5分)某种编码以4位二进制码为一组,每组前两位表示方向,后两位表示距离。编写一个程序,将编码翻译成方向和距离,距离值为每组编码后两位二进制码转换为十进制数的值。具体功能如下:在文本框Text1中输入连续多组编码,单击“翻译”按钮Command1,结果显示在列表框List1中。程序运行界面如图所示。
(1)要使程序运行时,文本框Text1的Width属性值为2018,可在Form_Load事件过程中添加语句 (单选,填字母:A.Width=2018/B.Text1.Width=2018/C.Width.Text1=2018)。?
(2)实现上述功能的 VB 程序如下,请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim s As String, c As String, d As String
Dim n As Integer, b1 As Integer, b2 As Integer, v As Integer, i As Integer
s = Text1.Text: n = Len(s): i = 1
Do While i <= n
c = Mid(s, i, 2)
If c = "00" Then
d = "东"
ElseIf c = "01" Then
d = "南"
ElseIf c = "10" Then
d = "西"
Else
d = "北"
End If
b1 = Val(Mid(s, i + 2, 1))
b2 = Val(Mid(s, i + 3, 1))
v= ① ?
List1.AddItem d + " " + Str(v)
② ?
Loop
End Sub
(3)若文本框 Text1 中输入的内容为“1111”,单击“翻译”按钮,列表框 List1 中显示的内容是 。?
答案 (1)B (2)①b1*2+b2 ②i=i+4 (3)北 3
3.(2017 浙江 11 月选考,14,5 分)编写“字符串生成”程序,实现如下功能:在文本框Text1 中(字符位置)输入多个正整数(以“,”为分隔符和结束符),单击“生成”按钮 Command1,程序以这些整数为位置信息,依次从文本框 Text2 中(字典内容)提取字符并连接成字符串,最后将字符串显示在标签 Label1 中(生成内容)。程序运行界面如图所示。
(1)要使程序运行时,窗体Form1标题显示“字符串生成”,可在Form_Load事件过程中添加语句 (单选,填字母:A.Form1="字符串生成"/ B.Form1.Text="字符串生成"/ C.Form1.Caption="字符串生成")。?
(2)实现上述功能的VB程序如下,请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim s As String, t As String, c As String
Dim i As Integer, p As Integer
s="":t=""
For i=1 To Len(Text1.Text)
c=Mid(Text1.Text, i, 1)
If c="," Then
p=Val(t)
s=s+Mid(Text2.Text, p, 1)
t=""
Else
t= ① ?
End If
Next i
Label1.Caption= ② ?
End Sub
(3)若文本框Text1中输入内容的结束符缺失(即输入内容为1,18,9,9),单击“生成”按钮后,标签Label1中显示的内容是 。?
答案 (1)C (2)①t+c(或 t&c) ②s (3)pas
(2)①变量t(字符串类型)存储字符位置。程序通过Mid函数将文本框Text1中的字符逐个读取并判断,如果所取字符是逗号,则表示一个字符位置已经读取完整,将变量t转换成数值,然后去字典里取对应字符,把它连接到s后面;如果所取字符不是逗号,表示字符位置尚未结束,则将该字符连接到t后面。②在Label1中输出最后的结果s。
(3)由于程序中将位置转换成字典中字符的指令是在条件c=“,”的情况下才执行的,因此输入“1,18,9,9”,前三个位置会从字典中取出字符“pas”。由于最后一个“9”缺失了“,”,因此不会从字典中取字符。
考点三 排序算法及程序实现
2015—2019年真题·提升题组
1.(2017浙江4月选考,12,2分)小赵对选择排序算法进行了如下改进:在数组的所有元素中找出最小和最大数据的元素,然后将这两个元素分别与第一个和最后一个元素交换数据,在余下的元素中找出最小和最大数据的元素,分别与第二个和倒数第二个元素交换数据,以此类推,直到所有元素的数据按升序排列。小赵编写的VB程序段如下:
p = 1: q = 10
Do While p < q
iMin = p:iMax = p
For i = p + 1 To q
If a(i) < a(iMin) Then iMin = i
If a(i) > a(iMax) Then iMax = i
Next i
t = a(iMin): a(iMin) = a(p): a(p) = t
t = a(iMax): a(iMax) = a(q): a(q) = t
p = p + 1
q = q - 1
Loop
要使程序实现上述算法思想,则方框中的语句是( )
A.If iMax = p Then iMax = iMin
B.If iMin = p Then iMin = iMax
C.If iMax = p Then iMin = iMax
D.If iMin = p Then iMax = iMin
答案 A
2.(2016浙江4月选考,11,2分)有如下程序段:
For i = 1 To 2
For j = 5 To i + 1 Step -1
If a(j) > a(i) Then
t = a(j): a(j) = a(i): a(i) = t
End If
Next j
Next i
数组元素a(1)到a(5)的值依次为“33,24,45,16,77”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为( )
A.77,45,33,16,24 B.77,33,45,16,24
C.77,24,45,16,33 D.77,45,33,24,16
答案 A
3.(2019浙江4月选考,16,3分)小明基于冒泡排序思想设计了一个改进的排序算法。该算法先用冒泡法将数组a中奇数位置的元素、偶数位置的元素分别进行排序,然后再进行后续处理。算法的VB程序段如下,但加框处代码有错,请改正。
’待排序数据存储在数组a中(a(1)~ a(n)),要求升序排列
For i = 1 To (n - 1) \ 2
For j = 1 To n - i * 2
If a(j) > a(j + 1)Then ’(1)
t = a(j): a(j) = a(j + 2): a(j + 2) = t
End If
Next j
Next i
For i = 1 To n \ 2
j = 2 * i - 1
If a(j) > a(j + 1) Then t = a(j): a(j) = a(j + 1): a(j + 1) = t
Next i
For i =1 To n Step 2 ’(2)
t = a(i): j = i - 1
Do While t < a(j)
a(j + 1) = a(j): j = j - 1
Loop
a(j + 1) = t
Next i
答案 (1) a(j)>a(j+2) 或 a(j)>=a(j+2) 或其他等价表达式 (2)3 To n
4.(2018浙江4月选考,16,3分)有一组正整数,要求仅对其中的素数进行升序排序。排序后素数在前,非素数在后。排序示例如下。
排序前 86 71 5 41 81 79 37 89
排序后 5 37 41 71 79 89 86 81
实现上述功能的VB代码如下,但加框处有错,请改正。
Const n=8
Dim a(1 To n) As Integer
Private Sub Command1_Click()
Dim i As Integer, j As Integer, k As Integer, t As Integer
Dim flag As Boolean
’读取一组正整数,存储在数组a中,代码略
For i = 1 To n - 1
k = 1 ’(1)
If IsPrime(a(k)) Then flag = True Else flag = False
For j = i + 1 To n
If IsPrime(a(j)) Then
If a(j) < a(k) Then ’(2)
k=j
flag = True
End If
End If
Next j
If k <> i Then
t=a(k): a(k) = a(i):a(i) = t
End If
If Not flag Then Exit For ’Exit For表示退出循环
Next i
’依次输出排序后的数据。代码略
End Sub
Function IsPrime(m As Integer) As Boolean
’本函数判断m 是不是素数:是素数返回值为True,不是素数返回值为False
’代码略
End Function
答案 (1) k=i (2)a(j)5.(2017浙江11月选考,16,3分)小李基于冒泡排序算法编写了一个VB程序,功能如下:在文本框Text1中显示排序前的数据,单击“排序”按钮Command1,在文本框Text2中显示剔除重复数据后的升序排序结果。程序运行界面如图所示。
实现上述功能的VB程序如下,但加框处代码有错,请改正。
Const n = 10
Dim a(1 To n) As Integer
Private Sub Command1_Click()
Dim i As Integer, j As Integer, t As Integer
Dim bottom As Integer
’获取排序前数据依次存储在数组a中,并在文本框Text1中显示。代码略
bottom = n
i = 1
Do While i <= bottom - 1
For j = bottom To i + 1 Step -1
If a(j) < a(i) Then ’(1)
t = a(j): a(j) = a(j - 1): a(j - 1) = t
ElseIf a(j) = a(j - 1) Then ’相邻两个数据相等,进行剔除处理
a(bottom)=a(j) ’(2)
bottom = bottom - 1
End If
Next j
i = i + 1
Loop
Text2.Text = " "
For i = 1 To bottom
Text2.Text = Text2.Text + Str(a(i))
Next i
End Sub
答案 (1)a(j)a(j))
(2)a(j)= a(bottom)
6.(2016浙江10月选考,16,3分)小吴为了研究冒泡排序过程中数据的“移动”情况,编写了一个VB程序,功能如下:在列表框List1中显示排序前数据(存储在数组a中),在文本框Text1中输入初始位置(即下标值),单击“排序”按钮Command1后,在标签Label1中显示指定初始位置的数据在排序过程中的位置变化情况,排序后的数据显示在列表框List2中。程序运行界面如图所示。
实现上述功能的VB程序如下,但加框处代码有错,请改正。
Dim a(1 To 8) As Integer
Dim n As Integer
Private Sub Form_Load()
a(1) = 30: a(2) = 47: a(3) = 30: a(4) = 72
a(5) = 70: a(6) = 23: a(7) = 99: a(8) = 24
n = 8
For i = 1 To 8
List1.AddItem a(i)
Next i
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, k As Integer
Dim pos As Integer
Dim s As String
s = Text1.Text
pos = Val(Text1.Text)
For i = 1 To n - 1
For j = n To i + 1 Step -1
If a(j) < a(j - 1) Then
k=a(j) ’(1)
a(j - 1) = a(j)
a(j) = k
’如果pos位置的数据参与交换,则更新pos值,记录pos变化位置
If pos = j Then
pos = j - 1
s = s + "→" + Str(pos)
Else ’(2)
pos = j
s = s + "→" + Str(pos)
End If
End If
Next j
Next i
Label1.Caption = "位置变化情况:" + s
For i = 1 To n
List2.AddItem Str(a(i))
Next i
End Sub
答案 (1) k=a(j-1) (2)ElseIf pos=j-1 Then
考点四 查找算法及程序实现
2015—2019年真题·提升题组
1.(2019浙江4月选考,12,2分)有1个升序排列的数组a(a(1)~a(n),n≥3),从左到右相邻两个元素的差值(后一个元素值减去前一个元素值)先由小到大、再由大到小,且相邻两个差值不相等,为了查找相邻两个元素的最大差值,小李编写的VB程序段如下:
i = 1:j = n
Do While i + 1 < j
m = (i + j) \ 2
If a(m + 1) - a(m) > a(m) - a(m - 1) Then
①
Else
②
End If
Loop
Label1.Caption="相邻两个元素的最大差值是" + Str(a(j) - a(i))
上述程序段两个方框处的语句分别为( )
A.① i = m ② j = m B.① i = m ② j = m - 1
C.① i = m + 1 ② j = m - 1 D.① i = m + 1 ② j = m
答案 A
2.(2018浙江4月选考,12,2分)数组a 为一组正整数,奇数在前,偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想,设计一个在数组a 中查找数据Key 的程序。实现该功能的VB 程序段如下:
i = 1: j = 10
Key = Val(Text1.Text)
Do While i <= j
m = (i + j) \ 2
If a(m) = Key Then Exit Do ’Exit Do表示退出循环
If Key Mod 2 = 1 And a(m) Mod 2 = 0 Then
(1)
ElseIf Key Mod 2 = 0 And a(m) Mod 2 = 1 Then
(2)
Else
(3)
End If
Loop
If i > j Then s = "没有找到!" Else s = "位置:" + Str(m)
Text2.Text = s
上述程序中方框处可选语句为:
①i = m + 1
②j = m - 1
③If Key < a(m) Then j = m - 1 Else i = m + 1
则(1)、(2)、(3)处语句依次是( )
A.①、②、③ B.①、③、②
C.②、①、③ D.③、②、①
答案 C
3.(2017浙江11月选考,12,2分)某对分査找算法的VB程序段如下:
i = 1: j = 7: s = ""
key = Int(Rnd*100)
Do While i <= j
m = (i + j) \ 2
If key = a(m) Then
s = s + "M": Exit Do ’Exit Do表示退出循环
ElseIf key < a(m) Then
j = m - 1: s = s + "L"
Else
i = m + 1: s = s + "R"
End If
Loop
Text1.Text = s
数组元素a(1)到a(7)的值依次为“24,35,38,41,45,69,78”。该程序段执行后,文本框Text1中显示的内容可能是( )
A.RL B.LMR C.RLR D.LRLM
答案 C
4.(2017浙江4月选考,11,2分)某对分查找算法的VB程序段如下:
key = Val(Text1.Text)
i = 1: j = 10
Text2.Text = ""
Do While i <= j
m = Int((i + j) / 2 + 0.5)
If key = a(m) Then Exit Do ’Exit Do表示退出循环
If key < a(m) Then j = m - 1 Else i = m + 1
Text2.Text = Text2.Text + Str(a(m))
Loop
数组元素a(1)到a(10)的值依次为“8,17,24,30,36,40,55,58,61,66”,文本框Text1中输入的值是30,执行该程序段,文本框Text2中显示的是( )
A.40 24 B.40 24 36 C.36 24 D.36 17 24
答案 B
5.(2016浙江10月选考,12,2分)某对分査找算法的VB程序段如下:
i= 1 : j =9 : n =0
key=Val(Text1.Text)
Do While i<= j
n=n+1
m=Fix((i + j) / 2)
If key = d(m) Then Exit Do
If keyLoop
数组元素d(1)到d(9)的值依次为“7,12,18,25,39,58,61,72,86”。若该程序段运行结束后,n的值为2,则key的值是( )
A.39 B.18或61 C.18或72 D.12或61
答案 D
6.(2016浙江4月选考,12,2分)已知一无序数组a(下标1到n),通过引入数组b(下标1到n),使得a(b(1))≤a(b(2))≤a(b(3))≤……≤a(b(n))(示例如图所示),对这些有序数据可进行对分查找。则第一次查找时,中点位置m与中点值分别是( )
A.m的值是Fix((1+n)/2),中点值是 a(m)
B.m的值是Fix((1+n)/2),中点值是 a(b(m))
C.m的值是Fix((b(1))+b(n))/2),中点值是 a(m)
D.m的值是Fix((b(1))+b(n))/2),中点值是 a(b(m))
答案 B
7.(2018浙江11月选考,16,3分)数组a中存储的是左右交替上升的n个正整数,如下表所示:
a(1) a(2) a(3) …… a(n-2) a(n-1) a(n)
3 25 38 …… 55 31 12
依据对分查找思想,设计一个在数组a中查找数据key的程序,实现该功能的VB程序如下,但加框处代码有错,请改正。
Private Sub Command1_Click()
Const n = 6
Dim a(1 To n) As Integer, flag As Boolean
Dim i As Integer, j As Integer, m As Integer, key As Integer
’读取一组正整数,按上述规则存入数组a中,代码略
key = Val(Text1.Text)
i = 1
j = (n + 1) \ 2
flag = False
Do While i < j And Not flag ’(1)
m = (i + j) \ 2
If key = a(m) Then
flag = True
ElseIf key < a(m) Then
j = m - 1
Else
i = m + 1
End If
Loop
If Not flag And j > 0 Then
m = n-i ’(2)
If key = a(m) Then flag = True
End If
If flag Then
Text2.Text = Str(m)
Else
Text2.Text = "找不到"
End If
End Sub
答案 (1)i<=j (2)n-i+2 或 n-j+1
考点五 递归算法及程序实现
考点六 算法在数据管理中的应用
2015—2019年真题·提升题组
(2016浙江10月选考,17,6分)小王与小李合作编写一个成绩统计的VB程序:小王编写一个过程,该过程从数据库读取某一指定科目的相关数据,存储在数组a中;小李编写一个过程,该过程依据数组a中的相关数据统计各班级平均分,小王与小李约定的数组a各元素含义如下表所示。
数组元素 数组元素的含义
a(1) 存储班级数n
a(2) 从a(2)到a(n+1)依次存储第1、第2、……、第n个班级的人数
…
a(n+1)
a(n+2) 从a(n+2)开始依次存储第1个班级每个学生的单科成绩、第2个班级每个学生的单科成绩、……、第n个班级每个学生的单科成绩
…
…
程序功能如下:在文本框Text1中输入科目名称,单击“读数据库”按钮Command1,程序从数据库读取数据;单击“开始统计”按钮Command2,程序进行统计处理,结果输出在列表框List1中。程序运行界面如图所示。
实现上述功能的VB程序如下,请回答下列问题:
(1)根据程序运行界面中的数据及数组a各元素的含义进行分析,数组元素a(5)的值为 (填写数值)。?
(2)分析程序,可知数据库的文件名为 。?
(3)请在划线处填入合适的代码。
Dim a(1 To 600)As Integer ’数组大小满足处理要求
Private Sub Command1_Click()
’本过程由小王完成,从数据库读取指定科目的各相关数据,存储在数组a中
Dim conn As New ADODB.Connection
Dim rs As New ADODB.Recordset
conn.ConnectionString="provider = Microsoft.ACE.OLEDB.12.0;datasource="+"Score.accdb"
conn.Open
Set rs.ActiveConnection=conn
’本过程的其他语句略
End Sub
Private Sub Command2_Click()
’本过程由小李完成,依据数组a中的相关数据统计各班级平均分
Dim i As Integer,j As Integer,n As Integer
Dim p As Integer,sum As Integer,aver As Single
① ?
p=n+2
For i=1 To n
sum=0
For j=1 To a(i+1)
② ?
p=p+1
Next j
aver=sum/a(i+1)
List1.AddItem Str(i)+" "+Str(a(i+1))+" "+Str(aver)
Next i
End Sub
答案 (1)33 (2)Score.accdb
(3)①n=a(1) ②sum=sum+a(p)
教师专用题组
1.采用如下对分查找算法对数组a中7个有序数据“about、count、end、fly、high、jack、month”进行查找。
i=1:j=7:x=“high”
Do While i <=j
m=(i+j)\2
If a(m)=x Then Exit Do
If a(m) > x Then
j=m-1
Else
i=m+1
End If
Loop
执行完上述代码后,根据最终变量值判断下列表达式,其中成立的是( )
A.i=j B.i=m-1 C.j>m+1 D.j答案 A
2.(2015浙江10月选考,11,2分)已知单调函数f(x)在[0,1]区间存在一个x0,使f(x0)=0。现用对分查找法搜索x0的值,开始搜索区间为[0,1],若经过10次对分查找后还需继续搜索,则第11次搜索区间的长度为( )
A.1/2 B.1/10 C.1/102 D.1/210
答案 D
3.“角谷猜想”规则:对任意一个大于1的正整数n,若n 是奇数,则n的值改为3n+1;若n是偶数,则n的值改为n/2,重复以上操作,n 的值最终会变为1。使用VB验证这个猜想。程序界面如图所示,在文本框Text1中输入一个大于1的正整数,单击“验证”按钮Command1,在列表框List1中输出每一步的运算过程。
(1)在界面设计时,没有使用到的控件为 (填字母)。 ?
(2)为实现上述功能,请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim n As Integer, i As Integer
List1.Clear
① ?
If n > 1 Then
List1.AddItem "步数对应值"
i=1
Do While ② ?
If n Mod 2=1 Then
n=n * 3+1
Else
n= ③ ?
End If
List1.AddItem Str(i)+" "+Str(n)
i=i+1
Loop
Else
List1.AddItem "输入有误!"
End If
End Sub
答案 (1)C (2)①n=Val(Text1.Text) ②n<>1
③n/2或n\2
4.小明编写了一个简易加法器VB程序,运行界面如图a所示。在文本框Text1中输入一个数字后再输入空格表示一个加数输入完毕,连续不断输入不同的加数,待所有需要相加的数输入完毕后,单击“求和”按钮Command1后,在标签Label1中显示加数的个数以及总和。
图a 图b
(1)该界面中除了窗体外,还使用了 个对象,界面中用于输出结果的标签Label1,是使用了图b控件工具箱中的 (填数字)控件添加的。?
(2)实现上述功能的VB程序如下,在划线处填入合适的代码。
Private Sub Command1_Click()
Dim s As String,t As String,c As String
Dim n As Integer
Dim k As Integer ’记录加数的个数
Dim sum As Integer ’记录和
s=Text1.Text
t=""
① ?
For i =1 To n
c =Mid(s, i, 1)
If c= " " Then ’如果是空格的情况
sum=sum + Val(t)
k=k + 1
t= ""
Else
t= ② ?
End If
Next
Label1.Caption="这" + ③ + "个数的和为:"+ Str(sum)?
End Sub
(3)如果输入“5 4 6 8”,则得到的和为 。?
答案 (1)3;① (2)①n=Len(s)
②t+c或t+mid(s,i,1) ③str(k) (3)15
5.(2016温州3月选考模拟,16,4分)如果两个质数的差为2,则这两个质数称为孪生质数对。编写VB程序,实现如下功能:单击“显示孪生质数对”按钮Command1,在列表框List1中显示100以内的所有孪生质数对(运行效果如图所示)。
实现上述功能的VB代码如下,但加框处代码有错,请改正。
Dim a(1 To 50)As Integer
Private Sub Command1_Click()
Dim i As Integer
k=0:i=3
Do While i<=100
If prime(i) Then ’(1)
k=k+1
a(k)=i
End If
i=i+2
Loop
For i=2 To k
If a(i)=a(i+1)+2 Then ’(2)
List1.AddItem Str(a(i-1))+"和"+Str(a(i))
End If
Next i
End Sub
Function prime(x As Integer)As Boolean
prime=False
For i=2 To Int(Sqr(x))
If x Mod i=0 Then
prime=True
Exit For
End If
Next i
End Function
答案 (1)Not prime(i)或 prime(i)=False
(2)a(i)=a(i-1)+2
6.(2017浙江4月选考,16,3分)小王编写了一个实现文字查找替换功能的VB程序,运行界面如图所示。文本框Text1显示原文内容,Text2中输入查找内容,Text3中输入替换内容,单击“全部替换”按钮Command1后,Text4显示查找替换的结果,Text5显示替换的次数,Text6显示“查找内容”在原文中的起始位置。
实现上述功能的VB程序如下,但加框处代码有错,请改正。
Private Sub Command1_Click()
Dim s As String, resule As String, pos As String
Dim count As Integer, i As Integer
i = 1: count = 0
result = "": pos = ""
Do While i <= Len(Text1.Text)
s = Mid(Text1.Text, i, Len(Text2.Text))
If s = Text2.Text Then
result = result + Text3.Text
count = count + 1
pos = pos + Str(count) ’(1)
i = i + Len(Text2.Text)
Else
result = result + Text2.Text ’(2)
i = i + 1
End If
Loop
Text4.Text = result
Text5.Text = Str(count)
Text6.Text = pos
End Sub
答案 (1)pos+Str(i)
(2)result=result+Mid(Text1.Text,i,1)
7.(2015浙江10月选考,14,5分)编写VB程序,实现如下功能:在文本框Text1和Text2中分别输入一个整数,单击命令按钮Command1,在列表框List1中显示结果,运行效果如图a所示。结果包含两列数据,第1列为相邻两数之间的摄氏温度值(间隔1摄氏度、升序),第2列为对应的华氏温度值。
图a
图b
(1)要使命令按钮Command1上显示的文本改为“转换”,可在其属性窗口(图b)中将 属性的属性值修改为“转换”。?
(2)为实现上述功能,请在划线处填入合适代码或选项。
Private Sub Command1_Click( )
Dim t1 As Integer,t2 As Integer
Dim i As Integer,t As Integer
Dim f As Single ’f存储华氏温度值
List1.Clear
t1=Val(Text1.Text)
t2=Val(Text2.Text)
If ① Then ’(选填字母,从下面A、B、C、D四个选项中选取一项)?
t=t1:t1=t2:t2=t
End If
i=t1
Do While ② ? ’(选填字母,从下面A、B、C、D四个选项中选取一项)?
f=i*9/5+32 ’摄氏温度转换为华氏温度
List1.AddItem Str(i)+“ ”+Str(f)
i= ③ ? ’(填程序代码)?
Loop
End Sub
划线①、②处的选项:
A.i<=t2 B.f<=t2 C.t1>t2 D.i答案 (1)Caption (2)①C ②A ③i+1
8.合唱队列是按队员的身高进行排列,形成中间高两边有序降低的队形。例如有六个队员“己、戊、丁、丙、乙、甲”身高依次由低到高,则排列后的顺序为“戊、丙、甲、乙、丁、己”。小李用VB编写模拟“合唱队列”程序,功能如下:在文本框Text1中输入各队员身高,输入结束后回车,则输入的各队员身高分别存入数组a中;单击“合唱队列”按钮Command1,对数组a的元素进行有序排列后,将各元素存入数组c中形成合唱队列,并将结果显示在文本框Text2中。程序运行界面如图所示。
(1)如果输入各队员身高为“190,191,194,179,166”,则合唱队列的结果为 。?
(2)实现上述功能的VB程序如下,请在划线处填入合适的代码。
Dim a(1 To 20) As Integer
Dim n As Integer
Private Sub Text1_KeyPress(KeyAscii As Integer)
’输入各队员身高分别存入数组a中,队员个数为n,代码略
End Sub
Private Sub Command1_Click()
Dim c(1 To 20) As Integer
Dim right As Integer,left As Integer,i As Integer
For i = 1 To n-1
For j = 1 To n-i
If ① Then?
t = a(j):a(j)= a(j + 1) :a(j + 1)= t
End If
Next j
Next i
’下列程序段实现数组c的合唱队列
m=(1+n) \2
left=m:right = m
c(m)=a(n)
i = 2
Do While i< = n
If i Mod 2 = 0 Then
right = right +1
c(right) = a(n-i+l)
Else
② ?
c(left)= a(n-i+l)
End If
i = i+l
Loop
s= ③ ?
For i = 2 To n
s = s+","+Str(c(i))
Next i
Text2.Text = s
End Sub
答案 (1)166,190,194,191,179
(2)①a(j)>a(j+1) ②left=left-1 ③Str(c(1))
9.有一组正整数,要求仅对其中的偶数进行降序排序。排序后偶数在前,奇数在后。排序示例如图所示。
排序前 75 78 60 86 61 75 36 88
排序后 88 86 78 60 36 75 61 75
实现上述功能的VB程序如下,但加框处代码有错,请改正。
Const n = 8
Dim a(1 To n) As Integer
Private Sub Form_Load()
’排序前数据存储在数组a中,并在文本框Text1中显示
End Sub
Private Sub Command1_Click()
Dim k As Integer, i As Integer, j As Integer, t As Integer
i = 1
Do While i <= n -1
k = i
For j = i + 1 To n
If a(i) Mod 2 = 1 And a(k)Mod 2 = 0 Then ’①
k = j
ElseIf a(k) Mod 2 = 0 And a(j) Mod 2 = 0 And a(j) > a(k) Then
k = j
End If
Next j
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
End If
i=j+k ’②
Loop
’依次输出排序后的数据,代码略
End Sub
答案 ①a(k) Mod 2=1 And a(j) Mod 2=0 ②i=i+1
10.编写一个成绩查找程序,只要输入成绩,即可输出其排名、同分数的人数以及比此分高的人数。具体算法思路如下:
(1)预处理。用数组a存放不同的分值,数组b存放相同分数的人数,数组s存放高于此分数的人数,数组下标表示名次。依次从数据库读取每个学生的成绩(数据库中每个学生的成绩已降序存储,即从高到低排列),当读入数与前一个数相同时,该名次的人数加1,当读入数与前一个数不同时,名次加1,即数组下标加1,存储当前分数,求高于本分数的人数并存储。
举例:如果数据库中有一组成绩(降序):95,95,93,93,92,91,90,按上述算法处理,三个数组的最终结果如下:
下标 数组 1 2 3 4 5
a 95 93 92 91 90
b 2 2 1 1 1
s 0 2 4 5 6
(2)对需要查找的成绩进行二分查找。读入需要查找的成绩x,在数组a中二分查找成绩,若找到,输出名次、相同分数的人数和高于本分数的人数;若找不到,输出“查无此分”。
程序代码如下,在横线处填入合适的代码。
Dim rank As Integer
Dim a(1 to 1000) As Integer ’存放不同的分数值
Dim b(1 to 1000) As Integer ’存放相同分数的人数
Dim s(1 to 1000) As Integer ’存放高于此分数的人数
rank=0
Private Sub Form_Load()
Dim conn As New ADODB.Connection
Dim rs As New ADODB.Recordset
Dim tmp As Integer, n As Integer
tmp=-1: n=0
conn.ConnectionString="provider=Microsoft.ACE.OLEDB.12.0;data source="App.Path+"Score.accdb"
conn.open
Set rs.ActiveConnection=conn
rs.open "Select * from score"
n=0
Do While Not rs.EOF
n=n+1
mark=rs.fields("成绩")
If mark=tmp Then ’当前读入分数与上一个分数相同时,对应名次的人数增加1
b(rank)=b(rank)+1
Else ’当前读入分数与上一个分数不同时
rank= ① ’名次增加1 ?
a(rank)= ② ’存储当前分数到数组a中?
s(rank)= ③ ’求高于本分数的人数并存储至数组s?
b(rank)=1 ’将自身统计入同分人数
End If
④ ’更新上一个分数 ?
rs.Movenext
Loop
End Sub
Private Sub Command1_Click()
Dim x As Integer,low As Integer,high As Integer,mid As Integer
x=Val(Text1.Text)
low=1: high=rank
mid=(low+high)\ 2
Do While low <=high And ⑤ ?
mid=(low+high)\ 2
If a(mid) < x Then
high=mid-1
Else
low=mid+1
End If
Loop
If a(mid)=x Then
Label1.Caption="名次:"+mid+"同分人数:"+b(mid)+"高于此分人数:"+s(mid)
Else
Label1.Caption="查无此分"
End If
End Sub
答案 ①rank+1 ②mark ③n-1 或b(rank-1)+s(rank-1) ④tmp=mark ⑤a(mid)<>x
11.活动课上,n个学生要两两组队进行拔河比赛,要求每个小组总体重不超过120 kg,小林想知道最多可以组成多少个队伍,并希望得到可行的组队方案。于是设计了如下界面的程序,在文本框Text1中输入n 个学生的体重(数字之间用逗号隔开),单击“队伍”按钮Command1后在标签Label1上显示最多可组队数量,同时在列表框List1输出方案。
实现上述功能程序如下,在划线处填入合适的代码。
Dim n As Integer
Dim a(1 To 50) As Integer
Sub makedata(s As String)’该过程实现将输入的体重分别存入数组a中
Dim in As Long, x As Long, c As String, i As Integer
m=Len (s) : n=0
For i=1 To m
c=Mid(s, i, 1)
If c >="0" And c <="9" Then
x= ① ?
Else
If x > 0 Then n=n+1: a(n)=x
x=0
End If
Next i
n=n+1: a(n)=x
End Sub
Private Sub Command1_Click()
Dim s As String, i As Integer, j As Integer, t As Integer
Dim cnt As Integer, st As Integer, ed As Integer
s=Text1.Text
Call makedata(s) ’调用过程
For i=1 To n-1 ’实现降序排序
For j=n To i+1 Step -1
If ② Then ?
a(j)=a(j)+a(j-1):a(j-1)=a(j)-a(j-1): ③ ?
End If
Next j
Next i
’下列程序段实现计算最多可组队伍
cnt=0: st=1: ed=n
Do While st < ed
If a(st)+a(ed) <=120 Then
List1. AddItem Str(a(st))+"和"+Str(a(ed))+"组队"
cnt=cnt+1
st=st+1
④ ?
Else
st=st+1
End If
Loop
Label2. Caption="最多可以组"+Str (cnt)+"组队伍"
End Sub
答案 ① x * 10+Asc(c)-Asc(“0”) ② a(j) > a(j-1) ③ a(j)=a(j)-a(j-1) ④ ed=ed-1
12.(2016浙江4月选考,14,5分)编写VB程序,实现如下功能:在文本框Text1中输入某一年份,单击“天干地支与生肖”按钮Command1,在列表框List1中输出该年份开始的12个年份及对应的“天干地支”与“生肖”,运行界面如图所示,程序代码如下。
(1)代码“Private Sub Command1_Click()”中的Click是 (单选,填字母:A.对象名/B.属性名/C.事件名)。?
(2)为实现上述功能,请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim a As Integer, b As Integer
Dim i As Integer, n As Integer
Dim c1 As String, s1 As String
Dim c2 As String, s2 As String
Dim c3 As String, s3 As String
List1.Clear
s1="甲乙丙丁戊己庚辛壬癸"
s2="子丑寅卯辰巳午未申酉戌亥"
s3="鼠牛虎兔龙蛇马羊猴鸡狗猪"
n=Val(Text1.Text)
For i=n To ① ?
a=(i+6) Mod 10
b=(i+8) Mod 12
c1=Mid(s1, a+1, 1)
c2=Mid(s2, b+1, 1)
c3=Mid(s3, b+1, 1)
List1.AddItem ② + "年" +c1+c2+" "+c3?
Next i
End Sub
(3)由上述算法可知,2024年对应的“天干地支”为 。?
答案 (1)C (2)①n+11 ②Str(i) (3)甲辰
13.(2016浙江10月选考,14,5分)编写“加法练习题生成器”程序,实现如下功能:在文本框Text1中输入题数n,单击“生成”按钮Command1,在列表框List1中显示n个两数之和小于100的加法练习题。程序运行界面如图a所示。
(1)在设计程序界面时,应使用图b所示“控件工具箱”中的 (填写相应编号)添加“生成”按钮。?
(2)实现上述功能的VB程序如下,请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim n As Integer, i As Integer, a As Integer, b As Integer
Randomize
n = Val(Text1.Text)
i= ① ?
Do While i<= n
a = Int(Rnd * 100)
b = Int(Rnd * 100)
If ② Then?
List1.AddItem "(" + Str(i) + ")" + Str(a) + "+" + Str(b) + "="
i = i + 1
End If
Loop
End Sub
(3)运行该程序,在文本框中输入5,单击“生成”按钮后,对语句a = Int(Rnd * 100)执行次数的描述,最合理的是 (单选,填字母:A.执行次数等于5/B.执行次数大于等于5/C.执行次数小于等于5)。?
答案 (1)3 (2)①1 ②a+b<100 或其他等价表达式
(3)B
14.(2015浙江10月选考,16,4分)n个数据的冒泡排序需要经过n-1遍加工,每一遍加工自下而上比较相邻两个数据,把较小者交换到上面。小刘发现:当某一遍加工过程中没有数据交换,说明数据已经有序,无需进一步加工。为此,小刘对算法进行优化,编写了一个VB程序,功能如下:运行程序时,在列表框List1中显示排序前数据,单击“排序”按钮Command1,在列表框List2 中显示这些数据按升序排序后的结果,在标签Label3中显示排序过程的加工遍数。运行效果如图所示。
实现上述功能的VB代码如下,但加框处代码有错,请改正。
Dim a(1 To 8) As Integer
Dim n As Integer
Private Sub Form_Load()
’n=8,排序前数据存储在数组a中,并在列表框List1中显示
’代码略
End Sub
Private Sub Command1_Click()
Dim flag As Boolean ’flag值为True表示一遍加工中发生过交换
i = 1
flag = True
Do While i <= n - 1 Or flag = True ’(1)
flag= False
For j= n To i + 1 Step -1
If a(j) < a(j - 1) Then
k = a(j): a(j) = a(j - 1): a(j - 1) = k
flag = True
End If
Next j
i = i + 1
Loop
Label3.Caption = "排序过程的加工遍数为" +Str(i) ’(2)
For i = 1 To n
List2.AddItem Str(a(i))
Next i
End Sub
答案 (1)i <=n - 1 And flag=True (2)Str(i-1)
【三年模拟】
A组 2018—2020年模拟·考点题组
考点一 解析算法及程序实现
1.基姆拉尔森公式可根据日期判断是星期几。基姆拉尔森公式在VB中的计算式如下:week= (d + 2 * m + 3 * (m + 1) \ 5 + y + y \ 4 - y \ 100 + y \ 400 + 1) Mod 7。在公式中d表示日期中的日数,m表示月份数,y表示年数。余数为0表示星期日,余数为1表示星期一,以此类推。在公式中有个特殊的地方:把一月和二月看成上一年的十三月和十四月,例:如果是2004-1-10,则换算成2003-13-10代入公式计算。小明编写了VB程序,运行界面如图所示,程序代码如下。
Private Sub Command1_Click()
Dim y As Integer,m As Integer,d As Integer,week As Integer
Dim ss As String,weekday As String
ss = "日一二三四五六"
y = Val(Text1.Text)
m = Val(Text2.Text)
d = Val(Text3.Text)
If ① Then?
m = m + 12
y = y - 1
End If
week = (d + 2 * m + 3 * (m + 1) \ 5 + y + y \ 4 - y \ 100 + y \ 400 + 1) Mod 7
weekday = ② ?
Label1.Caption = "星期" & weekday
End Sub
(1)代码“Private Sub Command1_Click()”中的Command1_Click()是 (单选,填字母:A.对象名/B.事件/C.事件处理过程)。?
(2)为实现上述功能,请在划线处填入合适的代码。
(3)由上述算法可知,2010年2月5日应为星期 。?
答案 (1)C (2)①m=1 Or m=2或m<3或m<=2
②Mid(ss,week+1,1) (3)五
2.(2019金华十校第一学期调研考试,14,5分)趣味数学题:n的阶乘n!=1×2×3×4×5×…×n,当n≥5时,其结果末尾必然包含1或多个0,求n!(5≤n≤32726)末尾包含0的个数。
算法思路:n较大时,n!的值将超出long类型范围,求出n!的结果再数0的个数不现实。那么末尾的0到底是从哪里来的?每一个因子5与任一偶数相乘就会产生一个0。所以末尾有多少0是由因子5的个数决定的,求出因子5的个数即是末尾0的个数。程序运行界面和代码如下所示。
(1)为使窗体加载时,窗体标题栏自动显示为“第14题程序”,则可以在 过程(填写过程名)中添加代码:Form1.Caption=“第14题程序”。?
(2)实现上述算法的VB程序如下,请补充程序中划线处的代码。
Private Sub Command1_Click()
Dim n As Integer
n = Val(Text1.Text)
i = 1
Do While ① ?
s = s + n \ 5 ^ i
i = i + 1
Loop
List1.AddItem Str(n) + "!末尾包含 0 的个数:" + ② ?
End Sub
(3)根据上述算法,2018!末尾包含 0 的个数是 。?
答案 (1)Form_load (2)①5 ^ i <= n 或其他等价表达式
②Str(s) (3)502
3.(2018浙南名校联盟期末)Base64 编码是将待转换的字符串以每 3 个字节分为一组转换为 24 位二进制数,再以每 6 位二进制数一组分为 4 组,转换为 4 个字节。对照下面的 Base64 编码表,根据每个字节的十进制值转换为对应的加密字符。
十进 制值 0 1 … 24 25 26 27 … 50 51 52 … 61 62 63
加密 字符 A B … Y Z a b … y z 0 … 9 + -
现设计一个程序,在文本框 Text1 输入字符串(长度为 3 的倍数),在文本框 Text2输出对应的 Base64 加密字符,运行效果如图所示,实现上述功能的 VB 代码如下:
Private Sub Command1_Click()
Dim s As String, txt As String
Dim s1 As String, t As String
Dim tmp As Integer, n As Integer
Dim i As Integer, j As Integer
Dim ans As String
txt="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-"
s1 = Text1.Text
For i = 1 To Len(s1)
n = Mid(s1, i, 1)
t = ""
For j = 1 To 8
t = n Mod 2 & t
① ?
Next j
s = s & t
Next i
For i = 1 To Len(s)
’二进制编码转换为加密字符
tmp = ② ?
If i Mod 6 = 0 Then
ans = ans & Mid(txt, tmp + 1, 1)
tmp = 0
End If
Next i
Text2.Text = ans
End Sub
(1)代码“Private Sub Command1_Click ()”中的 Command1_Click 是 (单选,填字母:A.属性名 / B.事件名 / C.事件过程 / D.方法名)。?
(2)程序代码加框处有错,请改正。
(3)请将程序代码划线处语句补充完整。
(4)根据图中数据,结合程序代码,最终 i 的值是 。?
答案 (1)C (2)Asc(Mid(s1,i,1))
(3)①n=n\2 ②tmp * 2 + Val(Mid(s,i,1)) (4)49
考点二 枚举算法及程序实现
1.一个十进制整数的二进制表示中,如果数字“1”的个数多于数字“0”的个数,则称该整数为A 类数。如十进制整数26 的二进制表示为11010,26 是一个A 类数。下列VB程序的功能是:寻找前1000 个自然数中所有A 类数,在List1中输出,并统计个数,在Text1中输出。
请在下面划线处填入合适的代码。
Private Sub Command1_Click()
Dim i, n ,s ,t, k As Integer ’s 为A 类数的个数,t 为二进制数中“1”的个数,k 为“0”的个数
s = 0
For i = 1 To 1000
n = i: t = 0: k = 0
Do While n > 0
If ① Then t=t+1 Else k=k+1?
② ?
Loop
If t>k Then
List1.AddItem Str(i)
s = s + 1
End If
Next i
Text1.Text = Str(s)
End Sub
答案 ①n Mod 2 <>0 或n Mod 2=1 ②n=n\2
2. (2019浙江十校联盟适应性考试)某密码强度判断程序功能如下:在文本框Text1中输入由大写字母、小写字母、数字和其他字符 4种不同类型字符组成的密码字符串,单击“判断”按钮Cmd1,在标签框Label3中显示判断结果。程序运行界面如图所示。
密码强度判断条件如下:密码长度小于6,则强度为“弱”。在密码长度大于等于6的情况下,若只出现一种字符,则密码强度为“弱”;若出现两种不同字符,则密码强度为“中”,出现3种以上不同字符,则密码强度为“强”。
(1)Cmd1对象属于 类。(单选,填字母:A.Label /B.TextBox /C.CommandButton)?
(2)实现上述功能的VB程序如下,请在划线处填入合适的代码。
Private Sub Cmd1_Click()
Dim n As Integer, i As Integer, m As Integer, s As String, c As String
① ?
If n<6 Then
Label3.Caption ="弱"
Else
s = "0000"
For i = 1 To n
c = Mid(Text1.Text, i, 1)
If c >= "0" And c<="9" Then
Mid(s,4,1) ="1"’将字符串s第4位上的字符替换为"1"
Elself c >= "A" And c<= "Z" Then
Mid(s,3,1) = "1"
Elself c>= "a" And c <= "z" Then
② ?
Else
Mid (s,1,1) = "1"
End If
Next i
m = 0
For i = 1 To 4
If Mid(s,i,1) = "1" Then ③ ?
Next i
If m< 2 Then
Label3.Caption="弱"
Elself m = 2 Then
Label3.Caption="中"
Else
Label3.Caption="强"
End If
End If
End Sub
(3)若文本框Text1中输入的内容为“a26$gh2!”,单击判断按钮Cmd1,事件过程运行结束时,变量s的值为 。?
答案 (1)C (2)①n = Len(Text1.Text) ②Mid(s, 2, 1) = "1" ③m = m + 1 (3)1101
考点三 排序算法及程序实现
1.(2020届浙江名校新高考研究联盟(Z20联盟)联考)下列程序段运行后,数组元素a(3)的值是( )
a(1) = 55:a(2) = 44:a(3) = 11
a(4) = 22:a(5) = 33
For i = 1 To 2
For j = 1 To 4 - i
If a(j) > a(j + 1) Then
t = a(j):a(j) = a(j + 1):a(j + 1) =t
End If
Next j
Next i
A.44 B.33 C.22 D.11
答案 A
2.(2018浙江“五校联考”第一次考试,11,2分)有如下VB程序段:
Dim a(1 To 6) As String
Text1.Text = ""
For i = 1 To 3
For j = 1 To 6 - i
If a(j) < a(j + 1) Then t = a(j): a(j) = a(j + 1): a(j + 1) = t
Next j
Text1.Text = Text1.Text + a(j)
Next i
数组元素a(1)到a(6)的值依次是“231”“123”“12”“59”“41”“33”。该程序段执行后,文本框Text1中显示的内容是( )
A.123341 B.23112359
C.12123231 D.594133
答案 C
3.有以下VB程序段:
For i=1 To 3
For j=i To 5
If a(j) > a(j+1) Then
t=a(j): a(j)=a(j+1): a(j+1)=t
End If
Next j
List1.AddItem Str(a(i))
Next i
a(1)到a(6)的初始值依次为“8 6 5 7 9 3 ”,经过该程序段“加工”后,列表框List1中显示的是( )
A.8 7 6 B.8 7 9 C.6 5 3 D.5 6 7
答案 C
4.某算法的部分程序段如下:
For i=1 To 7
k=i
For j=i+1 To 8
If a(j)>a(k) And a(j)>85 Then k=j
Next j
If k<>i Then t=a(i): a(i)=a(k): a(k)=t
Next i
数组元素a(1)到a(8)的原始数据依次为“89,70,79,85,99,80,82,74”,则第3遍“加工”后数组元素a(1)到a(8)的数据依次是( )
A.99,89,79,85,80,70,82,74
B.99,89,85,79,70,80,82,74
C.99,89,79,85,70,80,82,74
D.99,89,85,82,80,79,74,70
答案 C
5.(2019宁波新高考选考适应性考试)下列VB程序段的功能为:对数组a中的n个元素进行排序,生成左右交替上升的数据序列。如排序前a中元素依次为:48,34,86,46,85,100,程序运行后a中元素依次为:34,48,86,100,85,46。
For i = 1 To (1)
k=i
For j=i+1 To n-i+1
If a(k) > a(j) Then k = (2)
Next j
If k <> i Then t = a(k): a(k) = a(i): a(i) = t
For j = (3)
If a(j) < a(j + 1) Then t = a(j): a(j) = a(j + 1): a(j + 1) = t
Next j
Next i
上述程序段3个方框处的表达式分别为( )
A.(1)n-1 (2)j+1 (3)i To n-i+1
B.(1)n-1 (2)j+1 (3)i To n-i
C.(1)n\2 (2)j (3)i+1 To n-i+1
D.(1)n\2 (2)j (3)i+1 To n-i
答案 D
6.(2019浙江十校联盟适应性考试)有如下VB程序段:
n = 8
For i = 1 To n
d(i) = Int(Rnd * 10) + 1
Next i
For i = 2 To n - 1
k = 1
For j = 1 To n - i
If d(j) * k > d(j + 2) * k Then
Temp= d(j): d(j)=d(j + 2): d(j + 2)= temp
End If
Next j
Next i
执行该程序段后,d数组各元素可能是( )
A.3,10,3,5,4,4,10,1 B.0,3,4,5,6,6,7,8
C.2,1,3,4,5,6,8,7 D.6,4,5,6,5,7,1,10
答案 A
7.(2020届浙江名校新高考研究联盟(Z20联盟)联考)食堂排队买菜问题。在食堂排队买菜时,每个同学都有一个窗口买菜时间,如果某同学的等待时间超过他在窗口买菜时间的 3 倍,他就会不愉快,并且不参与排队,反之是愉快的。等待时间是指排在该同学之前的所有人的买菜时间之和。 已知每个同学在窗口的买菜时间,请确定如何排队才能使愉快的人数最多,并输出最多的人数。例如: 10 个同学的买菜时间如下表所示,则最多有 8 个人是愉快的。
学生 编号 1 2 3 4 5 6 7 8 9 10
买菜 时间 3 2 5 5 6 7 1 8 1 3
最终是 否参与 排队 是 是 是 是 否 是 是 否 是 是
Const n = 10
Dim a(1 To n) As Integer
Private Sub Command1_Click()
Dim i As Integer,s As Integer,ans As Integer,t As Integer
’读取每个学生的买菜时间,依次存储在数组 a 中,代码略
For i = 1 To n -1
k = i
For j = n To i + 1 Step -1
If (2) Then k = j?
Next j
If a(i)<>a(k) Then t=a(i):a(i)=a(k):a(k)=t
Next i
s = 0:ans = 0
For i = 1 To n
If s < ans Then s = s + a(i):ans = ans + 1
Next i
Label1.Caption = "共有" + Str(ans) + " 个人是愉快的,且参与排队买菜。 "
(1)代码“Private Sub Command1_Click()”中的 Command1 是 (单选,填字母: A.对象名/B.事件名/C.事件处理过程名)。?
(2)请在划线处填入合适代码。
(3)程序代码的加框处有错,请改正。
(4)若 10 个同学的买菜时间都相同,则有 个人是愉快的,且参与排队。?
答案 (1)A (2)a(j) < a(k) (3)a(i)*3 >= s (4)4
8.(2020届浙江十校联盟联考)纪念品分组问题。某教师节晚会的纪念品分组规则如下:按纪念品价值进行分组,每组总价值不超过限定值w且最多包含两件,要求分组数最少。编写VB程序解决该问题,程序运行时,在文本框Text1中依次输入每件纪念品的价格(不超过w),以逗号分隔,在文本框Text2中输入限定值w,单击“分组”按钮,在标签Label2上输出最少的分组数。程序运行界面如图所示。
(1)要使程序启动后,窗体的标题栏显示“纪念品分组”文字,可在Form_Load事件过程中添加语句 (单选,填字母:A.Form1="纪念品分组" / B.Form1.Name="纪念品分组" C.Form1.Caption="纪念品分组"/ D.Form1.Text="纪念品分组")。?
(2)实现上述功能的VB程序如下,请在划线处填入合适的代码;并且加框处代码有错,请改正。
Private Sub Command1_Click()
Dim a(1 To 1000),n As Integer,w As Integer,t As Integer
Dim i As Integer,j As Integer,cnt As Integer
Dim s As String,ch As String
Dim p As Integer,q As Integer
s=Text1.Text:w=Val(Text2.Text):n=0
For i = 1 To Len(s)
ch = Mid(s, i, 1)
If ch ="," Then
n = n +1: a(n) = t: t = 0
Else
t = ① ?
End If
Next i
For i = n To 2 Step -1
For j = 1 To n-i’②
If a(j) < a(j + 1) Then
t = a(j): a(j) = a(j + 1): a(j + 1) = t
End If
Next j
Next i
cnt=0
p = 1: q = n
Do While p < q
cnt = cnt + 1
If ③ Then?
p=p+1:q=q-1
Else
p=p+1
End If
Loop
If p = q Then cnt = cnt + 1
Label2.Caption = Str(cnt)
End Sub
(3)若在文本框 Text1中输入 “50,30,100,70,80,40,50,20,”,文本框 Text2 中输入 “110” , 单击“分组”按钮,标签Label2中显示的内容是 。?
答案 (1)C (2)①t*10 + Val(ch) 或其他等价答案
②i-1 或其他等价答案 ③a(p)+a(q)<=w 或其他等价答案
(3)5
考点四 查找算法及程序实现
1.某数组的6个元素依次为“27,32,57,78,80,90”。若对该数组进行顺序查找,其平均查找次数为(1+2+3+4+5+6)/6=7/2;若对该数组进行对分查找,其平均查找次数为( )
A.7/2 B.7/3 C.5/2 D.2
答案 B
2.某对分查找算法的VB程序段如下:
t="": i=0 : j=9 : key=62: f=False
Do While i <=j And Not f
m=Fix((i+j) / 2)
t=t+Str(m)
If a(m)=key Then
f=True
Elself a(m) > key Then
i=m+1
t=t+"→"
Else
j=m-1
t=t+"←"
End If
Loop
数组元素a(0)到a(9)的值依次为“99, 94, 90, 87, 78,70, 63,56, 45,36”,执行该程序段,t的值是( )
A.“4→7←5→” B.“4→ 7← 5→ 6→”
C.“4→7←5→6” D.“4→ 7← 5”
答案 B
3.(2018浙南名校联盟期末)有如下 VB 程序段:
i=1 : j=8 : n=0
Do While i <= j
n = n + 1
m = (i + j) \ 2
If key < a(m) Then j=m-1 Else i=m+1
Loop
数组元素 a(1)到 a(8)的值依次为“22,32,39,48,71,82,96,106”。若该程序段运行结束后,n 的值为 3,则 key 的值不可能是( )
A.110 B.82 C.39 D.10
答案 A
4.(2018浙江“五校联考”,12,2分)有如下VB程序段:
i = 1: j = 10:n = 0: Key = Val(Text1.Text)
Do While i <= j
m = (i + j) \ 2
If a(m) < Key Then
i = m + 1: n = n + 1
Else
j = m - 1: n = n - 1
End If
Loop
数组元素a(1)到a(10)依次是33,42,48,57,69,71,75,89,91,96,在文本框Text1中输入89,则变量n的最终值为( )
A.2 B.1 C.0 D.-2
答案 A
5.(2019衢州教学质量检测)有 VB 程序段如下:
a(1) = 2: a(2) = 2: a(3) = 5: a(4) = 6: a(5) = 7
Key = 2
i = 1: j = 5: flag = False
Do While i <= j And Not flag
m = (i + j) \ 2
If Key = a(m) Then
s = "找到第" + Str(m) + "个"
flag = True: Exit Do
ElseIf Key < a(m) Then
j = m - 1
Else
i = m + 1
End If
s = Str(m) + s
Loop
Label1.Caption = s
执行该程序段后,在标签 Label1 中显示的内容是( )
A.1 3 B.3 1 C.找到第 1 个 D.找到第 2 个
答案 C
6.(2018稽阳联谊学校联考,12,2分)有如下程序段:
Dim a(1 To 10) As Integer
Dim i As Integer, j As Integer, m As Integer
Dim key As Integer
i = 1: j = 10: key = Val(Text1.Text)
Do While i <= j
m = (i + j) \ 2
If key < a(m) Then
j = m - 1
ElseIf key > a(m) Then
i = m + 1
Else
Do While m > 1
If a(m - 1) = key Then
m = m - 1
Else
Exit Do
End If
Loop
Exit Do
End If
Loop
数组中a(1)到a(10)依次为“1,1,2,3,3,3,3,4,4,4”,若在文本框Text1中输入3,经上述程序段执行后,变量m的值为( )
A.7 B.6 C.5 D.4
答案 D
7.(2020届浙江十校联盟联考)某对分查找算法的部分VB程序如下:
i = 1 : j = 12 : k = 0 : s =""
key = Val(Text1.Text) : c ="N": flag = False
Do While i <= j And flag = False
m=(i + j +1) \ 2:k = k + 1
If key = a(m) Then c ="Y" : flag = True
If key > a(m) Then j = m - 1 Else i = m + 1
s = s & Str(a(m))
Loop
Text2.Text = s : Text3.Text = c
数组 a(1)到a(12)的值依次为“99,91,85,76,68,61,53,42,34,27,20,13”,执行该程序段后,下列说法正确的是( )
A.该程序段只能进行两位正整数的查找
B.在文本框Text1中输入两位任意正整数,则k的值介于1和3之间
C.在文本框Text1中输入76,程序执行后变量i和j的值分别为1和6
D.若文本框Text2中显示了两个正整数,则文本框Text3中显示的内容一定是Y
答案 D
8.(2019浙江十校联盟适应性考试)某对分查找算法的程序如下:
Dim d(1 To 63) As Integer
For i=1 To 63
d(i)=i
Next i
s=0:i=1:j=63
Key=Int(Rnd*63)+1
Do While i<=j
m=(i+j)\2
If Key=d(m) Then Exit Do
If Key j=m-1:s=2*s
Else
i=m+1:s=2*s+1
End If
Loop
Label1.Caption=Str(s)
若运行该程序段后,标签Label1中显示的结果是28,则查找的Key值是( )
A.28 B.29 C.57 D.58
答案 C
9.(2019浙江名校新高考研究联盟(Z20联盟)联考)对于一组升序不重复的正整数,在任意数字位置分成两段,并交换前后两段的位置,存入数组a。例如6、17、25、36、44、58,在数字6处分成两段,交换位置后为:
a(1) a(2) a(3) a(4) a(5) a(6)
6 17 25 36 44 58
在数字 44 处分成两段, 交换位置后为:
a(1) a(2) a(3) a(4) a(5) a(6)
44 58 6 17 25 36
依据对分查找思想,设计一个在数组a中查找最小值,并输出在Text1中的程序,实现该功能的VB程序如下,但加框处代码有错,请改正。
Private Sub Command1_Click()
Const n = 6
Dim a(1 To n) As Integer
Dim i As Integer, j As Integer, m As Integer
’读取数据, 按上述规则存入数组 a 中, 代码略
i = 1: j = n
If a(i) > a(j) Then Text1.Text = Str(a(i)) ’(1)
Do While i <= j
m = (i + j) \ 2
If a(m) < a(j) Then
j = m - 1 ’(2)
Else
i = m + 1
End If
Loop
Text1.Text = a(j)
End Sub
答案 (1)a(i)
10.(2019浙江普通高中学考选考模拟)数组a中存储的是一组正整数,特征是:以三个数为一组,每组中任意一个数都比前面一组中的任意一个数要大;②每组中三个数依次递减;③数组中数的总个数为3的倍数。依据对分查找思想,设计一个在数组a中查找数据key的程序。实现该功能的VB程序如下,但加框处代码有错,请改正。
8 5 3 17 15 10 32 23 18 53 43 37 82 72 63 ……
Private Sub Command1_Click()
Const n = 15
Dim a(1 To n) As Integer, search As Integer, key As Integer
Dim i As Integer, j As Integer, m As Integer
’读取一组正整数,按上述规则存入数组a中,代码略
key = Val(Text1.Text)
i = 1: j = n: search = 0
Do While i <= j
m = (i + j) \ 2
If m Mod 3 <> 0 Then m=m -2 ’(1) 把m调整到三个数一组的最后一个数的位置
If key = a(m) Then
search = m : Exit Do
ElseIf key < a(m) Then
j = m - 3
ElseIf key <= a(m - 2) Then ’(2)
i = m + 1
ElseIf key = a(m - 2) Then
search = m - 2 : Exit Do
ElseIf key = a(m - 1) Then
search = m - 1 : Exit Do
Else
search = 0 : Exit Do
End If
Loop
If search <> 0 Then
Text2.Text = Str(search)
Else
Text2.Text = "找不到"
End If
End Sub
答案 (1)m + 3 - m Mod 3 (2)key > a(m - 2)
考点五 递归算法及程序实现
1.某VB程序使用了递归函数,代码如下:
Private Sub Command1_Click()
Text1.Text = f(3)
End Sub
Function f(x As Integer) As String
If x = 1 Then f = 1 Else f = f(x-1) + 2
End Function
运行程序并点击按钮Command1后,文本框Text1中显示的内容是( )
A.1 B.3 C.5 D.7
答案 C
2.执行以下代码,单击命令按钮Command1后,显示在窗体第二行的内容是 ( )
Private Sub Command1_Click()
Dim n As Integer,m As Integer
n=2:m=0
Do While m < 3
n=n+2
If fun(n) Then
Print n
m=m+1
End If
Loop
End Sub
Function fun(x As Integer) As Boolean
fun=false
If x/2=Int(x/2) Then
fun=fun(x/2)
Else
If x=1 Then fun=True
End If
End Function
A.4 B.6 C.8 D.16
答案 C
3.(2018温州六校期末联考)小明设计了如下一个查找数据的程序: 在一组升序的数列当中, 查找不小于 k 的最小数的位置, 如果该值存在, 则返回其第一次出现的位置, 如果不存在则返回 0。程序界面如下:
(1)若在 Text1 中输入“8”,Text2、Text3 输出的分别为 。?
(2)请在划线处填入合适的代码。
Dim a(1 To 10) As Integer
Function find(L As Integer, R As Integer, key As Integer)As Integer
If L > R Then
find = 0: Exit Function
ElseIf a(L) >= key Then
find = L: Exit Function
Else
① ?
If a(m) < key Then
find = find(M + 1, R, key)
ElseIf ② Then?
find = find(L, M - 1, key)
Else
find = M
End If
End If
End Function
Private Sub Command1_Click()
Dim k As Integer
Dim p As Integer
k = Val(Text1.Text)
③ ?
Text2.Text = a(p)
Text3.Text = Str(p)
If p = 0 Then
Text2.Text = "无"
End If
End Sub
Private Sub Form_Load()
a(1)=3 : a(2)=3 : a(3)=3 : a(4)=4 : a(5)=7 : a(6)=7 : a(7)=10 : a(8)=13 : a(9)=19 : a(10)=21
For i = 1 To 10
List1.AddItem Str(a(i))
Next i
End Sub
答案 (1)10,7 (2)①m = (L+ R) \ 2或 m = (L+ R+ 1) \ 2或其他等价答案 ②a(m - 1) >= key
③p = find(1, 10, k)
考点六 算法在数据管理中的应用
1.(2020届浙江名校新高考研究联盟(Z20联盟)联考)有如下 VB 程序段:
Dim conn As New ADODB.Connection
Dim rs As New ADODB.Recordset
conn.ConnectionString = "provider=Microsoft.ACE.OLEDB.12.0;data source ="+ App.Path+"\score.accdb"
conn.Open
Set rs.ActiveConnection = conn
rs.Open "Select * from cj"
n=1
Do While Not rs.EOF
Score(n)=rs.fields("成绩"):Name(n)= rs.fields("姓名")
n=n+1:rs.MoveNext
Loop
下列说法中不正确的是( )
A.定义的 ADO 的 Connection 对象实例名称是“conn”
B.连接的数据库文件名是“\score.accdb”
C.查询的数据表名是“cj”
D.该程序段运行后, 可知所查询的数据表共有 n-1 条记录
答案 B
2.小王为学校教务处编写了一个排考场座位的VB程序。考场采用“6排5列”共30人的模式。程序执行后,考生的考号与姓名显示在列表框List1中,单击“考场座位”按钮Command1,考场号与座位显示在Text1中,程序运行界面如图a所示,考生数据存放在数据库文件“kaochang.accdb”中,数据表如图b所示。
实现上述功能的VB程序如下,请回答下列问题:
(1)当“Form_Load()”事件处理过程运行结束时,变量x的值为 。 ?
(2)请在横线处填入合适的代码。
Private Sub Command1_Click()
Dim y As Integer
Dim start As Integer ’考场第1位数据元素的下标
Dim pa As Integer ’数据库导入VB时学生数据下标
Dim pb As Integer ’考场座位数据下标
Dim i As Integer,j As Integer,k As Integer,m As Integer
start=1
pa=start
recCount=x-1
If recCount Mod 30 <> 0 Then
① ?
For i=1 To y ’将当前考生人数添加到30的整数倍
recCount=recCount+1
sName(recCount)=""
Next i
End If
For j=1 To recCount / 30
pa=start
pb=start
For i=1 To 30
kcsName(pb)=sName(pa)
pb=pb+1
If i Mod 5=0 Then
pa=start+i \ 5
Else
② ?
End If
Next i
start=start+30
Next j
Text1.Text=""