2023-2024学年高二上学期浙教版(2019)选修一5.2 迭代与递归

2023-2024学年高二上学期浙教版(2019)选修一5.2 迭代与递归 一、选择题 1．下列程序代码采用的算法是（    ） def mi（x，n）：     if n==0：          return 1     else：          return x*mi（x，n-1） A．迭代法 B．枚举法 C．递归法 D．解析法 2．关于8个圆盘的汉诺塔问题，要求将塔座A上的所有圆盘借助塔座B移到塔座C上，并仍按同样顺序叠放。移动圆盘时，需遵守汉诺塔问题的移动规则。由此设计出了下列解决汉诺塔问题的递归算法，能按要求正确解决此问题的选项是（   ） A．   B．   C．   D．   3．定义如下函数： def move(n,a,b,c):     if n==1:         print(a,"->",c)         return     move(n-1,a,c,b)     move(1,a,b,c)     move(n-1,b,a,c) 执行语句move(2,"A","B","C")，输出的第一行内容是（   ） A．a -> c B．A -> C C．a -> b D．A -> B 4．直接或间接地调用函数自身的方法为(  )，不断用变量的旧值推出新值的过程为(  ). A．递归  枚举 B．迭代  枚举 C．迭代  递归 D．递归  迭代 5．运用分治策略将一个难以直接解决的大问题分割成规模较小的子问题分别解决，最终达到解决大问题的目的。这要求原问题和子问题的（    ） A．问题性质相同，问题规模相同 B．问题性质不同，问题规模相同 C．问题性质相同，问题规模不同 D．问题性质不同，问题规模不同 6．下列有关迭代算法和递归算法的描述，不正确的是（   ） A．在使用递归算法时，必须有一个明确的递归结束条件，称为递归出口 B．一般来说，迭代算法效率较低，而递归算法效率较高 C．递归中一定有迭代，但迭代中不一定有递归 D．通常情况下，迭代算法和递归算法可以相互转换 7．定义如下函数： def fnl (n, num1, num2):     if n==1:         return num1     return fn1 (n-1, num2, num1 +num2) def fn2(n):     if n==1or n==2:         return 1     return fn2(n-1)+fn2(n-2) 下列说法正确的是（   ） A．两种算法的时间复杂度相同 B．fn1(n,1,1)与fn2(n)的功能相同 C．执行语句fn2(8)时，fn2(5)被调用了2次 D．fn1函数的调用次数取决于num1和num2的值 8．下列关于递归和迭代两种算法的描述错误的是（   ） A．迭代算法和递归算法原理不同，因此迭代程序和递归程序不能相互转换 B．递归是重复调用函数自身 C．迭代通常使用计数器结束循环 D．递归中遇到满足终止条件的时候逐层返回 9．下列函数实现的功能是（    ） 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！ 10．有Python程序段如下: def f(s): if len(s)==1: return s[0] return f(s[1:])+s[0] s="abcdefg" print(f(s)) 执行该程序段后，输出的结果为（   ） A．"a" B．"aceg" C．"bef" D．"gfedcba" 11．在计算机中，一种不断用变量的旧值递推新值的过程。这种用计算机解决问题的基本方法是（   ） A．查找法 B．排序法 C．分析法 D．迭代法 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．下列关于递归算法的说法中，正确的是（    ） A．在1977年前后形成标准的计算机高级语言“F0RTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间 B．和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些 C．对于较复杂的问题，用递归方式编程一般比非递归方式更难一些 D．对于已经定义好的标准数学函数sin（x），应用程序中的语句“y=sin（sin（x））；”就是一种递归调用 14．定义如下函数： def pd(s)： if len(s)<=1： return True elif s[0]!=s[len(s)-1]： return False else： return pd(s［1：len(s)-1］) 执行语句f=pd("abcba")，函数pd被调用的次数是（    ） A．2 B．3 C．4 D．5 15．递归算法在非数值计算中的应用不包括（   ） A．图遍历 B．字符串处理 C．数据加密 D．矩阵运算 二、填空题 16．结合分治策略，递归也可以用 三个字概况。分：将原有问题 成K个子问题；治：对这K个子问题 。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。合：将求出的小规模问题的解 为一个更大规模问题的解，自下而上逐步求出原问题的解。 17．迭代法也称 ，是用计算机解决问题的一种基本方法。迭代通常是为了接近并达到所需的目标或结果。每一次对过程的 称为一次“迭代”，而每一次迭代得到的 会被用来作为下一次迭代的 。 18．迭代算法与递归算法都需要 某些代码，两者既有区别又有密切的联系。迭代是重复 的活动，其目的通常是逼迫 ，其结束方式，通常使用 结束循环。 递归的重复方式是重复 ，其结束方式是遇到 的情况时逐层返回。 19．在数学与计算机领域中，递归函数是指用 定义该函数的方法。 三、操作题 20．根据题目补全下列代码。 题目：有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ def peach(n):     if  ① :         return 0     elif n == 9:         return 2  # 第九天还有两个桃子，都被吃了     else:         return (peach(n+1)+1)*2 print("猴子们摘来了:{}个桃子".format(peach(1))) s = peach(1) for i in range(   ② ,  ③ ):     print("第{}天吃了{}个桃子，剩余桃子数为{}". format(i, s-peach(i+1), peach(i+1)))     s = peach(i+1) 四、简答题 21．迭代和递归的相同点与不同点。 22．请简述什么是递归函数，并给出一个递归函数的例子。 23．请解释什么是递归，并给出一个使用递归的Python函数示例。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 2．B 3．D 4．D 5．C 6．B 7．B 8．A 9．A 10．D 11．D 12．A 13．A 14．B 15．C 16． “分”“治”“合” 分解 分别求解 合并 17． 辗转法 重复 结果 初始值 18． 重复执行 反馈过程 所需目标或结果 计数器 调用函数自身 满足终止条件 19．函数自身 20． n>9 1 10 21．相同点：都需要重复执行某些代码 不同点： 1.重复内容不同：迭代是重复反馈过程的活动，其目的通常是逼近所需目标或结果。递归是重复调用函数自身。 2.结束条件不同：递归中，遇到满足终止条件的情况时逐层返回。迭代则通常使用计数器结束循环。 22．递归函数是一种在函数体内调用自身的函数。一个递归函数的例子是计算斐波那契数列的函数，其中每个数是前两个数的和，递归定义为Fib(n) = Fib(n-1) + Fib(n-2)，基本情况是Fib(0) = 0和Fib(1) = 1。 23．递归是一种函数自己调用自己的现象。示例：def factorial(n): if n == 1: return 1 else: return n * factorial(n-1)。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$