資源簡介

數據結構與算法效率
一 、選擇題(每小題列出的四個備選項中只有一個是符合題目要求
的，不選、多選、錯選均不得分)
1.某算法的時間復雜度為O(n ),表明該算法的
A.問題規模是n
B.執行時間等于n
C.問題規模與n 成正比
D.執行次數與n 呈線性增大關系
2. 某Python 程序如下：
i=1
k=0
n=int(input())
while i<=n:
k+=2*i
i+=1
該算法的時間復雜度是
A.O(1)
B.O(n)
C.O(n )
D.0(log n)
3. 某 Python 程序如下：
n=int(input("n=")
ansl=ans2=0
fori in range(0,n,2):
for j in range(n):
ansl=ans1+2
ans2=ans2+2*ans1
print("ansl=",ans1,"ans2=",ans2)
該算法的時間復雜度是 ( )
A.O( 1)
B.O(n)
C.O(n )
D.O(2")
4.某算法的部分流程圖如圖所示。
(
開始
輸入
a
a<5
Y
a>10
b~-a%2
輸出
b
結束
b--abs(a)
b*-a/2
N
N
Y
)
該算法的時間復雜度是
A.常量階
B.線性階
C.指數階
D.對數階
5. 某 Python 程序如下：
def f(n):
if n<=2:
return n
else:
return f(n- 1)*n
x=int(input("x=")
print(f(x))
該算法的時間復雜度是
A.O(n)
B.O(n )
C.O(n!)
D.O(nlog n)
6. 對于線性表，適合采用數組存儲數據的情況是
A. 經常需要隨機地訪問查詢數據元素
B.經常需要進行插人和刪除操作
C.表中數據元素經常需要移動位置
D.表中數據元素的個數經常變動
( )
( )
( )
二、非選擇題
7.某算法的Python代碼如下：
def BSearch(key,a):
L=0
R=len(a)-1
while L<=R:
m=(L+R)//2
if a[m]=key:
return m #找到key值則返回m
if a[m]L=m+1
else:
R=m- 1
return None #未找到則返回None
已知列表a的元素已實現升序排序，則函數BSearch()的算法時間復
雜度為 。
8. 某Python程序如下：
def ct(n):
s=0
while n>0:
s+=n%2
n//=2
return s
n=int(input("輸入一個正整數：")
ans=ct(n)
print(ans)
請回答下列問題：
程序運行后，輸入整數23,自定義函數ct(n)中語句“s+=n%2”執 行的次數是
(2)該算法的時間復雜度為 (單選，填字母：A.O(n)/B.O(log n))。
迭代與遞歸
選擇題(每小題列出的四個備選項中只有一個是符合題目要求的，不
選、多選、錯選均不得分)
1.某Python程序如下：
n=int(input())
s=x=0
while n!=0：
x=n%10
s=x+s
n=n//10
print(s)
程序運行后，輸入n 的值為20220412,輸出的結果是 ( )
A.13 B.1119 C.2022 D.9
2. 下列Python程序的功能是求斐波那契數列的第n 項的值：
n=int(input())
t1=t2=1
for i in range(3,n+1):
print("斐波那契數列第"+str(n)+"項的值為："+str(t)
方框中的代碼由以下三部分組成：①tl=t2 ②t2=t ③t=t1+t2
下列選項中代碼順序正確的是 ( )
A.①②③
B.①③②
C.③②①
D.③①②
3. 利用迭代算法求圓周率π值的方法是：計算公式π/4=1-1/3+1/5-
1/7+…,直到最后一項的絕對值小于10- 為止。 Python程序如下：
pi=0
fm=1
k=1
while abs(1/fm*k)>=0.0000001:
pi=pi*4
print(round(pi,6)
方框中的代碼由以下三部分組成：
① fm=fm+2 ②k=-k ③pi=pi+1/fm*k 下列選項中代碼順序正確的是
A.①②③
B.③②①
C.②①③
D.②③①
4.某Python程序如下：
def add(n):
if n==1 or n==2:
s=1
else:
s=2*(add(n- 1)+add(n-2))
return s
m=5
sum=0
for i in range(1,m+1):
sum+=add(i)
print(str(sum))
程序運行后，輸出的結果是
A.44
C.16
5.某 Python程序如下：
def convert(n,base):
s="0123456789ABCDEF"
if nreturn s[n]
else:
( )
B.32
D.6
return convert(n//base,base)+s[n%base]
x=int(input())
y=int(input())
print(convert(x,y))
程序運行后，輸入x的值為164,y 的值為16,輸出的結果是( )
A.104 B.401 C.4A D.A4
6. 編寫一個簡短的遞歸Python 函數，它接受一個字符串s 并且輸出其
逆置字符串。例如字符串“dog”的逆置字符串為“god”。程序代碼
如下：
s=input("請輸入字符串：")
def reverse(s):
if len(s)<=1:
return s
return
print("逆置字符串為：",reverse(s))
劃線處應填入的代碼應是 ( )
A.s[- 1]+reverse(s[1:])
B.reverse(s[1:])+s[- 1]
C.s[- 1]+reverse(s[:- 1])
D.reverse(s[:- 1])+s[- 1]
7.有如下兩個Python自定義函數：
def gcd1(a,b):
if a%b==0:
ans=b
else:
ans=gcd1(b,a%b)
return ans
def gcd2(a,b):
r=a%b
while r!=0:
a=b
b=r
r=a%b
return b
下列說法不正確的是
A.函數gcd1采用了遞歸算法
B.函數gcd2采用了迭代算法
C.gcd1(18,gcd2(9,30))返回的結果是9
D.gcd1(6,15)和gcd2(9,24)返回的結果是相等的
數據結構與數據算法 參考答案
1.D 2.B 3.C 4.A 5.A 6.A
O(log2n)
(1)5 (2)B
迭代與遞歸 參考答案
1.A 2.D 3.B 4.A 5.D 6.C 7.C

展開更多......

收起↑