資源簡介

4.4二分查找法訓練7
學校:___________姓名：___________班級：___________考號：___________
一、選擇題
1．某對分查找算法的VB程序段如下：
Key = Val(Text1. Text)
n = Val(Text2. Text)
i = 1:j = n
Do While i < = j
m = (i+j) \2
If a(m) = Key Then Exit Do' Exit Do表示退出循環
If a(m)> Key Then j= m - 1 Else i= m+ 1
LooP
整數數組元素a(1)到a(100)為升序序列。在文本框Text1和Text2中分別輸入待查找數Key及n，表示在數組a(1)~a(n)間查找數字key。輸入key的值，若找不到該數，且“m=(i+j)\2”該語句執行了4次，則n值可能是（ ）
A．7或8 B．5或31 C．8或30 D．6或15
2．已知一無序數組a中的元素為“90，15，40，72，65，32，81，6”，通過引入數組b存儲數組a元素按升序排列時的下標，b數組元素為“8，2，6，3，5，4，7，1”，使得a(b(1))≤a(b(2))≤a(b(3))……≤a(b(n))，從而對a數組中的數據進行對分查找。部分程序如下：
i＝1:j＝8:c＝0
key＝Val(Text1.Text）
Do While i＜＝j
m＝Int((i+j)/2)
t＝b(m)
c＝c+1
If a(t)＝key Then p＝t:Exit Do
If a(t)＜key Then
i＝m+1
Else
j＝m-1
End If
Loop
當文本框Text1中輸入的值為32時，程序運行結束后變量c的值為（ ）
A．1 B．2 C．3 D．4
3．有10個數據34，22，101，8，14，88，24，17，54，7依次存放在數組a(1 to 10)中，下列關于數據查找的說法中，正確的是（ ）
A．數據19不在數組a(1 to 10)中，不能進行查找
B．可以直接對數組a(1 to 10)采用對分查找
C．最多經過10次比較，肯定能得出查找結論
D．順序查找肯定比對分查找效率低
4．某對分查找算法的VB程序段如下
Key =Val(Text1. Text)
i=1:j=10:n=0
Do While i <=j
m= (i+j)\2
n=n+1
If a(m)>Key Then
j=m-1
Else
i=m+1
End If
Loop
Text2. Text = str(n)
數組元素a(1)到a(10)的值依次為“2，3，5，8，9，10，13，17，19，25”，在文本框Text1中入待查找的整數，執行該程序段，則文本框Text2中顯示3，待查找數不可能是（ ）
A．2 B．4 C．9 D．19
5．以下是依據對分查找思想,設計的一個三分查找程序。已知數組a(1 To 10)中的數據分別是12、21、34、45、59、63、72、86、94、100,當在文本框Text1中輸入“34”時,輸出“34”的位置值“3”,當輸入“33”時,輸出“33”鄰近數的位置值“23”。實現該功能的VB程序段如下:
Key = Val (Text1. Text)
i=1 : j=10
flag = False
Do While i < = j And Not flag
mid1= Int (i + (j-i) /3)
mid2= Int (j - (j-i) /3)
If Key = a(mid1) Or Key = a (mid2) Then
flag = True
ElseIf Key < a (mid1) Then
______(1)______
ElseIf Key > a (mid2) Then
______(2)_______
El se
i=mid1 + 1
j=mid2 - 1
End If
Loop
If _______(3)_______ Then
List2. AddItem Str (mid1)
ElseIf flag Then
List2. AddItem Str (mid2)
Else
List2. AddItem Str(j) + Str (i)
End If
上述程序中方框處可選語句為 ①i=mid1+1;② i=mid2+1;③ j=mid1-1;④ j=mid2-1;⑤ Key=a(mid1);⑥ flag And Key=a(mid1),則(1)、(2)、(3)處語句依次是（ ）
A．④②⑤ B．③②⑥ C．②③⑥ D．④③⑤
6．某對分查找算法的VB程序段如下：
i =1：j=10：nc=0：f=False
Key = Val(Textl. Text)
Do Whilei < = j And Not f
m=(i+j)\ 2
nc=nc+1
If a(m) = Key Then
f = True
ElseIf Key > a(m) Then
j = m-1
Else
i = m+1
End If
Loop
數組元素a(1)到a(10)的值依次為“94，91，87，76，73，70，67，61，18，17”，該程序段運行結束后，若nc的值為2，則Key的值是 （ ）
A．76或67 B．91或61 C．87或61 D．94或91
7．有如下 VB 程序段：
a(1) = 13: a(2) = 22: a(3) = 36: a(4) = 42: a(5) = 50: a(6) = 58: a(7) = 62: a(8) = 70 i = 1: j = 8: count = 0
Randomize
key = Int(Rnd * 100 )
Do While i <= j
m = (i + j + 1) \ 2
If a(m) >= key Then
count = count * 2 + 1
j = m - 1
Else
count = count * 2
i = m + 1
End If
Loop
執行該程序段后，count 的值不可能的是（ ）
A．15 B．14 C．7 D．6
8．有如下VB程序段：
key=Val(Text1.Text)
i=0:j=9:n=0
Do While i<=j
m=(i+ j)\2
n=n+1
If key<=a(m)Then
j=m-1
Else
i=m+1
End If
Loop
s=i
Do While i<9 And a(i)=a(i+1)
i=i+1
Loop
Labe12.Caption = Str(n)+":"+Str(i+1-s)
數組元素a(0~9)的值依次為“3，4，7，8，8，8，9，9，10，12”在文本框Text1中輸入“8”，點擊“查找”按鈕后，Labe12中輸出的結果是（ ）
A．3：3 B．3：4 C．4：3 D．4：4
9．某對分查找的程序代碼如下
Key = Int(Rnd * 25) * 2
n = 0: i = 1: j = 10
Do While i <= j
m = (i + j) \ 2
If Key = a(m) Then
Exit Do
If Key < a(m) Then
j = m - 1: n = n + 1
Else
i = m + 1: n = n - 1
End If
Loop
Text2.Text = Str(n)
其中 a(1)到 a(10)數組的值分別“2，3，6，9，10，18，38，40，47，48”， 執行該程序段后，n 的值不可能的是（ ）
A．0 B．-1 C．-2 D．-3
10．有如下VB程序段：
i =1:j= 6:n =o :Key = Val(Text1.Text)
Do While i<= j
m = (i+j) \ 2
n = n＋1
If Key > a(m) Then j = m- 1 Else i = m ＋1
Loop
a(1)到a(6)的值依次為“99，77，55，44，33，22”，下列說法正確的是（ ）
A．數組a中的元素若無序，也可用此程序段進行查找某個數字
B．無論key值是多少，循環結束后“i >j”一定成立
C．如果key值為55，那么該程序段運行后，變量n的值為1
D．如果key值為40，那么該程序段運行后，變量m的值為5
11．有n個連續的自然數，刪除首尾兩端之外的其中一個數后存儲在數組元素a(1)到a(n-1)中，利用對分查找算法找出這個數的某VB程序段代碼如下：
Constn=10
i=1:j=n–l
DoWhilej-i>=2
m=(i+j)\2
If (1) Then
i=m
Else
__(2)
EndIf
Loop
Text1.Text=Str(( 3 ))
上述程序中(1)(2)(3)劃線處可選語句有:
①a(j)-a(m)=j-m②a(m)-a(i)=m–i
③j=m–1④j=m
⑤a(i)+1⑥a(i)
則上述程序中(1)、(2)、(3)劃線處的代碼依次為
A．①③⑤ B．②④⑤ C．①③⑥ D．②④⑥
12．有一組升序排列的數：3、6、7、10、12、17、26、31、79，如果用對分法查找數據10，則依次訪問的數據為（ ）
A．12、6、7、10 B．12、7、10 C．12、6、10 D．12、7、6、10
13．有如下 VB 程序段：
Const n = 10
key = Val(Text1.Text) '文本框 1 中輸入待查找的數據
i = 1: L = 1: R = n
If check(key) Then 'check(x)為自定義函數,判斷 x 為否偶數,若是返回 True,否則為 False.
Do While Not check(a(L))
L = L + 1
Loop
Else
Do While check(a(R))
R = R - 1
Loop
End If
Do While L <= R
m = (L + R) \ 2
If key = a(m) Then Exit Do
If key > a(m) Then
L = m + 1
If key < a(m) Then
R = m - 1
Loop
若數組元素 a(1)到 a(10)依次為“1，3，5，7，9，2，4，6，8，10”，執行以上程序段，依次對該組數據進行查找，平均查找次數（平均查找次數=總查找次數/數據總個數）為（ ）
A．22/10 B．29/10 C．55/10 D．29/20
14．已知一元二次函數 f（x）=在區間[0，1]之間必定存在著一個極大點x0，使 f（x0）達到最大值?，F用對分查找算法搜索x0的值，開始搜索區間為[0，1]，在搜索到第 n 次時找到x0，已知第n次搜索區間的長度是1/32，則 n 的值是（ ）
A．3 B．4 C．5 D．6
參考答案：
1．C
【詳解】本題主要考查對分查找算法。對分查找算法，最大比較次數為int(log2n)+1，由此可知C選項正確。
2．C
【詳解】本題考查查找算法相關知識。由題目可知，key=32，初始值i=1，j=8，c=0，進入循環：
第一遍循環，m=4，t=3，c=c+1=1，a（t）>key，故執行j＝m-1=3；
第二遍循環，m=2，t=2，c=c+1=2，a（t）第三遍循環，m=3，t=6，c=c+1=3， a（t）=key，故執行p＝t：Exit Do，循環結束，可知程序運行結束后變量c的值為3，故本題選C。
3．C
【詳解】本題考查查找算法相關知識。數據19雖然不在數組a（1 to 10）中，仍舊可對其進行查找，只是查找結果是找不到，選項A錯誤；數組a是無序數組，無法采用對分查找，對分查找是數組必須是有序排列的，選項B錯誤；最多經過10次比較，肯定能得出查找結論，選項C正確；若查找元素是第一個，則順序查找比對分查找效率高，選項D錯誤。故本題正確的是選項C的說法。
4．D
【詳解】本題考查查找算法相關知識。
假設Key=2；
第一次查找，i=1，j=10，則m=5，n=1，a（m）>key成立，故執行j=m-1=4；
第二次查找，i=1，j=4，則m=2，n=2，a（m）>key成立，故執行j=m-1=1；
第三次查找，i=1，j=1，則m=1，n=3，a（m）>key不成立，故執行i=m+1=2，此時i>j，退出循環，故最終n=3，符合題干。
假設Key=4；
第一次查找，i=1，j=10，則m=5，n=1，a（m）>key成立，故執行j=m-1=4；
第二次查找，i=1，j=4，則m=2，n=2，a（m）>key不成立，故執行i=m+1=3；
第三次查找，i=3，j=4，則m=3，n=3，a（m）>key成立，故執行j=m-1=2，此時i>j，退出循環，故最終n=3，符合題干。
假設Key=9；
第一次查找，i=1，j=10，則m=5，n=1，a（m）>key不成立，故執行i=m+1=6；
第二次查找，i=6，j=10，則m=8，n=2，a（m）>key成立，故執行j=m-1=7；
第三次查找，i=6，j=7，則m=6，n=3，a（m）>key成立，故執行j=m-1=5，此時i>j，退出循環，故最終n=3，符合題干。
假設Key=19；
第一次查找，i=1，j=10，則m=5，n=1，a（m）>key不成立，故執行i=m+1=6；
第二次查找，i=6，j=10，則m=8，n=2，a（m）>key不成立，故執行i=m+1=9；
第三次查找，i=9，j=10，則m=9，n=3，a（m）>key不成立，故執行i=m+1=10；
第四次查找，i=10，j=10，則m=10，n=4，a（m）>key成立，故執行j=m-1=9，此時i>j，退出循環，故最終n=4，不符合題干。
故本題待查找數不可能是19，本題選D。
5．B
【詳解】本題主要考查對分查找算法知識點。如果Key = a(mid1) Or Key = a (mid2)，則flag=True，循環結束，如果Key < a (mid1) ，說明查找關鍵字在左邊1/3處，執行 j=mid1-1；如果Key > a (mid2) ，說明查找關鍵字在右邊1/3處，執行 i=mid2+1；如果flag=True，且 Key=a(mid1)，即找到關鍵字key在mid1處，執行List2. AddItem Str (mid1)，故本題選B選項。
6．B
【詳解】本題主要考查對分查找算法實現。對分查找的基本思路：在有序的數據序列中（一般放在數組中）， 首先把查找的數據與數組中間位置的元素進行比較，若相等，則查找成功并退出查找；否則，根據數組元素的有序性，確定數據應在數組的前半部分還是在后半部分查找；在確定了新的查找范圍后，重復進行以上比較，直到找到或未找到為止。本題中，i和j為數組元素的位置，即下標，key為查找關鍵字，nc為查找次數，m為對分查找時分別獲得的數組元素的下標，要嚴格按照公式m=(i+j)\ 2來獲得數據，第一次獲得數據a (5) =73, 接下來有兩種可能，可能key> 73或key<73，獲得數據a(2) =91或a(8)=61，因此B選項正確。
【點睛】
7．C
【詳解】本題考查查找算法相關知識。本題采用選項倒推法，選項A，若最終count=15，則倒推count的變化過程15→7→3→1→0，可知循環每一次都執行count=count*2+1和j=m-1，最終要得到count=15，i=1，j=0，選項A的值可能；選項B，若最終count=14，則倒推count的變化過程14→7→3→1→0，前三趟循環執行count=count*2+1，最后一趟執行count=count*2，最終要得到count=14，i=2，j=1，選項B的值可能；選項C，若最終count=7，則倒推count的變化過程7→3→1→0，當count=7時，此時i=1，j=1，循環并未結束，故count的值無法是7；選項D，若最終count=6，則倒推count的變化過程6→3→1→0，可知當i=3，j=2時，可以得到，選項D的值也可能。故執行該程序段后，count的值不可能的是選項C的值，本題選C。
8．C
【詳解】本題主要考查VB程序查找算法。key=8，i=0，j=9，n=0，第一遍循環，滿足i<=j，m=(0+9)\2=4，n=n+1=1，key=a(4)=8，j=m-1=3；第二遍循環，滿足i<=j，m=(0+3)\2=1，n=n+1=2，key>a(1)=4，i=m+1=2；第三遍循環，滿足i<=j，m=(2+3)\2=2，n=n+1=3，key>a(2)，i=m+1=3；第四遍循環，滿足i<=j，m=(3+3)\2=3，n=n+1=4，key=a(3)，j=m-1=2，退出循環，s=i=3。第二個while循環，當i<9且a(i)=a(i+1)時，i遞增，循環結束后i=5，i+1-s=5+1-3=3，故點擊“查找”按鈕后，Labe12中輸出的結果是4:3，故本題選C選項。
9．C
【詳解】本題主要考查對分查找。對分查找首先將查找鍵與有序數組內處于中間位置的元素進行比較，如果中間位置上的元素內的數值與查找鍵不同，根據數組元素的有序性，就可確定應該在數組的前半部分還是后半部分繼續進行查找；在新確定的范圍內，繼續按上述方法進行查找，直到獲得最終結果。題中a數組共10個元素，所查找數據Key = Int(Rnd * 25) * 2，由此可知，key取值范圍為0-48之間的偶數，則程序執行結束后，n的值不可能為-2，因此C選項正確。
10．B
【詳解】本題主要考查二分查找算法。二分查找的條件是數組有序，選項A說法錯誤；分析程序可知，無論key值是多少，循環結束后“i >j”一定成立，故本題選B選項；如果key值為55，那么該程序段運行后，變量n的值為3，選項C說法錯誤；如果key值為40，那么該程序段運行后，變量m的值為6，選項D說法錯誤。
11．B
【詳解】本題主要考查VB程序的調試。如果a(m)-a(i)=m-i(因為是n個連續的自然數)，則表明刪除的數在m的右邊，令i=m，繼續循環，否則令j=m，最后循環結束，刪除的數即為a(i)的下一個，即a(i)+1，故上述程序中(1)(2)(3)劃線處可選語句有②④⑤，故本題選B選項。
12．A
【詳解】本題主要考查對分查找算法。一共9個數，（1+9）/2=5，第一次查找的數是12，10<12，（1+4）/2=2，第二次查找的數是6，6<10，（3+4）/2=3，第三次查找的數是7，7<10，（4+4）/2=4，第四次查找的數是10，故依次訪問的數據為12、6、7、10，故本題選A選項。
13．A
【詳解】本題主要考查二分查找算法知識點。該數組前半段是奇數，后半段是偶數，所以當查找的關鍵字是奇數時，只需要在左半邊查找，即L=1，R=5，故a(1)到a(5)的查找次數分別為3次、2次、1次、2次、3次，總共是3+2+1+2+3=11次，同理，當查找的關鍵字是偶數時，只需要在右半邊查找，總的查找次數也是11次，故執行以上程序段，依次對該組數據進行查找，平均查找次數（平均查找次數=總查找次數/數據總個數）為（11+11）/10=22/10，故本題選A選項。
14．D
【詳解】本題主要考查對分查找知識點。第一次搜索區間的長度是1，第二次搜索區間的長度是1/2，第三次搜索區間的長度是1/22，則第n次搜索區間的長度是1/2n-1。已知第n次搜索區間的長度是1/32，則1/2n-1=1/32，n=6，故本題選D選項。

展開更多......

收起↑