2025年csp认证考试题及答案

2025年csp认证考试题及答案第一题：字符统计与筛选（100分）问题描述：给定一个由小写字母组成的字符串$S$，长度不超过1000。要求统计字符串中每个字母出现的次数，并筛选出出现次数为偶数的字母，按字母表顺序输出这些字母及其出现次数。输入格式：输入仅一行，包含一个由小写字母组成的字符串$S$。输出格式：对于出现次数为偶数的字母，按字母表顺序每行输出一个字母及其出现次数，中间用一个空格分隔。如果没有出现次数为偶数的字母，则输出“None”。样例输入：```abacabad```样例输出：```b2d2```代码实现（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")```复杂度分析：时间复杂度：$O(n)$，其中$n$是字符串的长度。空间复杂度：$O(1)$，因为只使用了固定大小的数组。第二题：区间合并（100分）问题描述：给定$n$个区间$[l_i,r_i]$，其中$1\leql_i\leqr_i\leq10^9$。要求将这些区间进行合并，使得合并后的区间两两不相交，并且合并后的区间数量最少。输入格式：第一行包含一个整数$n$（$1\leqn\leq10^5$），表示区间的数量。接下来$n$行，每行包含两个整数$l_i$和$r_i$，表示一个区间。输出格式：输出合并后的区间，按区间左端点从小到大的顺序排列，每行输出一个区间的左端点和右端点，中间用一个空格分隔。样例输入：```31326810```样例输出：```16810```代码实现（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])```复杂度分析：时间复杂度：$O(n\logn)$，主要是排序的时间复杂度。空间复杂度：$O(n)$，用于存储合并后的区间。第三题：迷宫寻路（100分）问题描述：有一个$n\timesm$的迷宫，迷宫中包含空地（用'.'表示）、墙壁（用''表示）和起点（用'S'表示）、终点（用'E'表示）。你可以从起点出发，每次可以向上下左右四个方向移动一步，但不能穿过墙壁。要求计算从起点到终点的最短路径长度，如果无法到达终点，则输出-1。输入格式：第一行包含两个整数$n$和$m$（$1\leqn,m\leq100$），表示迷宫的行数和列数。接下来$n$行，每行包含$m$个字符，表示迷宫的布局。输出格式：输出从起点到终点的最短路径长度，如果无法到达终点，则输出-1。样例输入：```33S.......E```样例输出：```4```代码实现（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)```复杂度分析：时间复杂度：$O(nm)$，其中$n$和$m$分别是迷宫的行数和列数。空间复杂度：$O(nm)$，主要用于存储访问标记数组。第四题：树的遍历与重建（100分）问题描述：给定一棵二叉树的前序遍历序列和中序遍历序列，要求重建这棵二叉树，并输出该二叉树的后序遍历序列。输入格式：第一行包含一个整数$n$（$1\leqn\leq100$），表示二叉树的节点数量。第二行包含$n$个整数，表示二叉树的前序遍历序列。第三行包含$n$个整数，表示二叉树的中序遍历序列。输出格式：输出二叉树的后序遍历序列，整数之间用一个空格分隔。样例输入：```3123213```样例输出：```231```代码实现（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)))```复杂度分析：时间复杂度：$O(n)$，其中$n$是二叉树的节点数量。空间复杂度：$O(n)$，主要是递归调用栈的空间。第五题：动态规划之最长上升子序列（100分）问题描述：给定一个长度为$n$的整数序列$a_1,a_2,\cdots,a_n$，要求找出该序列的最长上升子序列的长度。输入格式：第一行包含一个整数$n$（$1\leqn\leq1000$），表示序列的长度。第二行包含$n$个整数$a_1,a_2,\cdots,a_n$。输出格式：输出最长上升子序列的长度。样例输入：```513254```样例输出：```3```代码实现（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))```复杂度分析：时间复杂度：$O(n^2)$，其中$n$是序列的长度。空间复杂度：$O(n)$，用于存储动态规划数组。第六题：图的最短路径（100分）问题描述：有一个包含$n$个节点和$m$条边的有向图，每条边都有一个正的权重。给定一个起点$s$和一个终点$t$，要求计算从起点到终点的最短路径长度。输入格式：第一行包含三个整数$n$、$m$、$s$和$t$（$1\leqn\leq1000$，$1\leqm\leq10^5$，$1\leqs,t\leqn$），分别表示节点数量、边的数量、起点和终点。接下来$m$行，每行包含三个整数$u$、$v$和$w$，表示从节点$u$到节点$v$有一条权重为$w$的边。输出格式：输出从起点到终点的最短路径长度，如果无法到达终点，则输出-1。样例输入：```3313121231133```样例输出：```2```代码实现（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