浙教版（2019）信息技术选考二轮复习系列专题配套练习——二分查找扩展选择题专题

二分查找扩展选择题专题 班级 姓名 1.如下Python程序实现的功能是：在非降序的数组a中查找“小于等于key”的元素的最大下标值。 #读取一批非降序的数据保存在数组a中，代码略 key=int(input("请输入待查找大的数据：")) i,j=0,len(a)-1 while i<j: m=(i+j+1)//2 if ① : j=m-1 else: i=m print(i) 划线处的代码应为( ) A.a[m]<=key B.a[m]<key C.a[m]>=key D.a[m]>key 2.有如下Python程序段如下： key=int(input("请输入任意一个整数：")) a=[12,18,22,27,36,45] ans=0 i,j=0,len(a)-1 while i<=j: m=(i+j+1)//2 if a[m]<=key: i=m+1 else: j=m-1 ans+=a[m] print(ans) 执行以上程序段，输入任意的key值，则ans的值不可能是( ) A.45 B.57 C.67 D.72 3.某二分查找算法的Python程序段如下： n=len(a) ; f=[0]*n key=int(input()) i,j=0,n-1 while i<=j: m=(i+j)//2 f[m]=1 if a[m]>=key: j=m-1 else: i=m+1 整型数组元素a[0]到a[n-1]为升序序列，输入待查找数，执行该程序段后，数组f中值为1的元素有3个，则n的值不可能为( ) A.5 B.8 C.14 D.15 4.下列Python程序段功能为：在非降序排序列表L中，采用二分查找的方式查找某数值，若能找到则输出该数值在列表L中的起始和结束位置，否则输出“未找到”。 L=[1,2,2,2,2,2,2,2,2,9] key=int(input("key=")) ; i=0 ; j=9 while i<=j: m=(i+j)//2 if ① : j=m-1 else: i=m+1 if L[j]!=key: print("找不到") else: s1=j while key==L[j] and j>=1: j=j-1 ② : print(str(s2),"-",str(s1)) 以上两空中填入的正确代码为( ) A.①key<L[m] ②s2=j B.①key<L[m] ②s2=j+1 C.①key<=L[m] ②s2=j D.①key<=L[m] ②s2=j+1 5.有如下二分查找程序，a为按非降序排序的整形数组： import random key=random.randint(0,4)*2+20 a=[12,14,15,15,19,x,20,24,y,26] n=10 ; i=0 ; j=n-1 ; c=0 ; ans=0 while i<=j: m=(i+j)//2 ; c+=1 if a[m]<=key: i=m+1 else: j=m-1 测试所有可能的key值，程序执行后c均等于4，下列正确的x，y值可以为( ) A.19,25 B.20,26 C.20,25 D.20,24 6.有如下Python程序段： def search(i,j): while i<=j: m=(i+j)//2 if a[m]>a[m-1] and a[m]<a[m+