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

高中信息技术浙教版(2019)5.2 迭代与递归 一、选择题 1．递归算法可以用三个字来概括，但不包括下列选项中的（   ） A．解 B．分 C．治 D．合 2．以下选项中，对于递归程序的描述错误的是（   ） A．递归程序都可以有非递归编写方法 B．执行效率高 C．一定要有基例 D．书写简单 3．下列程序代码采用的算法是（    ） def mi（x，n）：     if n==0：          return 1     else：          return x*mi（x，n-1） A．迭代法 B．枚举法 C．递归法 D．解析法 4．某个使用递归算法的Python程序段如下： def doit(x):    tmp=0    if   x<=2:       tmp=2    else:       tmp=3*doit(x-1)+2*doit(x-2)    return    tmp print(doit(5)) 执行该程序段后，输出的结果是（   ） A．16 B．34 C．122 D．434 5．观察如下VB程序段： Function fx(n As Integer) As Long If n＝1 Then fx＝1 Else fx＝2*fx(n－1) End If End Function Private Sub Command1_Click() Dim n As Integer，x As Long n＝Val(Text1.Text) x＝fx(n) Text2.Text＝Str(x) End Sub 若在文本框Text1中输入数字5，单击命令按钮Command1后，在文本框Text2显示的内容为(  ) A．2 B．8 C．16 D．32 6．定义如下函数： def  f(s,r): if  s-r**2<0 or r==0 return  r+1 else: return  f(s-r**2,r-1) 执行语句k=f(50,5)后，k的值为（   ） A．4 B．3 C．2 D．1 7．______是重复反馈过程的活动，______是重复调用函数自身（   ） A．递推，递归 B．递归，递推 C．迭代，递归 D．递归，迭代 8．关于8个圆盘的汉诺塔问题，要求将塔座A上的所有圆盘借助塔座B移到塔座C上，并仍按同样顺序叠放。移动圆盘时，需遵守汉诺塔问题的移动规则。由此设计出了下列解决汉诺塔问题的递归算法，能按要求正确解决此问题的选项是（   ） A．   B．   C．   D．   9．已知递归式为F（n）=F（n-1）+2，且F（1）=5，则当n=3时，F的值为（    ） A．7 B．9 C．11 D．13 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．递归也可用“分”“治”“合”三个字概括。下列说法错误的是（  ） A．分:将原问题分解成k个子问题 B．治:对这k个子问题分别求解，如果子问题的规模仍然不够小，则将其再分解为k个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解 C．合:将求出的小规模问题的解合并为一个更大规模问题的解自下而上涿步求出原问题的解 D．整个递归不需要终止条件，自动返回运算结果 12．有如下 Python 程序段: def fx(s): if len(s)<=1: return True elif s[0]!=s[-1]: return False else: return fx(s[1:-1]) s="110011" print(fx(s)) 运行上述程序后，下列说法正确的是（   ） A．程序输出结果是 False B．函数 fx被调用了3次 C．最后一次调用函数 fx时s的值是"" D．函数 fx的算法时间复杂度是 O(n/2) 13．有如下程序段：      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 14．定义如下函数： 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 15．定义如下函数： def f（a，s）：     if a>=s：         return a     else：         return f（a+1，s-a） 执行语句k=f（6，21）后，k的值为（   ） A．6 B．7 C．8 D．9 二、填空题 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．迭代算法与递归算法都需要 某些代码，两者既有区别又有密切的联系。迭代是重复 的活动，其目的通常是逼迫 ，其结束方式，通常使用 结束循环。 递归的重复方式是重复 ，其结束方式是遇到 的情况时逐层返回。 18．迭代法也称 ，是用计算机解决问题的一种基本方法。迭代通常是为了接近并达到所需的目标或结果。每一次对过程的 称为一次“迭代”，而每一次迭代得到的 会被用来作为下一次迭代的 。 19．在数学与计算机领域中，递归函数是指用 定义该函数的方法。 三、操作题 20．用Python编辑器打开“451”下的文件“计算.py”，进行以下操作并保存结果。 （1）一个正整数的阶乘是所有小于及等于该数的正整数的积，并且0的阶乘为1，即n!=1×2×3×..×（n-1）×n。即，现计算，并输出A的值。 （3）编写完成后原名保存并关闭应用软件。 def jc(n):    #利用递归的方法求n！     if n == 0 or :            return        else:         return     n=int(input('请输入正整数n：')) if n>0:   #如果n为正数，且为整数     A =      #计算A的值     print('A=', A) else: print('输入的数据有误，无法计算') 四、简答题 21．迭代和递归的相同点与不同点。 22．解释递归算法的基本原理，并讨论它在非数值计算中的应用。 23．请简述什么是递归函数，并给出一个递归函数的例子。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 2．B 3．C 4．C 5．C 6．B 7．C 8．B 9．B 10．D 11．D 12．C 13．B 14．C 15．C 16． 9 22 17． 重复执行 反馈过程 所需目标或结果 计数器 调用函数自身 满足终止条件 18． 辗转法 重复 结果 初始值 19．函数自身 20． n==1 1 n*jc(n-1) 3**n/jc(n) 21．相同点：都需要重复执行某些代码 不同点： 1.重复内容不同：迭代是重复反馈过程的活动，其目的通常是逼近所需目标或结果。递归是重复调用函数自身。 2.结束条件不同：递归中，遇到满足终止条件的情况时逐层返回。迭代则通常使用计数器结束循环。 22．递归算法是一种通过函数自我调用来解决问题的算法，它在非数值计算中的应用包括图遍历、分治算法等。 23．递归函数是一种在函数体内调用自身的函数。一个递归函数的例子是计算斐波那契数列的函数，其中每个数是前两个数的和，递归定义为Fib(n) = Fib(n-1) + Fib(n-2)，基本情况是Fib(0) = 0和Fib(1) = 1。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$