教科版（2019）选修一3.1迭代与递归课时作业

教科版（2019）选修一3.1迭代与递归课时作业 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．对于下列递归式子，当n=5时，F的值是（    ）    F(1)=3    F(n)=F(n-1)*2 A．16 B．48 C．32 D．64 2．下面的故事与（    ）算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’” （   ） A．枚举 B．递归 C．二分 D．迭代 3．有如下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 4．猴子吃桃：猴子第一天摘了若干个桃子，当即吃了一半，还不解馋，又多吃了一个；第二天，吃剩下的桃子的一半，还不过瘾，又多吃了一个；以后每天都吃前一天剩下的一半多一个，到第10天想再吃时，只剩下一个桃子了，问第一天共摘了多少个桃子？使用迭代法时首先确定迭代变量为桃子数n，并设置最后一天的桃子数1为初始值，则迭代关系式和迭代次数分别是（   ） A．n=n/2-1           9 B．n=(n+1)*2     9 C．n=n/2-110         10 D．n=(n+1)*2     10 5．下列程序代码采用的算法是（    ） def mi（x，n）：     if n==0：          return 1     else：          return x*mi（x，n-1） A．迭代法 B．枚举法 C．递归法 D．解析法 6．关于8个圆盘的汉诺塔问题，要求将塔座A上的所有圆盘借助塔座B移到塔座C上，并仍按同样顺序叠放。移动圆盘时，需遵守汉诺塔问题的移动规则。由此设计出了下列解决汉诺塔问题的递归算法，能按要求正确解决此问题的选项是（   ） A．   B．   C．   D．   7．递归算法可以用三个字来概括，但不包括下列选项中的（   ） A．解 B．分 C．治 D．合 8．下列关于递归和迭代两种算法的描述错误的是（   ） A．迭代算法和递归算法原理不同，因此迭代程序和递归程序不能相互转换 B．递归是重复调用函数自身 C．迭代通常使用计数器结束循环 D．递归中遇到满足终止条件的时候逐层返回 9．关于迭代与递归算法，下列说法错误的是（   ） A．迭代是重复反馈的活动，其目的通常是逼近所需目标或结果 B．递归是重复调用函数自身 C．迭代程序可以转换成等价的递归程序 D．迭代和递归是同一种算法的两种不同的表述 10．斐波那契数列，运用函数递归的方法可以实现，运用迭代的方式也可以实现，而且比函数递归要快许多。下列关于斐波那契数列的迭代表达式正确的是（   ）。 A．f，f2，f2=f1+f2 B．fl=fl+f2，f2= C．fl，f2=f2，fl+f2 D．f=f1+f2，fl=f2，f2=f 11．斐波那契在《计算之书》中提出了一个有趣的兔子问题:从第三个月开始，每个月的兔子对数是前两个月的兔子对数之和，又同时作为下一个月兔子对数的加数。这种重复反馈的过程称为迭代。迭代法也称辗转法，阅读下列程序代码。 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代替 12．用递归求n!，当n=1时，f(1)=1，否则f(n)=f(n-1)*n，当n=3时，递归调用顺序正确的是（   ） A．f(1)、f(2)、f(3) B．f(2)、f(3)、f(1) C．f(3)、f(2)、f(1) D．以上都不对 13．上台阶：每一步只能迈上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 14．关于“递归”，下列说法不正确的是（  ） A．可以利用“递归”进行具有自相似性无限重复事物的定义 B．可以利用“递归”进行具有自重复性无限重复动作的执行，即“递归计算”或“递归执行” C．可以利用“递归”进行具有自相似性无限重复规则的算法的构造 D．递归算法的关键只要给出递归关系式即可求出问题的解 15．下面代码的输出结果是（   ）。 def add(x): if x>0: return x＋add(x-l) else: return 0 result＝add(10) print(result) A．0 B．10 C．55 D．45 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】本题主要考查递归算法。F(5)=F(4)*2=F(3)*2*2=F(2)*2*2*2=F(1)*2*2*2*2=3*2*2*2*2=48，故本题选B选项。 2．B 【详解】本题主要考查递归的描述。一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，故本题选B选项。 3．C 【详解】本题主要考查递归函数的应用。n=7，double_f(7)=double_f(5)*7=double_f(3)*5*7=double_f(1)*3*5*7=1*3*5*7=105，故本题选C选项。 4．B 【详解】本题考查的是迭代算法相关知识。采用倒推方法，每天都吃前一天剩下的一半多一个，故迭代关系式为：n=(n+1)*2 ；从第9天倒推到第1天，共需要迭代9次。选项B正确。 5．C 【详解】本题考查的是算法相关知识。迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题；枚举法将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃；能采用递归描述的算法通常有这样的特征:为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解；解析法又称为分析法，它是应用数学推导、演绎去求解数学模型的方法。分析本题代码可知采用的算法是递归法，故本题应选C。 6．B 【详解】本题考查的是递归算法应用。解决汉诺塔问题的算法是先把n-1个圆盘从刚开始的塔座上移动到过渡塔座上，然后把开始塔座上的最后一个圆盘移动到目的塔座上，最后是把中间塔座上的n-1个圆盘移动到目的塔座上。故本题应选B。 7．A 【详解】本题主要考查递归算法。递归算法即在程序中不断反复调用自身来达到求解问题的方法。此处的重点是调用自身，这就要求待解决的问题能够分解为相同问题的一个子问题，每个子问题分别解决，这样通过多次调用，将所有的子问题合在一起就可以完成求解。递归算法可以用三个字来概括，即分、治、合，故本题选A选项。 8．A 【详解】本题考查的是递归和迭代算法的区别。迭代算法和递归算法递归算法原理不同，但迭代程序和递归程序可以相互转换，选项A说法错误；递归是重复调用函数自身，其结束方式是遇到满足终止条件的时候逐层返回，迭代算法通常使用计数器结束循环，故选项BCD正确。 9．D 【详解】本题主要考查迭代与递归算法。迭代是重复反馈的活动，其目的通常是逼近所需目标或结果；递归是重复调用函数自身；迭代程序可以转换成等价的递归程序；迭代和递归不是同一种算法的两种不同的表述，故本题选D选项。 10．D 【详解】本题主要考查迭代与递归算法。斐波那契数列指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义： F (0)=0， F (1)=1, F (n)= F (n - 1)+ F (n - 2)（ n ≥ 2， n ∈ N*）。所以关于斐波那契数列的迭代表达式正确的是f=f1+f2，fl=f2，f2=f，故本题选D选项。 11．D 【详解】本题主要考查迭代算法及Python程序实现。从第三个月开始，每个月的兔子对数是前两个月的兔子对数之和，又同时作为下一个月兔子对数的加数，故确定迭代变量， 程序中的的f1、f2；建立迭代关系式，②处应填写：f1，f2=f2，f1+f2；对迭代过程进行控制，①处应填写range(3，n+1)枚举从第三个月开始；f1，f2=f2，f1+f2可以用temp=f1+f2，f1=f2，f2=temp代替，故本题选D选项。 12．C 【详解】本题主要考查递归算法。当n=3时，f(3)=f(2)*3，f(2)=f(1)*2，f(1)=1，故递归调用顺序是f(3)、f(2)、f(1)，故本题选C选项。 13．B 【详解】本题主要考查递归算法。n=0 和 n=1 的时候并没有其他可选择的，所以可以得出f(0)=0，f(1)=1。 n>=2时情况就变复杂起来，但是这个时候可以操作的步骤也就2种，也就是走1步(n-1)与走2步(n-2)，所以可以得到f(n)=f(n-1)+f(n-2)，故本题选B选项。 14．D 【详解】本题主要考查递归算法。可以利用“递归”进行具有自相似性无限重复事物的定义；可以利用“递归”进行具有自重复性无限重复动作的执行，即“递归计算”或“递归执行”；可以利用“递归”进行具有自相似性无限重复规则的算法的构造；递归算法的关键要给出递归关系式和递归出口即可求出问题的解， 故本题选D选项。 15．C 【详解】本题主要考查递归算法及Python程序实现。add(x)函数是一个递归函数，如果x>0，则返回x+add(x-1)，所以result=add(10)=10+9+8+7+6+5+4+3+2+1=55，故本题选C选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$