2025年csp認證考試題及答案第一題：字符統(tǒng)計與篩選（100分）問題描述：給定一個由小寫字母組成的字符串$S$，長度不超過1000。要求統(tǒng)計字符串中每個字母出現(xiàn)的次數(shù)，并篩選出出現(xiàn)次數(shù)為偶數(shù)的字母，按字母表順序輸出這些字母及其出現(xiàn)次數(shù)。輸入格式：輸入僅一行，包含一個由小寫字母組成的字符串$S$。輸出格式：對于出現(xiàn)次數(shù)為偶數(shù)的字母，按字母表順序每行輸出一個字母及其出現(xiàn)次數(shù)，中間用一個空格分隔。如果沒有出現(xiàn)次數(shù)為偶數(shù)的字母，則輸出“None”。樣例輸入：```abacabad```樣例輸出：```b2d2```代碼實現(xiàn)（Python）：```pythons=input()count=[0]26forcharins:index=ord(char)ord('a')count[index]+=1has_even=Falseforiinrange(26):ifcount[i]%2==0andcount[i]>0:print(chr(i+ord('a')),count[i])has_even=Trueifnothas_even:print("None")```復(fù)雜度分析：時間復(fù)雜度：$O(n)$，其中$n$是字符串的長度?？臻g復(fù)雜度：$O(1)$，因為只使用了固定大小的數(shù)組。第二題：區(qū)間合并（100分）問題描述：給定$n$個區(qū)間$[l_i,r_i]$，其中$1\leql_i\leqr_i\leq10^9$。要求將這些區(qū)間進行合并，使得合并后的區(qū)間兩兩不相交，并且合并后的區(qū)間數(shù)量最少。輸入格式：第一行包含一個整數(shù)$n$（$1\leqn\leq10^5$），表示區(qū)間的數(shù)量。接下來$n$行，每行包含兩個整數(shù)$l_i$和$r_i$，表示一個區(qū)間。輸出格式：輸出合并后的區(qū)間，按區(qū)間左端點從小到大的順序排列，每行輸出一個區(qū)間的左端點和右端點，中間用一個空格分隔。樣例輸入：```31326810```樣例輸出：```16810```代碼實現(xiàn)（Python）：```pythonn=int(input())intervals=[]for_inrange(n):l,r=map(int,input().split())intervals.append((l,r))intervals.sort()merged=[]forintervalinintervals:ifnotmergedormerged[-1][1]<interval[0]:merged.append(interval)else:merged[-1]=(merged[-1][0],max(merged[-1][1],interval[1]))forintervalinmerged:print(interval[0],interval[1])```復(fù)雜度分析：時間復(fù)雜度：$O(n\logn)$，主要是排序的時間復(fù)雜度?？臻g復(fù)雜度：$O(n)$，用于存儲合并后的區(qū)間。第三題：迷宮尋路（100分）問題描述：有一個$n\timesm$的迷宮，迷宮中包含空地（用'.'表示）、墻壁（用''表示）和起點（用'S'表示）、終點（用'E'表示）。你可以從起點出發(fā)，每次可以向上下左右四個方向移動一步，但不能穿過墻壁。要求計算從起點到終點的最短路徑長度，如果無法到達終點，則輸出-1。輸入格式：第一行包含兩個整數(shù)$n$和$m$（$1\leqn,m\leq100$），表示迷宮的行數(shù)和列數(shù)。接下來$n$行，每行包含$m$個字符，表示迷宮的布局。輸出格式：輸出從起點到終點的最短路徑長度，如果無法到達終點，則輸出-1。樣例輸入：```33S.......E```樣例輸出：```4```代碼實現(xiàn)（Python）：```pythonfromcollectionsimportdequen,m=map(int,input().split())maze=[]for_inrange(n):maze.append(input())start=Noneend=Noneforiinrange(n):forjinrange(m):ifmaze[i][j]=='S':start=(i,j)elifmaze[i][j]=='E':end=(i,j)directions=[(-1,0),(1,0),(0,-1),(0,1)]visited=[[False]mfor_inrange(n)]queue=deque([(start[0],start[1],0)])visited[start[0]][start[1]]=Truewhilequeue:x,y,dist=queue.popleft()if(x,y)==end:print(dist)breakfordx,dyindirections:new_x,new_y=x+dx,y+dyif0<=new_x<nand0<=new_y<mandmaze[new_x][new_y]!=''andnotvisited[new_x][new_y]:queue.append((new_x,new_y,dist+1))visited[new_x][new_y]=Trueelse:print(-1)```復(fù)雜度分析：時間復(fù)雜度：$O(nm)$，其中$n$和$m$分別是迷宮的行數(shù)和列數(shù)。空間復(fù)雜度：$O(nm)$，主要用于存儲訪問標記數(shù)組。第四題：樹的遍歷與重建（100分）問題描述：給定一棵二叉樹的前序遍歷序列和中序遍歷序列，要求重建這棵二叉樹，并輸出該二叉樹的后序遍歷序列。輸入格式：第一行包含一個整數(shù)$n$（$1\leqn\leq100$），表示二叉樹的節(jié)點數(shù)量。第二行包含$n$個整數(shù)，表示二叉樹的前序遍歷序列。第三行包含$n$個整數(shù)，表示二叉樹的中序遍歷序列。輸出格式：輸出二叉樹的后序遍歷序列，整數(shù)之間用一個空格分隔。樣例輸入：```3123213```樣例輸出：```231```代碼實現(xiàn)（Python）：```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefbuildTree(preorder,inorder):ifnotpreorderornotinorder:returnNoneroot_val=preorder[0]root=TreeNode(root_val)inorder_index=inorder.index(root_val)root.left=buildTree(preorder[1:inorder_index+1],inorder[:inorder_index])root.right=buildTree(preorder[inorder_index+1:],inorder[inorder_index+1:])returnrootdefpostorderTraversal(root):result=[]defhelper(node):ifnode:helper(node.left)helper(node.right)result.append(node.val)helper(root)returnresultn=int(input())preorder=list(map(int,input().split()))inorder=list(map(int,input().split()))root=buildTree(preorder,inorder)postorder=postorderTraversal(root)print("".join(map(str,postorder)))```復(fù)雜度分析：時間復(fù)雜度：$O(n)$，其中$n$是二叉樹的節(jié)點數(shù)量?？臻g復(fù)雜度：$O(n)$，主要是遞歸調(diào)用棧的空間。第五題：動態(tài)規(guī)劃之最長上升子序列（100分）問題描述：給定一個長度為$n$的整數(shù)序列$a_1,a_2,\cdots,a_n$，要求找出該序列的最長上升子序列的長度。輸入格式：第一行包含一個整數(shù)$n$（$1\leqn\leq1000$），表示序列的長度。第二行包含$n$個整數(shù)$a_1,a_2,\cdots,a_n$。輸出格式：輸出最長上升子序列的長度。樣例輸入：```513254```樣例輸出：```3```代碼實現(xiàn)（Python）：```pythonn=int(input())nums=list(map(int,input().split()))dp=[1]nforiinrange(1,n):forjinrange(i):ifnums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1)print(max(dp))```復(fù)雜度分析：時間復(fù)雜度：$O(n^2)$，其中$n$是序列的長度?？臻g復(fù)雜度：$O(n)$，用于存儲動態(tài)規(guī)劃數(shù)組。第六題：圖的最短路徑（100分）問題描述：有一個包含$n$個節(jié)點和$m$條邊的有向圖，每條邊都有一個正的權(quán)重。給定一個起點$s$和一個終點$t$，要求計算從起點到終點的最短路徑長度。輸入格式：第一行包含三個整數(shù)$n$、$m$、$s$和$t$（$1\leqn\leq1000$，$1\leqm\leq10^5$，$1\leqs,t\leqn$），分別表示節(jié)點數(shù)量、邊的數(shù)量、起點和終點。接下來$m$行，每行包含三個整數(shù)$u$、$v$和$w$，表示從節(jié)點$u$到節(jié)點$v$有一條權(quán)重為$w$的邊。輸出格式：輸出從起點到終點的最短路徑長度，如果無法到達終點，則輸出-1。樣例輸入：```3313121231133```樣例輸出：```2```代碼實現(xiàn)（Python）：```pythonimportheapqfromcollectionsimportdefaultdictn,m,s,t=map(int,input().split())graph=defaultdict(list)for_inrange(m):u,v,w=map(int,input().split())graph[u].append((v,w))dist=[float('inf')](n+1)dist[s]=0pq=[(0,s)]whilepq:d,node=heapq.heappop(pq)ifd>dist[node]:continueifnode==t:print(d)breakforneighbor,weightin