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

2024年CSP-S提高级(第一轮)C++真题(含答案)一、单选题。1.在Linux系统中，如果你想显示当前工作目录的路径，应该使用哪个命令？（）。A.pwdB.cdC.LsD.echo标准答案：A。2.假设一个长度为n的整数数组中每个元素互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（）。A.O(n)B.O(logn)C.O(nlogn)D.O(1)标准答案：A。3.在C++中，以下哪个函数调用会造成栈溢出？（）。A.intfoo(return0;)B.Intbar(intx=1;returnx)C.Voidbaz(){inta[1000];baz();}D.Voidqux(){return;}标准答案：C。4.在一场比赛中，有10名选手参加，前三名将获得金银铜牌，若不允许并列，且每名选手只能获得一枚铜牌，则不同的颁奖方式共有多少种？（）。A.120B.720C.504D.1000标准答案：B。5.下面那个数据结构最适合实现先进先出（FIFO）的功能？（）。A.栈B.队列C.线性表D.二叉搜索树标准答案：B。6.一直f(1)=1，且对于n≥2有f(n)=f(n-1)+f([n/2])，则f(4)的值为：（）？A.4B.5C.6D.7标准答案：B。7.假设一个包含n个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪项不一定正确？（）。A.所有顶点的度数均为偶数B.该图联通C.该图存在一个欧拉回路D.该图的边数是奇数标准答案：D。8.对数组进行二分查找的过程中，以下哪个条件必须满足？（）。A.数组必须是有序的B.数组必须是无序的C.数组长度必须是2的幂D.数组中的元素必须是整数标准答案：A。9.考虑一个自然数n以及一个模数m，你需要计算n的逆元（即n在模m意义下的乘法逆元）。下列哪种算法最为合适？（）。A.使用暴力方法依次尝试B.使用扩展欧几里得解法C.使用快速幂解法D.使用线性筛法标准答案：B。10.在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有n个键值对，表的装载因子为α(0<α≤1)。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为（）？A.O(1)B.O(logn)C.O(1/(1-α))D.O(n)标准答案：D。11.假设有一颗h层的完全二叉树，该树最多包含（）个节点？A.2h-1B.2(h+1)-1C.2hD.2h+1标准答案：A。12.设有一个10个顶点的完全图，每两个顶点之间都有一条边，有多少个长度为4的环（）？A.120B.210C.630D.5040标准答案：C。13.对于一个整数n，定义f(n)为n的各个位数之和，问使f(f(x))=10的最小自然数x是（）？A.29B.199C.299D.399标准答案：B。14.设有一个长度为n的01字符串，其中有k个1，每次操作可以交换相邻两个字符。在最坏的情况下将这k个1移到字符串最右边所需要的交换次数是（）？A.KB.K*(k-1)/2C.(n-k)*kD.(2n-k-1)*k/2标准答案：C。15.如图是一张包含7个顶点的有向图。如果要删除一些边，使得从节点1到节点7没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合（）？A.1B.2C.3D.4标准答案：D。二、组合题（阅读程序）。阅读程序（1）。1-5题组合题。#include<iostream>usingnamespacestd;constintN=1000;intc[N];intlogic(intx,inty){return(x&y)^((x^y)|(~x&y));}voidgenerate(inta,intb,int*c){for(inti=0;i<b;i++){c[i]=logic(a,i)%(b+1);}}voidrecursion(intdepth,int*arr,intsize){if(depth<=0||size<=1)return;intpivot=arr[0];inti=0,j=size-1;while(i<=j){while(arr[i]<pivot)i++;while(arr[j]>pivot)j--;if(i<=j){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;i++;j--;}}recursion(depth-1,arr,j+1);recursion(depth-1,arr+i,size-i);}intmain(){inta,b,d;cin>>a>>b>>d;generate(a,b,c);recursion(d,c,b);for(inti=0;i<b;i++)cout<<c[i]<<"";}1.当1000≥d≥b时，输出的序列是有序？（）。A.正确B.错误标准答案：A。2.当输入“551”时，输出为“11555”（）。A.正确B.错误标准答案：B。3.假设数组c长度无限制，该程序所实现的算法的时间复杂度是O(b)的（）。A.正确B.错误标准答案：B。4.函数intlogic(intx,inty)的功能？（）？A.按位与B.按位或C.按位异或D.以上都不是标准答案：B。5.当输入为“10100100”时，输出的第100个数？（）？A.91B.94C.95D.98标准答案：C。阅读程序（2）。6-11题组合题。#include<iostream>#include<string>usingnamespacestd;constintP=998244353,N=1e4+10,M=20;intn,m;strings;intdp[1<<M];intsolve(){dp[0]=1;for(inti=0;i<n;i++){for(intj=(1<<(m-1))-1;j>=0;j--){intk=(j<<1)|(s[i]-'0');if(j!=0||s[i]=='1')dp[k]=(dp[k]+dp[j])%P;}}intans=0;for(inti=0;i<(1<<m);i++){ans=(ans+1ll*i*dp[i])%P;}returnans;}intsolve2(){intans=0;for(inti=0;i<(1<<n);i++){intcnt=0;intnum=0;for(intj=0;j<n;j++){if(i&(1<<j)){num=num*2+(s[j]-'0');cnt++;}}if(cnt<=m)(ans+=num)%=P;}returnans;}intmain(){cin>>n>>m;cin>>s;if(n<=20){cout<<solve2()<<endl;}cout<<solve()<<endl;return0;}6.假设输入的s是包含n个字符的01串，函数solve()所实现的算法时间复杂度是O(n*2m)（）。A.正确B.错误标准答案：A。7.输入“11210000000001”时，程序输出两个数32和23（）。A.正确B.错误标准答案：A。8.在n≤10时，solve()的返回值始终小于410（）。A.正确B.错误标准答案：A。9.当n=10且m=10时，有多少种输入使得两行的结果完全一致？（）。A.1024B.11C.10D.0标准答案：B。10.当n≤5时，solve()的最大可能返回值？（）？A.65B.211C.665D.2059标准答案：C。11.若n=8，m=8，solve和solve2的返回值的最大可能的差值？（）？A.1477B.1995C.2059D.2187标准答案：C。阅读程序（3）。12-17题组合题。#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintmaxn=1000000+5;constintP1=998244353,P2=1000000007;constintB1=2,B2=31;constintK1=0,K2=13;typedeflonglongll;intn;boolp[maxn];intp1[maxn],p2[maxn];structH{inth1,h2,l;H(boolb=false){h1=b+K1;h2=b+K2;l=1;}Hoperator+(constH&h)const{Hhh;hh.l=l+h.l;hh.h1=(1ll*h1*p1[h.l]+h.h1)%P1;hh.h2=(1ll*h2*p2[h.l]+h.h2)%P2;returnhh;}booloperator==(constH&h)const{returnl==h.l&&h1==h.h1&&h2==h.h2;}booloperator<(constH&h)const{if(l!=h.l)returnl<h.l;elseif(h1!=h.h1)returnh1<h.h1;elsereturnh2<h.h2;}}h[maxn];voidinit(){memset(p,1,sizeof(p));p[0]=p[1]=false;p1[0]=p2[0]=1;for(inti=1;i<=n;i++){p1[i]=(1ll*B1*p1[i-1])%P1;p2[i]=(1ll*B2*p2[i-1])%P2;if(!p[i])continue;for(intj=2*i;j<=n;j+=i){p[j]=false;}}}intsolve(){for(inti=n;i;i--){h[i]=H(p[i]);if(2*i+1<=n){h[i]=h[2*i]+h[i]+h[2*i+1];}elseif(2*i<=n){h[i]=h[2*i]+h[i];}}cout<<h[1].h1<<endl;sort(h+1,h+n+1);intm=unique(h+1,h+n+1)-(h+1);returnm;}intmain(){cin>>n;init();cout<<solve()<<endl;}12.假设程序运行前能自动将maxn改为n+1，所实现的算法的时间复杂度是O(nlogn)（）。A.正确B.错误标准答案：A。13.时间开销的瓶颈是init()函？（）。A.正确B.错误标准答案：B。14.若修改常数B1或K1的值，该程序可能会输出不同的结？（）。A.正确B.错误标准答案：A。15.在solve()函数种，h[]的合并顺序可以看作？（）。A.二叉树的BFS序B.二叉树的先序遍历C.二叉树的中序遍历D.二叉树的后序遍历标准答案：C。16.输入“10”，输出的第一行是（）？A.83B.424C.54D.110101000标准答案：A。17.输入“16”，输出的第二行？（）？A.7B.9C.10D.12标准答案：C。三、单选题（完善程序）。完善程序（1）。1-5题组合题。合并序列。有两个长度为N的单调不降序列A和B，序列的每个元素都是小于109的非负整数。在A和B中各取一个数相加可以得到N2个和，求其中第k小的和。上述参数满足N≤105和1≤K≤N2。#include<iostream>usingnamespacestd;constintmaxn=100005;intn;longlongk;inta[maxn],b[maxn];int*upper_bound(int*a,int*an,intai){intl=0,r=(①);while(l<r){intmid=(l+r)>>1;if(②){r=mid;}else{l=mid+1;}}return(③);}longlongget_rank(intsum){longlongrank=0;for(inti=0;i<n;i++){rank+=upper_bound(b,b+n,sum-a[i])-b;}returnrank;}intsolve(){intl=0,r=（④）;while(l<r){intmid=((longlong)l+r)>>1;if(⑤）{l=mid+1;}else{r=mid;}}returnl;}intmain(){cin>>n>>k;for(inti=0;i<n;i++)cin>>a[i];for(inti=0;i<n;i++)cin>>b[i];cout<<solve()<<endl;return0;}1.题①处应？（）。A.an-aB.an-a-1C.aiD.ai+1标准答案：A。2.题②处应？（）。A.a[mid]>aiB.a[mid]≥aiC.a[mid]<aiD.a[mid]≤ai标准答案：A。3.题③处应？（）。A.a+lB.a+l+1C.a+l-1D.an-l标准答案：A。4.题④处应？（）。A.a[n-1]+b[n-1]B.a[n]+b[n]C.2*maxnD.maxn标准答案：A。5.题⑤处应？（）。A.get_rank(mid)<kB.get_rank(mid)≤kC.get_rank(mid)>kD.get_rank(mid)≥k标准答案：A。完善程序（2）。6-10题组合题。已知有一个n个点m条边的有向图G，并且给定图中的两个点s和t，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行“-1”。如果存在，输出两行，第一行表示此段路经的长度，第二行表示此段路的一个方案。#include<cstdio>#include<queue>#include<utility>#include<cstring>usingnamespacestd;constintmaxn=2e5+10,maxm=1e6+10,inf=522133279;intn,m,s,t;inthead[maxn],nxt[maxm],to[maxm],w[maxm],tot=1;intdis[maxn<<1],*dis2;intpre[maxn<<1],*pre2;boolvis[maxn<<1];voidadd(inta,intb,intc){++tot;nxt[tot]=head[a];to[tot]=b;w[tot]=c;head[a]=tot;}boolupd(inta,intb,intd,priority_queue<pair<int,int>>&q){if(d>=dis[b])returnfalse;if(b<n)(①);q.push(②);dis[b]=d;pre[b]=a;returntrue;}voidsolve(){priority_queue<pair<int,int>>q;q.push(make_pair(0,s));memset(dis,(③),sizeof(dis));memset(pre,-1,sizeof(pre));dis2=dis+n;pre2=pre+n;dis[s]=0;while(!q.empty()){intaa=q.top().second;q.pop();if(vis[aa])continue;vis[aa]=true;inta=aa%n;for(inte=head[a];e;e=nxt[e]){intb=to[e],c=w[e];if(aa<n){if(!upd(a,b,dis[a]+c,q))(④);}else{upd(n+a,n+