查找算法的程序实现【教师版】
【例1】 在数组元素a(1)到a(8)中查找键值为key的数,其顺序查找的VB程序段如下,请在划线处填写正确的语句。
for i=1 to 8
if ① then
Text1.text=str(i)
exit for
end if
next i
if ② then
text1.text=″在数组中没有找到″+str(key)
end if
答案:①a(i)=key ② i>8
解析:根据顺序查找的基本思想,依次将数组元素a(1)到a(8)跟查找键值key比较,若相等,显示找到结果并退出循环,否则继续查找。程序实现时,变量i用来表示第几次查找,而a(i)则是第i次查找时被访问到的数组元素。如果某个数组元素a(i)的值等于key则将该数组元素的下标值i显示在text1文本框中,并通过exit for来结束查找。若没有找到key,则i的值必定大于8,故划线①处的条件表达式为“a(i)=key”,划线②处的条件表达式为“i>8”。
【例2】.某数组的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
答案：D
对分查找最多进行[log2N]+1次查找,N=6,所以最多进行2次查找。
【例3】.某对分查找算法的VB程序段如下:
i=1:j=8:c=0
Do While i<=j
c=c+1
m=Fix((i+j)/2)
If key=b(m) Then Exit Do
If key
Loop
数组元素b(1)到b(8)的值依次为“22,32,39,48,71,82,96,106”。若该程序段运行结束后,c的值为2,则key的值是( )
A.48或32 B.48或96
C.32或82 D.82或96
答案：C
解析：程序采用对分查找算法,变量c表示查找次数,第一次查找的值为48,第二次查找的值为32或82。可以用二叉树的方法考虑这个问题,如下图所示,节点中的数字表示元素编号,节点在第n层,表示找到该数要n次。对于8个升序的数列a,第1次查找的是a(4),第2次找的是a(2)、a(6),第3次找的是a(1)、a(3)、a(5)、a(7),第4次找的是a(8)。
【例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则(1)、(2)、(3)处语句依次是( )
A.①、②、③ B.①、③、②
C.②、①、③ D.③、②、①
答案：C
解析：如果key是奇数并且查找区间的中间是偶数,则在前半段查找(因为后半段肯定都是偶数),即j=m-1;否则如果key是偶数并且查找区间的中间是奇数,则在后半段查找(因为前半段肯定都是奇数),即i=m+1;否则就是纯偶数升序列中找偶数或纯奇数的升序列中找奇数,按正常对分查找即If Key强化训练
1.数组a中存放着已排序的n-1个实验数据(a(1)≥a(2)≥……≥a(n-1),a(n)暂未存储数据)。现将文本框Text1中输入的新数据插入到数组a中相应位置,从而使n个数据仍保持有序。完成该功能的VB程序段如下,请在划线处填入正确的语句。
x=Val(Text1.Text)
i=l:j=n-l
Do While i<=j
m=(i+j)\2
If xLoop
For k=n To ① Step-1
a(k)=a(k-1)
Next k
a(i)=x
答案 i+1或j+2
解析 程序中通过对分查找法找到插入位置,该位置是i,那么就需要把a(n-1)、a(n-2)……a(i)依次往后移一个位置,相当于各位置加1,然后把x存入a(i)中。该位置也可以是j+2。
2.某对分查找算法的VB程序段如下:
n=0:i=1:j=6
Key=Val(Text1.Text)
Do While i<=j
m=(i+j)\2
n=n+1
If Key=d(m) Then Exit Do
If Key>d(m) Then j=m-1 Else i=m+1
Loop
If i<=j Then s=m-n Else s=n
d(1)到d(6)的值依次为“88,77,53,47,39,28”,输入某个Key值后,运行该程序段后,变量s结果为1,则输入key的值是( )
A.89 B.77 C.47 D.39
答案 C
解析 程序采用对分查找算法,由代码得如果s=n为1,需满足i>j,即需要查找的key不在数组中,但是仅查找1次不满足该条件,故s=m-n=1,查找3次满足。本题可以用二叉树的方法解决,如下图所示,节点中的数字表示元素编号,节点在第n层,表示找到该数要n次。要满足m-n=1,即中点值比查找次数要大1,由图可知,a(4)满足这个条件。
3.某对分査找算法的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
答案 C
解析 分析程序得知,查找成功会输出″M″,循环结束,所以 M 不可能在中间,排除B 选项。对 n 个数据查找,最多查找次数为 Log2n+1(向下取整),7 个元素,最多查找 3 次,所以排除 D 选项。如果无法找到(不输出″M″),则需要查找 3 次,也就是最多查找次数,故选C。
4.数组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=True
Do While 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=′(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)处应改正为________；
加框(2)处应改正为________。
解析 本题考核的对分查找的思想，算法比较简单，关键是对数组a中存储的是左右交替上升的n个正整数的理解，数组的前半部分是递增的，后半部分是递减的，且他们的大小变化规律是3→12→25→31→38→55。因此如果在前半部分找不到，还可能在右半部分对称的位置找到。因此(1)应修改为i<＝j，也就是说最后一次查找，变量i＝j＝m。如果在前半部分找不到，该数可能比a(m)小，此时j＝m－1，该数大于(j)但小于a(m)，在与j对称的位置(即n－j＋1)可能是要找的数；该数可能比a(m)大，此时i＝m＋1，该数大于a(m)但小于a(i)，在与(i－1)对称的位置(即n－(i－1)＋1)可能是要找的数。
答案 (1)i＜＝j
(2)n－i＋2
或n－j＋1
或n＋1－(i＋j)\2
或其他等价表达式
5.)数组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
ElseIf Key Mod 2＝0 And a(m) Mod 2＝1 Then
Else
End If
Loop
If i>j Then s＝”没有找到！” Else s＝”位置：”＋Str(m)
Text2.Text＝s
上述程序中方框处可选语句为：
①i＝m＋1
②j＝m－1
③If Key则(1)、(2)、(3)处语句依次是( )
A.①、②、③ B.①、③、②
C.②、①、③ D.③、②、①
解析 本题考核对分查找算法基本思想。语句Key Mod 2＝1 And a(m) Mod 2＝0表示要查找的key是奇数，且m指向的数是偶数。奇数在前，向前找，移动尾指针。语句Key Mod 2＝0 And a(m) Mod 2＝1表示要查找的key是偶数，且m指向的数是奇数。
答案 C
6.采用如下对分查找算法对数组a中7个有序数据“15，38，51，66，77，81，99”进行查找，查找数据为“55”，
i＝1∶j＝7∶x＝55
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
Loop
经过上述代码查找后，下列表述正确的是( )
A.i＝m＋1 B.i＝m－1
C.j＞m＋1 D.j＜m－1
解析 本题为对分查找算法程序，分析程序运行过程中的变量变化情况：
查找次数 变量i 变量j 变量m a(m)
第1次查找 1 7 4 66
第2次查找 1 3 2 38
第3次查找 3 3 3 51
退出循环 4 3
经过3次查找，i＝4，j＝3，i＞j，退出循环，根据此时变量值判断A正确。
答案 A
7.某学校图书管理系统中有10万条图书资料记录(已经索引排序)，假设从中取出一条记录并与待查找项进行比较所花时间为10毫秒，则用对分法在该系统中查找任意一本指定图书最多花费的时间约为( )
A.100万毫秒 B.50万毫秒
C.10毫秒 D.170毫秒
解析 对分查找的查找效率较高，无论是否找到，最多进行Int(log2n)＋1次查找，表示小于等于log2n＋1的最大整数。
n＝100000，比较次数为17次，因此最多花费的时间是170毫秒。
答案 D
8.使用VB程序查找单词最大间距:在文本框Text1中输入一段英文,并在文本框Text2中输入英文段落中的某个单词(或字符串),单击“最大间距”按钮(Command1)后,在文本框Text3中显示该单词在文中某两次出现的最大间距,若只出现一次或不出现则显示值为0。程序运行界面如下图所示:
实现上述功能的VB程序如下,请在划线处填入正确的代码。
Private Sub Command1_Click()
Dim a(1 To 1000)As String '数组a存储文中出现该指定单词(或字符串)的各个位置
Dim s As String,c As String,ch As String
Dim n As Integer,max As Integer,i As Integer
s=Text1.Text
c=Text2.Text
n=0∶Max=0
For i=1 To Len(s)-Len(c)+1
ch= ①
If ch=c Then
n=n+1
②
If n>=2 Then
If a(n)-a(n-1)-Len(c)>Max Then Max=a(n)-a(n-1)-Len(c)
End If
End If
Next i
Text3.Text=str(max)
End Sub
答案 ①mid(s,i,len(c)) ②a(n)=i
解析 程序采用顺序查找算法,查找单词c。输入的英文总长度为len(s),待查的单词长度为len(c),循环查找从第1个字符开始,依次截取len(c)个字符与待查单词对比,对比一致则记录个数和出现位置,出现位置存入数组,即a(n)=i。如果找到2个或2个以上相同的字符,储存间距较大的间距值Max。所以①处应为在一段英文s中,从第i个字符开始截取len(c)个字符,即mid(s,i,len(c))。
9..某排序算法的VB程序段如下：
For i＝7 To 5 Step －1
k＝i
For j＝1 To i－1
If a(j)Next j
If i<>k Then
t＝a(i)：a(i)＝a(k)：a(k)＝t
End If
Next i
数组元素a(1)到a(7)的数据依次为“10，41，75，12，63，11，85”。则排序“加工”后数组元素a(1)到a(7)的数据依次是( )
A.85，41，75，63，12，11，10
B.85，75，63，41，12，11，10
C.10，11，12，63，75，41，85
D.10，11，12，41，63，75，85
解析 这是选择排序的变形。当i＝7时，k＝i，k指向的数与前面6个数进行比较，k指向前面较小的数，并交换，第一轮10与85互换。
当i＝6时，k＝i，k指向的数与前面5个数进行比较，k指向前面较小的数，并交换，第二轮没有交换。当i＝5时，k＝i，k指向的数与前面4个数进行比较，k指向前面较小的数，并交换，第三轮12与63交换。
答案 A
10..双向选择排序算法。在经典的选择排序基础上，如果在选择出最小数的同时，也能选择预见最大数并将两数放置合适位置，这样就使排序效率提高一倍。依照上述双向选择排序的算法，小张编写了一个VB程序，功能如下：在列表框List中显示排序前数据，单击“排序”按钮Command1，在列表框List中显示这些数据按升序排序后的结果。运行效果如下图所示。
实现上述功能的VB程序如下，但加框处代码有错，请改正。
Const n＝10
Dim b(1 To n)As Integer
Private Sub command1_Click( )
Dim i As Integer
Dim t As Integer
For i＝1 To ′①
For j＝i To ′②
If b(j) t＝b(i)：b(i)＝b(j)：b(j)＝t
End If
If b(j)>b(n－i＋1) Then
t＝b(j)：b(j)＝b(n－i＋1)：b(n－i＋1)＝t
End If
Next j
Next i
For i＝1 To n
List2.AddItem Str(b(i))
Next i
End Sub
Private Sub Form_Load( )
For i＝1 To 10
b(i)＝1＋Int(Rnd*100)
List1.AddItem Str(b(i))
Next i
End Sub
解析 每次找出两个最值，因此只要比较的趟数是总数的一半即可。每次实现头尾有序，i相对的数在n－i＋1。
答案 n\2 n-i+1查找算法的程序实现【学生版】
【例1】 在数组元素a(1)到a(8)中查找键值为key的数,其顺序查找的VB程序段如下,请在划线处填写正确的语句。
for i=1 to 8
if ① then
Text1.text=str(i)
exit for
end if
next i
if ② then
text1.text=″在数组中没有找到″+str(key)
end if
课后笔记：
【例2】.某数组的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
课后笔记：
【例3】.某对分查找算法的VB程序段如下:
i=1:j=8:c=0
Do While i<=j
c=c+1
m=Fix((i+j)/2)
If key=b(m) Then Exit Do
If keyLoop
数组元素b(1)到b(8)的值依次为“22,32,39,48,71,82,96,106”。若该程序段运行结束后,c的值为2,则key的值是( )
A.48或32 B.48或96
C.32或82 D.82或96
课后笔记：
【例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则(1)、(2)、(3)处语句依次是( )
A.①、②、③ B.①、③、②
C.②、①、③ D.③、②、①
课后笔记：
强化训练
1.数组a中存放着已排序的n-1个实验数据(a(1)≥a(2)≥……≥a(n-1),a(n)暂未存储数据)。现将文本框Text1中输入的新数据插入到数组a中相应位置,从而使n个数据仍保持有序。完成该功能的VB程序段如下,请在划线处填入正确的语句。
x=Val(Text1.Text)
i=l:j=n-l
Do While i<=j
m=(i+j)\2
If xLoop
For k=n To ① Step-1
a(k)=a(k-1)
Next k
a(i)=x
2.某对分查找算法的VB程序段如下:
n=0:i=1:j=6
Key=Val(Text1.Text)
Do While i<=j
m=(i+j)\2
n=n+1
If Key=d(m) Then Exit Do
If Key>d(m) Then j=m-1 Else i=m+1
Loop
If i<=j Then s=m-n Else s=n
d(1)到d(6)的值依次为“88,77,53,47,39,28”,输入某个Key值后,运行该程序段后,变量s结果为1,则输入key的值是( )
A.89 B.77 C.47 D.39
3.某对分査找算法的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
4.数组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=True
Do While 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=′(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)处应改正为________；
加框(2)处应改正为________。
5.)数组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
ElseIf Key Mod 2＝0 And a(m) Mod 2＝1 Then
Else
End If
Loop
If i>j Then s＝”没有找到！” Else s＝”位置：”＋Str(m)
Text2.Text＝s
上述程序中方框处可选语句为：
①i＝m＋1
②j＝m－1
③If Key则(1)、(2)、(3)处语句依次是( )
A.①、②、③ B.①、③、②
C.②、①、③ D.③、②、①
6.采用如下对分查找算法对数组a中7个有序数据“15，38，51，66，77，81，99”进行查找，查找数据为“55”，
i＝1∶j＝7∶x＝55
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
Loop
经过上述代码查找后，下列表述正确的是( )
A.i＝m＋1 B.i＝m－1
C.j＞m＋1 D.j＜m－1
7.某学校图书管理系统中有10万条图书资料记录(已经索引排序)，假设从中取出一条记录并与待查找项进行比较所花时间为10毫秒，则用对分法在该系统中查找任意一本指定图书最多花费的时间约为( )
A.100万毫秒 B.50万毫秒
C.10毫秒 D.170毫秒
8.使用VB程序查找单词最大间距:在文本框Text1中输入一段英文,并在文本框Text2中输入英文段落中的某个单词(或字符串),单击“最大间距”按钮(Command1)后,在文本框Text3中显示该单词在文中某两次出现的最大间距,若只出现一次或不出现则显示值为0。程序运行界面如下图所示:
实现上述功能的VB程序如下,请在划线处填入正确的代码。
Private Sub Command1_Click()
Dim a(1 To 1000)As String '数组a存储文中出现该指定单词(或字符串)的各个位置
Dim s As String,c As String,ch As String
Dim n As Integer,max As Integer,i As Integer
s=Text1.Text
c=Text2.Text
n=0∶Max=0
For i=1 To Len(s)-Len(c)+1
ch= ①
If ch=c Then
n=n+1
②
If n>=2 Then
If a(n)-a(n-1)-Len(c)>Max Then Max=a(n)-a(n-1)-Len(c)
End If
End If
Next i
Text3.Text=str(max)
End Sub
9..某排序算法的VB程序段如下：
For i＝7 To 5 Step －1
k＝i
For j＝1 To i－1
If a(j)Next j
If i<>k Then
t＝a(i)：a(i)＝a(k)：a(k)＝t
End If
Next i
数组元素a(1)到a(7)的数据依次为“10，41，75，12，63，11，85”。则排序“加工”后数组元素a(1)到a(7)的数据依次是( )
A.85，41，75，63，12，11，10
B.85，75，63，41，12，11，10
C.10，11，12，63，75，41，85
D.10，11，12，41，63，75，85
10..双向选择排序算法。在经典的选择排序基础上，如果在选择出最小数的同时，也能选择预见最大数并将两数放置合适位置，这样就使排序效率提高一倍。依照上述双向选择排序的算法，小张编写了一个VB程序，功能如下：在列表框List中显示排序前数据，单击“排序”按钮Command1，在列表框List中显示这些数据按升序排序后的结果。运行效果如下图所示。
实现上述功能的VB程序如下，但加框处代码有错，请改正。
Const n＝10
Dim b(1 To n)As Integer
Private Sub command1_Click( )
Dim i As Integer
Dim t As Integer
For i＝1 To ′①
For j＝i To ′②
If b(j) t＝b(i)：b(i)＝b(j)：b(j)＝t
End If
If b(j)>b(n－i＋1) Then
t＝b(j)：b(j)＝b(n－i＋1)：b(n－i＋1)＝t
End If
Next j
Next i
For i＝1 To n
List2.AddItem Str(b(i))
Next i
End Sub
Private Sub Form_Load( )
For i＝1 To 10
b(i)＝1＋Int(Rnd*100)
List1.AddItem Str(b(i))
Next i
End Sub
错题反思：