25 二分查找强化练习 浙教版（2019）高中信息技术选考（学考）一轮复习（含答案）

数据结构大单元
——二分查找强化练习
班级 姓名
已知单调函数f(x)在[0,1]区间存在一个x0，使f(x0)=0。现用二分查找法搜索x0的值，开始搜索区间为
[0，1]，若经过10次二分查找后还需继续搜索，则第11次搜索区间的长度为( )
A. 1/2 B. 1/10 C. 1/102 D. 1/210
2. 某二分查找算法的python程序段如下：
d=[7,12,18,25,39,58,61,72,86]
i=0 ; j=8 ; n=0 ; key=int(input())
while i<=j:
n=n+1 ; m=int((i + j)/2)
if key==d[m]:
break
if keyj = m - 1
else:
i = m + 1
若该程序段运行结束后，n的值为2，则key的值是( )
A. 39 B. 18或61 C. 18或72 D. 12或61
3. 某二分查找算法的python程序段如下：
key=int(input()) ; s="" ; i=0 ; j=9
while i<=j:
m=(i+j)//2
if a[m]==key: break
if keyj=m-1 ; s=s+"L"
else:
i=m+1 ; s=s+"R"
按非降序排序的整型数组a的值依次为“11,23,31,39,44,52,60,x,69,89”。输入66，执行该程序段后s值为“RRL”，则x的可能值的个数为( )
A. 3 B. 4 C. 5 D. 6
4. 某二分查找算法的python程序段如下:
key=int(input())
i=0 ; j=8 ; f=[0]*9
while i<=j:
m=int((i+j)/2) ; f[m]=1
if a[m]==key: break
if a[m]>key:
j=m-1
else:
i=m+1
整型数组元素a为升序序列，执行该程序段后，下列选项中，f的值不可能的是( )
A. 1,1,0,0,1,0,0,0,0 B. 0,0,0,0,1,0,0,0,0 C. 0,0,0,0,1,1,1,1,0 D. 0,1,1,1,1,0,0,0,0
5. 某二分查找算法的PYTHON程序段如下：
i=0 ; j=29 ; m=(i+j)//2
while i<=j and key!=a[m]:
if key>a[m]:
i=m+1
else:
j=m-1
m=(i+j)//2 #①
数组元素a[0]到a[29]各不相同且按升序排列，若查找键key与a[8]相等，执行该程序段，①处语句的执行次数是( )
A. 2 B. 3 C. 4 D. 5
6. 某二分查找算法程序段如下:
a=[2,3,5,8,9,10,13,17,19,20]
key=int(input()) ; s=[] ; i=0 ; j=9
while i<=j:
m=(i+j)//2 ; s.append(a[m])
if a[m]>key:
j=m-1
else:
i=m+1
执行该程序段，则s的值可能是( )
A. 9 3 B. 9 3 5 C. 9 17 19 13 D. 9 3 5 8 19
7. 某二分查找算法程序段如下:
a=[14,17,18,19,22,22,22,28,28]
key=int(input("key:")) ; s=0; L=0 ; R=len(a)-1
while L<=R:
m=(L+R)//2
s+=1
if a[m]>key:
R=m-1
else:
L=m+1
执行该程序段后，输入key的值为22，下列描述不正确的是( )
m的值是7 B. s的值是3 C. L的值是6 D. R的值是6
8. 某二分查找算法的程序段如下:
import random
d=[1,3,4,5,7,8,11,13,15,18]
key=random.randint(1,10) ; i=0 ; j=9 ; n=0
if key>5:
key=key+5
while i<=j:
m=(i+j)//2
if key<=d[m]:
j=m-1 ; n=n-1
else:
i=m+1 ; n=n+1
执行该程序段后，变量n的值不可能为( )
A. -2 B. -1 C. 1 D. 2
1——5：DDDCB
6——8：BCA