资源简介

浙教版（2019）选修一5.2迭代与递归同步练习
学校:___________姓名：___________班级：___________考号：___________
一、选择题
1．有如下Python程序段：
def f（n）：
if n==0：
return 1
elif n==1：
return 2
else：
return 2*f（n-1）+f（n-2）
执行该程序段，则f（5）返回的值为（ ）
A．29 B．169 C．70 D．12
2．有如下Python程序段：
def fac（n）：
res=0
for i in range（n）：
res+=2**i
return res
执行语句print（fac（5）），输出的结果为（ ）
A．30 B．31 C．62 D．63
3．在计算机中，一种不断用变量的旧值递推新值的过程。这种用计算机解决问题的基本方法是（ ）
A．查找法 B．排序法 C．分析法 D．迭代法
4．下列适合用来解决裴波那契数列的方法的是（ ）
A．枚举法 B．直接法 C．迭代法 D．以上均不是
5．有如下程序段：
from random import randint
def f(i, j):
if i>=j:
return 0
t=randint (1, 2) # randint (1,2)随机生成1或2
return f(i+t, j)+1
执行语句k=f(0,5)后，k的值不可能为（ ）
A．3 B．4 C．5 D．6
6．定义如下函数：
def f (n, k):
if n==k or k==0:
return 1
else:
return f (n-1, k) +f (n-1, k-1)
执行语句 ans=f (5,3)后, ans的值为（ ）
A．2 B．8 C．10 D．20
7．下列选项中没有体现递归思想是（ ）
A．快速排序 B．二叉树的先序遍历 C．图的深度优先搜索 D．图的广度优先搜索
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的值为100，则程序运行后，输出的结果是（ ）
A．100 B．2500 C．2550 D．5050
9．下面关于递归说法正确的是（ ）
A．函数间接调用自己不是递归 B．递归函数的嵌套调用次数没有限制
C．递归函数的执行效率优于非递归函数 D．递归出口和递归关系是递归函数编写的关键
10．斐波那契数列也叫兔子繁殖数列，小明编写了下列代码求第74个月能繁殖多少对兔子，他使用的算法是（ ）
f1=f2=1
for i in range(3,75):
f1,f2=f2,f1+f2
print('兔子总对数为：',f2)
A．迭代法 B．枚举法 C．二分法 D．解析法
11．定义如下函数:
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"
12．定义如下函数：
def move(n,a,b,c):
if n==1:
print(a,"->",c)
return
move(n-1,a,c,b)
move(1,a,b,c)
move(n-1,b,a,c)
执行语句move(2,"A","B","C")，输出的第一行内容是（ ）
A．a -> c B．A -> C C．a -> b D．A -> B
13．有如下Python程序段：
下列关于两个程序段的说法，正确的是（ ）
A．程序1和程序2都使用了递归算法 B．若问题规模为n，程序1和程序2的时间复杂度不同
C．若程序1中问题规模为n，则n的值就是其循环执行的次数 D．若程序2中自定义函数内的代码只保留①处语句，也能获取到目标值
14．斐波那契数列：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
15．有Python程序段如下:
def f(s):
if len(s)==1:
return s[0]
return f(s[1:])+s[0]
s="abcdefg"
print(f(s))
执行该程序段后，输出的结果为（ ）
A．"a" B．"aceg" C．"bef" D．"gfedcba"
试卷第2页，共2页
试卷第1页，共1页
参考答案：
1．C
【详解】本题考查的是递归。阅读程序可知，f(0)=1，f(1)=2，f(2)=2*f(1)+f(0)=4+1=5，f(3)=2*f(2)+f(1)=2*5+2=12，f(4)=2*f(3)+f(2)=2*12+5=29，f(5)=2*f(4)+f(3)=2*29+12=70。故选C。
2．B
【详解】本题考查的是迭代算法。fac(5)=2**0+2**1+2**2+2**3+2**4=1+2+4+8+16=31，故选B。
3．D
【详解】本题考查迭代法。迭代法是一种不断用变量的旧值递推新值的过程，在计算机中被广泛应用。它是一种基本的计算方法，通过重复执行某个过程或操作来逐步逼近问题的解。在迭代过程中，每次迭代都会使用上一次迭代得到的结果作为新的输入，直到达到满足特定条件或精度要求为止。故答案为：D。
4．C
【详解】本题考查迭代法。迭代法是一种通过重复应用某个固定的程序来逼近所需解的方法。在裴波那契数列中，可以使用循环来计算每个数字，直到得到所需的结果。故答案为：C。
5．D
【详解】本题考查递归算法及随机数逻辑判断知识。由于变量t的取值范围是1或2，而函数f每调用一次，额外增加1，因此每次当t取1的时候，函数f的终值最大。经过模拟可知，每次t都为1时，可知f(0，5)的值为5，也即其最大值为5，因此k值不可能为6。若t的值2次取2，1次取1，则得到k的最小值为3。故本题选项D不可能。
6．C
【详解】本题考查递归函数。这个函数的递归终止条件是 n==k 或 k == 0。 ans=f (5,3)=f (4,3)+f (4,2)=f (3,3)+f (3,2)+f (3,2)+f (3,1)=1+2*(f (2,2)+f(2,1))+f(2,1)+f(2,0)=1+2*(1+f(1,1)+f(1,0))+f(1,1))+f(1,0)+1=1+2*(1+1+1)+1+1=1+6+1+1+1=10。故选C。
7．D
【详解】本题考查递归算法相关知识。快速排序：使用分而治之的策略，它递归地将待排序的数组划分为两个子数组，然后对这两个子数组分别进行排序，最终合并结果。递归是快速排序算法的核心。二叉树的先序遍历：先序遍历二叉树时，首先访问根节点，然后递归地先序遍历左子树，最后递归地先序遍历右子树。这个过程明显体现了递归思想。图的深度优先搜索：深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。在图的深度优先搜索中，从某个节点开始，尽可能深地搜索图的分支，直到该分支的末端，然后回溯并探索下一条路径。这个过程也使用了递归。图的广度优先搜索：广度优先搜索（BFS）是另一种用于遍历或搜索图的算法。与深度优先搜索不同，广度优先搜索按层次遍历图，即首先访问起始节点，然后访问所有相邻节点，接着再访问这些相邻节点的未访问过的相邻节点，依此类推。广度优先搜索通常使用队列来实现，而不是递归。故答案为D选项。
8．C
【详解】本题考查Python程序设计相关内容。本题涉及到递归算法的应用。计算f(100)的值，由f(n)函数可以得到如下递推关系式：f(100)=100+f(98)，f(98)=98+f(96)，f(96)= 96+f(94)，……，f(2)=2+f(0)，f(0)=0，f(101)=100+98+96+……+2=(100+2)*50/2=2550。故本题答案是C选项。
9．D
【详解】本题考查递归。A选项错误。函数间接调用自己仍然是递归，只是通过其他函数进行了间接调用而已。B选项错误。在实际情况下，递归函数的嵌套调用次数是有限制的，受限于计算机的内存和栈空间。C选项错误，通常情况下，递归函数的执行效率较低，因为它需要频繁地压栈和出栈操作，相比之下，非递归函数可能会更高效。D选项正确。递归函数的正确性取决于递归出口（递归终止条件）和递归关系（递归调用），它们是递归函数编写的关键。故答案为：D。
10．A
【详解】本题考查算法相关内容。迭代算法是一类利用递推公式或循环算法通过构造序列来求问题近似解的方法。枚举算法是指在算法中采用搜索的方法，把各种可能的情况都考虑到，并对所得的结果逐一进行判断，过滤掉那些不符合要求的结果，保留那些符合要求的结果。二分法是一种数学方法，也称为二分查找或折半查找，它是一种在有序数组中查找特定元素的算法，这种方法从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果要查找的元素小于中间元素，则在数组的前半部分继续搜索；如果要查找的元素大于中间元素，则在数组的后半部分继续搜索；通过不断缩小搜索范围，最终可以找到要查找的元素。解析算法是指能够找出表示问题的前提条件和结果之间的关系的数学表达式，并通过表达式的计算来实现问题的求解。计算斐波那契数列的算法属于迭代法。故本题答案是A选项。
11．B
【详解】本题考查递归。执行m=chg(4)的过程如下：当k=4时，生成字母"e"，进入递归调用chg(k-1)。当k=3时，生成字母"d"，返回"d"+chg(k-1)。当k=2时，生成字母"c"，进入递归调用chg(k-1)。当k=1时，生成字母"b"，返回"b"+chg(k-1)。当k=0时，生成字母"a"，因为k为偶数，返回chg(k-1)+"a"。当k=-1时，递归结束，返回空字符串，即chg(k-1)=""。回到步骤4，拼接得到chg(k-1)+"a"，即"b"+"a"。回到步骤3，拼接得到"ba"+"c"。回到步骤2，拼接得到"d"+"bac"。回到步骤1，拼接得到"dbac"+"e"，即最终的m的值为"dbace"。故答案为：B。
12．D
【详解】本题考查递归调用。观察代码，本函数为递归函数，具体来讲是解决汉诺塔问题的递归函数。调用语句move(2,"A","B","C"),后，a="A",b="B"，c="C"，第二次调用是执行递归函数中的第一条递归语句move(n-1,a,c,b)，即执行move(1,"A","C","B"),此时a="A"，b="C",c="B";n==1时会执行print(a,"->",c), ,实参代入即执行print("A","->","B")，故第一条输出的是A->B。故答案为：D。
13．C
【详解】本题考查迭代与递归相关知识。A选项错误，程序1使用的是迭代算法，程序2使用的是递归算法。B选项错误，程序段1采用迭代算法实现n的阶乘，循环n次，时间复杂度为O(n)，程序段2采用递归算法求n的阶乘，递归一共调用了n-1次，每次递归执行一个语句，即O(1)，总的时间复杂度为为O(1)*O(n-1)，即为O(n)。故时间复杂度一样。C选项正确，根据循环语句for i in range(1,n+1)，循环n次。D选项错误，若只保留①处的语句，递归算法讲没有出口，即没有结束条件，不能实现算法要求的目标。故答案为：C。
14．A
【详解】本题考查递归调用相关知识。第一次调用函数为fib(5)，fib(5)=fib(4)+fib(3)，fib(4)为第二次调用，fib(3)为第三次调用，fib(3)=fib(2)+fib(1)=1+1=2。故第三次调用返回值为2。故答案为：A。
15．D
【详解】本题考查的是递归算法。阅读自定义函数可知，在递归算法的运行过程中，每一次都将第一个字符移动到最后面。因此该函数实现了倒序输出字符的功能。故本题应选D。
答案第1页，共2页
答案第1页，共2页

展开更多......

收起↑