2026年程序设计专业水平测试算法设计与程序调试实战题

2026年程序设计专业水平测试：算法设计与程序调试实战题一、编程实现题（共3题，每题15分，合计45分）1.（15分）设计一个函数，用于计算一个字符串中所有数字字符的和。输入为一个包含大小写字母、数字和其他符号的字符串，输出为字符串中所有数字字符对应的数值之和。例如，输入`"a1b2c3"`，输出为`6`。要求：-忽略非数字字符。-输入字符串长度不超过1000个字符。-不能使用现成的数字求和库函数，需手动解析字符并转换。参考代码（Python示例）：pythondefsum_of_digits(s:str)->int:total=0forcharins:ifchar.isdigit():total+=int(char)returntotal2.（15分）实现一个函数，将一个整数列表按奇偶性分组，并分别排序。例如，输入`[3,1,2,4,5,6]`，输出为`[[1,3,5],[2,4,6]]`。要求：-先将列表分为奇数和偶数两个子列表。-对两个子列表分别进行升序排序。-返回一个包含两个已排序子列表的元组。参考代码（Python示例）：pythondefsort_odd_even(nums:list)->tuple:odd=sorted([xforxinnumsifx%2!=0])even=sorted([xforxinnumsifx%2==0])return(odd,even)3.（15分）编写一个函数，检查一个字符串是否为“回文串”（即正读和反读相同），忽略大小写和非字母字符。例如，输入`"Aman,aplan,acanal:Panama"`，输出为`True`。要求：-忽略空格、标点符号，统一转换为小写后比较。-使用栈或双指针方法实现。参考代码（Python示例）：pythondefis_palindrome(s:str)->bool:importres=re.sub(r'[^a-zA-Z]','',s).lower()returns==s[::-1]二、算法设计题（共2题，每题20分，合计40分）4.（20分）设计一个算法，找出一个无重复元素的整数数组中所有和为特定目标值的不重复三元组。例如，输入`[2,7,11,15]`，目标值`9`，输出为`[[2,7]]`（按升序排列）。要求：-不能有重复的三元组（例如`[2,7]`和`[7,2]`视为相同）。-时间复杂度尽量低（不超过O(n²)）。思路提示：-先排序数组，使用双指针法。-固定第一个数，再用左右指针分别遍历剩余部分。5.（20分）设计一个算法，判断一个二叉树是否为“完全二叉树”。完全二叉树的定义：除最后一层外，每一层节点都填满，且最后一层节点从左到右连续排列。例如：1/\23/\/456是完全二叉树；1/\23\4不是完全二叉树。要求：-使用层序遍历（广度优先搜索）实现。-时间复杂度O(n)，空间复杂度O(n)。思路提示：-使用队列进行层序遍历。-遇到空节点后，后续节点都必须为空。三、程序调试题（共2题，每题15分，合计30分）6.（15分）以下代码存在逻辑错误，请找出并修正，使其能够正确计算斐波那契数列的第n项（n≥1）。pythondeffibonacci(n:int)->int:ifn<=0:return0elifn==1:return1else:returnfibonacci(n-1)+fibonacci(n-2)#无递归终止条件调试要求：-写出修正后的代码。-说明错误原因及修正方法。参考答案：错误原因：递归没有终止条件，会导致栈溢出。修正后：pythondeffibonacci(n:int)->int:ifn<=0:return0elifn==1:return1else:a,b=0,1for_inrange(2,n+1):a,b=b,a+breturnb7.（15分）以下代码用于查找列表中的最大值，但存在语法错误，请修正并解释错误原因。pythondeffind_max(nums:list)->int:max_num=0fornuminnums:ifnum>max_num:max_num=numreturnmax_num#错误：未处理空列表情况调试要求：-写出修正后的代码。-说明错误原因及修正方法。参考答案：错误原因：未处理空列表的情况，会导致`max_num=0`时无法返回正确值。修正后：pythondeffind_max(nums:list)->int:ifnotnums:raiseValueError("Listisempty")max_num=nums[0]fornuminnums[1:]:ifnum>max_num:max_num=numreturnmax_num答案与解析一、编程实现题1.sum_of_digits函数-输入：`"a1b2c3"`-输出：`6`（解析：`'1'+'2'+'3'=6`）2.sort_odd_even函数-输入：`[3,1,2,4,5,6]`-输出：`([1,3,5],[2,4,6])`3.is_palindrome函数-输入：`"Aman,aplan,acanal:Panama"`-输出：`True`（解析：忽略大小写和标点后为`"amanaplanacanalpanama"`，是回文）二、算法设计题4.三元组求和-输入：`[2,7,11,15]`，目标值`9`-输出：`[[2,7]]`5.完全二叉树判断-示例树1（完全）：1/\23/\/456输出：`True`-示例树2（非完全）：1/\23\4输出：`False`三、程序调试题6.斐波那契数列修正-修正后代码：pythondeffibonacci(n:int)->int:ifn<=0:return0elifn==1:return1else:a,b=0,1for_inrange(2,n+1):a,b=b,a+breturnb-错误原因：原始递归无终止条件，会导致栈溢出。-修正方法：改用循环实现。7.最大值查找修正-修正后代码：pythondeffind_max(nums:list)->int:ifnotnums:raiseValueError("Listisempty"