高中信息技术粤教版(2019)选修一 5.1迭代与递归

高中信息技术粤教版(2019)5.1迭代与递归 一、选择题 1．走楼梯的问题可以利用迭代算法来解决，解决该问题的正确顺序应该是（    ） ①建立迭代关系式  ②让迭代过程无休止地重复执行  ③对迭代过程进行控制  ④确定迭代变量 A．④①③② B．①②③ C．④①③ D．①④③ 2．定义如下函数： 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 3．下列对递归思想的形象化表示错误的是（   ）。 A． B． C． D． 4．斐波那契数列也叫兔子繁殖数列，小明编写了下列代码求第74个月能繁殖多少对兔子，他使用的算法是（   ） f1=f2=1 for i in range(3,75):     f1,f2=f2,f1+f2 print('兔子总对数为：',f2) A．迭代法 B．枚举法 C．二分法 D．解析法 5．有如下Python程序段： 下列关于两个程序段的说法，正确的是（   ） A．程序1和程序2都使用了递归算法 B．若问题规模为n，程序1和程序2的时间复杂度不同 C．若程序1中问题规模为n，则n的值就是其循环执行的次数 D．若程序2中自定义函数内的代码只保留①处语句，也能获取到目标值 6．有如下Python程序段 def s(x):     if x<=2:         y=x     else:         y=s(x-1)+s(x-2)     return y a=int(input("请输入正整数：")) result=s(a) print(result) 运行程序，输入值为6，则输出结果为（ ） A．8 B．9 C．13 D．14 7．上台阶：每一步只能迈上1个或2个台阶，上完n级台阶，一共有多少种走法，下面说法正确的是（ ） A．用递归算法，递归关系式为f(n)=f(n-1)+2 B．用递归算法，递归关系式为f(n)=f(n-1)+f(n-2) C．用递归算法，递归关系式为f(n)=f(n+1)+f(n+2) D．用递归算法，递归关系式为f(n)=f(n-1)*2 8．下列python代码运行的结果是（    ） def f(m, n):     q=m%n     if q == 0:         return n     else:         return f(n,q) print(f(14,10)) A． 4 B．24 C．2 D．70 9．直接或间接地调用函数自身的方法为(  )，不断用变量的旧值推出新值的过程为(  ). A．递归  枚举 B．迭代  枚举 C．迭代  递归 D．递归  迭代 10．递归算法设计的关键点是（   ） A．确保每次递归调用都朝着基本情况靠近 B．保证递归函数的参数每次都减少 C．设置明确的递归停止条件 D．以上都是 11．下列函数实现的功能是（    ） def mi（x，n）： if n==0：    return 1 else：    return x*mi（x，n-1） A．计算x的n次方 B．计算n的x次方 C．计算x！*n D．计算x*n！ 12．定义如下函数: 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" 13．有如下Python程序：     def trans(n):        ch=″0123456789ABCDEF″        if n < 16:           return ch[n ％ 16]        else:           digit = trans(n // 16) + ch[n ％ 16]           return digit     n = int(input(″请输入一个正整数:″))     print(trans(n)) 执行该程序时，输入“268”(不含引号)，则输出的结果为（   ） A．C01 B．C010 C．10C D．010 14．定义如下函数： def f（x）:    if x<3:       return 2    return f（x-1）*f（x-3） 关于该函数，下列说法正确的是（    ） A．采用了迭代算法 B．时间复杂度是0（log2n） C．计算f(5)，函数f被调用的次数是6次 D．f(5)的返回值为16 15．有如下Python程序段： def double f(m):    if   m==1   or   m==2:       return    m    else:       return double f(m-2)*m n=int(input("请输入一个正整数n:") print(double f(n)) 执行该程序段后，输入n 的值为7，输出的结果是（   ） A．1 B．7 C．105 D．35 二、填空题 16．def f(x,y):     ans=y;     for i in range(1,y-x+1):         ans = ans + f(x+i,y-i)     return ans; def init():     x = int(input())     y = int(input())     print(f(x,y)) init() (1) 输入：4 5 输出：     (2) 输入：3 6 输出：     三、操作题 17．运用辗转相除法求两个正整数的最大公约数。 def f(m, n):  # 递归定义函数，求m和n的最大公约数     if == 0:   # m可以被n整除         return n  # 求得最大公约数      :         q = m % n     return f(n, q) a = int(input('请输入第一个正整数：')) b = int(input('请输入第二个正整数：')) print( ) 18．斐波那契在《计算之书》中提出了一个有趣的兔子问题：假设一对兔子每个月可以生一对小兔子，一对兔子出生后第2个月就开始生小兔子。则一对兔子一年内能繁殖成多少对？程序代码如下，请补全划线处对应的代码： def fib(n):       f2=f1= （1）       for i in range (3,  （2） ）：            f1,f2=f2,f1=f2       return （3） n=int(input(“输入月份数:”)) print(“兔子总对数为：”，fib(n)) n = int(input("输入月份数：")) print("兔子总对数为：", fib(n)) 【填空】 （1）      【填空】 （2） 【填空】 （3） 四、简答题 19．请简述什么是递归函数，并给出一个递归函数的例子。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 2．C 3．D 4．A 5．C 6．C 7．B 8．C 9．D 10．D 11．A 12．B 13．C 14．D 15．C 16． 9 22 17． m%n else f(a,b) 18． 1 n+1 f2 19．递归函数是一种在函数体内调用自身的函数。一个递归函数的例子是计算斐波那契数列的函数，其中每个数是前两个数的和，递归定义为Fib(n) = Fib(n-1) + Fib(n-2)，基本情况是Fib(0) = 0和Fib(1) = 1。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$