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選項變量名不能以數(shù)字開頭；C選項科學計數(shù)法格式錯誤，指數(shù)部分不能含小數(shù)；D選項字符型變量需用單引號賦值，雙引號用于字符串。已知數(shù)組inta[5]={1,2,3,4,5}，則a[3]的值為（）A.2B.3C.4D.5答案：C解析：C++數(shù)組下標從0開始，a[3]對應第四個元素4。以下哪種數(shù)據(jù)結構適合實現(xiàn)“先進先出”的操作邏輯？（）A.棧B.隊列C.鏈表D.二叉樹答案：B解析：隊列的核心特性為“先進先出（FIFO）”，棧為“后進先出（LIFO）”，鏈表和二叉樹無固定操作順序。執(zhí)行以下C++代碼后，輸出結果為（）#include<iostream>usingnamespacestd;intmain(){intx=10,y=3;cout<<x%y<<endl;return0;}A.1B.3C.10D.0答案：A解析：%為取余運算符，10除以3的余數(shù)為1。以下關于函數(shù)的描述中，錯誤的是（）A.函數(shù)可提高代碼復用性B.函數(shù)必須有返回值C.函數(shù)可接受多個參數(shù)D.主函數(shù)main()是程序入口答案：B解析：函數(shù)可分為有返回值和無返回值（void類型）兩種，無返回值的函數(shù)無需返回結果。已知boolflag=(3>5)&&(4<6)，則flag的值為（）A.trueB.falseC.1D.0答案：B解析：邏輯與&&運算中，只要有一個條件為假則結果為假，3>5為假，故整體結果為假。以下哪種排序算法的平均時間復雜度為O(n2)？（）A.快速排序B.歸并排序C.冒泡排序D.堆排序答案：C解析：冒泡排序、插入排序等簡單排序算法平均時間復雜度為O(n2)，快速排序、歸并排序、堆排序的平均時間復雜度為O(nlogn)。執(zhí)行以下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，根節(jié)點為A。中序遍歷CBA表示A的右子樹為BC且無左子樹，前序應先遍歷A再遍歷右子樹BC，與前序ABC矛盾。以下關于循環(huán)結構的說法中，正確的是（）A.for循環(huán)只能用于已知循環(huán)次數(shù)的場景B.while循環(huán)不能實現(xiàn)無限循環(huán)C.do-while循環(huán)至少執(zhí)行一次循環(huán)體D.循環(huán)嵌套的層數(shù)最多為3層答案：C解析：do-while循環(huán)先執(zhí)行循環(huán)體再判斷條件，故至少執(zhí)行一次；for循環(huán)可通過條件控制實現(xiàn)未知次數(shù)循環(huán)，while循環(huán)可通過while(1)實現(xiàn)無限循環(huán)，循環(huán)嵌套層數(shù)無固定限制。已知inta=5，執(zhí)行a+=3后，a的值為（）A.3B.5C.8D.15答案：C解析：a+=3等價于a=a+3，5+3=8。以下哪種不屬于計算機中的基本數(shù)據(jù)類型？（）A.intB.stringC.floatD.bool答案：B解析：string（字符串）屬于復合數(shù)據(jù)類型，int（整數(shù)）、float（浮點數(shù)）、bool（布爾）為基本數(shù)據(jù)類型。執(zhí)行以下代碼后，輸出的i值為（）inti=0;while(i<5){i++;}cout<<i<<endl;A.4B.5C.6D.無限循環(huán)答案：B解析：循環(huán)執(zhí)行5次，i依次變?yōu)?、2、3、4、5，此時不滿足i<5，循環(huán)結束，輸出5。以下關于數(shù)組的描述中，正確的是（）A.數(shù)組的大小在定義后可動態(tài)修改B.數(shù)組元素的類型必須一致C.數(shù)組下標可以為負數(shù)D.二維數(shù)組的行和列大小必須相同答案：B解析：數(shù)組大小定義后不可修改，下標從0開始且為非負數(shù)，二維數(shù)組行和列大小可不同，元素類型必須一致。以下哪種操作可實現(xiàn)對字符串的拼接？（）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解析：程序通過雙層循環(huán)實現(xiàn)冒泡排序，每次循環(huán)將未排序部分的最大元素“冒泡”到末尾，最終實現(xiàn)數(shù)組升序排列，輸出排序后的數(shù)組元素。（二）程序功能與輸出分析deffunc(n):ifn==1orn==2:return1else:returnfunc(n-1)+func(n-2)print(func(5))該函數(shù)的功能是計算_______。（4分）程序的輸出結果為_______。（6分）答案：斐波那契數(shù)列的第n項（斐波那契數(shù)列定義：F(1)=1，F(xiàn)(2)=1，F(xiàn)(n)=F(n-1)+F(n-2)）5解析：函數(shù)采用遞歸方式實現(xiàn)斐波那契數(shù)列計算，func(5)=func(4)+func(3)=(func(3)+func(2))+(func(2)+func(1))=(2+1)+(1+1)=5。三、編程題（每題25分，共50分）（一）題目：計算數(shù)塔最大路徑和問題描述：給定一個n行的數(shù)塔，從塔頂出發(fā)，每次只能向下或向右下移動，求經(jīng)過的數(shù)字的最大和。輸入格式：第一行輸入正整數(shù)n（1≤n≤100），接下來n行，第i行輸入i個整數(shù)（整數(shù)范圍-100~100）。輸出格式：輸出最大路徑和。示例輸入：5738810274445265示例輸出：30答案代碼（C++）：#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intmain(){intn;cin>>n;vector<vector<int>>tower(n,vector<int>(n));//讀取數(shù)塔數(shù)據(jù)for(inti=0;i<n;++i){for(intj=0;j<=i;++j){cin>>tower[i][j];}}//動態(tài)規(guī)劃自底向上計算vector<vector<int>>dp(n,vector<int>(n));//初始化最底層for(intj=0;j<n;++j){dp[n-1][j]=tower[n-1][j];}//從倒數(shù)第二層向上計算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)#動態(tài)規(guī)劃數(shù)組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])解析：采用動態(tài)規(guī)劃思想，定義dp[i][j]為從第i行第j列到塔底的最大路徑和。通過自底向上計算，避免重復計算子問題，時間復雜度O(n2)，空間復雜度O(n2)。（二）題目：統(tǒng)計單詞出現(xiàn)次數(shù)問題描述：給定一個字符串（僅含字母、空格），統(tǒng)計其中每個單詞出現(xiàn)的次數(shù)，單詞區(qū)分大小寫，按單詞首字母升序輸出結果。輸入格式：輸入一行字符串（長度≤1000）。輸出格式：每行輸出一個單詞及其出現(xiàn)次數(shù)，格式為“單詞：次數(shù)”。示例輸入：HelloworldHelloCSPCSPCSP示例輸出：CSP:3Hello:2world:1答案代碼（Python）：#讀取輸入并分割單詞s=input().strip()words=s.split()#統(tǒng)計單詞次數(shù)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存儲單詞與次數(shù)的映射關系，map可自動按單詞升序排序，實現(xiàn)簡單高效的統(tǒng)計與輸出。第二部分CSP-S（提高級）考試說明考試時間：180分鐘滿分：100分編程語言限C++一、單項選擇題（每題2分，共20分）以下關于STL容器的描述中，錯誤的是（）A.vector支持隨機訪問B.list的插入刪除效率高C.map基于哈希表實現(xiàn)D.set中元素不重復答案：C解析：map基于紅黑樹（平衡二叉搜索樹）實現(xiàn)，unordered_map基于哈希表實現(xiàn)。已知一棵完全二叉樹有2025個節(jié)點，則該樹的深度為（）A.10B.11C.12D.13答案：B解析：完全二叉樹深度h滿足2^(h-1)≤n<2^h，2^10=1024，2^11=2048，2025在[1024,2048)范圍內(nèi)，故深度為11。以下關于遞歸算法的說法中，正確的是（）A.遞歸算法的時間復雜度一定高于非遞歸算法B.遞歸算法必須有終止條件C.遞歸算法的空間復雜度一定為O(1)D.所有遞歸問題都不能用動態(tài)規(guī)劃解決答案：B解析：遞歸算法需有終止條件避免無限遞歸；部分遞歸問題可通過記憶化搜索優(yōu)化為動態(tài)規(guī)劃，空間復雜度通常與遞歸深度相關。執(zhí)行以下代碼后，輸出結果為（）#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僅初始化一次，生命周期貫穿程序。第一次調(diào)用f(2)，y=1+2=3；第二次調(diào)用f(3)，y=3+3=6。以下哪種排序算法是穩(wěn)定排序？（）A.快速排序B.堆排序C.歸并排序D.選擇排序答案：C解析：歸并排序、插入排序、冒泡排序為穩(wěn)定排序，快速排序、堆排序、選擇排序為不穩(wěn)定排序。已知inta[4][5]，則a[2][3]的地址相對于數(shù)組首地址的偏移量為（）（假設int占4字節(jié)）A.36B.40C.44D.48答案：C解析：偏移量計算：(2*5+3)4=134=44字節(jié)。以下關于圖的遍歷的說法中，正確的是（）A.BFS適合求解最短路徑問題B.DFS不需要使用棧或遞歸C.BFS只能用隊列實現(xiàn)D.DFS遍歷結果唯一答案：A解析：BFS（廣度優(yōu)先搜索）按層次遍歷，適合求解無權圖最短路徑；DFS需用?；蜻f歸實現(xiàn)，遍歷結果因訪問順序不同可能不唯一。已知某算法的時間復雜度為O(nlogn)，當n擴大為原來的4倍時，算法執(zhí)行時間大約擴大為原來的（）A.4倍B.8倍C.16倍D.4log4倍答案：B解析：原時間T1=Cnlogn，擴大后T2=C4nlog(4n)=C4n(log4+logn)≈4n2logn*C=8Cnlogn=8T1。以下關于指針的描述中，正確的是（）A.指針可以指向任意類型的數(shù)據(jù)B.空指針指向的地址為1C.指針變量的大小與指向的數(shù)據(jù)類型無關D.野指針不會導致程序錯誤答案：C解析：指針變量大小取決于系統(tǒng)位數(shù)（如32位系統(tǒng)占4字節(jié)，64位占8字節(jié)），與指向類型無關；空指針指向地址0，野指針可能導致程序崩潰。以下關于動態(tài)規(guī)劃的說法中，錯誤的是（）A.動態(tài)規(guī)劃可解決重疊子問題B.動態(tài)規(guī)劃需滿足最優(yōu)子結構性質C.動態(tài)規(guī)劃只能自底向上實現(xiàn)D.記憶化搜索是自頂向下的動態(tài)規(guī)劃答案：C解析：動態(tài)規(guī)劃有兩種實現(xiàn)方式：自底向上（遞推）和自頂向下（記憶化搜索）。二、閱讀程序題（每題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;}該程序解決的經(jīng)典算法問題是_______。（5分）程序的輸出結果為_______。（5分）若輸入nums=[1,-2,3,4,-5]，輸出結果為_______。（5分）答案：最大子數(shù)組和問題（Kadane算法）67解析：程序通過動態(tài)規(guī)劃求解最大子數(shù)組和，dp[i]表示以第i個元素結尾的最大子數(shù)組和。示例1中最大子數(shù)組為[4,-1,2,1]，和為6；輸入[1,-2,3,4,-5]中最大子數(shù)組為[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;}該程序實現(xiàn)的算法名稱是_______，用于解決_______問題。（6分）程序的輸出結果為_______。（4分）該算法的時間復雜度為_______（用堆優(yōu)化后的復雜度）。（5分）答案：Dijkstra算法單源最短路徑（帶非負權邊）4O(mlogn)（n為頂點數(shù)，m為邊數(shù)）解析：程序實現(xiàn)堆優(yōu)化的Dijkstra算法，計算從起點0到其他頂點的最短路徑。起點0到3的最短路徑為0→1→2→3，總權重2+1+1=4；堆優(yōu)化后時間復雜度為O(mlogn)。三、編程題（每題25分，共50分）（一）題目：免費餡餅問題描述：有一條10米長的小路（坐標0-10），n個餡餅將在不同時間掉落在不同坐標。初始時人站在坐標5，每秒可移動1米，能接到所在位置及左右1米范圍內(nèi)的所有餡餅。求最多能接到的餡餅數(shù)。輸入格式：第一行輸入n（1≤n≤1000），接下來n行每行輸入x（0≤x≤10）和T（1≤T≤1000），表示第T秒餡餅掉落在x處。輸出格式：輸出最多接到的餡餅數(shù)。示例輸入：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位置最多接到的餡餅數(shù)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范圍內(nèi)）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;}解析：采用動態(tài)規(guī)劃，定義dp[T][x]為第T秒在x位置接到的最大餡餅數(shù)。狀態(tài)轉移時考慮上一秒可到達當前位置的三個可能坐標（x-1、x、x+1），取最大值累加當前位置餡餅數(shù)。時間復雜度O(MAX_T*MAX_X)，滿足題目約束。（二）題目：區(qū)間覆蓋問題問題描述：給定一個長度為L的線段（起點0，終點L）和n個區(qū)間，每個區(qū)間有起點s_i、終點e_i和成本c_i。選擇若干區(qū)間，使它們能完全覆蓋線段[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（選擇區(qū)間0-3、2-5、4-7、6-10，