資源簡介

(共20張PPT)
對分查找變式
基礎知識
key不確定情況
key確定情況
代碼選填情況
基礎知識
（1）基本理念
（2）基本代碼
（3）查找次數
（4）中值情況
m=(i+j)\2
m=Int((i+j))/2
m=Int(i+j+1)\2
m=Fix((i+j)/2)
m=Fix((i+j)/2+0.5)
m=Fix((i+j+0.5)/2)
左
左
右
左
右
左
1.某對分查找算法的部分代碼如下：
i=1:j=1000:flag=True:p=0
key=val(Text1.Text)
Do
While
i<=j
And
flag
m=(i+j)\2
p=p+1
if
a(m)=key
Then
flag=False
if
a(m)>key
Then
j=m-1
Then
i=m+1
Loop
數組元素a(1)到a(1000)中存放著升序排列的數據。下列說法正確的是（
）
A.若key的值小于a(1)，則執行該段程序后，變量j的值等于1
B.若key的值等于a(1)，則執行該段程序后，變量p的值等于10
C.若key的值等于a(1000)，則執行該段程序后，變量i的值等于1001
D.無論key的值是否在數值中a中，執行該段程序后，變量i的值均不可能等于m
基礎知識
key確定情況
（1）觀察key的值
（2）注意分支語句代碼塊的變化
（3）通過輸出進行推導
key確定情況
1.數組元素a(0)到a(9)的值依次為“15,20,25,30,35,40,45,50,55,60”，文本框Text1中輸入的是40，執行該程序段，下列描述正確的是（
）
Key=Val(Text1.Text)
i=0：j=9：s=0
Do
While
i<=j
m=Fix((i+j)/2+0.5)
s=s+1
if
Key=a(m)
Then
Label1.Caption=Label1.Caption+”→”+Str(m)
Exit
Do
End
if
if
KeyThen
j=m-1
Else
i=m+1
Label1.Caption=Label1.Caption+”→”+Str(m)
Loop
Label2.Caption=“經歷”+
Str(s)+“步”
A.標簽Label1顯示內容為“→4→7→5”
B.標簽Label2顯示內容為“歷經1步”
A.該程序為順序結構，查找次數為3
A.該程序為對分查找，查找次數為3
key確定情況
2.已知數組元素a(1)到a(9)的值依次為19,28,37,46,55,64,73,82,91，若在Text1中輸入29，然后執行以下程序段：
Key=Val(Text1.Text)\10
Text2.Text=””
i=1:j=9:f=False
Do
While
i<=j
And
Not
f
m=(i+j)\2
if
a(m)
Mod
10=Key
Then
search=m
f=True
Elseif
a(m)
Mod
10>Key
Then
i=m+1
Else
j=m-1
End
if
Text2.Text=Text2.Text+Str(m)
Loop
則在執行該程序后，Text2中顯示的內容是（
）
A.5
2
B.5
7
8
C.55
28
37
D.55
37
28
key不確定情況
（1）觀察key的取值
（2）注意分支語句代碼塊的變化
（3）通過二叉樹求解
key不確定情況
1.a(1)=2:a(2)=4:a(3)=5:a(4)=6:a(5)=8:a(6)=10:a(7)=11:a(8)=12
n=0
Key=int(Rnd
7)+2
L=1:R=8
Do
While
L<=R
m=(L+R)\2
if
Key=a(m)
Then
Exit
Do
Elseif
a(m)Then
L=m+1
n=n+1
Else
R=m-1
n=n-1
Loop
print
Str(n)
則程序運行后，輸出的結果不可能是（
）
A.0
B.1
C.-1
D.-2
key不確定情況
2.某對分查找算法的VB程序段如下:
Key=int(Rnd
49)
2+1
s=0:i=1:j=10
Do
While
i<=j
m=(i+j)\2
if
Key=a(m)
Then
Exit
Do
if
KeyThen
j=m-1:s=2
s
Else
i=m+1:s=2
s+1
End
if
Loop
數組元素a(1)到a(10)的值依次為“2,6,7,15,20,24,27,43,52,63”，執行該程度段后，s的值不可能為（
）
A.2
B.3
C.5
D.15
代碼選填情況
（1）關注填空區域
（2）考慮最不利情況
代碼選填情況
1.用對分查找的方法求不等式2x+3x-5≤n(n≥0)的最大正整數解，編寫的VB程序段如下：
Private
Sub
Command1_Click(
)
Dim
L
As
Integer,R
As
Integer,n
As
Integer
x
As
Integer
n=Val(Text1.Text)
L=1
R=n+1
Do
While
①
x=(L+R)\2
if
2^X+3
x-5<=n
Then
L=x+1
Else
R=x-1
Loop
Label1.Cption=”方程2^X+3
x-5<=n的最大正整數解為：”
+
②
End
Su
要使程序實現上述算法思想，則橫線上的語句是（
）
A.①L②Str(L)
B.①L②Str(R)
C.①L<=R
②Str(L)
D.①L<=R
②Str(R)
代碼選填情況
2.某vb程序段如下：
L=1：R=10：n=10:key=78
Do
While
L<=R
m=Fix((L+R)/2)
if
①
Then
R=m-1
Else
L=m+1
End
If
Loop
For
i=1
To
R
List1.Additem
Str(a(i))
Next
i
數組元素a(1)到a(10)的值依次為86,78,78,77,73,69,60,54,54,51，若執行該程序段后，列表框List1中輸出的數據個數為3，則①處的代碼為（
）
A.Key>a(m)
B.Key>=a(m)
C.KeyD.Key<=a(m)
實戰訓練
1.
有如下VB程序段：
i=1:j=63:n=0
Do
While
i<=j
M=(i+j)\2
If
Key=a(m)
Then
Exit
Do
Elself
Key＜a(m)
Then
J=m-1:n=n-1
Else
I=m+1:n=n+1
End
if
Loop
數組元素a(1)到a(63)存放著遞增的數據。若執行該程序段后n的值為6,則下列表達式成立的是（
）
A.keyB.key=a(1)
C.key=a(63)
D.key>a(63)
2.有VB程序段如下：
a(1)=2:a(2)=2:a(3)=5:a(4)=6:a(5)=7
Key=2
i=1:j=5:flag=False
Do
While
i<=j
And
Not
Flag
m=(i+j)\2
if
Key
=
a(m)
Then
s=”找到第”+Str(m)+“個”
flag=True:Exit
Do
Elseif
KeyThen
j=m-1
Else
i=m+1
End
if
s=str(m)+s
Loop
Label1.Caption=s
實戰訓練
執行該程序后，在標簽Label1中顯示的內容是（
）
A.1
3
B.3
1
C.找到第1個
D.找到第2個
實戰訓練
3.某對分查找算法的VB程序段如下:
i=1:j=8:t=0
key=int(Rnd()
7)+14
Do
While
i<=j
m=int((i+j)/2)
t=t+1
if
a(m)=key
Then
Exit
Do
Else
if
a(m)>Key
Then
j=m-1
Else
i=m+1
End
if
End
if
Loop
數組元素a(1)到a(8)的值依次為“2,11,14,15,18,19,20,22”，執行該程度段后，變量t的最大值可能是（
）
A.1
B.2
C.3
D.4
實戰訓練
4.
數組元素a(1)-a(2
n)中存儲的一批正整數，以兩個數為一組，每組中兩個數均比前面一組的兩個數要大。現用對分查找的思想，設計一個在數組a中查找數據key的程序，如果找到key，在標簽Label1上顯示“yes”，否則顯示“no”。
Key=Val(Text1.Text)
i=1:j=n
2:flag=False
Do
While
i+1＜=j
And
Not
flag
m=(i+j)\2
If
①
Then
m=m-1
If
a(m)=Key
or
a(m+1)=Key
Then
Flag=True
Elseif
a(m)＞key
Then
②
Else
③
End
if
Loop
If
a(i)=Key
Or
a(j)=Key
Then
flag=True
If
flag
Then
Label1.Caption=”yes”
Else
Label1.Caption=”no”
劃線處的代碼正確的是（
）
A.①m
Mod
2=1
②j=m-1
③i=m+2
B.①m
Mod
2=0
②j=m-1
③i=m+2
C.①m
Mod
2=1
②j=m-2
③i=m+2
D.①m
Mod
2=0
②j=m-2
③i=m+2
小結
1.key確定情況
2.key不確定情況
3.代碼選填情況中小學教育資源及組卷應用平臺
對分查找變式
【基礎知識】
1.某對分查找算法的部分代碼如下：
i=1:j=1000:flag=True:p=0
key=val(Text1.Text)
Do
While
i<=j
And
flag
m=(i+j)\2
p=p+1
if
a(m)=key
Then
flag=False
if
a(m)>key
Then
j=m-1
Then
i=m+1
Loop
數組元素a(1)到a(1000)中存放著升序排列的數據。下列說法正確的是（
）
A.若key的值小于a(1)，則執行該段程序后，變量j的值等于1
B.若key的值等于a(1)，則執行該段程序后，變量p的值等于10
C.若key的值等于a(1000)，則執行該段程序后，變量i的值等于1001
D.無論key的值是否在數值中a中，執行該段程序后，變量i的值均不可能等于m
【key確定情況】
技巧：（1）觀察key的值
（2）注意分支語句代碼塊的變化
（3）通過輸出進行推導
1.數組元素a(0)到a(9)的值依次為“15,20,25,30,35,40,45,50,55,60”，文本框Text1中輸入的是40，執行該程序段，下列描述正確的是（
）
Key=Val(Text1.Text)
i=0：j=9：s=0
Do
While
i<=j
m=Fix((i+j)/2+0.5)
s=s+1
if
Key=a(m)
Then
Label1.Caption=Label1.Caption+”→”+Str(m)
Exit
Do
End
if
if
KeyThen
j=m-1
Else
i=m+1
Label1.Caption=Label1.Caption+”→”+Str(m)
Loop
Label2.Caption=“經歷”+
Str(s)+“步”
A.標簽Label1顯示內容為“→4→7→5”
B.標簽Label2顯示內容為“歷經1步”
A.該程序為順序結構，查找次數為3
A.該程序為對分查找，查找次數為3
2.已知數組元素a(1)到a(9)的值依次為19,28,37,46,55,64,73,82,91，若在Text1中輸入29，然后執行以下程序段：
Key=Val(Text1.Text)\10
Text2.Text=””
i=1:j=9:f=False
Do
While
i<=j
And
Not
f
m=(i+j)\2
if
a(m)
Mod
10=Key
Then
search=m
f=True
Elseif
a(m)
Mod
10>Key
Then
i=m+1
Else
j=m-1
End
if
Text2.Text=Text2.Text+Str(m)
Loop
則在執行該程序后，Text2中顯示的內容是（
）
A.5
2
B.5
7
8
C.55
28
37
D.55
37
28
【key不確定情況】
技巧：（1）觀察key的取值
（2）注意分支語句代碼塊的變化
（3）通過二叉樹求解
1.a(1)=2:a(2)=4:a(3)=5:a(4)=6:a(5)=8:a(6)=10:a(7)=11:a(8)=12
n=0
Key=int(Rnd
7)+2
L=1:R=8
Do
While
L<=R
m=(L+R)\2
if
Key=a(m)
Then
Exit
Do
Elseif
a(m)Then
L=m+1
n=n+1
Else
R=m-1
n=n-1
Loop
print
Str(n)
則程序運行后，輸出的結果不可能是（
）
A.0
B.1
C.-1
D.-2
2.某對分查找算法的VB程序段如下:
Key=int(Rnd
49)
2+1
s=0:i=1:j=10
Do
While
i<=j
m=(i+j)\2
if
Key=a(m)
Then
Exit
Do
if
KeyThen
j=m-1:s=2
s
Else
i=m+1:s=2
s+1
End
if
Loop
數組元素a(1)到a(10)的值依次為“2,6,7,15,20,24,27,43,52,63”，執行該程度段后，s的值不可能為（
）
A.2
B.3
C.5
D.15
【代碼選填情況】
技巧：（1）關注填空區域
（2）考慮最不利情況
1.用對分查找的方法求不等式2x+3x-5≤n(n≥0)的最大正整數解，編寫的VB程序段如下：
Private
Sub
Command1_Click(
)
Dim
L
As
Integer,R
As
Integer,n
As
Integer
x
As
Integer
n=Val(Text1.Text)
L=1
R=n+1
Do
While
①
x=(L+R)\2
if
2^X+3
x-5<=n
Then
L=x+1
Else
R=x-1
Loop
Label1.Cption=”方程2^X+3
x-5<=n的最大正整數解為：”
+
②
End
Sub
要使程序實現上述算法思想，則橫線上的語句是（
）
A.①L②Str(L)
B.①L②Str(R)
C.①L<=R
②Str(L)
D.①L<=R
②Str(R)
2.某vb程序段如下：
L=1：R=10：n=10:key=78
Do
While
L<=R
m=Fix((L+R)/2)
if
①
Then
R=m-1
Else
L=m+1
End
If
Loop
For
i=1
To
R
List1.Additem
Str(a(i))
Next
i
數組元素a(1)到a(10)的值依次為86,78,78,77,73,69,60,54,54,51，若執行該程序段后，列表框List1中輸出的數據個數為3，則①處的代碼為（
）
A.Key>a(m)
B.Key>=a(m)
C.KeyD.Key<=a(m)
【實戰演練】
有如下VB程序段：
i=1:j=63:n=0
Do
While
i<=j
M=(i+j)\2
If
Key=a(m)
Then
Exit
Do
Elself
Key＜a(m)
Then
J=m-1:n=n-1
Else
I=m+1:n=n+1
End
if
Loop
數組元素a(1)到a(63)存放著遞增的數據。若執行該程序段后n的值為6,則下列表達式成立的是（
）
A.keyB.key=a(1)
C.key=a(63)
D.key>a(63)
2.有VB程序段如下：
a(1)=2:a(2)=2:a(3)=5:a(4)=6:a(5)=7
Key=2
i=1:j=5:flag=False
Do
While
i<=j
And
Not
Flag
m=(i+j)\2
if
Key
=
a(m)
Then
s=”找到第”+Str(m)+“個”
flag=True:Exit
Do
Elseif
KeyThen
j=m-1
Else
i=m+1
End
if
s=str(m)+s
Loop
Label1.Caption=s
執行該程序后，在標簽Label1中顯示的內容是（
）
A.1
3
B.3
1
C.找到第1個
D.找到第2個
3.某對分查找算法的VB程序段如下:
i=1:j=8:t=0
key=int(Rnd()
7)+14
Do
While
i<=j
m=int((i+j)/2)
t=t+1
if
a(m)=key
Then
Exit
Do
Else
if
a(m)>Key
Then
j=m-1
Else
i=m+1
End
if
End
if
Loop
數組元素a(1)到a(8)的值依次為“2,11,14,15,18,19,20,22”，執行該程度段后，變量t的最大值可能是（
）
A.1
B.2
C.3
D.4
數組元素a(1)-a(2
n)中存儲的一批正整數，以兩個數為一組，每組中兩個數均比前面一組的兩個數要大。現用對分查找的思想，設計一個在數組a中查找數據key的程序，如果找到key，在標簽Label1上顯示“yes”，否則顯示“no”。
Key=Val(Text1.Text)
i=1:j=n
2:flag=False
Do
While
i+1＜=j
And
Not
flag
m=(i+j)\2
If
①
Then
m=m-1
If
a(m)=Key
or
a(m+1)=Key
Then
Flag=True
Elseif
a(m)＞key
Then
②
Else
③
End
if
Loop
If
a(i)=Key
Or
a(j)=Key
Then
flag=True
If
flag
Then
Label1.Caption=”yes”
Else
Label1.Caption=”no”
劃線處的代碼正確的是（
）
A.①m
Mod
2=1
②j=m-1
③i=m+2
B.①m
Mod
2=0
②j=m-1
③i=m+2
C.①m
Mod
2=1
②j=m-2
③i=m+2
D.①m
Mod
2=0
②j=m-2
③i=m+2
答案：
1.C
1.B
2.B
1.B
2.A
1.D
2.A
1.D
2.C
3.C
4.B
21世紀教育網
www.21cnjy.com
精品試卷·第
2
頁
（共
2
頁）
HYPERLINK
"http://21世紀教育網(www.21cnjy.com)
"
21世紀教育網(www.21cnjy.com)

展開更多......

收起↑