資源簡介

登錄二一教育在線組卷平臺 助您教考全無憂
查找算法的程序實現專項訓練 浙江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)暫未存儲數據)?，F將文本框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)暫未存儲數據)?，F將文本框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

展開更多......

收起↑