资源简介

数据查找
一 、选择题(每小题列出的四个备选项中只有一个是符合题目要求
的，不选、多选、错选均不得分)
1.给定任意的查找键，在序列3,5,8,12,15,23中进行数据查找，下列
说法不正确的是 ( )
A.若用顺序查找实现，则最少查找1次
B.若用二分查找实现，则最少查找1次
C.若用顺序查找实现，则最多查找6次
D.若用二分查找实现，则最多查找4次
2. 使用二分查找在有序序列21,45,56,65,68,72,79,83,88,96中查 找75,依次需要进行比较的数据是 ( )
A.68,83,72
B.21,45,56,65,68,72,79
C.68,83,72,79
D.68,45,56,65
3. 某查找算法的Python 程序如下：
key=int(input())
s=0
a=[2,5,18,14,5,56,9,5,37,35,5]
for i in range(len(a)):
if a[i]=key:
s+=1
print(s)
程序运行后，输入key的值为5,输出的结果是 ( )
A.1 B.2
C.3 D.4
4.某Python程序如下：
a=[3,5,8,11,13,15,16,20,25,30]
i.j,x=0,9,20
while i<=j:
m=(i+j)//2
if x==a[m]:
break
if xj=m- 1
else:
i=m+1
(
(
)
)程序运行后，下列表达式的值为True的是
A.i==m+1
B.j=m- 1
C.j>m+1
D.i==m- 1
5.某二分查找算法的Python程序如下：
a=[125,117,115,108,102,95,88,63,51,36]
key=108
i,j=0,len(a)- 1
ss=""
while i<=j:
m=int(i+j)/2+0.5)
ss=ss+str(m)
if key==a[m]:
break
if keyi=m+1
ss=ss+">>"!
else:
j=m- 1
ss=ss+"<<"
print(ss)
程序运行后，输出的结果是
A.4<<1>>2>>3
B.5<<2<<4>>3
C.5<<2>>4<<3
D.5<<2>>4>>3
6. 某Python程序如下：
s=""
a=[4,7,10,13,16,19,22,25]
for k in range(4):
key=5+k*2
i.j=0,7
while i<=j:
m=(i+j)//2
if a[m]==key:
s=s+"M"
break
if a[m]i=m+1
s=s+"R"
else:
j=m- 1
s=s+"L"
print(s)
程序运行后，字符串s中出现次数最多的字母是 ( )
A.L B.R C.M D.L 和R 一样多
7.某二分查找算法的Python程序如下：
a=[6,9,11,16,19,20,24,27,29]
key=int(input("请输入key的值：")
i,j=0,len(a)- 1
s=1"
while i<=j:
m=int((i+j)/2)
s=s+str(m)
if key= =a[m]:
break
elif keyj=m- 1
s=s+","
else:
i=m+1
s=s+","
print(s)
程序运行后，输入key的值，输出的结果为“4,6,7,8,”,则key 的值可
能是 ( )
A.26 B.27 C.28 D.29
8. 用二分查找的方法求不等式2^x+4*x-7<=n(n>=0) 的最大正整数
解，编写Python程序如下：
n=int(input())
L,R=1,n+1
while Lx=(L+R+1)/2
if 2**x+4*x-7<=n:
①
else:
②
print("方程2^x+4*x-7<=n 的最大正整数解为：",R)
(
(
)
)划线处应填入的代码是
A.①L=x+1 ②R=x- 1
B.①R=x- 1 ②L=x+1
C.①L=x②R=x- 1
D.①L=x ②R=x
9. 某二分查找算法的Python 程序如下：
def search(a,key):
i,j=0,len(a)- 1
s=""
while i<=j:
m=(i+j+1)/2
s+=str(m)
if key==a[m]:
break
if key>a[m]:
i=m+1
else:
j=m- 1
print(s)
a=[3,10,25,34,40,52,61,72,83,90]
key=int(input("请输入查找值："))
search(a,key)
程序运行后，下列说法正确的是
A.每次访问区间中中间偏左的数据
B.输入任意正整数进行查找，则最多的查找次数为5
C.输入key的值为10,输出的结果为52
D. 若在某次查找中，当i=j 时，条件“key==a[m]”仍不成立，则表示
查找的数据不存在
二、非选择题
10. 数 组a 中存放着一组正整数，其中奇数在前，偶数在后，奇数与偶 数已分别升序排序，形如[1,7,13,15,21,2,4,8,22,26,30,36,40]。依据
二分查找思想，小马设计了一个从数组a中查找数据key的算法，
其 Python程序如下，请在划线处填入合适的代码。
i=0;j=9
a=[1,7,13,15,21,2,4,8,22,26,30,36,40]
key=int(input("请输入待查找数据："))
while i<=j:
m=(i+j)/2
if a[m]= =key:
break
if key%2==0 and a[m]%2==1:
①
elif key%2==1 and a[m]%2==0:
②
else:
if ③
j-m- 1
else:
i-m+1
if i>j:
print("未找到")
else:
print("数组元素a["+str(m)+"]即为所查找的数据!")
11. 小王家里装修，需要长度相同的k 根木板，因为考虑不周，在购买 原材料时没有提出明确要求，所以供应商提供的木板长度是随机 的。因此他只能将已有的木板切割成k根木板(木板切割前后的 长度均为整数),为了计算最大能够切割出的木板长度，他编写了
一 个Python程序，程序运行示例如图所示。
请输入待分割的木板长度，用空格隔开：759126 请输入需要的木板根数：4 最大切割长度为：6
请回答下列问题：
(1)若给出的木板长度为10,8,3,5,9,18,需要的木板根数为4,则 切割的最大长度为
(2)实现上述功能的Python程序如下，请在划线处填入合适的 代码。
def check(x,k,a):
sum=0
for i in range(len(a)):
if sum>=k
return True
sum= ①
if sum>=k:
return True
else:
return False
s=input("请输入待分割的木板长度，用空格隔开：").split("")
a=[0]*len(s)
for i in range(len(s)):
a[i]-int(s[i])
n=len(s)
k=int(input("请输入需要的木板根数：")
R=0
for i in range(n):
② :
R=a[i]
L=0
ans=0
while L<=R:
m=(L+R)//2
if check(m,k,a):
L=m+1
ans=m
else:
③
print("最大切割长度为：",ans)

展开更多......

收起↑