2026年编程能力测评中级代码题解析及答案

2026年编程能力测评：中级代码题解析及答案题型一：函数与算法设计（共3题，每题15分）题目1（15分）：设计一个函数，实现快速排序算法。要求：1.输入一个整数数组，返回快速排序后的数组。2.不能使用内置的排序函数。3.示例输入：`[3,6,8,10,1,2,1]`，示例输出：`[1,1,2,3,6,8,10]`答案：pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)示例测试print(quick_sort([3,6,8,10,1,2,1]))#输出:[1,1,2,3,6,8,10]解析：快速排序是一种分治算法，核心思想是选择一个基准值（pivot），将数组分为小于、等于、大于基准值的三部分，然后递归地对小于和大于基准值的部分进行排序。上述实现中，基准值选择为数组的中间元素，然后通过列表推导式分别生成小于、等于、大于基准值的部分，最后将排序后的三部分拼接返回。时间复杂度为O(nlogn)，空间复杂度为O(logn)。题目2（15分）：设计一个函数，检查一个字符串是否为有效的括号组合。要求：1.输入一个字符串，包含`'(',')','{','}','[',']'`。2.返回布尔值，表示字符串是否为有效的括号组合。3.示例输入：`"()[]{}"`，示例输出：`True`4.示例输入：`"([)]"`，示例输出：`False`答案：pythondefis_valid_parentheses(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack示例测试print(is_valid_parentheses("()[]{}"))#输出:Trueprint(is_valid_parentheses("([)]"))#输出:False解析：括号匹配问题可以使用栈来解决。遍历字符串，对于每个字符：-如果是右括号，检查栈顶元素是否与当前右括号匹配（即`')'`对应`'('`，`'}'`对应`'{'`，`']'`对应`'['`）。如果不匹配，返回`False`。-如果是左括号，压入栈中。-最后检查栈是否为空，如果为空，表示所有括号匹配；否则不匹配。题目3（15分）：设计一个函数，找出数组中第三大的数。要求：1.输入一个整数数组，返回第三大的数。2.如果数组不足三个不同的数，返回最大的数。3.示例输入：`[2,2,3,4,0,4,5,5,6]`，示例输出：`3`4.示例输入：`[1,1]`，示例输出：`1`答案：pythondefthird_largest(nums):first=second=third=float('-inf')fornuminnums:ifnum>first:third=secondsecond=firstfirst=numeliffirst>num>second:third=secondsecond=numelifsecond>num>third:third=numreturnfirstifthird==float('-inf')elsethird示例测试print(third_largest([2,2,3,4,0,4,5,5,6]))#输出:3print(third_largest([1,1]))#输出:1解析：使用三个变量`first`、`second`、`third`分别记录第一大、第二大、第三大的数，初始化为负无穷。遍历数组：-如果当前数大于`first`，更新`first`、`second`、`third`。-如果当前数在`first`和`second`之间，更新`second`、`third`。-如果当前数在`second`和`third`之间，更新`third`。最后，如果`third`仍为负无穷，表示数组不足三个不同的数，返回`first`；否则返回`third`。题型二：数据结构与链表操作（共3题，每题15分）题目4（15分）：设计一个函数，删除链表的中间节点。要求：1.输入一个链表的头节点，删除该链表的中间节点。2.假设链表长度为奇数，删除最中间的节点。3.示例输入：`1->2->3->4->5`，示例输出：`1->2->3->5`答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefdelete_middle_node(head):ifnotheadornothead.next:returnNoneslow=headfast=headprev=Nonewhilefastandfast.next:prev=slowslow=slow.nextfast=fast.next.nextprev.next=slow.nextreturnhead示例测试defprint_list(head):current=headwhilecurrent:print(current.val,end="->")current=current.nextprint("None")head=ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))print_list(delete_middle_node(head))#输出:1->2->3->5->None解析：使用快慢指针法。慢指针`slow`每次移动一步，快指针`fast`每次移动两步。当快指针到达链表末尾时，慢指针位于中间节点。通过`prev`指针记录慢指针的前一个节点，删除慢指针指向的节点。题目5（15分）：设计一个函数，判断链表是否存在环。要求：1.输入一个链表的头节点，返回布尔值，表示链表是否存在环。2.示例输入：`1->2->3->4->2`（2为环的入口），示例输出：`True`3.示例输入：`1->2->3->4->5`，示例输出：`False`答案：pythondefhas_cycle(head):slow=headfast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:returnTruereturnFalse示例测试defcreate_cycle(head,pos):ifnothead:returnheadtail=headcycle_entry=Noneforiinrange(1,pos+1):tail=tail.nextfast=headwhilefast.next:fast=fast.nextfast.next=tailreturnheadhead=create_cycle(ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5))))),2)print(has_cycle(head))#输出:True解析：使用快慢指针法。慢指针`slow`每次移动一步，快指针`fast`每次移动两步。如果链表存在环，快慢指针最终会相遇；否则快指针会到达链表末尾。上述实现中，`create_cycle`函数用于创建一个带有环的链表，`pos`表示环的入口节点位置（-1表示无环）。题目6（15分）：设计一个函数，反转链表的一部分。要求：1.输入链表的头节点、开始位置`m`和结束位置`n`，反转链表从`m`到`n`的部分。2.示例输入：`1->2->3->4->5`，`m=2`，`n=4`，示例输出：`1->4->3->2->5`答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_between(head,m,n):ifnotheadorm==n:returnheaddummy=ListNode(0)dummy.next=headprev=dummyfor_inrange(m-1):prev=prev.nextcurrent=prev.nextprev_node=Nonefor_inrange(n-m+1):next_node=current.nextcurrent.next=prev_nodeprev_node=currentcurrent=next_nodeprev.next.next=currentprev.next=prev_nodereturndummy.next示例测试defprint_list(head):current=headwhilecurrent:print(current.val,end="->")current=current.nextprint("None")head=ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))reversed_head=reverse_between(head,2,4)print_list(reversed_head)#输出:1->4->3->2->5->None解析：首先找到反转部分的起始节点`current`和其前一个节点`prev`。然后使用经典的链表反转方法，将`current`到`n`的部分反转。最后将反转后的部分与前面的部分和后面的部分连接起来。题型三：树与二叉树操作（共3题，每题15分）题目7（15分）：设计一个函数，判断二叉树是否对称。要求：1.输入一个二叉树的头节点，返回布尔值，表示该二叉树是否对称。2.示例输入：`[1,2,2,3,4,4,3]`（二叉树表示），示例输出：`True`3.示例输入：`[1,2,2,2,null,2]`，示例输出：`False`答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_symmetric(root):defis_mirror(t1,t2):ifnott1andnott2:returnTrueifnott1ornott2:returnFalsereturn(t1.val==t2.val)andis_mirror(t1.left,t2.right)andis_mirror(t1.right,t2.left)returnis_mirror(root,root)示例测试defbuild_tree(values):ifnotvalues:returnNonenodes=[NoneifvalisNoneelseTreeNode(val)forvalinvalues]kids=nodes[::-1]root=kids.pop()fornodeinnodes:ifnode:ifkids:node.left=kids.pop()ifkids:node.right=kids.pop()returnrootroot1=build_tree([1,2,2,3,4,4,3])root2=build_tree([1,2,2,2,None,2])print(is_symmetric(root1))#输出:Trueprint(is_symmetric(root2))#输出:False解析：对称二叉树是指左右子树镜像对称。可以使用递归方法判断。定义`is_mirror`函数，检查两个树是否镜像对称：-如果两个节点都为空，对称。-如果一个节点为空，另一个不为空，不对称。-如果两个节点不为空，且值相等，递归检查左子树的右节点和右子树的左节点，以及右子树的右节点和左子树的左节点。题目8（15分）：设计一个函数，找出二叉树的最大深度。要求：1.输入一个二叉树的头节点，返回该二叉树的最大深度。2.示例输入：`[3,9,20,null,null,15,7]`（二叉树表示），示例输出：`3`答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmax_depth(root):ifnotroot:return0left_depth=max_depth(root.left)right_depth=max_depth(root.right)returnmax(left_depth,right_depth)+1示例测试defbuild_tree(values):ifnotvalues:returnNonenodes=[NoneifvalisNoneelseTreeNode(val)forvalinvalues]kids=nodes[::-1]root=kids.pop()fornodeinnodes:ifnode:ifkids:node.left=kids.pop()ifkids:node.right=kids.pop()returnrootroot=build_tree([3,9,20,None,None,15,7])print(max_depth(root))#输出:3解析：最大深度是指从根节点到最远叶子节点的最长路径上的节点数。可以使用递归方法计算：-如果节点为空，深度为0。-否则，深度为左子树和右子树深度的最大值加1。题目9（15分）：设计一个函数，判断二叉树是否是完全二叉树。要求：1.输入一个二叉树的头节点，返回布尔值，表示该二叉树是否为完全二叉树。2.示例输入：`[1,2,3,4,5,6,7]`（二叉树表示），示例输出：`True`3.示例输入：`[1,2,3,4,None,6]`，示例输出：`False`答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_complete_binary_tree(root):ifnotroot:returnTruequeue=[root]end=Falsewhilequeue:node=queue.pop(0)ifnode:ifend:returnFalsequeue.append(node.left)queue.append(node.right)else:end=TruereturnTrue示例测试defbuild_tree(values):ifnotvalues:returnNonenodes=[NoneifvalisNoneelseTreeNode(val)forvalinvalues]kids=nodes[::-1]root=kids.pop()fornodeinnodes:ifnode:ifkids:node.left=kids.pop()ifkids:node.right=kids.pop()returnrootroot1=build_tree([1,2,3,4,5,6,7])root2=build_tree([1,2,3,4,None,6])print(is_complete_binary_tree(root1))#输出:Trueprint(is_complete_binary_tree(root2))#输出:False解析：完全二叉树是指除最后一层外，每一层都是满的，并且最后一层节点从左到右连续排列。可以使用层序遍历判断：-使用队列进行层序遍历。-遇到空节点后，后续节点都应为空。如果遇到非空节点，后续节点不为空，则不是完全二叉树。题型四：动态规划与算法优化（共3题，每题15分）题目10（15分）：设计一个函数，计算不同路径的数量。要求：1.输入一个mxn的网格，返回从左上角到右下角的路径数量。2.只能向下或向右移动。3.示例输入：`m=3`，`n=2`，示例输出：`3`答案：pythondefunique_paths(m,n):dp=[[0]nfor_inrange(m)]foriinrange(m):dp[i][0]=1forjinrange(n):dp[0][j]=1foriinrange(1,m):forjinrange(1,n):dp[i][j]=dp[i-1][j]+dp[i][j-1]returndp[m-1][n-1]示例测试print(unique_paths(3,2))#输出:3解析：可以使用动态规划方法。定义`dp[i][j]`表示到达第`i`行第`j`列的路径数量。初始条件：-第一行和第一列的路径数量为1。-其他位置的数量为左方和上方位置的数量之和。最终结果为`dp[m-1][n-1]`。题目11（15分）：设计一个函数，找出最长递增子序列的长度。要求：1.输入一个整数数组，返回最长递增子序列的长度。2.示例输入：`[10,9,2,5,3,7,101,18]`，示例输出：`4`3.示例输入：`[0,1,0,3,2,3]`，示例输出：`4`答案：pythondeflength_of_lis(nums):ifnotnums:return0dp=[1]len(nums)foriinrange(1,len(nums)):forjinrange(i):ifnums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1)returnmax(dp)示例测试print(length_of_lis([10,9,2,5,3,7,101,18]))#输出:4print(length_of_lis([0,1,0,3,2,3]))#输出:4