文档介绍：该【2023CSP-S提高组第一轮试题及答案参考资料v1 】是由【1781111****】上传分享，文档一共【14】页，该文档可以免费在线阅读，需要了解更多关于【2023CSP-S提高组第一轮试题及答案参考资料v1 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..CCF(CSP-S1)提高级C++语言试题认证时间:2023年9月16日14:30~16:30考生注意事项:试题纸共有13页,答题纸共有1页,满分100分。请在答题纸上作答,写在试题纸上的一律无效。?不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。一、单项选择题(共题,每题2分,共计30分;每题有且仅有一个正确选项),以下哪个命令用于创建一个新的目录?(),1,2,3,4中选取4个数字,能组成()个不同四位数。(注:最小的四位数是1000,最大的四位数是9999。),m是图的边的个数,为求解某一问题有下面四种不同时间复杂度的算法。对于mΘ(n)的稀疏图而言,下面的四个选项,哪一项的渐近时间复杂度最小。()(mlogn?loglogn)(n2+m)(n2logm+mlogn)(m+nlogn),需要按照以下规则依次放置编号为1、2、3、...的圆环:每根柱子的底部固定,顶部可以放入圆环;每次从柱子顶部放入圆环时,需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有4根柱子时,最多可以放置()个圆环。CSP-S2023C++语言试题第1页,共13页:..:()。(FIFO),()一定可以用不超过两种颜色进行染色。。其定义如下:给定两个序列X{x,x,x,?,x}和Y={y,y,y,?,y},最长公共子序列(LCS)问题的目标是找到一个123m123n最长的新序列Z={z,z,z,?,z},使得序列Z既是序列X的子序列,又是序列Y的子序123k列,且序列Z的长度k在满足上述条件的序列里是最大的。(注:序列A是序列B的子序列,当且仅当在保持序列B元素顺序的情况下,从序列B中删除若干个元素,可以使得剩余的元素构成序列A。)则序列“ABCAAAABA”和“ABABCBABA”的最长公共子序列长度为()。,游戏要求连续掷两次骰子,收益规则如下:玩家第一次掷出x点,得到2x元;第二次掷出y点,当y=x时玩家会失去之前得到的2x元,而当y≠x时玩家能保住第一次获得的2x元。上述x,y∈{1,2,3,4,5,6}。例如:玩家第一次掷出3点得到6元后,但第二次再次掷出3点,会失去之前得到的6元,玩家最终收CSP-S2023C++语言试题第2页,共13页:..益为元;如果玩家第一次掷出3点、第二次掷出4点,则最终收益是6元。假设骰子掷出任意一点的概率均为1/6,玩家连续掷两次骰子后,所有可能情形下收益的平均值是多少?()++代码:inta=5,b=3,c=4;boolres=a&b||c^b&&a|c;请问,res的值是什么?()提示:在C++中,逻辑运算的优先级从高到低依次为:逻辑非(!)、逻辑与(&&)、逻辑或(||)。位运算的优先级从高到低依次为:位非(~)、位与(&)、位异或(^)、位或(|)。同时,双目位运算的优先级高于双目逻辑运算;逻辑非和位非优先级相同,且高于所有双目运算符。,且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?(),因为数组已经排序。(nlogn)。(n2)。,因为数组已经排序。,能将一个名为“”的C++源文件,编译并生成一个名为“main”的可执行文件?()CSP-S2023C++语言试题第3页,共13页:..g++-++-++main-++-,树的重心是树上的一个结点,以该结点为根时,使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心?()。,但顶点间不存在拓扑序。如果要删除其中一条边,使这6个顶点能进行拓扑排序,请问总共有多少条边可以作为候选的被删除边?()?k16i?x,定义f(n)=?kx;其中x∈0,1,?,15。对于给定自然数n,存i=0ii=0ii0在序列n,n,n,?,n,其中对于1≤i≤m都有n=f(n),且n=n,称n为n关012mii?1mm?1m0于f的不动点。问在100至1A0中,关于f的不动点为9的自然数个数为()。-S2023C++语言试题第4页,共13页:..现在用如下代码来计算xn,其时间复杂度为()。doublequick_power(doublex,unsignedn){if(n==0)return1;if(n==1)returnx;returnquick_power(x,n/2)*quick_power(x,n/2)*((n&1)?x:1);}()(1)(log)(log)二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填,错误填×;除特殊说明外,,选择题3分,共计40分)(1)01#include<iostream>02usingnamespacestd;0304unsignedshortf(unsignedshortx){05x^=x<<6;06x^=x>>8;07returnx;08}0910intmain(){11unsignedshortx;12cin>>x;13unsignedshorty=f(x);14cout<<y<<endl;15return0;16}假设输入的x是不超过65535的自然数,完成下面的判断题和单选题:判断题CSP-S2023C++语言试题第5页,共13页:..当输入非零时,输出一定不为零。()17.(2分)将f函数的输入参数的类型改为unsignedint,程序的输出不变。()“65535”时,输出为“63”。()“1”时,输出为“64”。()“512”时,输出为()。A.“33280”B.“33410”C.“33106”D.“33346”“64”时,执行完第5行后x的值为()。A.“8256”B.“4130”C.“4128”D.“4160”()01#include<iostream>02#include<cmath>03#include<vector>04#include<algorithm>05usingnamespacestd;0607longlongsolve1(intn){08vector<bool>p(n+1,true);09vector<longlong>f(n+1,0),g(n+1,0);10f[1]=1;11for(inti=2;i*i<=n;i++){12if(p[i]){13vector<int>d;14for(intk=i;k<=n;k*=i)(k);15reverse((),());16for(intk:d){17for(intj=k;j<=n;j+=k){18if(p[j]){19p[j]=false;20f[j]=i;21g[j]=k;22}23}24}25}26}27for(inti=sqrt(n)+1;i<=n;i++){28if(p[i]){CSP-S2023C++语言试题第6页,共13页:..f[i]=i;30g[i]=i;31}32}33longlongsum=1;34for(inti=2;i<=n;i++){35f[i]=f[i/g[i]]*(g[i]*f[i]-1)/(f[i]-1);36sum+=f[i];37}38returnsum;39}4041longlongsolve2(intn){42longlongsum=0;43for(inti=1;i<=n;i++){44sum+=i*(n/i);45}46returnsum;47}4849intmain(){50intn;51cin>>n;52cout<<solve1(n)<<endl;53cout<<solve2(n)<<endl;54return0;55}假设输入的是不超过1000000的自然数,完成下面的判断题和单选题:,输出不变。()“10”时,输出的第一行大于第二行。()24.(2分)当输入为“1000”时,输出的第一行与第二行相等。()?(n)的时间复杂度为()。(n)的时间复杂度为()。CSP-S2023C++语言试题第7页,共13页:..“5”时,输出的第二行为()。A.“20”B.“21”C.“22”D.“23”()01#include<vector>02#include<algorithm>03#include<iostream>0405usingnamespacestd;0607boolf0(vector<int>&a,intm,intk){08ints=0;09for(inti=0,j=0;i<();i++){10while(a[i]-a[j]>m)j++;11s+=i-j;12}13returns>=k;14}1516intf(vector<int>&a,intk){17sort((),());1819intg=0;20inth=()-a[0];21while(g<h){22intm=g+(h-g)/2;23if(f0(a,m,k)){24h=m;25}else{26g=m+1;27}28}2930returng;31}3233intmain(){34intn,k;35cin>>n>>k;36vector<int>a(n,0);37for(inti=0;i<n;i++){CSP-S2023C++语言试题第8页,共13页:..cin>>a[i];39}40cout<<f(a,k)<<endl;41return0;42}假设输入总是合法的且8、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题:“m”改为“m-1”,输出有可能不变,而剩下情况为少1。()“g+(h-g)/2”改为“(h+g)>>1”,输出不变。()“572-451-3”,输出为“5”。()?,则f函数的时间复杂度为()。(?)“>”替换为“>=”,那么原输出与现输出的大小关系为()。“582-538-12”时,输出为()。A.“13”B.“14”C.“8”D.“15”三、完善程序(单选题,每小题3分,共计30分)(1)(第小路径)给定一张个点条边的有向无环图,顶点编号从0到?1。对于一条路径,我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中,“路径序列”字典序第小的路径。保证存在至少条路径。上述参数满足1≤?≤105和1≤≤1018。在程序中,我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据的值和每个顶点的路径数量,确定路径的起点,然后可以类似地依次求出路径中的每个点。试补全程序。01#include<iostream>CSP-S2023C++语言试题第9页,共13页:..#include<algorithm>03#include<vector>0405constintMAXN=100000;06constlonglongLIM=1000000000000000000ll;0708intn,m,deg[MAXN];09std::vector<int>E[MAXN];10longlongk,f[MAXN];1112intnext(std::vector<int>cand,longlong&k){13std::sort((),());14for(intu:cand){15if(①)returnu;16k-=f[u];17}18return-1;19}2021intmain(){22std::cin>>n>>m>>k;23for(inti=0;i<m;++i){24intu,v;25std::cin>>u>>v;//一条从u到v的边26E[u].push_back(v);27++deg[v];28}29std::vector<int>Q;30for(inti=0;i<n;++i)31if(!deg[i])(i);32for(inti=0;i<n;++i){33intu=Q[i];34for(intv:E[u]){35if(②)(v);36--deg[v];37}38}39std::reverse((),());40for(intu:Q){41f[u]=1;42for(intv:E[u])f[u]=③;43}44intu=next(Q,k);45std::cout<<u<<std::endl;CSP-S2023C++语言试题第10页,共13页:..while(④){47⑤;48u=next(E[u],k);49std::cout<<u<<std::endl;50}51return0;52}34.①处应填()>=f[u]<=f[u]>f[u]<f[u]35.②处应填()[v]==[v]==[v]>[v]>036.③处应填()::min(f[u]+f[v],LIM)::min(f[u]+f[v]+1,LIM)::min(f[u]*f[v],LIM)::min(f[u]*(f[v]+1),LIM)37.④处应填()!=-1B.!E[u].empty()>>138.⑤处应填()+=f[u]-=f[u]C.--kD.++k(最大值之和)给定整数序列,…,,求该序列所有非空连续子序列的最大值之0?1和。上述参数满足1≤≤105和1≤≤108。一个序列的非空连续子序列可以用两个下标和(其中0≤≤<)表示,对应的序列为,,…,。两个非空连续子序列不同,当且仅当下标不同。?1例如,当原序列为[1,2,1,2]时,要计算子序列1、2、1、2、1,2、2,1、1,2、1,2,1、2,1,2、[1,2,1,2]的最大值之和,答案为18。注意1,1和2,2虽然是原序列的子序列,但不是连续子序列,所以不应该被计算。另外,注意其中有一些值相同的子序列,但由于他们在原序列中的下标不同,属于不同的非空连续子序列,所以会被分别计算。解决该问题有许多算法,以下程序使用分治算法,时间复杂度log。试补全程序。01#include<iostream>02#include<algorithm>03#include<vector>04CSP-S2023C++语言试题第11页,共13页:..constintMAXN=100000;0607intn;08inta[MAXN];09longlongans;1011voidsolve(intl,intr){12if(l+1==r){13ans+=a[l];14return;15}16intmid=(l+r)>>1;17std::vector<int>pre(a+mid,a+r);18for(inti=1;i<r-mid;++i)①;19std::vector<longlong>sum(r-mid+1);20for(inti=0;i<r-mid;++i)sum[i+1]=sum[i]+pre[i];21for(inti=mid-1,j=mid,max=0;i>=l;--i){22while(j<r&&②)++j;23max=std::max(max,a[i]);24ans+=③;25ans+=④;26}27solve(l,mid);28solve(mid,r);29}3031intmain(){32std::cin>>n;33for(inti=0;i<n;++i)std::cin>>a[i];34⑤;35std::cout<<ans<<std::endl;36return0;37}39.①处应填()[i]=std::max(pre[i-1],a[i-1])[i+1]=std::max(pre[i],pre[i+1])[i]=std::max(pre[i-1],a[i])[i]=std::max(pre[i],pre[i-1])40.②处应填()[j]<[j]<a[i][j-mid]<[j-mid]>maxCSP-S2023C++语言试题第12页,共13页:..③处应填()A.(longlong)(j-mid)*maxB.(longlong)(j-mid)*(i-l)*[j-mid][j-mid]*(i-l)42.④处应填()A.(longlong)(r-j)*maxB.(longlong)(r-j)*(mid-i)*[r-mid]-sum[j-mid]D.(sum[r-mid]-sum[j-mid])*(mid-i)43.⑤处应填()(0,n)(0,n-1)(1,n)(1,n-1)CSP-S2023C++语言试题第13页,共13页:..BAACBACBBA√√×BD××√DBB√√√CBBBAADCDBACA