2025年03月中国电子学会青少年软件编程(Python)等级考试试卷(四级)答案

2025年03月中国电子学会青少年软件编程(Python)等级考试试卷(四级)答案本答案对应2025年3月中国电子学会青少年软件编程（Python）等级考试四级试卷，所有内容严格贴合官方考纲要求与命题逻辑，数据准确，解题过程附完整思路说明，符合Python3.8及以上版本语法规范。第一部分单项选择题（共15题，每题2分，总计30分）每题给出4个选项，只有1个符合题目要求。1.以下递归函数实现求n的阶乘，划线处应填入的代码是（）```pythondeffact(n):if____:return1returnn*fact(n-1)```A.n==0B.n>0C.n==1D.n<=1答案：D解析：阶乘的数学定义为0!=1，1!=1，n>1时n!=n*(n-1)!，因此终止条件需覆盖n=0和n=1两种边界情况，选择n<=1可以避免非法输入（如n=0）导致的递归深度溢出，同时符合数学定义。2.已知栈的初始状态为空，入栈序列为[1,3,5,7,9]，若入栈过程中允许出栈，以下不可能出现的出栈序列是（）A.9,7,5,3,1B.3,1,7,5,9C.5,3,1,7,9D.7,3,5,1,9答案：D解析：栈是后进先出的线性存储结构，仅允许在栈顶执行入栈、出栈操作。D选项中7最先出栈，说明此时栈内从栈底到栈顶的元素为1、3、5、7，7出栈后栈顶元素为5，下一个出栈元素不可能为3，因此该序列不合法。其余选项均符合栈的操作规则：A为所有元素全部入栈后依次出栈，B为1、3入栈后3出栈、1出栈，后续5、7入栈后7出栈、5出栈，最后9入栈后出栈；C为1、3、5入栈后依次出栈，后续7、9入栈后依次出栈。3.以下算法的平均时间复杂度为O(nlogn)的是（）A.冒泡排序B.插入排序C.快速排序平均情况D.选择排序答案：C解析：冒泡排序、插入排序、选择排序均为基础比较排序，平均时间复杂度为O(n²)，仅适用于小规模数据排序；快速排序采用分治思想，平均情况下每次分区将序列分为近似等长的两个子序列，递归深度为log₂n，每层分区的时间复杂度为O(n)，因此平均时间复杂度为O(nlogn)，是工业界最常用的排序算法之一。4.有序列表为[2,5,8,12,16,23,30,37,42,49]，用二分查找法查找元素23，需要比较的次数是（）A.2B.3C.4D.5答案：B解析：二分查找的核心逻辑是每次取区间中间元素与目标值比较，缩小查找范围。第一次比较区间[0,9]的中间元素（索引4）16，23>16，查找范围缩小为右半区间[5,9]；第二次比较区间[5,9]的中间元素（索引7）37，23<37，查找范围缩小为左半区间[5,6]；第三次比较区间[5,6]的中间元素（索引5）23，匹配成功，总比较次数为3次。5.已知队列初始为空，入队顺序为A、B、C、D，以下合法的出队顺序是（）A.A、B、C、DB.D、C、B、AC.A、C、B、DD.B、A、D、C答案：A解析：队列是先进先出的线性存储结构，入队操作在队尾执行，出队操作在队头执行，入队顺序与出队顺序完全一致，仅A选项符合规则，其余选项均为栈的合法出栈序列。6.斐波那契数列递归实现的代码如下，调用fib(5)时，函数fib被调用的总次数是（）```pythondeffib(n):ifn<=2:return1returnfib(n-1)+fib(n-2)```A.5B.9C.15D.25答案：B解析：递归调用树的节点依次为fib(5)、fib(4)、fib(3)、fib(3)、fib(2)、fib(2)、fib(1)、fib(2)、fib(1)，总调用次数为9次。递归实现斐波那契数列存在大量重复计算，时间复杂度为O(2ⁿ)，实际应用中通常采用迭代或动态规划优化。7.以下排序算法中属于稳定排序的是（）A.快速排序B.堆排序C.归并排序D.希尔排序答案：C解析：稳定排序指排序前后相等元素的相对位置保持不变，适用于需要保留原始序列顺序的场景，如学生成绩排序时要求相同分数的学生保留原始学号顺序。归并排序、冒泡排序、插入排序属于稳定排序，快速排序、堆排序、希尔排序、选择排序均为不稳定排序。8.某二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBDAEF，则后序遍历序列为（）A.CDBFEAB.CBAEDFC.FEDCBAD.CDBEFA答案：A解析：二叉树先序遍历顺序为根→左→右，中序遍历顺序为左→根→右，后序遍历顺序为左→右→根。由先序序列可知根节点为A，中序序列中A左侧的CBD为左子树，右侧的EF为右子树；左子树先序序列为BCD，可知左子树根节点为B，中序序列中B左侧的C为左子节点，右侧的D为右子节点；右子树先序序列为EF，可知右子树根节点为E，中序序列中E右侧的F为右子节点。因此后序遍历顺序为左子树→右子树→根，即CDBFEA。9.以下关于Python闭包的描述错误的是（）A.闭包是嵌套函数B.闭包的外层函数返回内层函数的引用C.闭包可以保留外层函数的变量状态D.闭包中不能修改外层函数的变量答案：D解析：闭包的核心特性是可以保留外层函数的变量状态，即使外层函数执行结束，变量依然可以被内层函数访问。Python3中引入nonlocal关键字，允许在内层函数中修改外层函数的非全局变量，因此D选项描述错误。10.Python装饰器本质上是一种（）A.类B.高阶函数C.迭代器D.生成器答案：B解析：装饰器本质是接收函数作为参数、返回新函数的高阶函数，用于在不修改原函数代码的前提下扩展函数功能，如日志统计、性能监控、权限校验等场景。Python也支持类装饰器，本质是重载类的__call__方法实现函数扩展，但其底层逻辑依然基于高阶函数的设计思想。11.计数排序适用于以下哪种场景（）A.待排序元素范围很大B.待排序元素为整数且范围较小C.待排序元素为浮点数D.待排序序列已经基本有序答案：B解析：计数排序是非比较排序，核心逻辑是统计每个整数出现的次数，再按次数输出排序结果，要求待排序元素为整数且取值范围较小，否则会导致空间复杂度过高。待排序序列基本有序的场景适合使用插入排序，浮点数排序通常采用快速排序或归并排序。12.以下关于哈希查找的描述正确的是（）A.哈希查找的时间复杂度一定为O(1)B.哈希冲突指的是不同关键字通过哈希函数得到相同的哈希地址C.解决哈希冲突的开放定址法不会产生堆积问题D.哈希函数越复杂查找效率越高答案：B解析：A选项存在哈希冲突时，哈希查找的时间复杂度会升高到O(n)；C选项开放定址法通过探测下一个空地址存储冲突元素，会导致同类哈希冲突元素堆积，降低查找效率；D选项哈希函数应尽量简单且分布均匀，过于复杂的哈希函数会增加计算开销，降低查找效率。仅B选项描述符合哈希查找的定义。13.以下算法的空间复杂度为O(1)的是（）A.递归实现的归并排序B.快速排序递归实现C.冒泡排序D.深度优先遍历二叉树答案：C解析：空间复杂度指算法执行过程中需要的额外存储空间，冒泡排序为原地排序算法，仅需要常数级的临时变量存储交换数据，空间复杂度为O(1)。递归实现的归并排序需要O(n)的临时数组存储合并结果，快速排序递归实现的递归栈平均空间复杂度为O(logn)，深度优先遍历二叉树的递归栈空间复杂度为O(h)（h为二叉树高度），均大于O(1)。14.以下场景不适合使用队列实现的是（）A.操作系统的进程调度B.表达式求值C.打印机的任务排队D.二叉树的层序遍历答案：B解析：表达式求值需要处理运算符的优先级，符合栈的后进先出特性，适合用栈实现。其余场景均符合队列先进先出的特性：操作系统进程调度的先来先服务策略、打印机任务排队均按提交顺序执行，二叉树层序遍历按层级顺序访问节点，均需要队列实现。15.Python默认的递归深度上限约为（）A.100B.1000C.10000D.无上限答案：B解析：Python为了避免无限递归占用大量内存，默认设置递归深度上限为1000左右，超过上限会触发RecursionError异常，可通过sys.setrecursionlimit()函数修改递归深度上限，但不建议设置过大，避免栈溢出。第二部分判断题（共10题，每题2分，总计20分）判断对错，正确填√，错误填×。1.递归函数必须有终止条件，否则会出现无限递归。（√）解析：递归函数的两个核心要素为终止条件和递归表达式，无终止条件会导致递归深度持续升高，最终触发递归深度溢出异常。2.快速排序的最坏时间复杂度为O(nlogn)。（×）解析：快速排序最坏情况为待排序序列完全有序或完全逆序，每次分区仅能将序列分为长度为1和n-1的两个子序列，时间复杂度为O(n²)，可通过随机选择基准元素的方式避免最坏情况出现。3.栈的插入和删除操作均在栈顶进行。（√）解析：栈是操作受限的线性表，仅允许在栈顶执行入栈（插入）和出栈（删除）操作，保证后进先出的特性。4.二分查找可以应用于任意无序序列。（×）解析：二分查找要求待查找序列为有序序列，否则无法通过中间元素与目标值的比较缩小查找范围，无序序列仅能使用顺序查找，时间复杂度为O(n)。5.Python中匿名函数的关键字是lambda。（√）解析：lambda关键字用于定义无需命名的匿名函数，适合实现简单的一次性功能，常作为参数传递给map、filter、sorted等高阶函数。6.二叉树的中序遍历是先遍历左子树，再访问根节点，最后遍历右子树。（√）解析：二叉树三种深度优先遍历的规则为：先序遍历（根→左→右）、中序遍历（左→根→右）、后序遍历（左→右→根）。7.归并排序是原地排序算法。（×）解析：归并排序需要额外的临时数组存储两个子序列的合并结果，空间复杂度为O(n)，不属于原地排序算法。8.深度优先遍历二叉树可以使用队列实现。（×）解析：深度优先遍历基于栈的后进先出特性实现，二叉树的广度优先（层序）遍历基于队列的先进先出特性实现。9.装饰器只能装饰函数，不能装饰类。（×）解析：Python中装饰器既可以装饰函数，也可以装饰类，通过装饰类可以实现类的功能扩展，如添加类属性、修改类方法等。10.队列的出队操作是在队头进行，入队操作是在队尾进行。（√）解析：队列是操作受限的线性表，仅允许在队尾执行入队操作、队头执行出队操作，保证先进先出的特性。第三部分编程题（共5题，每题10分，总计50分）要求代码逻辑正确，输出格式符合题目要求，可正常运行。编程题1：递归实现幂运算题目：编写递归函数power(x,n)，计算x的n次幂（x为整数，n为非负整数），要求不使用Python内置的pow函数和运算符。输入两个整数x和n，输出计算结果。样例输入：23样例输出：8考查点：递归函数的设计与实现解题思路：递归终止条件为n=0时返回1（数学定义中任何数的0次幂为1）；递归表达式为x的n次幂等于x乘以x的n-1次幂，逐步缩小问题规模直到触发终止条件。参考代码：```pythondefpower(x,n):ifn==0:return1returnx*power(x,n-1)x,n=map(int,input().split())print(power(x,n))```评分标准：正确实现递归结构得6分，边界条件（n=0）处理正确得2分，输入输出格式符合要求得2分。编程题2：栈实现括号匹配题目：给定一个只包含'('、')'、'['、']'、'{'、'}'的字符串，判断字符串中的括号是否匹配。匹配规则：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合。匹配输出True，不匹配输出False。样例输入1：([{}])样例输出1：True样例输入2：([)]样例输出2：False考查点：栈的应用解题思路：使用列表模拟栈存储左括号，构建右括号到对应左括号的映射字典；遍历字符串，遇到左括号入栈，遇到右括号时首先判断栈是否为空（无匹配的左括号）或栈顶左括号与当前右括号不匹配，两种情况均返回False，匹配则弹出栈顶元素；遍历结束后判断栈是否为空，为空则所有左括号均匹配成功，否则存在未匹配的左括号。参考代码：```pythondefis_valid(s):stack=[]bracket_map={')':'(',']':'[','}':'{'}forcharins:ifcharinbracket_map.values():stack.append(char)else:ifnotstackorstack[-1]!=bracket_map[char]:returnFalsestack.pop()returnlen(stack)==0s=input().strip()print(is_valid(s))```评分标准：栈结构使用正确得4分，括号映射规则正确得2分，边界情况（空栈、遍历结束栈非空）处理正确得2分，输入输出符合要求得2分。编程题3：快速排序实现题目：编写快速排序函数，对输入的整数列表进行升序排序，输出排序后的列表。要求使用递归实现快速排序。样例输入：5381294样例输出：1234589考查点：分治思想、快速排序实现解题思路：采用分治思想，选择列表中间元素作为基准，将列表划分为小于基准、等于基准、大于基准三个子列表；递归对小于基准和大于基准的子列表排序，最后合并三个子列表得到排序结果。参考代码：```pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]mid=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+mid+quick_sort(right)arr=list(map(int,input().split()))res=quick_sort(arr)print(''.join(map(str,res)))```评分标准：递归结构正确得3分，基准选择逻辑正确得2分，分区逻辑正确得3分，输入输出符合要求得2分。编程题4：二叉树层序遍历题目：给定一棵二叉树的节点个数n，以及n个节点的信息（每个节点包含值、左子节点索引、右子节点索引，根节点索引为0，子节点不存在时索引为-1），输出该二叉树的层序遍历结果。样例输入：61122343-154-1-15-1-16-1-1样例输出：123456考查点：队列的应用、二叉树遍历解题思路：使用collections.deque实现队列，先将根节点索引加入队列；循环取出队列头部的节点索引，输出节点值，依次将存在的左子节点、右子节点索引加入队列，直到队列为空，即可得到层序遍历结果。参考代码：```pythonfromcollectionsimportdequen=int(input())nodes=[]for_inrange(n):val,left,right=map(int,input().split())nodes.append((val,left,right))q=deque()q.append(0)res=[]whileq:idx=q.popleft()val,left,right=nodes[idx]res.append(str(val))ifleft!=-1:q.append(left)ifright!=-1:q.append(right)prin