2025年CSP软件能力认证考试模拟试题及答案

2025年CSP软件能力认证考试模拟试题及答案第一部分CSP-J（入门级）考试说明考试时间：120分钟满分：100分编程语言限C++/Python，编程题需提交可运行代码一、单项选择题（每题2分，共30分）以下关于C++变量定义的语句中，语法正确的是（）A.int1a=5;B.float_b=3.14;C.doublec=1e-5.2;D.chard="A";答案：B解析：A选项变量名不能以数字开头；C选项科学计数法格式错误，指数部分不能含小数；D选项字符型变量需用单引号赋值，双引号用于字符串。已知数组inta[5]={1,2,3,4,5}，则a[3]的值为（）A.2B.3C.4D.5答案：C解析：C++数组下标从0开始，a[3]对应第四个元素4。以下哪种数据结构适合实现“先进先出”的操作逻辑？（）A.栈B.队列C.链表D.二叉树答案：B解析：队列的核心特性为“先进先出（FIFO）”，栈为“后进先出（LIFO）”，链表和二叉树无固定操作顺序。执行以下C++代码后，输出结果为（）#include<iostream>usingnamespacestd;intmain(){intx=10,y=3;cout<<x%y<<endl;return0;}A.1B.3C.10D.0答案：A解析：%为取余运算符，10除以3的余数为1。以下关于函数的描述中，错误的是（）A.函数可提高代码复用性B.函数必须有返回值C.函数可接受多个参数D.主函数main()是程序入口答案：B解析：函数可分为有返回值和无返回值（void类型）两种，无返回值的函数无需返回结果。已知boolflag=(3>5)&&(4<6)，则flag的值为（）A.trueB.falseC.1D.0答案：B解析：逻辑与&&运算中，只要有一个条件为假则结果为假，3>5为假，故整体结果为假。以下哪种排序算法的平均时间复杂度为O(n²)？（）A.快速排序B.归并排序C.冒泡排序D.堆排序答案：C解析：冒泡排序、插入排序等简单排序算法平均时间复杂度为O(n²)，快速排序、归并排序、堆排序的平均时间复杂度为O(nlogn)。执行以下Python代码后，输出结果为（）s="CSP2025"print(len(s[1:4]))A.3B.4C.5D.6答案：A解析：切片s[1:4]取索引1-3的字符（"SP2"），长度为3。二叉树的前序遍历顺序为“根-左-右”，已知某二叉树前序遍历结果为ABC，则该二叉树不可能的中序遍历结果是（）A.ABCB.BACC.CBAD.ACB答案：C解析：若前序为ABC，根节点为A。中序遍历CBA表示A的右子树为BC且无左子树，前序应先遍历A再遍历右子树BC，与前序ABC矛盾。以下关于循环结构的说法中，正确的是（）A.for循环只能用于已知循环次数的场景B.while循环不能实现无限循环C.do-while循环至少执行一次循环体D.循环嵌套的层数最多为3层答案：C解析：do-while循环先执行循环体再判断条件，故至少执行一次；for循环可通过条件控制实现未知次数循环，while循环可通过while(1)实现无限循环，循环嵌套层数无固定限制。已知inta=5，执行a+=3后，a的值为（）A.3B.5C.8D.15答案：C解析：a+=3等价于a=a+3，5+3=8。以下哪种不属于计算机中的基本数据类型？（）A.intB.stringC.floatD.bool答案：B解析：string（字符串）属于复合数据类型，int（整数）、float（浮点数）、bool（布尔）为基本数据类型。执行以下代码后，输出的i值为（）inti=0;while(i<5){i++;}cout<<i<<endl;A.4B.5C.6D.无限循环答案：B解析：循环执行5次，i依次变为1、2、3、4、5，此时不满足i<5，循环结束，输出5。以下关于数组的描述中，正确的是（）A.数组的大小在定义后可动态修改B.数组元素的类型必须一致C.数组下标可以为负数D.二维数组的行和列大小必须相同答案：B解析：数组大小定义后不可修改，下标从0开始且为非负数，二维数组行和列大小可不同，元素类型必须一致。以下哪种操作可实现对字符串的拼接？（）A.在C++中使用+运算符B.在Python中使用*运算符C.在C++中使用=运算符D.在Python中使用%运算符答案：A解析：C++中+可拼接字符串，Python中+也可拼接字符串，*用于重复字符串，%用于格式化字符串。二、阅读程序题（每题10分，共20分）（一）程序功能与输出分析#include<iostream>usingnamespacestd;intmain(){intn=6;intarr[6]={2,5,1,6,3,4};for(inti=0;i<n-1;i++){for(intj=0;j<n-1-i;j++){if(arr[j]>arr[j+1]){inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}for(intnum:arr){cout<<num<<"";}return0;}该程序采用的排序算法是_______。（4分）程序的输出结果为_______。（6分）答案：冒泡排序123456解析：程序通过双层循环实现冒泡排序，每次循环将未排序部分的最大元素“冒泡”到末尾，最终实现数组升序排列，输出排序后的数组元素。（二）程序功能与输出分析deffunc(n):ifn==1orn==2:return1else:returnfunc(n-1)+func(n-2)print(func(5))该函数的功能是计算_______。（4分）程序的输出结果为_______。（6分）答案：斐波那契数列的第n项（斐波那契数列定义：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)）5解析：函数采用递归方式实现斐波那契数列计算，func(5)=func(4)+func(3)=(func(3)+func(2))+(func(2)+func(1))=(2+1)+(1+1)=5。三、编程题（每题25分，共50分）（一）题目：计算数塔最大路径和问题描述：给定一个n行的数塔，从塔顶出发，每次只能向下或向右下移动，求经过的数字的最大和。输入格式：第一行输入正整数n（1≤n≤100），接下来n行，第i行输入i个整数（整数范围-100~100）。输出格式：输出最大路径和。示例输入：5738810274445265示例输出：30答案代码（C++）：#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intmain(){intn;cin>>n;vector<vector<int>>tower(n,vector<int>(n));//读取数塔数据for(inti=0;i<n;++i){for(intj=0;j<=i;++j){cin>>tower[i][j];}}//动态规划自底向上计算vector<vector<int>>dp(n,vector<int>(n));//初始化最底层for(intj=0;j<n;++j){dp[n-1][j]=tower[n-1][j];}//从倒数第二层向上计算for(inti=n-2;i>=0;--i){for(intj=0;j<=i;++j){dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+tower[i][j];}}cout<<dp[0][0]<<endl;return0;}答案代码（Python）：n=int(input())tower=[]foriinrange(n):row=list(map(int,input().split()))tower.append(row)#动态规划数组dp=[[0]*nfor_inrange(n)]#初始化底层forjinrange(n):dp[n-1][j]=tower[n-1][j]#自底向上计算foriinrange(n-2,-1,-1):forjinrange(i+1):dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+tower[i][j]print(dp[0][0])解析：采用动态规划思想，定义dp[i][j]为从第i行第j列到塔底的最大路径和。通过自底向上计算，避免重复计算子问题，时间复杂度O(n²)，空间复杂度O(n²)。（二）题目：统计单词出现次数问题描述：给定一个字符串（仅含字母、空格），统计其中每个单词出现的次数，单词区分大小写，按单词首字母升序输出结果。输入格式：输入一行字符串（长度≤1000）。输出格式：每行输出一个单词及其出现次数，格式为“单词：次数”。示例输入：HelloworldHelloCSPCSPCSP示例输出：CSP:3Hello:2world:1答案代码（Python）：#读取输入并分割单词s=input().strip()words=s.split()#统计单词次数word_count={}forwordinwords:ifwordinword_count:word_count[word]+=1else:word_count[word]=1#按单词首字母升序排序并输出sorted_words=sorted(word_count.items())forword,countinsorted_words:print(f"{word}:{count}")答案代码（C++）：#include<iostream>#include<string>#include<map>usingnamespacestd;intmain(){map<string,int>word_count;stringword;//读取单词（自动以空格分隔）while(cin>>word){word_count[word]++;}//遍历map输出（map默认按key升序排列）for(auto&pair:word_count){cout<<pair.first<<":"<<pair.second<<endl;}return0;}解析：利用Python的字典或C++的map存储单词与次数的映射关系，map可自动按单词升序排序，实现简单高效的统计与输出。第二部分CSP-S（提高级）考试说明考试时间：180分钟满分：100分编程语言限C++一、单项选择题（每题2分，共20分）以下关于STL容器的描述中，错误的是（）A.vector支持随机访问B.list的插入删除效率高C.map基于哈希表实现D.set中元素不重复答案：C解析：map基于红黑树（平衡二叉搜索树）实现，unordered_map基于哈希表实现。已知一棵完全二叉树有2025个节点，则该树的深度为（）A.10B.11C.12D.13答案：B解析：完全二叉树深度h满足2^(h-1)≤n<2^h，2^10=1024，2^11=2048，2025在[1024,2048)范围内，故深度为11。以下关于递归算法的说法中，正确的是（）A.递归算法的时间复杂度一定高于非递归算法B.递归算法必须有终止条件C.递归算法的空间复杂度一定为O(1)D.所有递归问题都不能用动态规划解决答案：B解析：递归算法需有终止条件避免无限递归；部分递归问题可通过记忆化搜索优化为动态规划，空间复杂度通常与递归深度相关。执行以下代码后，输出结果为（）#include<iostream>usingnamespacestd;intf(intx){staticinty=1;y+=x;returny;}intmain(){cout<<f(2)<<""<<f(3)<<endl;return0;}A.35B.36C.25D.23答案：B解析：static变量y仅初始化一次，生命周期贯穿程序。第一次调用f(2)，y=1+2=3；第二次调用f(3)，y=3+3=6。以下哪种排序算法是稳定排序？（）A.快速排序B.堆排序C.归并排序D.选择排序答案：C解析：归并排序、插入排序、冒泡排序为稳定排序，快速排序、堆排序、选择排序为不稳定排序。已知inta[4][5]，则a[2][3]的地址相对于数组首地址的偏移量为（）（假设int占4字节）A.36B.40C.44D.48答案：C解析：偏移量计算：(2*5+3)4=134=44字节。以下关于图的遍历的说法中，正确的是（）A.BFS适合求解最短路径问题B.DFS不需要使用栈或递归C.BFS只能用队列实现D.DFS遍历结果唯一答案：A解析：BFS（广度优先搜索）按层次遍历，适合求解无权图最短路径；DFS需用栈或递归实现，遍历结果因访问顺序不同可能不唯一。已知某算法的时间复杂度为O(nlogn)，当n扩大为原来的4倍时，算法执行时间大约扩大为原来的（）A.4倍B.8倍C.16倍D.4log4倍答案：B解析：原时间T1=Cnlogn，扩大后T2=C4nlog(4n)=C4n(log4+logn)≈4n2logn*C=8Cnlogn=8T1。以下关于指针的描述中，正确的是（）A.指针可以指向任意类型的数据B.空指针指向的地址为1C.指针变量的大小与指向的数据类型无关D.野指针不会导致程序错误答案：C解析：指针变量大小取决于系统位数（如32位系统占4字节，64位占8字节），与指向类型无关；空指针指向地址0，野指针可能导致程序崩溃。以下关于动态规划的说法中，错误的是（）A.动态规划可解决重叠子问题B.动态规划需满足最优子结构性质C.动态规划只能自底向上实现D.记忆化搜索是自顶向下的动态规划答案：C解析：动态规划有两种实现方式：自底向上（递推）和自顶向下（记忆化搜索）。二、阅读程序题（每题15分，共30分）（一）程序功能与输出分析#include<iostream>#include<vector>usingnamespacestd;intsolve(vector<int>&nums){intn=nums.size();if(n==0)return0;vector<int>dp(n,0);dp[0]=nums[0];intmax_sum=dp[0];for(inti=1;i<n;++i){dp[i]=max(nums[i],dp[i-1]+nums[i]);if(dp[i]>max_sum){max_sum=dp[i];}}returnmax_sum;}intmain(){vector<int>nums={-2,1,-3,4,-1,2,1,-5,4};cout<<solve(nums)<<endl;return0;}该程序解决的经典算法问题是_______。（5分）程序的输出结果为_______。（5分）若输入nums=[1,-2,3,4,-5]，输出结果为_______。（5分）答案：最大子数组和问题（Kadane算法）67解析：程序通过动态规划求解最大子数组和，dp[i]表示以第i个元素结尾的最大子数组和。示例1中最大子数组为[4,-1,2,1]，和为6；输入[1,-2,3,4,-5]中最大子数组为[3,4]，和为7。（二）程序功能与输出分析#include<iostream>#include<queue>#include<vector>usingnamespacestd;constintINF=1e9;vector<int>dijkstra(intn,vector<vector<pair<int,int>>>&adj,intstart){vector<int>dist(n,INF);dist[start]=0;priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;pq.push({0,start});while(!pq.empty()){intu=pq.top().second;intd=pq.top().first;pq.pop();if(d>dist[u])continue;for(auto&edge:adj[u]){intv=edge.first;intw=edge.second;if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;pq.push({dist[v],v});}}}returndist;}intmain(){intn=4,m=5;vector<vector<pair<int,int>>>adj(n);adj[0].push_back({1,2});adj[0].push_back({2,5});adj[1].push_back({2,1});adj[1].push_back({3,4});adj[2].push_back({3,1});vector<int>dist=dijkstra(n,adj,0);cout<<dist[3]<<endl;return0;}该程序实现的算法名称是_______，用于解决_______问题。（6分）程序的输出结果为_______。（4分）该算法的时间复杂度为_______（用堆优化后的复杂度）。（5分）答案：Dijkstra算法单源最短路径（带非负权边）4O(mlogn)（n为顶点数，m为边数）解析：程序实现堆优化的Dijkstra算法，计算从起点0到其他顶点的最短路径。起点0到3的最短路径为0→1→2→3，总权重2+1+1=4；堆优化后时间复杂度为O(mlogn)。三、编程题（每题25分，共50分）（一）题目：免费馅饼问题描述：有一条10米长的小路（坐标0-10），n个馅饼将在不同时间掉落在不同坐标。初始时人站在坐标5，每秒可移动1米，能接到所在位置及左右1米范围内的所有馅饼。求最多能接到的馅饼数。输入格式：第一行输入n（1≤n≤1000），接下来n行每行输入x（0≤x≤10）和T（1≤T≤1000），表示第T秒馅饼掉落在x处。输出格式：输出最多接到的馅饼数。示例输入：6514161727383示例输出：4答案代码：#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;constintMAX_T=1001;constintMAX_X=11;intmain(){intn;cin>>n;vector<vector<int>>pies(MAX_T,vector<int>(MAX_X,0));intmax_T=0;for(inti=0;i<n;++i){intx,T;cin>>x>>T;pies[T][x]++;if(T>max_T)max_T=T;}//dp[T][x]表示第T秒在x位置最多接到的馅饼数vector<vector<int>>dp(MAX_T,vector<int>(MAX_X,0));//初始化第0秒（初始位置5，未接馅饼）dp[0][5]=0;for(intT=1;T<=max_T;++T){for(intx=0;x<=10;++x){//上一秒可能的位置：x-1,x,x+1（需在0-10范围内）intmax_prev=0;for(intdx=-1;dx<=1;++dx){intprev_x=x+dx;if(prev_x>=0&&prev_x<=10){if(dp[T-1][prev_x]>max_prev){max_prev=dp[T-1][prev_x];}}}dp[T][x]=max_prev+pies[T][x];}}//找所有时间点的最大值intans=0;for(intx=0;x<=10;++x){if(dp[max_T][x]>ans){ans=dp[max_T][x];}}cout<<ans<<endl;return0;}解析：采用动态规划，定义dp[T][x]为第T秒在x位置接到的最大馅饼数。状态转移时考虑上一秒可到达当前位置的三个可能坐标（x-1、x、x+1），取最大值累加当前位置馅饼数。时间复杂度O(MAX_T*MAX_X)，满足题目约束。（二）题目：区间覆盖问题问题描述：给定一个长度为L的线段（起点0，终点L）和n个区间，每个区间有起点s_i、终点e_i和成本c_i。选择若干区间，使它们能完全覆盖线段[0,L]，且总成本最小。输入格式：第一行输入n和L（1≤n≤1000，1≤L≤10000），接下来n行输入s_i、e_i、c_i（0≤s_i≤e_i≤L，1≤c_i≤1000）。输出格式：输出最小总成本，若无法覆盖则输出-1。示例输入：4100352534746102示例输出：10（选择区间0-3、2-5、4-7、6-10，