5.2迭代与递归（分层作业）-高中信息技术选修1数据与数据结构 分层作业

5.2迭代与递归（分层作业） 【夯实基础】 1. ______是重复反馈过程的活动，______是重复调用函数自身（ ） A．递推，递归 B．递归，递推 C．迭代，递归 D．递归，迭代 2.运用分治策略将一个难以直接解决的大问题分割成规模较小的子问题分别解决，最终达到解决大问题的目的。这要求原问题和子问题的（ ） A．问题性质相同，问题规模相同 B．问题性质不同，问题规模相同 C．问题性质相同，问题规模不同 D．问题性质不同，问题规模不同 3 . 有如下程序段： 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 4 . 走楼梯的问题可以利用迭代算法来解决，解决该问题的正确顺序应该是（ ） ①建立迭代关系式 ②让迭代过程无休止地重复执行 ③对迭代过程进行控制 ④确定迭代变量 A．④①③② B．①②③ C．④①③ D．①④③ 5. 定义如下函数： def tran(x,y): if x > 0: return tran(x//y,y) + str (x%y) else: return "0" 执行语句k = tran(14,2)后，k的值为（ ） A．″1010″ B．″1110″ C．″01010″ D．″01110″ 6.已知递归式为F（n）=F（n-1）+2，且F（1）=5，则当n=3时，F的值为（ ） A．7 B．9 C．11 D．13 7. 迭代与递归的根本区别在于？ ( ) A. 迭代使用循环结构，递归使用函数调用 B. 迭代处理问题更直观，递归更抽象 C. 迭代通常更节省空间 D. 以上都是 8. 递归调用的基本原则是？( ) A. 无须考虑退出条件 B. 必须有递归出口和递归体 C. 每次调用都要简化问题规模 D. 可以无限递归 【巩固提升】 9 . 有如下Python程序： def fun(x,n): if x == n: return 1 if n % x == 0: return fun(x,n//x)+1 else: return fun(x+1,n) print(fun(2,100)) 执行上述程序后，输出的结果是（ ） A．2 B．3 C．4 D．5 10. 有如下程序： def fun（k）: if k==1: return ″1″ elif k%2==0: return fun（k-1）+str（k%2） else: return str（k%2）+fun（k-1） 执行语句s=fun（5），则s的值为（ ） A． ″00111″ B．″11010″ C．″11100″ D．″10110″ 11. （   ）是重复反馈过程的活动，其目的通常是逼近所需目标或结果。（）是直接或间接地调用函数自身。 A．枚举   递归 B． 递归   迭代 C． 迭代   递归 D． 递归   迭代 12.关于迭代与递归算法，下列说法错误的是（     ） A．迭代是重复反馈的活动，其目的通常是逼近所需目标或结果 B．递归是重复调用函数自身 C．迭代程序可以转换成等价的递归程序 D．迭代和递归是同一种算法的两种不同的表述 13.以下程序代码采用的算法是( )。 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．迭代法 【拓展应用】 填空题1： 斐波那契在《计算之书》中提出了一个有趣的兔子问题：假设一对兔子每个月可以生一对小兔子，一对兔子出生后第2个月就开始生小兔子。则一对兔子一年内能繁殖成多少对？程序代码如下，请补全划线处对应的代码： def fib(n):           f2=f1= （1）           for i in range (3,   （2） ）：                   f1,f2=f2,f1=f2           return