编程竞赛常考题型及参考答案指南

2026年编程竞赛常考题型及参考答案指南1.数值计算与算法设计（3题，共45分）1.1排序算法应用（10分）题目：给定一个包含n个整数的无序数组`arr`，请实现快速排序算法，并返回排序后的数组。要求：-输入：`arr=[4,2,6,3,1,5]`-输出：`[1,2,3,4,5,6]`参考答案：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)arr=[4,2,6,3,1,5]sorted_arr=quick_sort(arr)print(sorted_arr)#输出：[1,2,3,4,5,6]解析：快速排序通过分治思想将数组分为小于、等于、大于枢轴的三个部分，递归排序左半部分和右半部分。时间复杂度平均为O(nlogn)。1.2动态规划问题（15分）题目：给定一个背包容量为`W`，以及n个物品，每个物品的重量为`weights`，价值为`values`。请计算背包能装下的最大价值。要求：-输入：`W=10`,`weights=[2,3,4,5]`,`values=[3,4,5,6]`-输出：`7`（选择物品2和物品3，价值4+5=9，但重量7>10，实际选物品1和物品4，价值3+6=9）参考答案：pythondefknapsack(W,weights,values):n=len(weights)dp=[[0](W+1)for_inrange(n+1)]foriinrange(1,n+1):forwinrange(1,W+1):ifweights[i-1]<=w:dp[i][w]=max(dp[i-1][w],dp[i-1][w-weights[i-1]]+values[i-1])else:dp[i][w]=dp[i-1][w]returndp[n][W]W=10weights=[2,3,4,5]values=[3,4,5,6]print(knapsack(W,weights,values))#输出：7解析：动态规划通过构建二维表`dp[i][w]`表示前i个物品在容量为w时的最大价值。状态转移方程为：`dp[i][w]=max(dp[i-1][w],dp[i-1][w-weights[i-1]]+values[i-1])`。1.3字符串匹配问题（20分）题目：给定文本串`text`和模式串`pattern`，请实现KMP算法，返回模式串在文本串中的起始索引（若有多个匹配，返回第一个）。要求：-输入：`text="ABABDABACDABABCABAB"`,`pattern="ABABCABAB"`-输出：`10`（"ABABCABAB"出现在文本的第10个字符处）参考答案：pythondefkmp_search(text,pattern):defcompute_lps(pattern):lps=[0]len(pattern)length=0i=1whilei<len(pattern):ifpattern[i]==pattern[length]:length+=1lps[i]=lengthi+=1else:iflength!=0:length=lps[length-1]else:lps[i]=0i+=1returnlpslps=compute_lps(pattern)i=j=0whilei<len(text):ifpattern[j]==text[i]:i+=1j+=1ifj==len(pattern):returni-jelifi<len(text)andpattern[j]!=text[i]:ifj!=0:j=lps[j-1]else:i+=1return-1text="ABABDABACDABABCABAB"pattern="ABABCABAB"print(kmp_search(text,pattern))#输出：10解析：KMP算法通过计算最长公共前后缀（LPS数组）避免重复比较，时间复杂度为O(n)。`compute_lps`函数用于生成LPS数组，匹配时若不匹配则跳转至`lps[j-1]`继续比较。2.数据结构与图论（4题，共60分）2.1链表操作（15分）题目：给定一个单链表，请实现反转链表。要求：-输入：`1->2->3->4->5`-输出：`5->4->3->2->1`参考答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev构建链表head=ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))reversed_head=reverse_list(head)遍历输出current=reversed_headwhilecurrent:print(current.val,end="->")current=current.next输出：5->4->3->2->1解析：反转链表通过迭代法实现，使用三个指针`prev`、`current`和`next_node`依次翻转每个节点的指向。2.2栈的应用（15分）题目：给定一个只包含`'('`,`')'`的字符串，请判断是否为有效的括号序列。要求：-输入：`"(()())"`-输出：`True`参考答案：pythondefisValid(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstackprint(isValid("(()())"))#输出：True解析：利用栈匹配括号，遍历字符串时：1.遇到左括号入栈；2.遇到右括号时，栈顶应为对应左括号，否则无效；3.遍历结束后栈为空则有效。2.3二叉树遍历（15分）题目：给定二叉树，请实现中序遍历（非递归）。要求：-输入：1/\23/\45-输出：`4->2->5->1->3`参考答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefinorder_traversal(root):stack,current=[],rootoutput=[]whilestackorcurrent:whilecurrent:stack.append(current)current=current.leftcurrent=stack.pop()output.append(current.val)current=current.rightreturnoutput构建二叉树root=TreeNode(1)root.left=TreeNode(2,TreeNode(4),TreeNode(5))root.right=TreeNode(3)print("->".join(map(str,inorder_traversal(root))))#输出：4->2->5->1->3解析：中序遍历通过栈实现，依次遍历左子树、访问节点、遍历右子树。时间复杂度为O(n)。2.4图的最短路径（15分）题目：给定一个无向图，请使用Dijkstra算法计算从起点`src`到终点`dest`的最短路径。要求：-输入：边列表：[(0,1,2),(0,2,3),(1,2,1),(1,3,1),(2,3,4),(3,4,2)]起点src=0，终点dest=4-输出：`4`（最短路径长度为0->1->3->4，总距离2+1+2=5）参考答案：pythonimportheapqdefdijkstra(n,edges,src):graph={i:[]foriinrange(n)}foru,v,winedges:graph[u].append((v,w))graph[v].append((u,w))heap=[(0,src)]distances={i:float('inf')foriinrange(n)}distances[src]=0whileheap:dist,u=heapq.heappop(heap)ifdist>distances[u]:continueforv,wingraph[u]:ifdistances[v]>dist+w:distances[v]=dist+wheapq.heappush(heap,(dist+w,v))returndistances[dest]edges=[(0,1,2),(0,2,3),(1,2,1),(1,3,1),(2,3,4),(3,4,2)]n=5src=0dest=4print(dijkstra(n,edges,src))#输出：5解析：Dijkstra算法使用优先队列（小顶堆）维护当前最短未访问节点，通过贪心策略不断更新邻接节点的距离。时间复杂度为O((E+V)logV)。3.系统设计与数据库（5题，共90分）3.1数据库查询（20分）题目：假设有表`Students`（`id`,`name`,`age`,`class_id`）和`Classes`（`class_id`,`class_name`），请查询年龄大于20且班级名称为"CS101"的学生姓名。要求：-输入：sqlStudents:[(1,'Alice',21,'CS101'),(2,'Bob',19,'CS101'),(3,'Charlie',22,'CS102')]Classes:[('CS101','ComputerScience'),('CS102','DataStructures')]-输出：`Alice`参考答案：sqlSELECTnameFROMStudentsJOINClassesONStudents.class_id=Classes.class_idWHEREage>20ANDClasses.class_name='CS101';解析：通过`JOIN`连接`Students`和`Classes`表，使用`WHERE`子句过滤年龄和班级名称，返回满足条件的姓名。3.2SQL优化（15分）题目：给定以下SQL查询：sqlSELECTCOUNT()ASuser_countFROMOrdersWHEREorder_dateBETWEEN'2023-01-01'AND'2023-12-31'ANDstatus='Completed';请提出至少两条优化建议。参考答案：1.为`order_date`和`status`列创建索引，加速范围查询和条件过滤。2.使用`EXPLAIN`分析查询计划，确保没有全表扫描。3.若`Orders`表数据量大，可考虑分区表按日期分区。解析：索引可以显著提升查询性能，特别是多列组合索引。分区表可以减少数据扫描范围。3.3分布式系统设计（20分）题目：设计一个高并发的短链接系统，要求：1.支持每天创建百万级短链接。2.系统可用性>99.9%。3.重定向速度<200ms。参考答案：1.短链接生成：使用62进制哈希（如`1r7z8a9`）映射至UUID，存储映射关系于Redis（主从复制+集群）。2.高可用：使用Nginx负载均衡多台后端服务，后端服务集群部署（如Kubernetes）。3.缓存优化：Redis缓存热点短链接，TTL设为24小时，过期自动清理。4.限流防攻击：Nginx配置限流规则，后端IP黑名单过滤恶意请求。解析：短链接系统需解决高并发、快速重定向和分布式存储问题，结合缓存和负载均衡实现性能和可用性。3.4微服务架构（20分）题目：设计一个电商平台的订单服务，要求：1.订单创建支持事务性。2.支持订单秒杀（10秒内完成库存锁定）。3.异步通知优惠券发放。参考答案：1.事务性：使用分布式事务（如2PC或TCC），订单与库存操作在一个分布式事务管理器（如Seata）下。2.秒杀：-库存预减：RedisLua脚本原子扣减库存。-超时回滚：使用Redis过期键实现自动回滚