资源简介

2023-2024学年高二上学期浙教版(2019)选修一5.2 迭代与递归
一、选择题
1．定义如下函数：
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]
执行语句print(f("lab2"))后，输出结果为（ ）
A．12ba B．12ab C．21ab D．2bal
2．递归算法可以用三个字来概括，但不包括下列选项中的（ ）
A．解 B．分 C．治 D．合
3．以下程序代码采用的算法是( )。
def gcd(m，n)：
while m%n != 0：
m，n=n，m%n
return n
a=int(input("请输入a的值："))
b=int(input("请输入b的值："))
print(gcd(a，b))
A．枚举法 B．二分法 C．递归法 D．迭代法
4．下列选项中没有体现递归思想是（ ）
A．快速排序 B．二叉树的先序遍历 C．图的深度优先搜索 D．图的广度优先搜索
5．斐波那契在《计算之书》中提出了一个有趣的兔子问题:从第三个月开始，每个月的兔子对数是前两个月的兔子对数之和，又同时作为下一个月兔子对数的加数。这种重复反馈的过程称为迭代。迭代法也称辗转法，阅读下列程序代码。
def fib(n):
#迭代求Fibonacci数列
f2=f1=1
for i in range(①，n+1):
②
return f2
n=int(input('输入需要计算的月份数：'))
print('兔子总对数为：'，fib(n))
input("运行完毕，请按回车键退出...")
下列说法错误的是（ ）
A．确定迭代变量， 程序中的的f1、f2
B．建立迭代关系式，②处应填写：f1，f2=f2，f1+f2
C．对迭代过程进行控制，①处应填写range(3，n+1)枚举从第三个月开始
D．f1，f2=f2，f1+f2不可以用temp=f1+f2，f1=f2，f2=temp代替
6．定义如下函数：
def peach(day):
if day==7:
num=1
else:
num=(peach(day+1)+1)*2
return num
print(peach(1))
执行该程序段后，输出的结果是（ ）
A．14 B．94 C．190 D．382
7．在递归算法中，以下哪种情况可能导致栈溢出？（ ）
A．递归深度太深 B．递归出口设置正确 C．递归调用自身 D．递归调用其他函数
8．有如下Python程序段：
下列关于两个程序段的说法，正确的是（ ）
A．程序1和程序2都使用了递归算法 B．若问题规模为n，程序1和程序2的时间复杂度不同
C．若程序1中问题规模为n，则n的值就是其循环执行的次数 D．若程序2中自定义函数内的代码只保留①处语句，也能获取到目标值
9．定义如下函数:
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
执行语句m=chg(4)后，m的值为（ ）
A．"ecabd" B．"dbace" C．"abcde" D．"edcba"
10．定义如下函数：
def rf（n）：
if n<3：
return n
return rf（n-1）+rf（n-3）
执行语句v=rf（5），函数rf被调用的次数是（ ）
A．11 B．5 C．7 D．15
11．金老师编写了一个函数，它的功能为使用递归的方法快速计算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．递归算法的基本结构通常包括哪两个部分？（ ）
A．递归出口和递归体 B．递归调用和递归出口
C．递归体和递归入口 D．递归调用和递归体
13．在递归算法中，递归出口的作用是什么？（ ）
A．减少计算量 B．增加计算量 C．结束递归 D．开始递归
14．有如下程序段：
def cal(n):
if n <= 1:
return 1
if n % 2 == 0:
return 2*cal(n-1)
return 1+cal(n-1)
执行语句k=cal(5)，则k的值为（ ）
A．6 B．7 C．10 D．11
15．19世纪末，在欧洲的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。玩家要将最左边杆上的盘子全部移到最右边的杆子上，要求一次只能移动一个盘，且不允许大盘放在小盘的上面。如果最左边杆子上只有3个盘子，则最少需要移动（ ）步才能将所有的盘子移至最右边杆。（ ）
A．15 B．31 C．7 D．8
二、填空题
16．在数学与计算机领域中，递归函数是指用 定义该函数的方法。
17．递归算法的优点之一是可以将复杂问题简化为更简单的 。
18．递归算法必须有一个 ，以防止无限递归。
19．递归算法的时间复杂度分析通常使用 表示。
三、操作题
20．有五位同学参加了植树活动，他们完成植树的棵数都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；如此追问，都说比另一位同学多植两棵，最后问到第五位同学时，他说自己植了10棵。问第一位同学植了多少棵树？以下代码是求第一位同学植树数量的代码，请你补全程序。
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．一个正整数的阶乘是所有小于及等于该数的正整数的积，并且0的阶乘为1，即n!=1×2×3×...×(n-1) ×n，现求n!。
def f(n): # 定义递归函数f(n)
if n == 0 or n == 1:
return 1 # 定义当n为0时函数返回值为1
else:
return # 递归定义n≥1时的通项公式
= int(input("请输入n：")) # 从键盘上输入n的值
print("n！的值为：", ) # 输出结果
四、简答题
22．简述递归方法的基本思想。
23．探讨递归算法在实际问题中的应用及其局限性。
参考答案：
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．函数自身
17．子问题
18．递归出口
19．大O符号
20． C D B
21． n*f(n-1) n f(n)
22．递归方法的基本思想是将一个问题分解为更小的子问题，这些子问题与原问题具有相同的结构。递归方法通过递归调用自身来解决这些子问题，直到达到终止条件为止。
23．递归算法在实际问题中广泛应用于阶乘计算、斐波那契数列计算、树的遍历等领域。然而，递归算法也有局限性，如空间复杂度高、可能导致栈溢出等问题。因此，在实际应用中需要根据问题的特点和需求来选择合适的算法。

展开更多......

收起↑