(共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
Key
Then
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)