資源簡(jiǎn)介

2023-2024學(xué)年高二上學(xué)期浙教版(2019)選修一5.2 迭代與遞歸
一、選擇題
1．定義如下函數(shù)：
def f(s):
if len(s)==1:
return s
elif "0"<=s[0]<="9":
return s[0]+f(s[1:])
else:
return f(s[1:])+s[0]
執(zhí)行語(yǔ)句print(f("lab2"))后，輸出結(jié)果為（ ）
A．12ba B．12ab C．21ab D．2bal
2．遞歸算法可以用三個(gè)字來(lái)概括，但不包括下列選項(xiàng)中的（ ）
A．解 B．分 C．治 D．合
3．以下程序代碼采用的算法是( )。
def gcd(m，n)：
while m%n != 0：
m，n=n，m%n
return n
a=int(input("請(qǐng)輸入a的值："))
b=int(input("請(qǐng)輸入b的值："))
print(gcd(a，b))
A．枚舉法 B．二分法 C．遞歸法 D．迭代法
4．下列選項(xiàng)中沒(méi)有體現(xiàn)遞歸思想是（ ）
A．快速排序 B．二叉樹(shù)的先序遍歷 C．圖的深度優(yōu)先搜索 D．圖的廣度優(yōu)先搜索
5．斐波那契在《計(jì)算之書(shū)》中提出了一個(gè)有趣的兔子問(wèn)題:從第三個(gè)月開(kāi)始，每個(gè)月的兔子對(duì)數(shù)是前兩個(gè)月的兔子對(duì)數(shù)之和，又同時(shí)作為下一個(gè)月兔子對(duì)數(shù)的加數(shù)。這種重復(fù)反饋的過(guò)程稱為迭代。迭代法也稱輾轉(zhuǎn)法，閱讀下列程序代碼。
def fib(n):
#迭代求Fibonacci數(shù)列
f2=f1=1
for i in range(①，n+1):
②
return f2
n=int(input('輸入需要計(jì)算的月份數(shù)：'))
print('兔子總對(duì)數(shù)為：'，fib(n))
input("運(yùn)行完畢，請(qǐng)按回車鍵退出...")
下列說(shuō)法錯(cuò)誤的是（ ）
A．確定迭代變量， 程序中的的f1、f2
B．建立迭代關(guān)系式，②處應(yīng)填寫(xiě)：f1，f2=f2，f1+f2
C．對(duì)迭代過(guò)程進(jìn)行控制，①處應(yīng)填寫(xiě)range(3，n+1)枚舉從第三個(gè)月開(kāi)始
D．f1，f2=f2，f1+f2不可以用temp=f1+f2，f1=f2，f2=temp代替
6．定義如下函數(shù)：
def peach(day):
if day==7:
num=1
else:
num=(peach(day+1)+1)*2
return num
print(peach(1))
執(zhí)行該程序段后，輸出的結(jié)果是（ ）
A．14 B．94 C．190 D．382
7．在遞歸算法中，以下哪種情況可能導(dǎo)致棧溢出？（ ）
A．遞歸深度太深 B．遞歸出口設(shè)置正確 C．遞歸調(diào)用自身 D．遞歸調(diào)用其他函數(shù)
8．有如下Python程序段：
下列關(guān)于兩個(gè)程序段的說(shuō)法，正確的是（ ）
A．程序1和程序2都使用了遞歸算法 B．若問(wèn)題規(guī)模為n，程序1和程序2的時(shí)間復(fù)雜度不同
C．若程序1中問(wèn)題規(guī)模為n，則n的值就是其循環(huán)執(zhí)行的次數(shù) D．若程序2中自定義函數(shù)內(nèi)的代碼只保留①處語(yǔ)句，也能獲取到目標(biāo)值
9．定義如下函數(shù):
def chg(k):
if k==-1:
return ""
else:
c=chr(ord("a")+k)
if k%2==1:
return c+chg(k-l)
else:
return chg(k-1)+c
執(zhí)行語(yǔ)句m=chg(4)后，m的值為（ ）
A．"ecabd" B．"dbace" C．"abcde" D．"edcba"
10．定義如下函數(shù)：
def rf（n）：
if n<3：
return n
return rf（n-1）+rf（n-3）
執(zhí)行語(yǔ)句v=rf（5），函數(shù)rf被調(diào)用的次數(shù)是（ ）
A．11 B．5 C．7 D．15
11．金老師編寫(xiě)了一個(gè)函數(shù)，它的功能為使用遞歸的方法快速計(jì)算Xn:
def fun(x,n):
if n==1:
return x
t=fun( )
if n%2==1:
return x*t*t
else:
return t*t
劃線處代碼為（ ）
A．n//2,x B．n/2,x C．x,n//2 D．x,n/2
12．遞歸算法的基本結(jié)構(gòu)通常包括哪兩個(gè)部分？（ ）
A．遞歸出口和遞歸體 B．遞歸調(diào)用和遞歸出口
C．遞歸體和遞歸入口 D．遞歸調(diào)用和遞歸體
13．在遞歸算法中，遞歸出口的作用是什么？（ ）
A．減少計(jì)算量 B．增加計(jì)算量 C．結(jié)束遞歸 D．開(kāi)始遞歸
14．有如下程序段：
def cal(n):
if n <= 1:
return 1
if n % 2 == 0:
return 2*cal(n-1)
return 1+cal(n-1)
執(zhí)行語(yǔ)句k=cal(5)，則k的值為（ ）
A．6 B．7 C．10 D．11
15．19世紀(jì)末，在歐洲的商店中出售一種智力玩具，在一塊銅板上有三根桿，最左邊的桿上自上而下、由小到大順序串著由64個(gè)圓盤(pán)構(gòu)成的塔。玩家要將最左邊桿上的盤(pán)子全部移到最右邊的桿子上，要求一次只能移動(dòng)一個(gè)盤(pán)，且不允許大盤(pán)放在小盤(pán)的上面。如果最左邊桿子上只有3個(gè)盤(pán)子，則最少需要移動(dòng)（ ）步才能將所有的盤(pán)子移至最右邊桿。（ ）
A．15 B．31 C．7 D．8
二、填空題
16．在數(shù)學(xué)與計(jì)算機(jī)領(lǐng)域中，遞歸函數(shù)是指用 定義該函數(shù)的方法。
17．遞歸算法的優(yōu)點(diǎn)之一是可以將復(fù)雜問(wèn)題簡(jiǎn)化為更簡(jiǎn)單的 。
18．遞歸算法必須有一個(gè) ，以防止無(wú)限遞歸。
19．遞歸算法的時(shí)間復(fù)雜度分析通常使用 表示。
三、操作題
20．有五位同學(xué)參加了植樹(shù)活動(dòng)，他們完成植樹(shù)的棵數(shù)都不相同。問(wèn)第一位同學(xué)植了多少棵時(shí)，他指著旁邊的第二位同學(xué)說(shuō)比他多植了兩棵；追問(wèn)第二位同學(xué)，他又說(shuō)比第三位同學(xué)多植了兩棵；如此追問(wèn)，都說(shuō)比另一位同學(xué)多植兩棵，最后問(wèn)到第五位同學(xué)時(shí)，他說(shuō)自己植了10棵。問(wèn)第一位同學(xué)植了多少棵樹(shù)？以下代碼是求第一位同學(xué)植樹(shù)數(shù)量的代碼，請(qǐng)你補(bǔ)全程序。
def f(n):
if n == 5:
return ___①___
else:
return _____②____
print(___③___)
（1）程序代碼中①處的代碼是( )
A．1 B．2 C．10 D．18
（2）程序代碼中②處的代碼是( )
A．f(n)-2 B．f(5)+2 C． f(n-1)+2 D．f(n+1)+2
（3）程序代碼中③處的代碼是( )
A．f(n) B．f(1) C． f(5) D．5
21．一個(gè)正整數(shù)的階乘是所有小于及等于該數(shù)的正整數(shù)的積，并且0的階乘為1，即n!=1×2×3×...×(n-1) ×n，現(xiàn)求n!。
def f(n): # 定義遞歸函數(shù)f(n)
if n == 0 or n == 1:
return 1 # 定義當(dāng)n為0時(shí)函數(shù)返回值為1
else:
return # 遞歸定義n≥1時(shí)的通項(xiàng)公式
= int(input("請(qǐng)輸入n：")) # 從鍵盤(pán)上輸入n的值
print("n！的值為：", ) # 輸出結(jié)果
四、簡(jiǎn)答題
22．簡(jiǎn)述遞歸方法的基本思想。
23．探討遞歸算法在實(shí)際問(wèn)題中的應(yīng)用及其局限性。
參考答案：
1．A
2．A
3．D
4．D
5．D
6．C
7．A
8．C
9．B
10．C
11．C
12．A
13．C
14．B
15．C
16．函數(shù)自身
17．子問(wèn)題
18．遞歸出口
19．大O符號(hào)
20． C D B
21． n*f(n-1) n f(n)
22．遞歸方法的基本思想是將一個(gè)問(wèn)題分解為更小的子問(wèn)題，這些子問(wèn)題與原問(wèn)題具有相同的結(jié)構(gòu)。遞歸方法通過(guò)遞歸調(diào)用自身來(lái)解決這些子問(wèn)題，直到達(dá)到終止條件為止。
23．遞歸算法在實(shí)際問(wèn)題中廣泛應(yīng)用于階乘計(jì)算、斐波那契數(shù)列計(jì)算、樹(shù)的遍歷等領(lǐng)域。然而，遞歸算法也有局限性，如空間復(fù)雜度高、可能導(dǎo)致棧溢出等問(wèn)題。因此，在實(shí)際應(yīng)用中需要根據(jù)問(wèn)題的特點(diǎn)和需求來(lái)選擇合適的算法。

展開(kāi)更多......

收起↑