高效作业15 第15课 迭代与递归-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

高效作业15[第15课　迭代与递归](见学生用书P227) 学科网（北京）股份有限公司 【A级　新教材落实与巩固】 1．有如下Python程序段： lis＝['a'，'b'，'c'，'d'] s＝0 for i in lis： c＝ord(i)－ord('a') s＋＝c print(s) 执行该程序段后，输出s的值为(　C　) A． 4　　B． 5　　C． 6　　D．10 【解析】 将列表lis中的小写字母转换为英文字母表中的对应位置，s＝0＋1＋2＋3＝6，选项C正确。 2． 使用Nilakantha 无穷级数求圆周率pi 的公式为： pi＝3＋4/(2*3*4)－4/(4*5*6)＋4/(6*7*8)－4/(8*9*10)… 计算该公式的Python 程序段如下： pi＝0；n＝50；i＝1；p＝3 while i<＝n： print(pi) 程序段中加框处的代码由以下三部分组成： ①pi＋＝p　②p＝(－1)**(i＋1)*4/((2*i)*(2*i＋1)*(2*i＋2))　③i＋＝1 下列选项中，代码顺序正确的是(　B　) A．③②① B．①②③ C．②①③ D．②③① 【解析】 先将上一次计算好的p累加到pi中，再计算新的p，由i＝1开始循环，先计算p，再后移i，选项B正确。 3． 有如下Python程序段，功能为将输入的二进制(字符串)转化成十进制数输出。 def mybtod(b)： d＝0 # return d b＝input() print(mybtod(b)) 为实现上述程序功能，则加框处的代码不可能是(　B　) A．for i in range(len(b))： d＝d＋int(b[i])*pow(2，len(b)－i－1) B．for i in range(len(b))： d＝d＋int(b[i])*pow(2，i) C．for i in range(len(b))： d＝d＋int(b[len(b)－i－1])*pow(2，i) D．for i in b： d＝d*2＋int(i) 【解析】 选项B，当i＝0时，提取的是二进制数的最高位，pow(2，0)＝20，0为最低位的乘幂，不符合，选项错误。 4．有表达式s＝＋＋＋…， 现根据输入的表达式项数，求s 的值，Python 程序段如下： def sum(n)： s＝0；x＝2；y＝1 for i in range(0，n)： # return s n＝int(input(”请输入表达式的项数：　”)) print(sum(n)) 上述程序中加框处可选的代码有： ①x＝x＋y　②y＝x　③s＝s＋x/y　④y＝x－y 下列选项中，代码顺序正确的是(　C　) A．③②① B．③①② C． ③①④ D．③④① 【解析】 s初始值为0，则先将2/1累加到s中，先是③；接着计算x的值，是①；最后更新y的值，由于x已经变了，②不符合，应是④，选项C正确。 5． 一个球从某一高度h(单位：米)落下，每次落地后反弹回原来高度的一半，再落下。编写Python程序计算球在第10 次落地时，经过的距离s，程序代码段如下： h＝20.0；s＝h for i in range(9)： # print(s) 程序段中加框处的代码由以下三部分组成： ①l＝h*2　②h＝h/2　③s＝s＋l 下列选项中，代码顺序正确的是(　B　) A．①②③ B．②①③ C．③①② D．②③① 【解析】 Python 语言中，使用变量需要先定义后使用，因此③在①之后。第一次落地，经过的距离为h，即s 的初值，后续落地都是先上升后落下，经过的是2 段路程，上升距离是原高度h 的一半，这个过程可以用②①表示。选项B正确。 6．小明编写了一段Python程序，用于检测输入的四位整数abcd是否满足下述关系：(ab＋cd)2＝abcd，程序代码如下： k＝int(input(“输入一个四位数：　”)) ①____________ y＝k%100 if ②______________： print(“符合条件”) else： print(“不符合条件”) 则①、②处填入的代码应为(　D　) A．①x＝k/100　②(x＋y)*2！＝k B．①x＝k//100　②(x＋y)*2＝＝k C．①x＝k/100　 ②(x＋y)**2！＝k D．①x＝k//100　②(x＋y)**2＝＝k 【解析】 ①求出前两位数字，采用移位思想，x＝k//100，选项A、C排除；②利用公式(ab＋cd)2＝abcd判断，(x＋y)**2＝＝k，选项D正确。 7．小明编写程序，计算表达式1－＋－＋…的前n项和，实现的Python程序段如下： n＝int(input(“请输入项数：”)) f，i＝1，1 s＝0 for i in range(1，n＋1)： # print (“前n项和为”，s) 上述程序中加框中的代码由以下三部分组成： ①f＝－f　②s＋＝f/m　③m＝2*i－1 下列选项中， 代码顺序正确的是(　C　) A．①③② B． ①②③ C． ③②① D．②③① 【解析】 f初始值为1，则需要先计算－1/3，将f取反，③②①和③①②都正确，选项C正确。 8．2023·义乌中学检测生成一组由数字1～8 组成的8 位不重复的随机密码，Python 程序段如下： from random import * a＝[0]*8 for i in range(8)： a[i]＝i＋1 k＝8；s＝” for i in range(8)： m＝randint(0，k－1) # print(s) 上述程序段中加框处的代码由以下三部分组成： ①k－＝1　②a[m]＝a[k－1] ③s＋＝str(a[m]) 下列选项中，代码顺序正确的是(　D　) A．①②③ B．②③① C．②①③ D．③②① 【解析】 利用第1个for循环，依次产生“1～8”8个数，a＝[1，2，3，4，5，6，7，8]；第2个for循环，随机产生索引，并连接到s中，之后用k－1位置的数将m位置的数替换，总数k自减1个，选项D正确。 9．有如下Python 程序段： def f(x)： if x＝＝1： return 1 else： return x*f(x－1) s＝0 for i in range(1，6)： s＋＝f(i) print(s) 执行该程序段后，变量s的值为(　D　) A．33 B．34 C．154 D．153 【解析】 通过自定义函数的关键代码“x*f(x－1)”，发现该函数是通过递归算法计算x 的阶层。后面的循环是把1 到5 的阶层进行累加，1！＋2！＋3！＋4！＋5！＝1＋2＋6＋24＋120＝153，选项D正确。 10．小王走楼梯时，每次走1个台阶或2个台阶。编写Python程序段，计算小王走n个台阶时，有多少种不同的走法。 def upstairs(n): if n＝＝0 or n＝＝1： return 1 else： return upstairs(n－1)＋upstairs(n－2) n＝int(input('请输入楼梯有几个台阶：　')) way＝upstairs(n) print(way) 当输入的楼梯有10个台阶时，有多少种走楼梯的方法？(　B　) A．88　 　B．89　 　C．90　 　D．91 【解析】 利用递归的方法求解数列： 1 1 2 3 5 8 13 21 34 55 89 0 1 2 3 4 5 6 7 8 9 10 选项B正确。 11．有如下Python 程序段： def trans(m，n)： if m！＝0： r＝m%n return trans(m//n，n)＋str(r) else： return ”0” a＝int(input(”a＝”)) b＝int(input(”b＝”)) print(trans(a，b)) 执行该程序段，依次输入11 和2，则输出的结果是(　C　) A．1011 B．1101 C．01011 D．11010 【解析】 列出表格如下： trans(11，2) trans(5，2) trans(2，2) trans(1，2) trans (0，2) 返回 值 trans(5，2)＋“1” trans(2，2)＋“11” trans(1，2) ＋“011” trans(1，2) ＋“1011” “01011” 选项C正确。 12．有如下Python程序段： def f(x)： if x＝＝1 or x＝＝2： return 1 else： return f(x－1)＋f(x－2) s＝0 for i in range(2，6)： s＋＝f(i) print(s) 执行该程序段后，变量s的值为(　D　) A． 20 B． 19 C． 12 D．11 【解析】 本题的递归式是f(x)＝f(x－1)＋f(x－2)，边界值为：当x为1或2时，返回1，即x从3开始，f(x)为前两项的和，循环中s对f(2)到f(5)进行求和，即s＝1＋2＋3＋5＝11。选项D正确。 13． 2023·湖州中学检测有如下Python 程序段： def output(s，n)： if n＝＝0： return print(s[n－1]，end＝””) output(s，n－1) s＝input(”input a string：”) x＝len(s) output(s，x) 执行该程序段，输入“12345”，则下列说法正确的是(　C　) A．输出的结果为12345 B．有0 个输出 C．n 为0 是递归结束的条件 D．程序无法结束 【解析】 选项A，输出结果为5 4 3 2 1，选项错误；选项B，解析同上有输出，选项错误；选项C，递归的出口是n＝＝0，即为递归结束的条件，选项正确；选项D，可以正常结束，选项错误。 14．李华同学尝试使用递归算法来实现斐波那契数列求值，用Python 程序实现如下： def fibo(n)： if n＝＝0 or n＝＝1： s＝n else： s＝fibo(n－1)＋fibo(n－2) return s n＝int(input(”输入所求项：　”)) print(fibo(n)) 关于递归算法及其应用，下列说法正确的是(　A　) A．递归算法的执行过程分递推和回归两个阶段 B．计算机在执行递归程序时，通过队列的调用来实现 C．使用上述递归算法求斐波那契数列，时间复杂度为O(n) D．求斐波那契数列的第6 项fibo(5)时，fibo(3)被调用了3 次 【解析】 选项B，计算机在执行递归程序时，通过栈的调用来实现，选项错误；选项C，使用上述递归算法求斐波那契数列，时间复杂度为O(n2)，选项错误；选项D，fibo(3)被调用了2次，选项错误。 【B级　素养形成与评价】 15．下列关于数据结构与算法效率的说法中，不正确的是(　C　) A．队列和栈都是一种线性表，但两者有不相同的特性 B．采用相同公式求解n！，使用迭代算法比递归算法的算法效率高 C．使用数组结构进行数据插入和删除操作时，一定会引起数据移动 D．某单向链表(节点数>2)设有头尾指针，在删除该链表尾节点时需要遍历多个节点 【解析】 选项A，队列和栈都是一种线性表，队列的特性是先进先出，栈的特性是先进后出，两者有着不相同的特性，选项正确。选项B，递归求n！，要递推和回归两个阶段(分解问题，逐级返回)；迭代求n！，循环代码中参与运算的变量作为下一次循环计算的初始值。当n 越大，迭代算法的效率明显高于递归算法，选项正确。选项C，使用数组这种数组结构在数组尾部进行数据插入和删除操作时，不会引起数据移动，选项错误。选项D，链表的操作需要从头指针开始，遍历到需要操作的节点，因为某单向链表(节点数>2)，所以在对该链表进行删除尾节点的操作时，需要遍历从头指针开始到尾指针的多个节点，选项正确。 16．学校举行大合唱比赛，每个班级演唱结束后会由10 个评委打分，最终得分的计分规则为：去掉一个最高分，去掉一个最低分，求剩余分数的平均分。 编程Python 程序，实现快速计分，代码如下： n＝10 scores，maxs，mins＝0，0，10 for i in range(n)： s＝float(input(”第”＋str(i＋1)＋”个评委给分：　”)) if maxs<s： maxs＝s if mins>s： mins＝s scores＋＝s avg＝____________# print(”平均分为：　”＋str(round(avg，2))) 下列关于该程序的说法中不正确的是(　B　) A． 将“if”改为“elif”，程序功能改变 B． 划线处代码为“(scores－maxs－mins)/n－2” C． 倒数第2 行代码取消缩进，算法更加优化 D．此程序段只适用于满分不超过10 的情况 【解析】 选项B，划线处代码为“(scores－maxs－mins)/(n－2)”选项错误。 17．2022·浙江6月选考列表a有2×n个元素，各元素为互不相等的正整数(n≥1)，要在其中找到最大值和次大值，并分别存储到变量m1和m2中。实现该功能的Python程序段如下： m1＝0；m2＝0 for i in range(0，2*n，2)： if a[i]>a[i＋1]： t1＝a[i]；t2＝a[i＋1] else： t1＝a[i＋1]；t2＝a[i] if： m1＝t1；m2＝t2 elif： m2＝m1；m1＝t1 elif： m2＝t1 上述程序段中加框处可选的代码有： ①t1>m1　②t1>m2　③t2>m1 下列选项中，代码顺序正确的是(　C　) A．①②③ B．②③① C．③①② D．③②① 【解析】 for循环中，将数组分成n组，相邻的两个数为一组。第一个if语句的作用是将相邻的两个数中较大的值存储在t1中，较小的值存储在t2中。第二个if语句的作用是对前面的数据进行进一步处理，将最终的最大值存放于m1中，次大值存放于m2中。解题的关键是if语句的分支(3)，该分支处理的是m2＝t1，因此可以推断该分支的条件是t1>m2，即②。选项C正确。该代码的算法思想是：(1)若t2>m1，此时应该赋初值，将t1赋给m1，t2赋给m2；(2)若t1>m1，且t2<＝m1，此时应该同时更新m1和m2，即现将当前的次大值m1赋给m2，再将当前的最大值t1赋给m1；(3)在t2<＝m1，且t1<＝m1，m1>m2时，若t1>m2，说明此时m2还不是次大值，需要更新其值，故m2＝t1。 18．2023·丽水中学检测定义函数isPalidrome() 用于判断回文字符串： def isPalidrome(s)： if len(s)<＝1： return True elif s[0]！＝s[len(s)－1]： return False else： return __________# 上述Python程序段中横线处可选的代码有： ①isPalidrome(s[1：－1]) ②isPalidrome(s[2：－1]) ③isPalidrome(s[1：len(s)－1]) ④isPalidrome(s[2：len(s)－1]) 下列选项中，可填入横线处的代码为(　D　) A．②或③ B．③或④ C．①或② D．①或③ 【解析】 该分支语句用于判断字符串s 中的第二个字符到倒数第二个字符是否满足回文串特性，根据字符串分片操作，选项D 正确。 19． 丑数是指不能被2、3、5 以外的质数整除的数。判断丑数的Python自定义函数程序如下： def ugly(n)： for i in [2，3，5]： return n＝＝1 若调用执行自定义函数ugly(30)，下列说法正确的是(　B　) A．函数返回值为False B．方框中的程序应用了迭代算法 C．该程序的时间复杂度为O(n2) D．条件语句n%i＝＝0 执行了3 次 【解析】 题目中对丑数的描述等价于：丑数是指只能被2、3、5 整除的数。选项A，30＝2×3×5，不能被2、3、5 以外的质数整除，说明30 是丑数，自定义函数应返回True，选项错误；选项B，方框中的程序为当n 能被i 整除时，不断求n 除以i 的商，是一个重复反馈的过程，选项正确；选项C，for 循环次数为列表的长度，while 循环次数是条件成立次数，该程序外循环执行3次，内循环最多执行log2n次，最大时间复杂度为O(log2n)，选项错误；选项D，条件语句n%i＝＝0 执行了6 次，选项错误。 20．2023·学军中学检测 已知s＝2＋4＋6＋8＋…＋2×n，为求s ＜1500 时，n 的最大值，小明编写了如下三个自定义函数f1()、f2()、f3()，其语句的总执行次数分别用T1、T2、T3 表示，则它们之间的关系为(　C　) A．T1<T2<T3 　　B． T3<T2<T1 C． T3<T1<T2 　　D．T1<T3<T2 【解析】 T1每次循环减去i；T2只有当i为偶数才减去i，s变小的速度慢；T3没有循环，故T3<T1<T2，选项C正确。 21．有如下两个Python 程序段： #程序段1 def rec(n)： if ：　　#① 　#② else： return n＋rec(n－1) print(rec(10)) #程序段2 def rec(n)： ans＝0 for i in range(1，n＋1，1)： ans＝ans＋ i return ans print(rec(10)) 下列关于两个程序段的说法中，正确的是(　D　) A．程序段1 和程序段2 的输出结果不相同 B．程序段1 和程序段2 都采用了递归算法 C．若问题规模为n，程序段2 的时间复杂度为O(n2) D．程序段1 中，将方框①、②中的数字1 同时修改为0，输出结果不变 【解析】 阅读程序段1，可知为使用递归算法实现求10＋9＋…＋1 的结果；阅读程序段2，可知为使用迭代算法实现求1＋2＋…＋10的结果。因此两段程序输出结果相同，选项A错误；程序段2 为迭代算法，选项B错误；程序段2 中只有一层循环，时间复杂度为O(n)，选项C错误；修改程序段1方框中的代码，仅仅多递归一层函数，但是返回值＋0并不会影响输出结果，选项D正确。 22． 2023·杭四中学检测对于如下两个Python程序段，下列说法不正确的是(　B　) #程序段1 a＝2 res＝1 n＝int(input()) for i in range(n)： res＝res*a print(res) #程序段2 def powr(a，n)： if n＝＝1： return a elif n＝＝0： return 1 else： tmp＝powr(a，n//2) return tmp*tmp a＝2 n＝int(input()) print(powr(a，n)) A． 若输入n＝8，程序段1、2都将输出256 B． 若输入n＝10，程序段1、2都将输出1024 C． 程序段1的算法时间复杂度是O(n) D．程序段2 的算法时间复杂度是O(log2n) 【解析】 选项A、B根据输入的值模拟运行得到相应的值。如选项B中，当n＝10 时，递归调用过程是：powr(2，10)→powr(2，5)→powr(2，2)→powr(2，1)→2。于是回归后powr(2，2)的值是2*2＝4，powr(2，5)的值是4*4＝16，powr(2，10)的值是16*16＝256，最终结果是256。选项B错误。选项C，程序段1的循环次数是n 次，算法时间复杂度是O(n)。选项D，程序段2的调用过程是：powr(a，n)→powr(a，n//2)→powr(a，n//4)→powr(a，n//8)→…→powr(a，1)，这里调用的次数约为log2n 次(n 除以几个2 会成为1)，因此算法时间复杂度是O(log2n)。 23．有如下Python 程序段： #程序段1 def fac(n)： s＝1 for i in range(1，n＋1)： 　s＝s*i return s print(fac(5)) #程序段2 def fac(n)： if n＝＝1： return 1 else： return n*fac(n－1) #① print(fac(5)) 下列关于两个程序段的说法中，正确的是(　C　) A． 程序段1 和程序段2 都使用了递归算法 B． 若问题规模为n，则程序段1 和程序段2 的时间复杂度不同 C． 若程序段1 中问题规模为n，则n 的值就是其循环执行的次数 D．若程序段2 中自定义函数内的代码只保留①处语句，也能获取到目标值 【解析】 选项A，程序段1 没有使用递归算法，选项错误；选项B，两段程序的算法复杂度都是O(n)，选项错误；选项C，根据代码“for i in range(1，n＋1)”可知，n 的值就是其循环执行的次数，选项正确；选项D，递归代码，在递推阶段必须有终止递推的代码，选项错误。 24．已知任取两个自然数，其互质(没有大于1的共同因数)的概率是，小蓝据此编写了Python程序： from math import sqrt from random import randint def fun(a，b)： if b＝＝0： return a else： return fun(b，a%b) cnt＝0 n＝1000；m＝100000 for i in range(n)： a＝randint(1，m) b＝randint(1，m) if fun(a，b)＝＝1： cnt＋＝1 print(sqrt(6*n/cnt)) 程序用频率估计概率，以验证该结论的准确性，下列说法正确的是(　D　) A．程序输出结果就是的近似值 B．该程序所描述算法的时间复杂度为O(n) C．函数fun()用递归算法求两个正整数的最小公倍数 D．要想提高程序结果的精确度，可以扩大n和m的范围 【解析】 选项A，根据公式，这是计算圆周率的近似值的公式，选项错误；选项B，本段代码的算法复杂度，除了for循环，还要考虑函数fun()的复杂度，函数fun()是用欧几里得算法求两个数的最大公约数，复杂度是O(log(mix(a，b))，最终的算法复杂度是O(log(mix(a，b)*n)，选项错误；选项C，是求两个数的最大公约数，选项错误；选项D，用概率的方法求近似值时，样本规模越大，得出的值越接近，选项正确。 25．2023·开化中学检测给定两个数，设计一个求最大公约数和最小公倍数的算法，该Python程序的运行结果如图所示： 请在横线处填入合适的代码。 def gys(x，y): #求最大公约数 if x>y： x，y＝y，x r＝1 for i in range(2，x＋1)： if ①__x%i＝＝0__and__y%i＝＝0__： 　　　r＝i return r def gbs(x，y): #求最小公倍数 if x<y： x，y＝y，x i＝x while True： if i%x＝＝0 and i%y＝＝0： 　　　②__break__ i＋＝1 return i m＝int(input(”请输入第一个数：　”)) n＝int(input(”请输入第二个数：　”)) print(m，”和”，n，”的最大公约数是：　”，gys(m，n)) print(m，”和”，n，”的最小公倍数是：　”，③__gbs(m，n)__ ) 【解析】 ①如果i能同时被x，y整除，则更新最大公约数，答案为x%i＝＝0 and y%i＝＝0。②若条件“i%x＝＝0 and i%y＝＝0”成立，则这是最小公倍数，不用继续查找下去，答案为break。③调用函数求解最小公倍数，答案为gbs(m，n)。 26．查找100以内的素数对。素数是指除了1和本身之外不再有其他因子的数。若两个素数的差为2，则称这两个素数为素数对。下列Python程序的功能是找出100以内的素数对，成对输出并统计对数。程序运行界面和代码如下，请在横线处填入合适的代码。 def isp(m)： flag＝True for i in range(2，m)： if m%i＝＝0： flag＝False break ①__return__flag__ # 主程序 cnt＝0 p1＝isp(3) i＝5 while i<100： ②__p2＝isp(i)__ if p1 and p2： print(str(i－2)＋”　 ”＋str(i)) cnt＋＝1 ③__p1＝p2__ i＋＝2 print(”共找到”＋str(cnt)＋”对”) 【解析】 题目中自定义函数的功能是判断是否素数，判断结果返回flag；程序需要找出100以内所有素数对，利用迭代算法思想解决该问题，用变量p1和p2表示枚举的素数对情况，p2获得从5开始的素数判断结果，p1迭代为上一轮数对p2的值。 学科网（北京）股份有限公司 $$