2025年CSP-S提高级(第一轮)C++真题(含答案)

2025年CSP-S提高级(第一轮)C++真题(含答案)一、单选题。1.有5个红色球和5个蓝色球，除颜色外完全相同，将10个球排成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法？（）。A.25B.30C.6D.120标准答案：C。2.在KMP算法中，对于模式串P='abacaba'，其next数组（next[i]定义为模式串P[0…i]最长公共前后缀的长度，且数组下标从0开始）的值是什么？（）。A.{0,0,1,0,1,2,3}B.{0,1,2,3,4,5,6}C.{0,0,1,1,2,2,3}D.{0,0,0,0,1,2,3}标准答案：A。3.对一个大小为16（下标0-15）的数组构建满线段树，查询区间[3,11]时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？（）。A.7B.8C.9D.10标准答案：B。4.将字符串“cat”“car”“cart”“case”“dog”“do”插入一个空的Trie树（前缀树）中，构建完成的Trie树（包括根节点）共有多少个结点？（）。A.8B.9C.10D.11标准答案：D。5.对于一个包含n个结点和m条边的有向无环图（DAG），其拓扑排序的结果有多少种可能？（）。A.只有1种B.最多n种C.等于n-m种D.以上都不对标准答案：D。6.在一个大小为13的哈希表中，使用闭散列法的线性探查来解决冲突，哈希函数为H(key)=keymod13，依次插入关键字18、26、35、9、68、74，插入74后，它最终被放置在哪个索引位置？（）。A.5B.7C.9D.11标准答案：D。7.一个包含8个顶点的完全图（顶点编号1到8），任意两点之间的边权重等于两顶点编号的差的绝对值，该图的最小生成树总权重是多少？（）。A.7B.8C.9D.10标准答案：A。8.如果一棵二叉搜索树的后序遍历序列是2,5,4,8,12,10,6，那么该树的前序遍历是什么？（）。A.6,4,2,5,10,8,12B.6,4,5,2,10,12,8C.2,4,5,6,8,10,12D.12,8,10,5,2,4,6标准答案：A。9.一个0-1背包问题，背包容量为20，现有5个物品，重量和价值分别为7,5,4,3,6和15,12,9,7,13，装入背包的物品能获得的最大总价值是多少？（）。A.43B.41C.45D.44标准答案：D。10.在一棵以结点1为根的树中，结点12和结点18的最近公共祖先（LCA）是结点4，下列哪个结点的LCA组合是不可能出现的？（）。A.LCA(12,4)=4B.LCA(18,4)=4C.LCA(12,18,4)=4D.LCA(12,1)=4标准答案：D。11.递归关系式T(n)=2T(n/2)+O(n²)描述了某个分治算法的时间复杂度，该算法的时间复杂度是多少？（）。A.O(n)B.O(nlogn)C.O(n2)D.O(n2logn)标准答案：C。12.在一个初始为空的最小堆（min-heap）中，依次插入元素20,12,15,8,10,5，然后连续执行两次“删除最小值”（delete-min）操作，此时堆顶元素是什么？（）。A.10B.12C.15D.20标准答案：A。13.题1到1000之间，不能被2、3、5中任意一个数整除的整数有多少个？（）。A.266B.267C.333D.734标准答案：A。14.斐波那契数列定义为F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)，使用朴素递归方法计算F(n)的时间复杂度是指数级的，而使用动态规划（或迭代）方法的时间复杂度是线性的，造成这种差异的根本原因是？（）。A.递归函数调用栈开销过大B.操作系统对递归深度有限制C.朴素递归中存在大量的重叠子问题未被重复利用D.动态规划使用了更少的数据存储空间标准答案：C。15.有5个独立的、不可抢占的任务A1,A2,A3,A4,A5需在一台机器上执行（从时间0开始），每个任务有处理时长和截止时刻（原文部分数据表述可能存在排版问题），为使总惩罚最小，应选择哪个任务作为第一个执行任务？（）。A.处理时间最短的任务A5B.截止时间最早的任务A3C.处理时间最长的任务A4D.任意一个任务都可以标准答案：B。二、组合题（阅读程序）。阅读程序（一）。16-21题组合题。1#include<algorithm>2#include<cstdio>3#include<cstring>4boolflag[27];5intn;6intp[27];7intans=0;8voiddfs(intk){9if(k==n+1){10++ans;11return;12}13for(inti=1;i<=n;++i){14if(flag[i])continue;15if(k>1&&i==p[k-1]+1)continue;16p[k]=i;17flag[i]=true;18dfs(k+1);19flag[i]=false;20}21return;22}23intmain(){24scanf("%d",&n);25dfs(1);26printf("%d\n",ans);27return0;28}16.当输入的n=3的时候，程序输出的答案为3。（）。A.正确B.错误标准答案：A。17.在dfs函数运行过程中，k的取值会满足1≤k≤n+1。（）。A.正确B.错误标准答案：A。18.删除第19行的“flag[i]=false;”，对答案不会产生影响。（）。A.正确B.错误标准答案：B。19.当输入的n=4的时候，程序输出的答案为？（）。A.11B.12C.24D.9标准答案：A。20.如果因为某些问题，导致程序运行第25行的dfs函数之前，数组p的初值并不全为0，则对程序的影响是？（）。A.输出的答案比原答案要小B.无法确定输出的答案C.程序可能陷入死循环D.没有影响标准答案：D。21.假如删去第14行的“if(flag[i])continue;”，输入3，得到的输出答案是？（）。A.27B.3C.16D.12标准答案：C。阅读程序（二）。22-27题组合题。include<algorithm>include<cstdio>include<cstring>definelllonglongintcnt_broken=0;intcnt_check=0;intn,k;inlineboolcheck(inth){printf("nowcheck:%d\n",h);++cnt_check;if(cnt_broken==2){printf("Youhavenoegg!\n");returnfalse;}if(h>=k){++cnt_broken;returntrue;}else{returnfalse;}}inlineboolassert_ans(inth){if(h==k){printf("YouareRightusing%dchecks\n",cnt_check);returntrue;}else{printf("Wronganswer!\n");returnfalse;}}inlinevoidguess1(intn){for(inti=1;i<=n;++i){if(check(i)){assert_ans(i);return;}}}inlinevoidguess2(intn){intw=1;while(w*(w+1)/2<n){++w;}intti=w;intnh=0;while(true){nh+=ti;if(nh>n){nh=n;}if(check(nh)){for(intj=nhti+1;j<nh;++j){if(check(j)){assert_ans(j);return;}}assert_ans(nh);return;}--ti;if(ti==0){assert_ans(n);return;}}}intmain(){scanf("%d%d",&n,&k);intt;scanf("%d",&t);if(t==1){guess1(n);}else{guess2(n);}return0;}22.当输入为“651”时，猜测次数为5；当输入“652”时，猜测次数为3。（）。A.正确B.错误标准答案：A。23.不管输入的n和k具体为多少，t=2时的猜测数总是小于等于t=1时的猜测数。（）。A.正确B.错误标准答案：B。24.不管t=1或t=2，程序都一定会猜到正确结果。（）。A.正确B.错误标准答案：A。25.函数guess1在运行过程中，cnt_broken的值最多为？（）。A.0B.1C.2D.n标准答案：B。26.函数guess2在运行过程中，最多使用的猜测次数的量级为？（）。A.O(n)B.O(n²)C.O(√n)D.O(logn)标准答案：C。27.当输入的n=100的时候，代码中t=1和t=2分别需要的猜测次数最多分别为？（）。A.100,14B.100,13C.99,14D.99,13标准答案：A。阅读程序（三）。28-33题组合题。1#include<algorithm>2#include<cstdio>3#include<cstring>4#include<vector>5#definelllonglong6intn,m;7std::vector<int>k,p;8inlineintmpow(intx,intk){9intans=1;10for(;k;k=k>>1,x=x*x){11if(k&1){12ans=ans*x;13}14}15returnans;16}17std::vector<int>ans1,ans2;18intcnt1,cnt2;19inlinevoiddfs(std::vector<int>&ans,int&cnt,intl,intr,intv){20if(l>r){21++cnt;22ans.push_back(v);23return;24}25for(inti=1;i<=m;++i){26dfs(ans,cnt,l+1,r,v+k[l]*mpow(i,p[l]));27}28return;29}30std::vector<int>cntans1;31intmain(){32scanf("%d%d",&n,&m);33k.resize(n+1);34p.resize(n+1);35for(inti=1;i<=n;++i){36scanf("%d%d",&k[i],&p[i]);37}38dfs(ans1,cnt1,1,n>>1,0);39dfs(ans2,cnt2,(n>>1)+1,n,0);40std::sort(ans1.begin(),ans1.end());41intnewcnt1=1;42cntans1.push_back(1);43for(inti=1;i<cnt1;++i){44if(ans1[i]==ans1[newcnt1-1]){45++cntans1[newcnt1-1];46}else{47ans1[newcnt1++]=ans1[i];48cntans1.push_back(1);49}50}51cnt1=newcnt1;52std::sort(ans2.begin(),ans2.end());53intlas=0;54llans=0;55for(inti=cnt2-1;i>=0;--i){56while(las<cnt1&&ans1[las]+ans2[i]<0){57++las;58}59if(las<cnt1&&ans1[las]+ans2[i]==0){60ans+=cntans1[las];61}62}63printf("%lld\n",ans);64return0;65}28.删除第52行的“std::sort(ans2.begin(),ans2.end());”后，输出的结果不会受到影响。（）。A.正确B.错误标准答案：B。29.假设计算过程中不发生溢出，函数mpow(x,k)的功能是求出x的k次方的值。（）。A.正确B.错误标准答案：A。30.代码中第40行到第50行的目的是为了将ans1数组进行“去重”操作。（）。A.正确B.错误标准答案：A。31.当输入为“31512-1212”时，输出结果为？（）。A.4B.8C.0D.10标准答案：B。32.记程序结束前p数组元素的最大值为P，则该代码的时间复杂度是？（）。A.O(n)B.O(mnlogmn)C.O(mn/2logmn/2)D.O(m3/2(logmn/2+logP))标准答案：C。33.本题所求出的是？（）。A.满足a,b,c∈[1,m]的整数方程a3+b2=c2的解的数量B.满足a,b,c∈[1,m]的整数方程a2+b2=c2的解的数量C.满足x∈[0,m]的整数方程Σk_i・x_i^p_i=0的解的数量D.满足x∈[1,m]的整数方程Σk_i・x_i^p_i=0的解的数量标准答案：D。三、单选题（完善程序）。完善程序（一）。34-38题组合题。特殊最短路。题目背景：给定一个含N个点、M条边的带权无向图，边权非负。起点为S，终点为T。对于一条S到T的路径，可以在整条路径中，至多选择一条边作为“免费边”：当第一次经过这条被选中的边时，费用视为0；如果之后再次经过该边，则仍按其原始权重视计费。点和边均允许重复经过。求从S到T的最小总费用。以下代码求解了上述问题。试补全程序。include<algorithm>include<iostream>include<queue>include<vector>usingnamespacestd;constlonglongINF=1e18;structEdge{intto;intweight;};structState{longlongdist;intu;intused_freebie;//0fornotused,1forusedbooloperator>(constState&other)const{returndist>other.dist;}};intmain(){intn,m,s,t;cin>>n>>m>>s>>t;vector<vector<Edge>>adj(n+1);for(inti=0;i<m;++i){intu,v,w;cin>>u>>v>>w;adj[u].push_back({v,w});adj[v].push_back({u,w});}vector<vector<longlong>>d(n+1,vector<longlong>(2,INF));priority_queue<State,vector<State>,greater<State>>pq;d[s][0]=0;pq.push(0,s,①);while(!pq.empty()){Statecurrent=pq.top();pq.pop();longlongdist=current.dist;intu=current.u;intused=current.used_freebie;if(dist>②){continue;}for(constauto&edge:adj[u]){intv=edge.to;intw=edge.weight;if(d[u][used]+u>③){③=d[u][used]+w;pq.push({③,v,used});}if(used==0&&(d[v][1]>④)){d[v][1]=④;pq.push({d[v][1],v,1});}}}cout<<⑤<<endl;return0;}34.题①处应填？（）。A.0B.1C.-1D.false标准答案：A。35.题②处应填？（）。A.d[u][!used]B.d[u][used]C.d[t][used]D.INF标准答案：B。36.题③处应填？（）。A.d[v][1]B.d[v][used]C.d[u][used]D.d[v][0]标准答案：B。37.题④处应填？（）。A.d[v][0]B.d[v][1]C.d[u][0]D.d[u][1]标准答案：C。38.题⑤处应填？（）。A.d[t][1]B.d[t][0]C.min(d[t][0],d[t][1])D.d[t][0]+d[t][1]标准答案：C。完善程序（二）。39-43题组合题。生产线测试。题目背景：工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有n条生产线（编号0～n-1），已知其中恰有一条生产线存在缺陷。每一轮测试为，从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退货（结果记为1），否则正常收货（记为0）。受售后压力限制，在所有发货批次中，最多只能有k次退货（即结果为1的次数≤k）。工厂的目标是，设计最少的间接测试轮数w（发货总批次），保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。以下程序实现了工厂的目标，包含两部分：(i)确定w的最小值，并设计最优测试方案。(ii)根据测试结果推断存在缺陷的生产线。该程序确定w最小值的方法为：由于不同的生产线故障时，测试应当返回不同的结果，因此w轮测试的可能结果数不应少于生产线数量。`test_subset()`函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码表示为每批次的检测结果（即最低位是第1批次、最高位是第w批次）；其实现在此处未给出。`test_subset()`函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码表示为每批次的检测结果（即最低位是第1批次、最高位是第w批次）；其实现在此处未给出。试补全程序。include<algorithm>include<cstddef>include<iostream>include<vector>usingnamespacestd;longlongcomb(intw,inti){if(i<0||i>w){return0;}longlongres=1;for(intt=1;t<=i;++t){res=res*(wt+1)/t;}returnres;}//计算长度为w、1的个数≤k的码字总数。longlongcount_patterns(intw,intk){longlongtotal=0;for(intt=0;t<=min(w,k);++t){total+=comb(w,t);}returntotal;}//抽象测试接口。inttest_subset(constvector<vector<int>>&plan);intsolve(intn,intk){//第1步：求最小w。intw=1;while(①){++w;}cout<<w<<endl;//第2步：生成测试方案。vector<vector<int>>code(n,vector<int>(w,0));intidx=0;for(intones=0;ones<=k&&idx<n;++ones){vector<int>bits(w,0);fill(bits.begin(),bits.begin()+ones,1);do{for(intb=0;b<w;++b){code[idx][b]=bits[b];}++idx;if(idx>=n){break;}}while(std::②);}vector<vector<int>>plan(w);for(inti=0;i<w;++i){for(intj=0;j<n;++j){