資源簡介

專題16　算法思想
知識點　遞歸算法
1.斐波那契數列：1，1，2，3，5，8，13，…現用遞歸算法求解第n項，代碼如下：
def fib(n)：
if (n> 2)：
return fib(n－ 1)＋ fib(n－2)
return 1
n＝int(input('輸入一個整數'))
print(fib(n))
程序執行時，輸入一個整數5，則函數fib被第3次調用時的返回值為(　　)
A.2 B.3
C.5 D.8
2.閱讀以下程序：
def f(x)：
if x>5 or x<1：
return '無法計算'
elif x＝＝5：
return 1
else：
return (f(x＋1)＋1)*2
若輸入的x為2，則函數返回值為(　　)
A.22 B.10
C.11 D.'無法計算'
3.有如下Python程序段判斷是否為素數：
from math import sqrt
def prime(x，y)：
if y>int(sqrt(x))＋1：
return ____________
elif x<2 or x%y＝＝0：
return ____________
else：
return ____________
a＝int(input(″請輸入正整數：″))
if prime(a，2)：
print(a，″是素數！″)
else：
print(a，″不是素數！″)
劃線處應填代碼的順序為(　　)
①True　②False　③prime(x，y＋1)
A.②③① B.②①③
C.①③② D.①②③
4.運行下列Python程序段，輸出結果是(　　)
def trans(n)：
if n<＝1：
return str(n)
else：
return trans(n//2)＋str(n % 2)
print(trans(13))
A.1101 B.1011 C.13 D.31
5.有兩個自定義函數如下：
def p1(a，b)： if b＝＝0： return 1 if b%2＝＝0： return p1(a，b//2)*p1(a，b//2) else： return a*p1(a，b－1)
def p2(a，b)： if b＝＝0： return 1 return a*p2(a，b－1)
下列說法不正確的是(　　)
A.p2(2，3)的返回值為 8
B.函數p2的時間復雜度是O(n)
C.函數p1和函數p2均采用了遞歸算法
D.計算p1(2，3)，函數p1的調用次數為4
6.有如下Python代碼：
def f(num)：
for i in range(2，int (num**0.5)＋1)：
if num%i＝＝0：
　　 　　return str(f(num//i))＋″*″＋str(i)
return num
n＝int(input(″輸入n：″))
print(f(n))
程序運行后，輸出的結果不可能是(　　)
A.2 B.3
C.2*2 D.2*3
7.定義如下Python函數；
def fn(n)：
if n＝＝0：
return n
else：
return n%10＋fn(n//10)
print(fn(2023))
運行程序，輸出的結果是(　　)
A.5 B.6
C.7 D.8
8.有如下Python程序段：
def f(n)：
if n<2：
return 0
elif n % 2＝＝0：
return n＋f(n－2)
else：
return f(n－1)
n＝int(input())
print(f(n))
若輸入 n 的值為 101，則程序運行后，輸出的內容為(　　)
A.100 B.2500
C.2550 D.5050
9.定義如下函數：
def myfun(a，s)：
if a*2>＝s：
return a
else：
return myfun(a＋3，s－2)
執行語句n＝myfun(4，18)后，n的值為(　　)
A.4 B.7
C.10 D.13
10.執行下列Python代碼，輸出結果為(　　)
def f(s)：
m＝len(s)
if m＝＝1：
return int(s)
else：
return f(s[：m－1])＋f(s[m－1])
print(f('101'))
A.11 B.2
C.5 D.101
11.有如下Python程序段：
def fun(k)：
if k＝＝0：
return ″″
elif k%2＝＝1：
return chr(k＋ord('A'))＋fun(k－1)
else：
return fun(k－1)＋chr(k＋ord('A'))
有關該程序段，下列說法正確的是(　　)
A.fun(5)的值為″FDBCE″
B.若執行 s＝fun(0)，則函數 fun 的調用次數為 0
C.該算法的時間復雜度為 O(n2)
D.計算機在執行上述遞歸程序時，是通過樹的調用來實現的
12.有如下Python函數：
def trans(num，n)：
s＝″0123456789ABCDEF″
if numreturn s[num]
else：
return trans(num//n，n)＋s[num%n]
執行語句 a＝trans(394，16)后，a 的值為(　　)
A.9A B.1810
C.180 D.18A
13.有如下Python程序段：
def tra(head，a)：
if head＝＝－1：
return
tra(a[head][1]，a)
print(a[head][0]，end＝″ ″)
a＝[[″A″，3]，[″C″，2]，[″D″，4]，[″B″，1]，[″E″，－1]]
head＝0
tra(head，a)
運行該程序段后，輸出的結果是(　　)
A.E D C B A B.A B C D E
C.E B D C A D.A C D B E
14.有如下Python程序段：
def fac(n)：
if n＝＝0：　#①
s＝1
else：
s＝n*fac(n－1)
return s
print(fac(3))
下列說法不正確的是(　　)
A.該程序應用了遞歸算法
B.程序運行后，fac()函數被調用 3 次
C.若問題規模為n，該程序段的時間復雜度為O(n)
D.將①處代碼改為“n＝＝1”，該程序功能不變
15.有如下程序段：
def bubbleSort(n)：
if n＝＝1：
return
for i in range(n－1)：
if arr[i]>arr[i＋1]：
　　 　　arr[i]，arr[i＋1]＝arr[i＋1]，arr[i]
bubbleSort(n－1)
from random import randint
arr＝[64，34，25，12，22，11，90]
n＝randint(3，5)
bubbleSort(n)
調用函數bubbleSort(n)后，arr[3]的值不可能的是(　　)
A.12 B.25 C.34 D.64
16.有如下Python程序段：
#程序段1 def fac(n)： s＝1 for i in range(1，n＋1)： s＝s*i return s print(fac(5))
#程序段2 def fac(n)： if n＝＝1： return 1 else： return n*fac(n－1)　#① print(fac(5))
下列關于兩個程序段的說法，正確的是(　　)
A.程序1和程序2都使用了遞歸算法
B.若問題規模為n，程序1和程序2的時間復雜度不同
C.若程序1中問題規模為n，則n的值就是其循環執行的次數
D.若程序2中自定義函數內的代碼只保留①處語句，也能獲取到目標值
專題16　算法思想
知識點
1.A　[本題考查遞歸算法的相關知識。fib(5)＝fib(4)＋fib(3)，fib(4)＝fib(3)＋fib(2)，fib(3)＝fib(2)＋fib(1)＝1＋1＝2，fib(3)為第3次調用函數fib，第3次調用時返回值為2。]
2.A　[本題考查遞歸算法。f(2)＝(f(3)＋1)*2＝11*2＝22。]
3.D　[本題考查遞歸算法。用2至x－1之間的數y去檢測能否被x整除。若條件y>int(sqrt(x))＋1成立，表示完成所有數檢測，返回True；若能夠除通返回False；否則將y加1，調用自身函數再次進行檢測。]
4.A　[本題考查遞歸算法及自定義函數知識。由遞推公式可以得到：trans(13)＝trans(6)＋″1″＝trans(3)＋″01″＝trans(1)＋″101″。該遞歸函數的功能是將參數n轉換為二進制輸出。]
5.D　[本題考查遞歸算法思想。A選項返回2的3次方。B選項a的n次方，函數調用n次就能得到結果，時間復雜度O(n)。C選項二段代碼都有函數的自我調用，是遞歸算法。D選項描述成如圖所示的二叉樹，共6個節點，計算6次。]
6.D　[該算法通過遞歸實現將一個數分解成質因子的乘積。return str(f(num//i))＋″*″＋str(i)是把大的質因子放在前面。]
7.C　[本題考查遞歸算法思想。根據算法，fn(2023)＝3＋fn(202)，fn(202)＝2＋ fn(20)，fn(20)＝0＋ fn(2)，fn(2)＝2＋fn(0)，因此算法實現將n上各個數字相加。]
8.C　[本題考查遞歸算法的應用。f(100)＝100＋f(98)，f(98)＝98＋f(96)，而后面的參數均為偶數，依此類推，可得：f(100)＝100＋98＋96＋94＋…＋2＝2550。]
9.C　[myfun(4，18)＝ myfun(7，16)＝ myfun(10，14)，滿足a*2>＝s，因此返回10。]
10.B　[程序的功能是分離各個數字并進行相加。]
11.A　[本題考查遞歸算法。fun(5)的調用過程如圖所示。A選項fun(5)的值為FDBCE；B選項 fun(0)的函數調用次數為 1；C選項，從右圖可以看出，該算法的時間復雜度只與 n 有關，應為 O(n)；D選項遞歸通過棧來實現的。]
12.D　[本題考查遞歸函數相關知識。該程序考查將十進制的數字轉換為十六進制。]
13.A　[本題考查遞歸算法和鏈表的遍歷。將頭指針和鏈表作為參數傳入函數，若頭指針不為－1，將下一節點的索引作為頭指針和鏈表a重新進行遞推，返回時先輸出最后一個節點，即對鏈表進行逆序輸出。]
14.B　[本題考查自定義函數和遞歸。A選項使用遞歸算法。B選項遞歸調用4次。C選項每次至多只調用一次，算法時間復雜度和n相關。D選項該自定義函數功能是計算n的階乘，乘以1的次數不影響結果。]
15.B　[本題考查冒泡排序的遞歸實現。函數bubbleSort(n)的功能為對數組arr的前n個元素升序排序。當n分別為3，4，5時，arr[3]的值依次為64，34，12不可能是25。]
16.C　[本題考查算法時間復雜度和遞歸算法。A選項程序段1沒有使用遞歸算法。B選項這兩段程序的算法復雜度都是O(n)。C選項根據循環執行的次數計算時間復雜度。D選項遞推階段必須有終止遞推的代碼。]

展開更多......

收起↑