資源簡介

數據結構大單元
——二分查找強化練習
班級 姓名
已知單調函數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

展開更多......

收起↑