資源簡介

查找算法的程序實現【教師版】
【例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 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?？梢杂枚鏄涞姆椒紤]這個問題,如下圖所示,節點中的數字表示元素編號,節點在第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))?、赼(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)暫未存儲數據)?，F將文本框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
錯題反思：

展開更多......

收起↑