查找算法的程序实现专项训练 浙江2022届选考专用

登录二一教育在线组卷平台 助您教考全无忧
查找算法的程序实现专项训练 浙江2022届选考专用
一、查找算法的程序实现专项训练 浙江2022届选考专用【gb】
1．（2022高三下·浙江）在数组元素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
【考点】查找算法及程序实现
【解析】【解答】程序实现时，变量i用来表示第几次查找，而a(i)则是第i次查找时被访问到的数组元素。如果某个数组元素a(i)的值等于key则将该数组元素的下标值i显示在text1文本框中，并通过exit for来结束查找。若没有找到key，则i的值必定大于8，故第一空答案为：a(i)=key，第一空答案为：i>8。
【分析】本题考查的是查找算法分析。根据顺序查找的基本思想，依次将数组元素a(1)到a(8)跟查找键值key比较，若相等，显示找到结果并退出循环，否则继续查找。
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
【答案】B
【考点】查找算法及程序实现
【解析】【解答】对该数组进行对分查找，查找关键字“27”需要查找次数是2，查找关键字“32”需要查找次数是3，查找关键字“57”需要查找次数是1，查找关键字“78”需要查找次数是3，查找关键字“80”需要查找次数是2，查找关键字“90”需要查找次数是3，因此平均查找次数为(2+3+1+3+2+3)/6=7/3。故答案选B。
【分析】本题考查对分查找算法。对分查找基本思想：将所要查找的关键数与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素数值与查找关键数相同，表示找到，否则根据数组元素的有序性，就可以确定应该在数组的前半部分还是后半部分继续进行查找。在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。
3．（2022高三下·浙江）某对分查找算法的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
【答案】C
【考点】查找算法及程序实现
【解析】【解答】程序采用对分查找算法，变量c表示查找次数，第一次查找的值为48，第二次查找的值为32或82。故答案选C。
【分析】本题考查的是查找算法。可以用二叉树的方法考虑这个问题，如下图所示：
节点中的数字表示元素编号，节点在第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．（2022高三下·浙江）数组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则横线处语句依次是(　　)
A．①、②、③ B．①、③、② C．②、①、③ D．③、②、①
【答案】C
【考点】查找算法及程序实现
【解析】【解答】如果key是奇数并且查找区间的中间是偶数，则在前半段查找(因为后半段肯定都是偶数)，即j=m-1；否则如果key是偶数并且查找区间的中间是奇数，则在后半段查找(因为前半段肯定都是奇数)，即i=m+1；否则就是纯偶数升序列中找偶数或纯奇数的升序列中找奇数，按正常对分查找即If Key【分析】本题考查的是查找算法。对分查找的基本思路：在有序的数据序列中(一般放在数组中)，首先把查找的数据与数组中间位置的元素进行比较，若相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。
5．（2022高三下·浙江）数组a中存放着已排序的n-1个实验数据(a(1)≥a(2)≥……≥a(n-1)，a(n)暂未存储数据)。现将文本框Text1中输入的新数据插入到数组a中相应位置，从而使n个数据仍保持有序。完成该功能的VB程序段如下，请在划线处填入正确的语句。
x=Val(Text1.Text)
i=1：j=n-1
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。故答案为： i+1或j+2。
【分析】本题考查的是查找算法。对分查找的基本思路：在有序的数据序列中(一般放在数组中)，首先把查找的数据与数组中间位置的元素进行比较，若相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。
6．（2022高三下·浙江）某对分查找算法的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
【考点】查找算法及程序实现
【解析】【解答】本题可以用二叉树的方法解决，如下图所示：
节点中的数字表示元素编号，节点在第n层，表示找到该数要n次。要满足m-n=1，即中点值比查找次数要大1，由图可知，a(4)满足这个条件。
【分析】本题考查的是对分查找算法。程序采用对分查找算法，由代码得如果s=n为1，需满足i>j，即需要查找的key不在数组中，但是仅查找1次不满足该条件，故s=m-n=1，查找3次满足。故答案选C。
7．（2022高三下·浙江）某对分查找算法的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。
【分析】本题考查的是对分查找算法。对分查找的基本思路：在有序的数据序列中(一般放在数组中)，首先把查找的数据与数组中间位置的元素进行比较，若相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。
8．（2022高三下·浙江）数组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′
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=
If key＝a(m) Then flag＝True
End If
If flag Then
Text2.Text＝Str(m)
Else
Text2.Text＝“找不到”
End If
End Sub
其中，加框处应改正为　 　、　 　
【答案】i＜＝j；n－i＋2或n－j＋1或n＋1－(i＋j)\2或其他等价表达式
【考点】查找算法及程序实现
【解析】【解答】数组的前半部分是递增的，后半部分是递减的，且他们的大小变化规律是3→12→25→31→38→55。因此如果在前半部分找不到，还可能在右半部分对称的位置找到。因此第一个加框处应修改为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)可能是要找的数。故答案为：i＜＝j，n－i＋2或n－j＋1或n＋1－(i＋j)\2或其他等价表达式。
【分析】本题考查的是对分查找的思想，算法比较简单，关键是对数组a中存储的是左右交替上升的n个正整数的理解。
9．（2022高三下·浙江）数组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则方框处语句依次是(　　)
A．①、②、③ B．①、③、② C．②、①、③ D．③、②、①
【答案】C
【考点】查找算法及程序实现
【解析】
10．（2022高三下·浙江）采用如下对分查找算法对数组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
【答案】A
【考点】查找算法及程序实现
【解析】【解答】程序运行过程中的变量变化情况：
查找次数 变量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。
【分析】本题考查的是对分查找算法程序。对分查找的基本思路：在有序的数据序列中(一般放在数组中)，首先把查找的数据与数组中间位置的元素进行比较，若相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。
11．（2022高三下·浙江）某学校图书管理系统中有10万条图书资料记录(已经索引排序)，假设从中取出一条记录并与待查找项进行比较所花时间为10毫秒，则用对分法在该系统中查找任意一本指定图书最多花费的时间约为(　　)
A．100万毫秒 B．50万毫秒 C．10毫秒 D．170毫秒
【答案】D
【考点】查找算法及程序实现
【解析】【解答】对分查找的查找效率较高，无论是否找到，最多进行Int(log2n)＋1次查找，表示小于等于log2n＋1的最大整数。n＝100000，比较次数为17次，因此最多花费的时间是170毫秒。故答案选D。
【分析】本题考查的是对分查找算法。对分查找的基本思路：在有序的数据序列中(一般放在数组中)，首先把查找的数据与数组中间位置的元素进行比较，若相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。
12．（2022高三下·浙江）使用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))。故答案为： mid(s，i，len(c))、a(n)=i。
【分析】本题考查的是查找算法。顺序查找的基本思想是：从第一个元索开始，按索引顺序遍历待查找序列，直到找出给定目标或者查找失败。
13．（2022高三下·浙江）某排序算法的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
【答案】A
【考点】排序算法及程序实现
【解析】【解答】当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。
【分析】本题考查的是排序算法的变形应用。
14．（2022高三下·浙江）双向选择排序算法。在经典的选择排序基础上，如果在选择出最小数的同时，也能选择预见最大数并将两数放置合适位置，这样就使排序效率提高一倍。依照上述双向选择排序的算法，小张编写了一个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
【答案】n\2；n-i+1
【考点】排序算法及程序实现
【解析】【解答】每次找出两个最值，因此只要比较的趟数是总数的一半即可。每次实现头尾有序，i相对的数在n－i＋1。故答案为：n\2、n-i+1。
【分析】本题考查的是排序算法的应用。
二一教育在线组卷平台（zujuan.21cnjy.com）自动生成 1 / 1登录二一教育在线组卷平台 助您教考全无忧
查找算法的程序实现专项训练 浙江2022届选考专用
一、查找算法的程序实现专项训练 浙江2022届选考专用【gb】
1．（2022高三下·浙江）在数组元素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．（2022高三下·浙江）某对分查找算法的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．（2022高三下·浙江）数组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则横线处语句依次是(　　)
A．①、②、③ B．①、③、② C．②、①、③ D．③、②、①
5．（2022高三下·浙江）数组a中存放着已排序的n-1个实验数据(a(1)≥a(2)≥……≥a(n-1)，a(n)暂未存储数据)。现将文本框Text1中输入的新数据插入到数组a中相应位置，从而使n个数据仍保持有序。完成该功能的VB程序段如下，请在划线处填入正确的语句。
x=Val(Text1.Text)
i=1：j=n-1
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
6．（2022高三下·浙江）某对分查找算法的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
7．（2022高三下·浙江）某对分查找算法的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
8．（2022高三下·浙江）数组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′
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=
If key＝a(m) Then flag＝True
End If
If flag Then
Text2.Text＝Str(m)
Else
Text2.Text＝“找不到”
End If
End Sub
其中，加框处应改正为　 　、　 　
9．（2022高三下·浙江）数组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则方框处语句依次是(　　)
A．①、②、③ B．①、③、② C．②、①、③ D．③、②、①
10．（2022高三下·浙江）采用如下对分查找算法对数组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
11．（2022高三下·浙江）某学校图书管理系统中有10万条图书资料记录(已经索引排序)，假设从中取出一条记录并与待查找项进行比较所花时间为10毫秒，则用对分法在该系统中查找任意一本指定图书最多花费的时间约为(　　)
A．100万毫秒 B．50万毫秒 C．10毫秒 D．170毫秒
12．（2022高三下·浙江）使用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
13．（2022高三下·浙江）某排序算法的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
14．（2022高三下·浙江）双向选择排序算法。在经典的选择排序基础上，如果在选择出最小数的同时，也能选择预见最大数并将两数放置合适位置，这样就使排序效率提高一倍。依照上述双向选择排序的算法，小张编写了一个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
答案解析部分
1．【答案】a(i)=key；i>8
【考点】查找算法及程序实现
【解析】【解答】程序实现时，变量i用来表示第几次查找，而a(i)则是第i次查找时被访问到的数组元素。如果某个数组元素a(i)的值等于key则将该数组元素的下标值i显示在text1文本框中，并通过exit for来结束查找。若没有找到key，则i的值必定大于8，故第一空答案为：a(i)=key，第一空答案为：i>8。
【分析】本题考查的是查找算法分析。根据顺序查找的基本思想，依次将数组元素a(1)到a(8)跟查找键值key比较，若相等，显示找到结果并退出循环，否则继续查找。
2．【答案】B
【考点】查找算法及程序实现
【解析】【解答】对该数组进行对分查找，查找关键字“27”需要查找次数是2，查找关键字“32”需要查找次数是3，查找关键字“57”需要查找次数是1，查找关键字“78”需要查找次数是3，查找关键字“80”需要查找次数是2，查找关键字“90”需要查找次数是3，因此平均查找次数为(2+3+1+3+2+3)/6=7/3。故答案选B。
【分析】本题考查对分查找算法。对分查找基本思想：将所要查找的关键数与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素数值与查找关键数相同，表示找到，否则根据数组元素的有序性，就可以确定应该在数组的前半部分还是后半部分继续进行查找。在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。
3．【答案】C
【考点】查找算法及程序实现
【解析】【解答】程序采用对分查找算法，变量c表示查找次数，第一次查找的值为48，第二次查找的值为32或82。故答案选C。
【分析】本题考查的是查找算法。可以用二叉树的方法考虑这个问题，如下图所示：
节点中的数字表示元素编号，节点在第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．【答案】C
【考点】查找算法及程序实现
【解析】【解答】如果key是奇数并且查找区间的中间是偶数，则在前半段查找(因为后半段肯定都是偶数)，即j=m-1；否则如果key是偶数并且查找区间的中间是奇数，则在后半段查找(因为前半段肯定都是奇数)，即i=m+1；否则就是纯偶数升序列中找偶数或纯奇数的升序列中找奇数，按正常对分查找即If Key【分析】本题考查的是查找算法。对分查找的基本思路：在有序的数据序列中(一般放在数组中)，首先把查找的数据与数组中间位置的元素进行比较，若相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。
5．【答案】i+1或j+2
【考点】查找算法及程序实现
【解析】【解答】 程序中通过对分查找法找到插入位置，该位置是i，那么就需要把a(n-1)、a(n-2)……a(i)依次往后移一个位置，相当于各位置加1，然后把x存入a(i)中。该位置也可以是j+2。故答案为： i+1或j+2。
【分析】本题考查的是查找算法。对分查找的基本思路：在有序的数据序列中(一般放在数组中)，首先把查找的数据与数组中间位置的元素进行比较，若相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。
6．【答案】C
【考点】查找算法及程序实现
【解析】【解答】本题可以用二叉树的方法解决，如下图所示：
节点中的数字表示元素编号，节点在第n层，表示找到该数要n次。要满足m-n=1，即中点值比查找次数要大1，由图可知，a(4)满足这个条件。
【分析】本题考查的是对分查找算法。程序采用对分查找算法，由代码得如果s=n为1，需满足i>j，即需要查找的key不在数组中，但是仅查找1次不满足该条件，故s=m-n=1，查找3次满足。故答案选C。
7．【答案】C
【考点】查找算法及程序实现
【解析】【解答】分析程序得知，查找成功会输出″M″，循环结束，所以M不可能在中间，排除B选项。对n个数据查找，最多查找次数为 Log2n+1(向下取整)，7个元素，最多查找3次，所以排除D选项。如果无法找到(不输出″M″)，则需要查找3次，也就是最多查找次数。故答案选C。
【分析】本题考查的是对分查找算法。对分查找的基本思路：在有序的数据序列中(一般放在数组中)，首先把查找的数据与数组中间位置的元素进行比较，若相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。
8．【答案】i＜＝j；n－i＋2或n－j＋1或n＋1－(i＋j)\2或其他等价表达式
【考点】查找算法及程序实现
【解析】【解答】数组的前半部分是递增的，后半部分是递减的，且他们的大小变化规律是3→12→25→31→38→55。因此如果在前半部分找不到，还可能在右半部分对称的位置找到。因此第一个加框处应修改为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)可能是要找的数。故答案为：i＜＝j，n－i＋2或n－j＋1或n＋1－(i＋j)\2或其他等价表达式。
【分析】本题考查的是对分查找的思想，算法比较简单，关键是对数组a中存储的是左右交替上升的n个正整数的理解。
9．【答案】C
【考点】查找算法及程序实现
【解析】
10．【答案】A
【考点】查找算法及程序实现
【解析】【解答】程序运行过程中的变量变化情况：
查找次数 变量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。
【分析】本题考查的是对分查找算法程序。对分查找的基本思路：在有序的数据序列中(一般放在数组中)，首先把查找的数据与数组中间位置的元素进行比较，若相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。
11．【答案】D
【考点】查找算法及程序实现
【解析】【解答】对分查找的查找效率较高，无论是否找到，最多进行Int(log2n)＋1次查找，表示小于等于log2n＋1的最大整数。n＝100000，比较次数为17次，因此最多花费的时间是170毫秒。故答案选D。
【分析】本题考查的是对分查找算法。对分查找的基本思路：在有序的数据序列中(一般放在数组中)，首先把查找的数据与数组中间位置的元素进行比较，若相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。
12．【答案】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))。故答案为： mid(s，i，len(c))、a(n)=i。
【分析】本题考查的是查找算法。顺序查找的基本思想是：从第一个元索开始，按索引顺序遍历待查找序列，直到找出给定目标或者查找失败。
13．【答案】A
【考点】排序算法及程序实现
【解析】【解答】当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。
【分析】本题考查的是排序算法的变形应用。
14．【答案】n\2；n-i+1
【考点】排序算法及程序实现
【解析】【解答】每次找出两个最值，因此只要比较的趟数是总数的一半即可。每次实现头尾有序，i相对的数在n－i＋1。故答案为：n\2、n-i+1。
【分析】本题考查的是排序算法的应用。
二一教育在线组卷平台（zujuan.21cnjy.com）自动生成 1 / 1