查找算法及程序实现 知识点题库
Dim ID（ ） As String '用于存放客户卡号
Dim total（ ） As Long '用于存放积分数
Dim sc As Long 'VIP客户人数
Dim jf As Long '积分数
Private Sub Command1_Click（ ）
Dim k As String '客户卡号
Dim q As Long '代金券额度
Dim i As Long
k = Text1.Text
For i = 1 To sc ’顺序查找
If ID（i） = k Then
jf = total（i）
cash（jf） = q ’ ①
Exit For
End If
Text2.Text = Str（jf）
Label3.Caption = “您可换购的代金券总额为：”+ Str（q） + “元”
Next i
End If
End Sub
' cash函数用于计算VIP客户可换购的代金券额度
Function cash（jf As Long） As Long
If jf >= 2000 And jf <= 20000 Then
Cash = jf\2000*10
ElseIf jf > 20000 And jf <= 50000 Then
Cash = jf\2000*11
ElseIf jf > 50000 And jf <= 100000 Then
Cash = jf\2000*12
ElseIf jf > 100000 And jf <= 150000 Then
Cash = jf\2000*13
Else jf > 150000 Then ’ ②
Cash = jf\2000*14
End If
End Function
Private Sub Form_Load（）
Dim conn As New ADODB.Connection, rs As New ADODB.Recordset
Dim intSQL As Long
conn.ConnectionString = "Provider=Microsoft.ACE.OLEDB.12.0;Data Source=" + App.Path + "\ customer.accdb"
conn.Open
intSQL = "SELECT score FROM Integral"
Set rs.ActiveConnection = conn
rs.CursorType = adOpenStatic
rs.Open intSQL
sc = 0
Do While Not rs.EOF
sc = sc + 1
total（sc） = rs.Fields（"score"）
rs.MoveNext
Loop
rs.Close
conn.Close
Set rs = Nothing
Set conn = Nothing
End Sub
-
（1） 加框处①有错，应改为__。
-
（2） 加框处②有错，应改为。
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)的值分别是（ ）
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的值为（ ）
对于一个轮转后有序数组arr也可以进行二分查找，算法思路如下（以升序为例）：每次根据查找的左侧位置L和右侧位置 R 求出中间位置M后，M左边[L，M]和右边
[M+1，R]这两部分中至少一个是有序的（可根据中间位置数据和边界数据的大小关系判 断）。
arr[M]和待查找数据key比较
⑴arr[M]=key，返回M的值；
⑵若M位置右侧有序，当待查找数据在右侧，则下次在右侧查找，否则在M左侧查找。
⑶若M位置左侧有序，当待查找数据在左侧，则下次在左侧查找，否则在M右侧查找。
问题：
-
（1） 对于轮转后有序数组{7，11，13，17，2，3，5}使用以上函数 search()查找key值3，所需要的查找次数为。
-
（2） 以下VB函数 search()实现了对轮转后有序数组arr进行二分查找的过程，如果查询 成功，返回M值，查询失败则返回-1。请补充程序①②③划线处的代码。
Function search(key As Integer, L As Integer, R As Integer) As Integer
Do While L <= R And search = -1
M = (L + R) \ 2
If arr(M) = key Then
search = M
Else
If Then
If arr(L) <= key And key < arr(M) Then
R = M - 1
Else
L = M + 1
End If
Else
If Then
L = M + 1
Else
R = M - 1
End If
End If
End If
Loop
End Function
参选地区用数字1，2，3……N表示，每个地区所属的省份依次存入数组a(1)到a(N)，若1号地区的省份编号是3，即a(1)=3。分析可知，所求区间的长度至少为K(省份的数量)，最大为N(地区的数量)。我们可以通过二分K到N之间的数求得最小区间长度。例如有10个参选地区，分别来自于5个不同的省份，从左到右排列，地区编号依次为2，1，2，4，3，3，5，5，3，5，则最小的一段包含所有5个地区的区间是从第2个到第7个地区，区间长度为6。
-
（1） 若有12个参选地区，分别来自于6个不同的省份，从左到右排列，地区编号依次为2，1，6，4，6，3，1，2，3，5，5，4，则最小的区间长度为。
-
（2） 请在划线处填入合适的代码。
Dim a(1 To 100) As Integer, K As Integer, N As Integer
Private Sub Form_Load()
‘产生N的值,表示地区数,产生K的值,表示省份数
‘产生编号为1到N的地区的省份编号,并存储在数组a中
‘代码略
End Sub
Private Sub Command1_Click()
Dim M As Integer
i = K: j = N
Do While i <= j
If bh(M) = True Then
j = M -1
ans = M
Else
i = M+1
End If
Loop
Text1.Text = Str(ans)
End Sub
Function bh(M As Integer) As Boolean
Dim f(1 To 25) As Integer ‘f(i)表示是否包含省份为i的地区
Dim t As Integer
bh= False
For i = 1 To N-M + 1 ‘枚举以i为起点的M个地区中各个省份是否都包含
For j =
f(a(j)) = 1
Next j
t= 0
For j = 1 To K
Next j
If t = K Then bh= True: Exit Function
For j = 1 To K
f(j) =0
Next j
Next i
End Function
-
（1） 若要将文本框的默认值设为空，则应设置文本框的属性为空。
-
（2） 为实现上述功能的VB程序，请在划线处填写合适的代码。
Private Sub Command1_Click()
Dim s As String, a As String, b As String
Dim p As Integer, sum As Integer
s=Text1.Text + "e" ′加一个结尾非数字字符
i=1
p=0
sum=0
Do While i<Len(s)
a=Mid(s,i,1)
b=Mid(s,i+1,1)
If (a>="0" And a<="9") And (b>="0" And b<="9") Then
p=p*10+Val(a)
p=p*10+Val(a)
sum=sum+p
i=i+1
End If
i=i+1
Loop
Text2.Text=Str(sum)
End Sub
-
（3） 若输入字符串是“a2b056789bc8”，则程序运行后显示的结果是：。
a(1)=1：a(2)=2：a(3)=3：a(4)=3：a(5)=1
n=5：k=3
L=3：R=10 ‘L值可以为数组元素最大值，R可以为数组所有元素和
Do While L+1<R
m=(L+R)\2
t=0：s=0
For i=1 To n
If t+a(i)>=m Then
s=s+1
t =a(i)
Else
t =t+a(i)
End If
Next i
If t>0 then s=s+1
If s<=k Then① Else ②
Loop
Label1.Caption=“最小值为”&Str(L)
要使程序实现上述算法思想，则代码中①②处应为（ ）
⑴在左边第1位至最后第n个数（从右向左的第n个数）之间，找出最大值，确定新数的最高位；
⑵从最大值的下个位置到第n-1个数之间查找最大值，确定新数的第二位。
⑶依次类推，确定最终的最大数。
设计了一个VB程序，在文本框Text1中输入一个n位正整数，在文本框Text2中输入保留的位数，点击“确定”按钮，在文本框Text3中输出保留的最大新数。程序运行界面如图所示。
-
（1） 如果输入的原数是3635132，保留4位数字，则输出的新数是。
-
（2） 实现上述功能的VB代码如下，请在划线处填入合适代码。
Private Sub Command1_Click()
Dim a(1 To 20)As String
Dim ys As String, xs As String 'xs 记录最大的新数
Dim k As Integer, h As Integer, n As Integer
Dim i As Integer,j As Integer
Dim F as Boolean
xs=" "
ys=Text1. Text
n=Len(ys)
k=Val(Text2. Text)
F=True
If ys=" " Or n>20 Or k=0 Or k>n Then
Label4. Caption="输入的原数或保留位数不符，请重输!"
F=False
End If
For i=1 To n
①
If a(i)<0" Or a(i)>9" Then
Label4. Caption="输人的原数不是数字，请重输!"
Text1. Text=" "
F= False
End If
Next i
If F= True Then
h=1
For i= 1 To k
For j= h To ②
If a(j)>a(h)Then h=j
Next j
③
h=h+1
Next i
Text3. Text=xs
End If
End Sub
① ② ③
实现上述功能的部分代码如下：
key = Val(Text2.Text) i = 1: j = 10
Do While i <= j m = (i + j) 2
if 
i = m + 1
Then
Else
j = m - 1 End If
Loop
Label1.Caption = "大于等于" + Str(key) + "的成绩有" + Str(num) + "个"
上述程序段2个方框处的代码分别为（ ）。
i=1：j=n：f=False
Do While i<=j and Not f
___________
If Val（a（m））=key Then
Search=m：f=True
Elself Val（a（m））>key Then
i=m\2+1
Else
j=m\2-1
End If
Loop
Text2.Text="成绩是"+Str（key）+"的同学叫："+a（m-1）
程序画线处应填入的代码为（ ）
Dim a(1 To 10) As Integer
Dim max As Integer
max=0
For i=1 To 10
If a(i)>max Then max=a(i)
Next i
Label1.Caption =“最大值是：”+ Str (max)
运行该程序时发现，当输入10个正整数时可以得到正确结果，但当输入10个负整数时结果错误。将上述程序段中相应语句仅进行一次更改，就可实现输入10任意整数都能得到最大值的结果，则下列修改正确的是（ ）
s = "AAABBBCCCCDDEFF"
i = 1: j = Len(s): Key = "H": v = ""
Do While i <= j
m = (i + j) \ 2
c = Mid(s, m, 1)
If c = Key Then Exit Do
If c > Key Then
j = m - 1: v = v & c
ElseIf c < Key Then
i = m + 1: v = v & c
End If
Loop
执行完以上程序后，v的值为（ ）
key = Val (Text1. Text)
i =0：j=9：n=0
Do While i<= j
m=(i+j)\2
n=n+1
If key <= a(m) Then
j=m-1
Else
i=m+1
End If
Loop
s=i
Do While i<9 And a(i)= a (i+1)
i=i+1
Loop
Label2.Caption = Str(n) +“：”+ Str(i + 1-s)
数组元素a(0~9)的值依次为“3，4，7，8，8，8，8，9， 10，12”。在文本框Text1中输入“8”，点击“查找”按钮后，Labe12 中输出的结果是( )
i=1： j=11
Do While i <=j
m=(i+j) \ 2
If a(m)=key Then Text1. Text=“查找成功”: Exit Do
If key<a(m) Thenj=m- 1
If key > a(m) Then i=m+1
Loop
