2019浙江选考信息技术查找算法专题.doc

(完整版)2019浙江选考信息技术查找算法专题
（一）顺序查找
1．顺序查找算法
①顺序查找算法的处理过程
假定在数组d中有n个数据，查找关键值已经存储在变量key中。其处理过程是：从数组d的第1个元素d（1)开始，依次判断各元素的值是否与key相等，若某个数组元素d（i)的值等于key，则结束处理（找到了指定的数据）;若找遍了所有的n个元素，无任何元素的值等于key，则结束处理(输出未找到信息).
②顺序查找算法流程图与程序结构

2。程序实现代码：

(二)对分查找
1。对分查找的过程
若key为查找键，数组d存放n个已按升序排序的数据。在使用对分查找时，把查找范围［i，j］的中间位置上的数据d（m)与查找关键值key进行比较,结果必然是如下三种情况之一：
（1)若key〈d(m)，查找key小于中点m处的数据.由数组d中的数据的递增性，可以确定:在（m，j）内不可能存在值为key的数据，必须在新的范围(i，m－1)中继续查找；
(2）key＝d（m),找到了需要的数据;
（3）key〉d(m)，由与(1）相同的理由，必须在新的范围(m＋1，j）中继续查找。
这样，除了出现情况（2)，在通过一次比较后,新的查找范围将不超过上次查找范围的一半。
以规模为16的递增数组d为例,观察对分查找的过程。要查找的数据key为37。

使用流程图描述对分查找的算法如下图所示：

2．对分查找算法程序的实现
Private Sub Command1_Click（)
i ＝ 1： j ＝ n
Do While i 〈＝ j
m ＝ （i ＋ j) \2
If d（m） ＝ Key Then
’输出结果，退出查找(代码略)
ElseIf Key 〈 d（m） Then
j ＝ m － 1
Else
i ＝ m ＋ 1
End If
Loop
End Sub
注意：中间位置数据d（m）的下标m的常见计算方法：m＝ (i＋j)\2、m＝ int(（i＋j）/2)、m＝fix(（i＋j）/2)、m＝fix（(i＋j)/2+0.5）
上面对分查找的算法用一个块if语句实现,也可以用其他等价的方式:

3．查找次数的估算
对规模为n的数组进行对分查找时,无论是否找到，至多进行 log2n＋1次查找就能得到结果，平均查找次数计算：（第1个数据需要的查找次数+第2个数据需要的查找次数+…+第n个数据需要的查找次数)/n而使用顺序查找算法,在最坏的情况下(查找键在最后一个或没找到），需要进行n次查找，最好的情况是一次查找(查找键在第一个)，平均查找次数是。

1、（2018.4）数组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．③、②、①
2、（2017。11）某对分査找算法的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（9）的值依次为“24,35，38，41,45，69，78”。若该程序段执行后,文本框Text1中显示的内容可能是
A。 RL B。 LMR C。 RLR D。 LRLM
3、（2017.4）某对分查找算法的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
4、(2016。10)某对分查找算法的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 key < dm） Then j = m — 1 Else i = m + 1
Loop
数组元素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
5、（2016。4）已知一无序数组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）)
6、（2015.10)已知单调函数在[0，1]区间存在一个，使。现用对分查找法搜索的值，开始搜索区间为［0，1］,若经过10次对分查找后还需继续搜索，则第11次搜索区间的长度为
A.1/2 B。 1/10 C。 D。
7、（2017。4）小王编写了一个实现文字查找替换功能的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
resule = "": 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)
i = i + Len（Text2。Text）
Else
result = result + Text2。Text
i = i + 1
End If
Loop
Text4.Text = result
Text5。Text = Str（count）
Text6。Text = pos
End Sub

1、 按钮command1的鼠标事件处理过程如下:
Private Sub Command1_Click(）
Dim st(1 To 6） As String
st（1） = ”she”:st（2) = ”her”:st(3） = "your”
st(4) = ”me”：t(5) = "you”:st(6） = ”i”
Key = text1.Text
t = False
i = 0
Do While i < 6 And t = False
i = i + 1
If st(i） = Key Then t = True
Loop
If t = flase Then i = 0
text2。Text = Str（i）
End Sub
程序运行时,在文本框中输入“you”后单击按钮command1后,在文本框text2中显示的内容是( ）
A.0 B。1 C。5 D.7
2、某8位男生的肺活量数据放在数组a（1）到a(8)中,其数据依次为“3104,3700,3058,3222，3621,3329,4233,4540”.使用顺序查找算法查找数据3339,则共需查找次数为( ）
A。0 B。1 C.8 D.9
3、有以下两组数据：
①54，31，43,12，8,73，56,34，89，60,23,67
②87，83,75,70,63，59，55，37，33,21，17,7
下列有关查找方法描述不正确的是（ ）
A. ①可以直接使用对分查找 B。 ②可以直接使用对分查找
C. ①可以直接使用顺序查找 D. ②可以直接使用顺序查找
4、某8位男生的肺活量数据放在数组a(1)到a（8）中,其数据依次为“3205,3408，3471，3498，3621，3829,4233，4540”。使用对分查找，设定查找键key，若第一个被访问到的数据是3498，小于key值，则第二个被访问到的数据是( ）
A。3408 B.3829 C。4233 D.4540
5、某对分查找算法的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 Key < d（m） Then j = m - 1 Else i = m + 1
Loop
数组元素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
6、数组元素d（1）到d(10)的值依次为“60，51，49,45，40,31，20,10，5”,用对分查找找到49的过程中，依次被访问到的数据是（ ）
A.49 B。40 49 C.40 45 49 D。40 51 49
7、下列有关查找的说法，正确的是（ )
A．进行顺序查找时，被查找的数据必须是有序的
B．在任何情况下，顺序查找比对分查找的查找次数要多
C．进行对分查找时，被查找的数据可以是有序的，也可以无序的
D．对规模为n的有序数据进行对分查找，最多查找的次数是[log2n］+1
8、某查找算法的部分 VB 程序代码如下： Key=Val（Text1。Text）
i = 1： j = 9: k = 0
Do While i <= j
k = k + 1
m = int(（i + j)/2+0.5）
If key = a(m) Then Exit Do
If key 〈 a（m） Then j = m — 1 Else i = m + 1 Loop
Text2。Text=str（k）
数组元素 a（1）到 a（9)的数据依次为“10，15，36,49，55，62，88,92，99”,该程序运行过程中,文本框 Text2 中显示的值为 2，文本框 Text1 中输入值可能是（ ）
A。88 B。62 C.92 D.15
9、某对分查找算法的VB程序段如下：
i=1: j=6: n=0: f=False
key=val（Text1.Text）
Do while i<=j and f=False
n=n+1
m=(i+j)\2
If key=d(m） then f=True
If key<d(m） then j=m—1 Else i=m+1
Loop
数组元素d(1)到d(6）的值依次为“13，18,25，30，35，59”。文本框Text1中输入33后运行该程序,运行结束后下列说法不正确的是（ )
A。 变量f的值为False B。 变量i的值为5
C。 变量m的值为4 D。 变量n的值为2
10、有如下程序段：
i = 1： j = 6： s = "": key = Text1.Text
Do While i 〈= j
m = Int（(i + j） /2 + 0.5)
s = s + ” ” + a（m)
If a(m） 〉 Key Then
i = m + 1
Else
j = m - 1
End If
Loop
Text1.Text = s
数组元素a（1)到a（6）的值依次为"Beijing”、”Guangdong”、”Jiangsu"、”Jiangxi”、”Shanghai”、"Zhejiang"，已按字典序排序。当key的值为”Zhejiang"时，单击命令按钮Command1，文本框Text1中显示的内容为（ ）
A. Jiangxi Zhejiang Zhejiang B。 Jiangsu Shanghai Jiangxi
C. Jiangxi Zhejiang Shanghai D。 Jiangsu Shanghai Zhejiang
11、某对分查找算法的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．40 24 36 30
D．36 17 24
12、下列程序执行后文本框 Text1 显示的内容是( )
s = ”ERROR：Divisor must not be zero!"
flag = False : m = 0
For i = 1 To Len（s）
ch = Mid（s, i， 1）
If ch >= ”a" And ch 〈= ”z” Then
If Not flag Then
m = m + 1 ： flag = True
End If
Else
flag = False
End If
Next i
Text1。Text=Str(m)
A．4 B．5 C．6 D．19
13、编写一个技术成绩查询的 VB 程序。程序功能如下：在文本框 Text1 中输入分数 key（0-50 的整数),单击“查询”按钮 Command1，查询出信息成绩大于等于 key 的所有记录，并以“信息”为主要关键字、“通用”为次要关键字均进行降序排序，结果输出在列表框 List2 中。运行界面如下图所示。

实现上述功能的 VB 程序如下，请回答下列问题：
（1）观察上图,排序后第 5 位的学生姓名是____________.
（2）请在划线处填入合适的代码。
Dim xm（1 To 600) As String ’存储学生姓名
Dim xx（1 To 600) As Integer '存储信息成绩
Dim ty(1 To 600） As Integer '存储通用成绩
Dim n As Integer ’存储记录总数
Private Sub Form_Load()
'本过程从数据库中读取学生数据，存储在相应的变量中，并在 List1 中显示,代码略
End sub
Private Sub Command1_Click()
Dim key As Integer, mid As Integer
Dim i As Integer， L As Integer, R As Integer， k As Integer
Dim tmp1 As String， tmp2 As Integer
'以“信息”为主要关键字、“通用"为次要关键字排序
For i = 1 To n — 1
k = i
For j = i + 1 To n
If xx(k） 〈 xx（j) or ______①______ Then
k = j
End If
Next j
If k <> i Then
tmp1 = xm(k) : xm（k） = xm(i） ： xm（i) = tmp1
tmp2 = xx(k) : xx（k） = xx（i) : xx(i) = tmp2
tmp2 = ty（k) ： ty(k) = ty（i） : ty（i) = tmp2
End If
Next i '查询记录
key = Val(Text1．Text） L = 1 ： R = n
Do While L <= R
mid = （L + R） \ 2
If ______②______ Then
L = mid + 1
Else
R = mid — 1
End If
Loop
List2．Clear
' vbTab 相当于是键盘上制表符 TAB 按键的功能
List2．AddItem ”姓名” & vbTab ＆ "信息" ＆ vbTab & ”通用"
For i = 1 to ______③______
List2．AddItem xm（i) & vbTab & xx（i) ＆ vbTab & ty(i）
Next i
End sub
14、要求从某一个字符串中删除指定的字符（假设所含的英文字母均为小写字母）,并将处理后的字符串重新输出。程序界面如图所示，在文本框text_1中输入原始字符串,在文本框text_2中输入需要删除的字符，单击“删除此字符”按钮(command1）后，在文本框text_3中输出处理后的结果，相应的vb程序如下:
Private Sub Command3_Click()
Dim p As String, k As String
Dim i As Integer, result As String
result = ""
p = text_1.Text
k = text_2。Text
For i = 1 To Len（p)
If Mid(p， i， 1） 〈〉 k Then
result = result + ____①______
End If
Next i
_______②________
End Sub
（1） 解决此问题的算法是_________________（选填:顺序查找 或 对分查找）
（2） 在程序①②处，填入适当的语句或表达式,把程序补充完整。
在程序①出填入：__________________
在程序②出填入：__________________
15、小王设计了学校食堂学生IC卡查询系统，输入学生的卡号，可以查出该卡号对应的余额。所有学生的IC卡号和相应的余额已分别保存在数组stu（按从小到大排序）和数组money中，第i个学生的卡号保存在stu(i）中,对应的卡号余额保存在money（i）中。程序界面如图所示，左边列表框List1中显示的是部分学生的卡号和余额，在文本框Text1中输入学生的IC卡号，单击“查询余额”按钮（Command1）后，如果找到此卡号，则在标签Lab3中显示“此卡号余额为”和卡号对应的余额值，如果未找到则显示“找不到此卡号”,请重新输入。

解决此问题的部分程序段如下：
Const n = 1500
Dim stu(1 To n） As Long
Dim money（1 To n) As Single
Private Sub Form_Load()
‘此过程用于对数组stu和数组money进行初始赋值,代码略
End Sub
Private Sub Command1_Click()
Dim x As Long, i As Long, j As Long， m As Long， find As Boolean
x = Val（Text1.Text)
________①__________
j = n
find = False
Do While i 〈= j And Not find
_________②_________
If x = stu(m） Then
________③__________
ElseIf x < stu(m) Then
j = m — 1
Else
i = m + 1
End If
Loop
If find Then
Lab3。Caption = "此卡号余额为” + Str（money(m）) + ”元"
Else
Lab3。Caption = "找不到此卡号，请重新输入"
End If
End Sub
（1） 解决此问题的算法是________（选题：对分查找或顺序查找)
（2） 在程序划线出填入适当的语句或表达式，将程序补充完整：
①________________________
② ________________________
③_________________________
16、对于无序数组 a(下标 1 到 n），通过引入数组 b(下标 1 到 n）,使得 a（b(1))≤a(b（2)） ≤a（b(3)）……≤a（b(n））。小王编写了一个 VB 程序，功能如下：在列表框 List1 中显 示 i、a(i）、b(i）、a（b(i))，在文本框 Text1 输入要查找的数据，单击“查找”按钮 Command1 后，在标签 Label3 中显示该数据在 a 数组中的位置。程序运行界面如图所示
实现上述功能的 VB 程序如下，但加框处代码有错,请改正.
Dim a(1 to 8） As Integer,b(1 to 8） As Integer
Dim n As Integer
Private Sub Form_Load（)
’n=8，对分查找前的 8 个数据存储在 a 数组中,每个数据的位次存储在 b 数组中
’在列表框 List1 中显示数组下标、a 数组、b 数组、a（b（i））数组
’代码略
End Sub
Private Sub Command1_Click（）
Dim i As Integer， j As Integer, k As Integer Dim m As Integer, key As Integer
key = Val(Text1.Text） i = 1：j = n
Do While i 〈= j
a(m)
m = （i + j） \ 2
k =a（m）
If key = k Then Exit Do
ElseIf key 〉 k Then i = m + 1
Else
j = m - 1 End If
Loop
If i > j Then Label3。Caption="该数据不存在”
Else
Str(m)
Label3.Caption =str（m）
End If
End Sub
【巩固训练-变式题】
1、对数组 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 Key 〈 a（m) Then j = m - 1 Else i = m + 1
Loop
A．i=5 B．j=4 C．m=3 D．p=2
2、有以下 VB 程序段（ )
a（1) = 6: a(2） = 8： a(3) = 7： a(4) = 3
a（5) = 1： a（6) = 2： a(7) = 5: a(8） = 4
i = 1: j = 8
key = a(1)
Do While i<j
Do While i 〈 j And a（j） >= key
j = j - 1
Loop
a（i） = a（j)
Do While i 〈 j And a(i) <= key
i = i + 1
Loop
a(j）=a(i）
Loop
a（i） = key
For i = 1 To 8
Label1。Caption = Label1。Caption + ” " + Str（a（i)）
Next i
执行该程序段,标签 Label1 上显示的内容是
A．1 2 3 4 5 6 7 8
B．8
7
6
5 4 3 2 1
C．4 5 2 3 1 6 7 8
D．4
5
1
3 2 6 7 8
3、某对分查找算法的VB程序段如下：
i = 1
j = 7
s = ””
Do While i 〈= j
m = （i + j) \ 2
If a(m） = Key Then
s = "E"
Exit Do
ElseIf a（m） > Key Then
j = m – 1
s = ”L”
Else
i = m + 1
s = "R"
End If
Loop
数组元素a(1)到a(7）的值依次为“25，42,53,66,77，83,98”，若key=60，运行上述程序段后，下列条件表达式成立的是( ）
A. s = ”E” B。 s = ”R" C. s = "L” D. s = ”LRR"
4、某对分查找算法的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
5、已知数组元素 a（1)到 a（9)的值为｛19,28,37,46,55，64，73,82,91}，若在 Text1 中输入 29，然后执行下面程序段：
Key = Val（Text1。Text) \10
Text2。Text = ””
i = 1: j = 9: f = False
Do While i 〈= j And Not f
m = (i + j)\ 2
If a（m） Mod 10 = Key Then
search = m: f = True
ElseIf a(m） Mod 10 〉 Key Then
i = m + 1
Else
j = m – 1
End If
Text2。Text = Text2。Text + Str（m）
Loop
执行完该程序段后,Text2 中显示的内容是( ）
A．5 2 B． 55 37 28 C．55 73 82 D． 5 7 8
6、数组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．③、②、①
7、有一种查找算法,VB程序设计如下：
cs = 0： i = 14: t = i: dx = 0
Do While t <= 100
cs = cs + 1
If a(t) = find Then
Exit Do
ElseIf a（t） 〉 find Then
t = t – 1
If dx = t Then Exit Do
Else
dx = t： i = i – 1
If t + i > 100 Then
t = t + 1
Else
t = t + i
End If
End If
Loop
已知数组a有序递增，有100个元素a（1）到a(100)，变量find的数值是从外部输入，则程序运行后，变量cs的值最大可以是
A． 7 B． 13 C． 14 D． 50
8、小明设计了如下一个查找数据的程序：在一组升序的数列当中，查找不小于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
E