資源簡介

數據查找
一 、選擇題(每小題列出的四個備選項中只有一個是符合題目要求
的，不選、多選、錯選均不得分)
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)

展開更多......

收起↑