2026年編程競(jìng)賽?？碱}型及參考答案指南1.數(shù)值計(jì)算與算法設(shè)計(jì)（3題，共45分）1.1排序算法應(yīng)用（10分）題目：給定一個(gè)包含n個(gè)整數(shù)的無(wú)序數(shù)組`arr`，請(qǐng)實(shí)現(xiàn)快速排序算法，并返回排序后的數(shù)組。要求：-輸入：`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]解析：快速排序通過(guò)分治思想將數(shù)組分為小于、等于、大于樞軸的三個(gè)部分，遞歸排序左半部分和右半部分。時(shí)間復(fù)雜度平均為O(nlogn)。1.2動(dòng)態(tài)規(guī)劃問(wèn)題（15分）題目：給定一個(gè)背包容量為`W`，以及n個(gè)物品，每個(gè)物品的重量為`weights`，價(jià)值為`values`。請(qǐng)計(jì)算背包能裝下的最大價(jià)值。要求：-輸入：`W=10`,`weights=[2,3,4,5]`,`values=[3,4,5,6]`-輸出：`7`（選擇物品2和物品3，價(jià)值4+5=9，但重量7>10，實(shí)際選物品1和物品4，價(jià)值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解析：動(dòng)態(tài)規(guī)劃通過(guò)構(gòu)建二維表`dp[i][w]`表示前i個(gè)物品在容量為w時(shí)的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程為：`dp[i][w]=max(dp[i-1][w],dp[i-1][w-weights[i-1]]+values[i-1])`。1.3字符串匹配問(wèn)題（20分）題目：給定文本串`text`和模式串`pattern`，請(qǐng)實(shí)現(xiàn)KMP算法，返回模式串在文本串中的起始索引（若有多個(gè)匹配，返回第一個(gè)）。要求：-輸入：`text="ABABDABACDABABCABAB"`,`pattern="ABABCABAB"`-輸出：`10`（"ABABCABAB"出現(xiàn)在文本的第10個(gè)字符處）參考答案：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算法通過(guò)計(jì)算最長(zhǎng)公共前后綴（LPS數(shù)組）避免重復(fù)比較，時(shí)間復(fù)雜度為O(n)。`compute_lps`函數(shù)用于生成LPS數(shù)組，匹配時(shí)若不匹配則跳轉(zhuǎn)至`lps[j-1]`繼續(xù)比較。2.數(shù)據(jù)結(jié)構(gòu)與圖論（4題，共60分）2.1鏈表操作（15分）題目：給定一個(gè)單鏈表，請(qǐng)實(shí)現(xiàn)反轉(zhuǎn)鏈表。要求：-輸入：`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構(gòu)建鏈表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解析：反轉(zhuǎn)鏈表通過(guò)迭代法實(shí)現(xiàn)，使用三個(gè)指針`prev`、`current`和`next_node`依次翻轉(zhuǎn)每個(gè)節(jié)點(diǎn)的指向。2.2棧的應(yīng)用（15分）題目：給定一個(gè)只包含`'('`,`')'`的字符串，請(qǐng)判斷是否為有效的括號(hào)序列。要求：-輸入：`"(()())"`-輸出：`True`參考答案：pythondefisValid(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstackprint(isValid("(()())"))#輸出：True解析：利用棧匹配括號(hào)，遍歷字符串時(shí)：1.遇到左括號(hào)入棧；2.遇到右括號(hào)時(shí)，棧頂應(yīng)為對(duì)應(yīng)左括號(hào)，否則無(wú)效；3.遍歷結(jié)束后棧為空則有效。2.3二叉樹遍歷（15分）題目：給定二叉樹，請(qǐng)實(shí)現(xiàn)中序遍歷（非遞歸）。要求：-輸入：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構(gòu)建二叉樹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解析：中序遍歷通過(guò)棧實(shí)現(xiàn)，依次遍歷左子樹、訪問(wèn)節(jié)點(diǎn)、遍歷右子樹。時(shí)間復(fù)雜度為O(n)。2.4圖的最短路徑（15分）題目：給定一個(gè)無(wú)向圖，請(qǐng)使用Dijkstra算法計(jì)算從起點(diǎn)`src`到終點(diǎn)`dest`的最短路徑。要求：-輸入：邊列表：[(0,1,2),(0,2,3),(1,2,1),(1,3,1),(2,3,4),(3,4,2)]起點(diǎn)src=0，終點(diǎn)dest=4-輸出：`4`（最短路徑長(zhǎng)度為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算法使用優(yōu)先隊(duì)列（小頂堆）維護(hù)當(dāng)前最短未訪問(wèn)節(jié)點(diǎn)，通過(guò)貪心策略不斷更新鄰接節(jié)點(diǎn)的距離。時(shí)間復(fù)雜度為O((E+V)logV)。3.系統(tǒng)設(shè)計(jì)與數(shù)據(jù)庫(kù)（5題，共90分）3.1數(shù)據(jù)庫(kù)查詢（20分）題目：假設(shè)有表`Students`（`id`,`name`,`age`,`class_id`）和`Classes`（`class_id`,`class_name`），請(qǐng)查詢年齡大于20且班級(jí)名稱為"CS101"的學(xué)生姓名。要求：-輸入：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';解析：通過(guò)`JOIN`連接`Students`和`Classes`表，使用`WHERE`子句過(guò)濾年齡和班級(jí)名稱，返回滿足條件的姓名。3.2SQL優(yōu)化（15分）題目：給定以下SQL查詢：sqlSELECTCOUNT()ASuser_countFROMOrdersWHEREorder_dateBETWEEN'2023-01-01'AND'2023-12-31'ANDstatus='Completed';請(qǐng)?zhí)岢鲋辽賰蓷l優(yōu)化建議。參考答案：1.為`order_date`和`status`列創(chuàng)建索引，加速范圍查詢和條件過(guò)濾。2.使用`EXPLAIN`分析查詢計(jì)劃，確保沒(méi)有全表掃描。3.若`Orders`表數(shù)據(jù)量大，可考慮分區(qū)表按日期分區(qū)。解析：索引可以顯著提升查詢性能，特別是多列組合索引。分區(qū)表可以減少數(shù)據(jù)掃描范圍。3.3分布式系統(tǒng)設(shè)計(jì)（20分）題目：設(shè)計(jì)一個(gè)高并發(fā)的短鏈接系統(tǒng)，要求：1.支持每天創(chuàng)建百萬(wàn)級(jí)短鏈接。2.系統(tǒng)可用性>99.9%。3.重定向速度<200ms。參考答案：1.短鏈接生成：使用62進(jìn)制哈希（如`1r7z8a9`）映射至UUID，存儲(chǔ)映射關(guān)系于Redis（主從復(fù)制+集群）。2.高可用：使用Nginx負(fù)載均衡多臺(tái)后端服務(wù)，后端服務(wù)集群部署（如Kubernetes）。3.緩存優(yōu)化：Redis緩存熱點(diǎn)短鏈接，TTL設(shè)為24小時(shí)，過(guò)期自動(dòng)清理。4.限流防攻擊：Nginx配置限流規(guī)則，后端IP黑名單過(guò)濾惡意請(qǐng)求。解析：短鏈接系統(tǒng)需解決高并發(fā)、快速重定向和分布式存儲(chǔ)問(wèn)題，結(jié)合緩存和負(fù)載均衡實(shí)現(xiàn)性能和可用性。3.4微服務(wù)架構(gòu)（20分）題目：設(shè)計(jì)一個(gè)電商平臺(tái)的訂單服務(wù)，要求：1.訂單創(chuàng)建支持事務(wù)性。2.支持訂單秒殺（10秒內(nèi)完成庫(kù)存鎖定）。3.異步通知優(yōu)惠券發(fā)放。參考答案：1.事務(wù)性：使用分布式事務(wù)（如2PC或TCC），訂單與庫(kù)存操作在一個(gè)分布式事務(wù)管理器（如Seata）下。2.秒殺：-庫(kù)存預(yù)減：RedisLua腳本原子扣減庫(kù)存。-超時(shí)回滾：使用Redis過(guò)期鍵實(shí)現(xiàn)自動(dòng)回滾