2023-2024学年高二上学期浙教版(2019)选修一5.2 迭代与递归

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页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 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．递归算法在实际问题中广泛应用于阶乘计算、斐波那契数列计算、树的遍历等领域。然而，递归算法也有局限性，如空间复杂度高、可能导致栈溢出等问题。因此，在实际应用中需要根据问题的特点和需求来选择合适的算法。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$