2022-CSP-S(提高组)认证第一轮试题详细解析

2022CSP-S提高级第一轮认证C++语言试题考生注意事项：●试题纸共满分100分。请在答题纸上作答，写在试题纸上的一律无效。●不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。一、单项选择题(共15题，每题2分，共计30分；每题有且仅有一个正确选项)1.在Linux系统终端中，用于切换工作日录的命令为()。A.lsB.cdC.CPD.all答案：Bls命令用于显示指定工作目录下之内容（列出目前工作目录所含之文件及子目录)。cd命令用于切换当前工作目录。cp命令主要用于复制文件或目录。all和Linux系统并无什么关联。2.你同时用time命令和秒表为某个程序在单核CPU的运行计时。假如time命令的输出如下：real0m30.721suser0m24.579ssys0m6.123s以下最接近秒表计时的时长为()。A.30sB.24sC.18sD.6s答案：ALinuxtime命令用于统计给定命令所花费的总时间。它报告了以下几个关键指标：实际时间(RealTime)：从命令行开始执行到运行终止的实际消逝时间。用户CPU时间(UserCPUTime)：命令行执行完成时用户模式下CPU消耗的总时间。系统CPU时间(SystemCPUTime)：命令行执行完成时内核模式下CPU消耗的总时间。RealTime>UserCPUTime+SystemCPUTime3.若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈操作，则不可能得到的出栈序列是()。A.dcebfaB.cbdaefC.bcaefdD.afedcb答案:DA选项abcd先依此进栈，dc再出栈，e进栈，eb出栈，f进栈后fa出栈。BC符合题目进栈退栈操作，D连续退栈操作远超三次2

4.考虑对n个数进行排序，以下最坏时间复杂度低于O(n)的排序方法是()。A.插入排序B.冒泡排序C.归并排序D.快速排序答案:C归并排序最环时间复杂度均为nlogn,插入排序和冒泡排序等简单排序方法的最坏时间复2

杂度都是O(n),而快速排序在最坏情况下则会退化为冒泡排序。5.假设在基数排序过程中，受宁宙射线的影响，某项数据异变为一个完全不同的值。请问排序算法结束后，可能出现的最坏情况是()。A.移除受影响的数据后，最终序列是有序序列B.移除受影响的数据后，最终序列是前后两个有序的子序列C.移除受影响的数据后，最终序列是一个有序的子序列和·个基本无序的子序列D.移除受影响的数据后，最终序列基本无序【答案】A【解析】基数排序是按桶排序思想，某一个值的改变，不会造成其他数据排序失败，排除这个数据，其余数据仍是有序序列6.计算机系统用小端(LittleEndian)和大端(BigEndian)来描述多字节数据的存储地址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下C++代码段表示的程序，将分别输出什么结果?()unsignedx=0xDEADBEEF;unsignedchar*p=(unsignedchar*)&x;printf(\"%X\",*p);A.EF、EFB.EF、DEC.DE、EFD.DE、DE【答案】B低位是最低位的的EF，高位的就是最高位的DE7.一个深度为5(根结点深度为1)的，按前序遍历的顺序给结点从1开始编号，则第100号结点的父结点是第()号。A.95B.96C.97D.98【答案】C前序遍历的顺序是先根，再左子树，最后右子树。完全3叉树的第1层节点数1，第2层3，第3层9，第4层27，第5层81，深度为5的完全3叉数节点总数为121个。根节点是1号结点，深度为1。根结点的第一个儿子是2号结点，并且2号结点为根的子树一定是一棵深度为4的满三叉树，因此有1+3+9+27=40个结点，所以根结点的第二个儿子是42号，根结点的三号儿子是82号。同理，可以得到82号的第一个儿子是83号，并且以83号为根的子树有1+3+9=13个结点，因此82号的第二个儿子是96号，96号的第一个儿子是97号，而97号有三个儿子分别是98号、99号和100号。8.强连通图的性质不包括():A.每个顶点的度数至少为1C.任意两个顶点之间都有路径相连B.任意两个顶点之间都有边相连D.每个顶点至少都连有一条边【答案】B强连通图，任意两顶点都有路径可达即可，并不需要一定有边相连9.每个顶点度数均为2的无向图称为“2正规图”。由编号为从1到n的顶点构成的所有2正规图，其中包含欧拉回路的不同2正规图的数量为()。A.n!B.(n-1)!C.n!/2D.(n-1)!/2【答案】D正规图理解为一个圆环排列，将某一个顶点固定进行排列则为An的全排列为(n-1)!,那么欧拉回路顺时针与逆时针需要除以2去重，因此为(n-1)!/210.共有8人选修了程序设计课程，期末大作业要求由2人组成的团队完成。假设不区分每个团队内2人的角色和作用，请问共有多少种可能的组队方案()。A.28B.32C.56D.642【答案】A8=8*7/2=2811.小明希望选到形如“省A·WDDD”的车牌号。车牌号在“.”之前的内容固定不变；后面的5位号码中，前2位必须是大写英文字母，后3位必须是阿拉伯数字(里代表A至Z,DD表示0至9,两个#和三个DD之间可能相同也可能不同)。请问总共有多少个可供选择的车牌号()。A.20280B.52000C.676000D.1757600【答案】C大写字母26个，数字10个，26*26*10*10*10=67600012.给定地址区间为0~9的哈希表，哈希函数为h(x)=x%10,采用线性探查的冲突解决策略(对于出现冲突情况，会往后探查第一个空的地址存储；若地址9冲突了则从地址0重新开始探查)。哈希表初始为空表，依次存储(71,23,73,99,44,79,89)后，请问89存储在哈希表哪个地址中。A.9B.0C.1D.2【答案】D存储情况见下表地址值

079171289323473544

678

999

13.对于给定的n,分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为()。inti,j,k=0;for(i=0;i2.#include3.#include4.

5.usingnamespacestd;6.

7.intf(conststring&s,conststring&t)8.{9.intn=s.length(),m=t.length();10.

11.vectorshift(128,m+1);12.

13.inti,j;14.

15.for(j=0;j18.for(i=0;i<=n-m;i+=shift[s[i+m]]){19.j=0;20.while(j24.return-1;25.}26.

27.intmain()28.{29.stringa,b;30.cin>>a>>b;31.cout<2.

3.usingnamespacestd;4.

5.constintMAXN=105;6.

7.intn,m,k,val[MAXN];8.inttemp[MAXN],cnt[MAXN];9.

10.voidinit()11.{12.cin>>n>>k;13.for(inti=0;i>val[i];14.intmaximum=val[];15.for(inti=1;imaximum)maximum=val[i];17.m=1;18.while(maximum>=k){19.maximum/=k;20.m++;21.}22.}23.

24.voidsolve()25.{26.intbase=1;27.for(inti=0;i=0;j--){32.temp[cnt[val[j]/base%k]-1]=val[j];33.cnt[val[j]/base%k]--;34.}35.for(intj=0;j40.intmain()41.{42.init();43.solve();44.for(inti=0;i●单选题25.当输入为“539826913746”时，程序第一次执行到第36行，val[]数组的内容依次为()。A.9126463798B.9146372698C.9826469137D.9137469826【答案】D3进制下的第一位数的比较,91,37,46,98,26的三进制最后一位是1,1,1,2,2。26.若val[i]的最大值为100,k取()时算法运算次数最少。A.2B.3C.10【答案】D运算次数不仅和k有关，还跟n有关D.不确定)27.当输入的k比val[i]的最大值还大时，该算法退化为()算法。A.选择排序B.冒泡排序C.计数排序【答案】Ck>max(val[i])时，算法成为了计数排序。(3)D.桶排序1.#include2.#include3.

4.usingnamespacestd;5.

6.constintMAXL=1000;7.

8.intn,k,ans[MAXL];9.

10.intmain(void)11.{12.cin>>n>>k;13.if(!n)cout<<0<=0;i--)23.cout<=10?24.ans[i]+'A'-10:25.ans[i]+'0');26.cout<假设输入的n在int范围内，k为不小于2且不大于36的正整数，完成下面的判断题和单选题：●判断题28.算法的时间复杂度为O(logkn)。()【答案】T每次循环后n除以k29.删除第23行的强制类型转换，程序的行为不变。()【答案】F不强制类型转换输出的是int类型的值30.除非输入的n为0,否则程序输出的字符数为O(⌊logk|n|⌋+1)()【答案】T有余数时+1●单选题31.当输入为“1007”时，输出为()。A.202B.1515C.244【答案】A31-33题可以直接模拟计算一下32.当输入为“-2558”时，输出为“()”。A.1400B.1401C.417【答案】B33.当输入为“100000019”时，输出为“()”。A.BG939B.87GIBC.1CD428【答案】BD.1754D.400D.7CF1B三、完善程序(单选题，每小题3分，共计30分)(1)(归并第k小)已知两个长度均为n的有序数组al和a2(均为递增序，但不保证严格单调递增),并且给定正整数k(1≤k≤2n),求数组al和a2归并排序后的数组里第k小的数值。试补全程序。1.#include2.usingnamespacestd;3.

4.intsolve(int*al,int*a2,intn,intk){5.intleft1=0,rightl=n-1;6.intleft2=0,right2=n-1;7.while(left1<=right1&&left2<=right2){8.intml=(leftl+rightl)>>1;9.intm2=(left2+right2)>>1;10.intcnt=①;11.if(②){12.if(cnt34.①处应填()A.(ml+m2)*2B.(ml-1)+(m2-1)C.ml+m2D.(m1+1)+(m2+1)【答案】C用来记录合并数组当前位置的下标35.②处应填()A.a1[ml]==a2[m2]B.a1[ml]<=a2[m2]C.a1[ml]>=a2[m2]D.a1[m1]!=a2[m2]【答案】B比较两个数组对应的中间位置的大小36.③处应填()A.left1==right1B.left1right1D.left1!=right1【答案】C二分结束条件是37.④处应填()A.y=a1[k-left2-1]B.y=a1[k-left2]C.y=a2[k-left1-1]D.y=a2[k-left1]【答案】Ca2数组组成k个数的数量38.⑤处应填()A.y=a1[k-left2-1]B.y=a1[k-left2]C.y=a2[k-left1-1]D.y=a2[k-left1]【答案】Aa1数组组成k个数的数量left1>right1或者left2>right2(2)(容器分水)有两个容器，容器1的容量为为a升，容器2的容量为b升；同时允许下列的三种操作，分别为：1)FILL(i):用水龙头将容器i(i∈{1,2})灌满水；2)DROP(i):将容器i的水倒进下水道；3)POUR(i,j):将容器i的水倒进容器j(完成此操作后，要么容器j被灌满，要么容器i被清空)。求只使用上述的两个容器和三种操作，获得恰好c升水的最少操作数和操作序列。上述a、b、c均为不超过100的正整数，c≤max{a,b}。试补全程序。1.#include2.usingnamespacestd;3.constintN=110;4.

5.intf[N][N];6.intans;7.inta,b,c;8.intinit;9.

10.intdfs(intx,inty){11.if(f[x][y]!=init)12.returnf[x][y];13.if(x==c||y==c)14.returnf[x][y]=0;15.f[x][y]=init-1;16.f[x][y]=min(f[x][y],dfs(a,y)+1);17.f[x][y]=min(r[x][y],dfs(x,b)+1);18.f[x][y]=min(f[x][y],dfs(0,y)+1);19.f[x][y]=min(f[x][y],dfs(x,0)+1);20.intt=min(a-x,y);21.f[x][y]=min(f[x][y],①);22.t=min(x,b-y);23.f[x][y]=min(f[x][y],②);24.returnf[x][y];25.}26.

27.voidgo(intx,inty){28.if(③)29.return;30.if(f[x][y]==dfs(a,y)+1){31.cout<<\"FILL(1)\"<58.intmain(){59.cin>>a>>b>>c;60.ans=1<<30;61.memset(r,127,sizeoff);62.init=**f;63.if((ans=dfs(0,0))==init-1)64.cout<<\"impossible\";65.else{66.cout<=c||y>=cD.x>=c&&y>=cB.dfs(x+t,y-t)-1C.dfs(x-t,y+t)+1D.dfs(x-t,y+t)-1【答案】A判断下一步是否为将容器2中的水倒入容器1中43.⑤处应填()A.dfs(x+t,y-t)+1B.dfs(x+t,y-t)-1C.dfs(x-t,y+t)+1D.dfs(x-t,y+t)-1【答案】C判断下一步是否为将容器1中的水倒入容器2中，和42题是对称的2022年CSP-S1提高组第一轮参考答案

序号12345678序号161718192021

答案BADCABCB答案√

×

序号9101112131415

答案DACDBBB

序号222324252627

答案X

×

√DAB

√DDC

序号282930313233序号3940414243答案√X√ABB答案ACAAC序号3435363738答案CBCCA