查找算法及程序实现 知识点题库
删数的算法如下:
⑴如果k>0，则从前往后检测相邻字符，否则，转(3)；
⑵①若所有相邻字符都已非降序，则将串尾k个字符删去，k值置0，转(1)；②若相邻两数存在逆序(即前一个数>后一个数)，则将前一个数删除，k值变化，然后回到(1)；
⑶去掉串首的0，输出结果。
按照上述算法思路，编写了VB程序，功能如下:在文本框Text1中输入数字串，在文本框Text2中输入删除的个数，单击“处理”按钮Command1，在文本框Text3中显示最小的整数。程序运行界面如下图所示。
-
（1） 如果输入的数字串为“20160125”，删除个数为4，则结果是。
-
（2） 实现上述功能的VB程序如下，请在划线处填入合适代码。
delete函数说明：(delete st，x，y)为自定义函数，功能为在字符串st中删除x位置开始的y长度的子串。
Private Sub Command1_Click ()
Dim s As String, k As Integer
Dim i As Integer, j As Integer, n As Integer
s = Text1.Text
k = Val(Text2.Text)
n = Len(s)
Do While k>0
i=1
Do While i<n And
i=i+1
Loop
If i=n Then
n=n-k
k = 0
Else
s = delete(s, i, 1)
n=n-1
End If
Loop
i= 1
Do While n>1 And Mid(s,1,1)= “0”
s = delete(s,1 ,1)
i = i+1
n = n-1
Loop
Text3.Text = s
End Sub
Function delete(st As String,x As Integer,y As Integer) As String
delete=Mid(st,1,x-1)+Mid(st,x+y)
‘Mid函数第3个参数省略，则截去从开始位置向右到字符串结尾的所有字符
End Function
-
（1） 如果输入的原数是3638132，删除3位数字，则输出的新数是。
-
（2） 实现上述功能的VB代码如下，请在划线处填入合适代码。
Private Sub Command1_Click()
Dim a(1 To 20) As String
Dim ys As String, xs As String ‘s记录最大的新数
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 n-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
|
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 
And Not flag ‘①
m = (i+j) \2
If key = a(m) Then
flag= True
ElseIf key < a(m) Then
j = m-1
Else
i = m+1
Loop
If Not flag And j > 0 Then
m = 
‘②
If key = a(m) Then flag = True
End If
If flag Then
Text2.ext = str(m)
Else
Text2.Text= “找不到”
End if
End sub
①加框处应改为。
②加框处应改为。
i= 1：j = 8：n = 0
key = Val（Text1.Text）
Do While i<= j
m =（i+j）\2
If a（m）> key Then
j=m-1：n=n-1
Else
i=m+1：n=n+1
End If
Loop
数组元素a（1）到a（8）的值依次是“6，18，23，42，42，42，56，63”。若在文本框Textl中输入42，则以上程序段执行后，下列说法正确的是（ ）
i = 1: j = 6: k = 0
key = Val(Text1.Text)
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
文本框Text1中输入27，执行该程序段后，k的值为2，则a(1)到a(6)各元素可能的值是（ ）
| a[1] | a[2] | a[3] | a[4] | a[5] | a[6] | a[7] | a[8] |
| 2 | 3 | 5 | 9 | 19 | 23 | 29 | 35 |
i=1
Do While i <= 9
If a(i) <> 0 Then
j=10
Do While j > i
If a(j)=a(i) Then a(j)=0
j=j - 1
Loop
End If
i=i+1
Loop
For i=1 To 10
If a(i) <> 0 ThenText1.Text= Text1.Text+str(a(i))
Next i
数组元素a(1)到a(10)的数据依次为“4，1，6，4，4，9，1，7，6”，则程序运行后，文本框Text1中显示的内容是( )
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））
上述程序段中两个方框处的语句分别应为（ ）
key = Val(Text1.Text)
i = 1 : j = 9
Text2.Text = ""
Do While i <= j
If key = a(m) Then Exit Do
If key < a(m) Then
i = m + 1
Else
j = m – 1
End If
Text2.Text = Text2.Text + " " + Str(a(m))
Loop
数组元素a(1)到a(9)的值依次为88，75，70，68，61，58，55，50，43，本框Text1中输入的值是58，执行该程序段，文本框Text2中显示的是61，50，55，则方框处的代码应为（ ）
Key = Val (Text2. Text)
i = 1
j = 9
flag = False
Do While i <= j And flag = False
m= (i+j) \ 2
If 
Then
j= m - 1
Else If Then
i = m+1
Else
If Then
j = m - 1
Else If Then
i = m+1
Else
flag = True
End If
End If
Loop
If flag Then Text3. Text =“在第”+ Str(m) +“个”Else Text3. Text =“找不到”
上述程序段中方框处可选语句为
①Key \ 10 > a(m) \ 10 ②Key \ 10 < a(m) \ 10
③Key Mod 10 < a(m) Mod 10 ④Key Mod 10 > a(m) Mod 10
则方框处处语句依次为（ ）
Key = Int(Rnd * 5 + 5)
i = 1: j = 10: sum = 0
Do While i <= j
m = (i + j ) \ 2
If a(m) <= Key Then
i = m + 1
Else
j = m - 1
End If
sum = sum + m
Loop
数组元素a（1）到a（10）分别是2、4、5、6、6、6、8、8、10、12，程序运行后，sum的值不可能是 （ ）
L = 1 : R = 5 : c = 0
Key = Val(Text1.Text)
Do While L < R And Not f
m = (L + R) \ 2
c = c + 1
If d(m) = Key Then
f = True : Text2.Text = Str(m)
ElseIf d(m) < Key Then
L = m + 1
Else
R = m
End If
Loop
Label1.Caption = Str(c)
数组元素 a(1)到 a(5)的值依次为“19，28，37，46，55”。执行该程序段，下列说法错误的是（ ）
i=1: j=8: t=0
key=int(Rnd( )*7)+14
Do While i<=j
m=int((i+j)/2)
t=t+1
if a(m)=key Then
Exit Do
Else
if a(m)>Key Then
j=m-1
Else
i=m+1
End if
End if
Loop
数组元素a(1)到a(8)的值依次为“2,11,14,15,18,19,20,22”，执行该程度段后，变量t的最大值可能是（ ）
key=Val(Text1. Text):i=1:j=10
Do While i <=J
m=Int(i+j)/2+0.5)
If key Mod 2+ a(m) Mod 2= 1 Then m=m-1
If a(m)= key Then
List 1. AddIton"找到了!": Exit Do
ElseIf a(m)> key Then
j=m-2
Else
i=m+2
End If
Loop
If i>j Then List1. AddItem "未找到此数"
如果数组元素a(1)到a(10)的数据依次是“1，4，5，6，11，10，23，16，25，20”，key的值为1，则执行上述程序段，变量m依次被赋值为（ ）
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
If key < a(m) Then j =m-1 Else i=m+1
Text2.Text = Text2.Text + Str (a (m))
Loop
数组元素a(1)到a(10)的值依次为“1，2，3，4，5，6，7，8，9，10"，文本框Text1中输入的值是4，执行该程序段，文本框Text2中显示的是( )
i = 1: j = 8 : n = 0
key = Val(Text1.Text)
Do While i <= j
m = (i + j- 1) \ 2
n=n+1
If a(m) >=key Then
i = m + 1
Else
j = m - 1
End If
Loop
Label1.Caption=Str(n)+Str(i)
数组元素a(1)到a(8)的值依次为“ 35,32,29,26,21,19,16,12”。在文本框Text1中输入17，执行该程序段后，标签Label1上显示的内容是（ ）
#为列表a赋值，元素均为整型数据，代码略
⑴
for i in range(1,5):
if a[i]>max:
⑵
print(max)
划线处（1）、（2）的代码分别为（ ）
