3.1迭代与递归同步训练-2023-2024学年高二信息技术教科版（2019）选择性必修1

教科版（2019）选修一3.1迭代与递归同步训练 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 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．下列选项中，递归算法不一定包括的是（   ） A．递推部分 B．回归部分 C．终止条件 D．循环结构 3．斐波那契的兔子繁殖问题可以利用迭代算法来解决的，解决该问题的正确选项及其顺序应该是（  ） ①建立迭代关系式 ②确定迭代变量 ③对迭代过程进行控制 ④让迭代过程无休止地重复执行 A．①②③④ B．①②③ C．②①③ D．②③④ 4．（  ）是重复反馈过程的活动，其目的通常是逼近所需目标或结果。（）是直接或间接地调用函数自身。 A．枚举  递归 B．递归  迭代 C．迭代  递归 D．递归  迭代 5．有如下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 6．以下程序代码采用的算法是(  )。 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．迭代法 7．直接或间接地调用函数自身的方法为(  )，不断用变量的旧值推出新值的过程为(  ). A．递归  枚举 B．迭代  枚举 C．迭代  递归 D．递归  迭代 8．金老师编写了一个函数，它的功能为使用递归的方法快速计算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 9．（   ）是重复反馈过程的活动，其目的通常是逼近所需目标或结果。是直接或间接地调用函数自身。 A．举递归 B．递归代 C．迭代递归 D．递归迭代 10．迭代法也称（ ），是用计算机解决问题的一种基本方法。迭代通常是为了接近并达到所需的目标或结果。每一次对过程的（ ）称为一次“迭代”，而每一次迭代得到的（ ）会被用来作为下一次迭代的（ ）。（  ） A．辗转法；重复；结果；初始值 B．重复；结果；辗转法；初始值 C．辗转法；结果；重复；初始值 D．结果；初始值；辗转法；重复 11．小明学习了算法后，写了以下两段代码来求斐波那契数列的第6项： a=1;b=1 for i in range(2,6): c=a+b a=b b=cprint(c) def f(n): if n==1 or n==2: return 1 else: return f(n-1)+f(n-2) print(f(6)) 算法一 算法二 下列说法正确的是（    ） A．两种算法的时间复杂度均为O（1） B．算法一是迭代算法，算法二是递归算法，相比之下，算法二的时间效率更高 C．执行算法二代码，f（4）共被调用了2次 D．执行算法一代码，当i=4这一遍循环刚结束时，a的值等于5 12．将十进制正整数转化为二进制数，对应的Python程序如下： def toStr(n,base): s = "01" if n < base: return s[n] else: return ① n = int(input('请输入正整数:')) result = toStr(n,2) print(result) 则代码中①处的语句可为（    ） A．toStr(n // base, base) + s[n % base] B．s[n % base] + toStr(n // base, base) C．toStr(n % base, base) + s[n // base] D．s[n // base] + toStr(n % base, base) 13．定义如下函数： 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 14．______是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。______是直接或间接的调用函数自身。（　　） A．枚举；递归 B．递归；迭代 C．迭代；递归 D．递归；迭代 15．下列函数实现的功能是（    ） 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！ 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 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．D 【详解】本题主要考查递归算法。递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归算法一定包括递推部分、回归部分以及终止条件，循环结构可能有也可能没有，故本题选D选项。 3．C 【详解】本题主要考查迭代算法。斐波那契的兔子繁殖问题可以利用迭代算法来解决的，解决该问题的步骤是：首先确定迭代变量，其次是建立迭代关系式 ，最后对迭代过程进行控制，故本题选C选项。 4．C 【详解】本题主要考查迭代和递归算法。迭代是重复反馈过程的活动，其目的通常是逼近所需目标或结果。递归是直接或间接地调用函数自身，故本题选C选项。 5．C 【详解】本题考查的是Python递归算法。输入值为6，由自定义函数 s(x)可知，s(6)=s(5)+s(4)=s(4)+s(3)+s(4)=s(3)+s(2)+s(2)+s(1)+s(3)+s(2)=s(2)+s(1)+s(2)+s(2)+s(1)+s(2)+s(1)+s(2)=2+1+2+2+1+2+1+2=13。选项C正确。 6．D 【详解】本题主要考查迭代算法。迭代法是用计算机解决问题的一种基本方法，它让计算机对一组指令或一定步骤进行重复执行，在每次执行这组指令或这些步骤是都从变量的原值推出他的一个新值，用迭代法解决问题，要考虑迭代的初值、迭代的过程、迭代的结束或迭代的次数。简单地说就是运算过程中的变量的不断交替，分析程序可知，辗转相除法求最大公约数采用的算法是迭代法，故本题选D选项。 7．D 【详解】本题主要考查递归和迭代算法。递归是直接或间接地调用函数自身的方法，迭代是不断用变量的旧值推出新值的过程，故本题选D选项。 8．C 【详解】本题主要考查递归算法及Python程序实现。由下文if条件分支代码可知，此处先递归计算x^n/2，即t=fun（x，n//2），如果n是偶数，则返回x*t*t，如果n是奇数，则直接返回t*t，故本题选C选项。 9．C 【详解】本题主要考查迭代与递归算法。迭代是重复反馈过程的活动，其目的通常是逼近所需目标或结果。递归是直接或间接地调用函数自身，故本题选C选项。 10．A 【详解】本题主要考查迭代算法。迭代法也称辗转法，是用计算机解决问题的一种基本方法。迭代通常是为了接近并达到所需的目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会被用来作为下一次迭代的初始值，故本题选A选项。 11．C 【详解】本题主要考查算法的应用。两种算法的时间复杂度均不为O（1）；算法一是迭代算法，算法二是递归算法，相比之下，算法一的时间效率更高；执行算法二代码，f（4）共被调用了2次；执行算法一代码，当i=4这一遍循环刚结束时，a的值等于3，b的值等于5，故本题选C选项。 12．A 【详解】本题主要考查递归算法及Python程序实现。分析程序可知，当n>=base时，十进制转换为二进制的方法是“除权取余、逆序排列”，该程序采用递归算法，故第一空第一部分继续调用toStr方法，第二部分将余数保存到列表s中，故填toStr(n // base, base) + s[n % base]，故本题选A选项。 13．C 【详解】本题考查的是递归函数。执行语句v=rf（5）时， 调用3次（rf(5)、rf(4)、rf(2)）；执行rf(4)时调用2次（rf(3)、rf(1)）；执行rf(3)时调用2次（rf(2)、rf(0)）；一共调用了3+2+2=7。故本题应选C。 14．C 【详解】本题主要考查迭代和递归的描述。迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。递归是直接或间接的调用函数自身，故本题选C选项。 15．A 【详解】本题主要考查递归算法及Python程序实现。分析程序，参数是x和n，当n=0时，返回1，否则返回x*mi(x,n-1)。而函数mi(x,n-1)当n-1不等于0时，返回x*mi(x,n-2)，依次类推，即函数实现的功能是计算x的n次方，故本题选A选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$