23 对分查找 巩固练习 浙教版（2019）高中信息技术选考（学考）一轮复习（含答案）

数据结构大单元
——对分查找巩固练习
班级 姓名
1.某二分查找算法的python程序段如下:
import random
a = [10,20,30,40,50,60,70,80]
key = random.choice(a)
i , j = 0,len(a)-1 ; s = ""
while i<=j:
m = (i+j)//2
if key == a[m]:
s = s+"M" ; break
elif key < a[m]:
j = m-1 ; s = s+"L"
else:
i = m+1 ; s = s+"R"
该段代码执行后，s的值不可能是( )
A. LLM B. LRM C. RRRM D. RRLM
2.某算法的python程序段如下:
from random import randint
a=[23,21,19,18,16,15,14,11]
key=randint(0,3)*2+13
i , j , c=0 , len(a)-1 , 0
while i<=j:
m=(i+j+1)//2
if a[m]>=key:
i=m+1
else:
j=m-1
c+=1
该程序段执行后，下列说法不正确的是( )
A. i的值为j+1 B. i的值可能是8 C. j的值可能是5 D. c的值一定是3
3.有如下 Python 程序段：
a=[10,15,32,32,45,53,53,65,77,98]
k=int(input()) ; s="" ; left,right=0,len(a)-1
while left<=right:
m=(left+right)//2
if a[m]left=m+1 ; s=s+"R"
else:
right=m-1 ; s=s+"L"
该程序运行后，变量s的值可能是( )
A. "LR" B. "LRL" C. "LRR" D. "RLR"
4.有如下Python程序段：
import random
a=[4,2,6,5,4,2,9,7]
k=random.randint(1,10)
i=0 ; j=len(a)-1 ; x=""
while i<=j:
m=(i+j)//2
if k<=a[m]:
j=m-1 ; x=x+"L"
else:
i=m+1 ; x=x+"R"
print(x)
执行该程序段后，输出的结果不可能出现的是( )
A. "LLL" B. "LRL" C. "RLR" D. "RRRR"
5.某 Python 程序如下：
import random
a=[58,69,78,80,83,84,90,90,95]
key=random.randint(35,45)*2
i=0 ; j=len(a)-1 ; s=[]
while i<=j:
m=(i+j)//2
if key==a[m]:
break
elif keyj=m-1
else:
i=m+1
s.append(a[m])
则执行该程序段后，数组s中的元素不可能为( )
A. 83,90,84 B. 83,69,58 C. 83,69,78 D. 83,90,84
6.某 Python 程序如下：
import random
a=[58,69,78,80,83,84,90,90,95]
key=random.randint(35,45)*2
i=0 ; j=len(a)-1 ; s=[]
while i<=j:
m=(i+j+1)//2 ; s.append(a[m])
if key==a[m]:
break
elif keyj=m-1
else:
i=m+1
则执行该程序段后，数组s的值不可能为( )
A. [83, 90, 90, 84] B.[83,78] C. [83,78,69] D. [83,90,95]
7.某 Python 程序如下：
import random
a=[58,69,78,80,83,84,90,90,95]
key=random.randint(35,45)*2
i=0 ; j=len(a)-1 ; s=[]
while i<=j:
m=(i+j+1)//2
s.append(a[m])
if keyj=m-1
else:
i=m+1
则执行该程序段后，数组s中的元素不可能为( )
A. 83,90,95 B. 83,78,80 C. 83,90,90,84 D. 83,78,69,58
8.有如下Python程序段：
a = [99,85,74,68,53,42,34,27,20,13]
key = int(input("请输入一个整数：")) ; i , j , k , c = 0 , 9 , 0 , "N"
while i <= j:
m = (i + j + 1) //2 ; k = k + 1
if key == a[m]:
c = "Y" ; break
if key > a[m]:
j = m -1
else:
i = m + 1
print(c,k)
执行该程序段后，下列说法不正确的是( )
A. 若输出 k 的值为 2，则 c 的值一定为 Y
B. 该程序段既能用于升序序列的查找，也能用于降序序列的查找
C. 若输入 key 的值为 74，程序执行后变量 i 和 j 的值分别为 0 和 4
D. 输入两位任意正整数，k 的值介于 1 和 4 之间
9.有如下Python程序段：
a = [99,85,74,68,53,42,34,27,20,13]
key = int(input("请输入一个整数：")) ; i , j , k , c = 0 , 9 , 0 , "N"
while i <= j and flag == False:
m = (i + j + 1) //2 ; k = k + 1
if key == a[m]:
c = "Y" ; flag = True
if key > a[m]:
j = m -1
else:
i = m + 1
print(c,k)
执行该程序段后，下列说法正确的是( )
A. 若输出 k 的值为 2，则 c 的值一定为 Y
B. 该程序段既能用于升序序列的查找，也能用于降序序列的查找
C. 若输入 key 的值为 74，程序执行后变量 i 和 j 的值分别为 0 和 4
D. 输入两位任意正整数，k 的值介于 1 和 3 之间
答案
1——5：DBBCB
6——9: DDBA