2023年信息学CSP-S组初赛真题及参考答案.docx

《2023年信息学CSP-S组初赛真题及参考答案.docx》由会员分享，可在线阅读，更多相关《2023年信息学CSP-S组初赛真题及参考答案.docx（16页珍藏版）》请在第一文库网上搜索。

1、2023年信息学CSP-S组初赛真题及参考答案一、单项选择题(共15题，每题2分，共计30分：每题有且仅有一个正确选项)1在1inUX系统终端中，以下那个命令用于创建一个新的目录()AnewdirBmkdirCcreateDmkfo1d答案B2由0,1,2,3,4中选取4个数字，能组成()个不同四位数注:最小的四位数是IOOO最大的四位数是9999A96B18C120D84答案A3假设n是图的顶点的个数,m是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法,对于m=O(n)的稀疏图而言下面的四个选项，哪一项的渐近时间复杂度最小AO(m*sqrt(1ogn)*1og1ogn)BO(n2

2、+m)CO(n21ogm+m1ogn)DO(m+n1ogn)答案A4假设有n根柱子，需要按照以下规则依次放置编号为1、2、3、.的圆环:每根柱子的底部固定，顶部可以放入圆环，每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有4根柱子时，最多可以放置()个圆环A7B9C11D5答案C5以下对数据结构的表述不恰当的一项是A队列是一种先进先出(FIFO)的线性结构B哈夫曼树的构造过程主要是为了实现图的深度优先搜索C散列表是一种通过散列函数将关键字映射到存储位置的数据结构D二又树是一种每个结点最多有两个子结点的树结构答案B6以下连通无向图中，()一定可以用不超过两

3、种颜色进行染色A完全三叉树B平面图C边双连通图D欧拉图答案A7最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下:给定两个序列X=x1,x2,x3,xm和Y=y1,y2,y3.yn,最长公共子序列（1CS）问题的目标是找到一个最长的新序列Z=z1,z2,z3zk,使得序列既是序列X的子序列，又是序列Y的子序列，且序列Z的长度k在满足上述条件的序列里是最大的。（注:序列A是序列B的子序列，当且仅当在保持序列B元索顺序的情况下，从序列B中删除若干个元素，可以使得剩余的元素构成序列Ao测序歹ABCAAAABA”和“ABABCBABA”的最长公共子序歹U长度为（）A4B5C6D7答案C8一位玩

4、家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下:玩家第一次掷出X点，得到2x元悌二次掷出y点，当y=x时玩家会失去之前得到的2x元而当y!=x时玩家能保住第一次获得的2x元。上述x,y1,2,3,4,5,6。例如:玩家第一次掷出3点得到6元后，但第二次再次掷出3点，会失去之前得到的6元，玩家最终收益为0元：如果玩家第一次掷出3点第二次掷出4点，则最终收益是6元。假设骰子挑出任意一点的概率均为1/6,玩家连续掷两次般子后所有可能情形下收益的平均值是多少？A7B35/6C16/3D19/3答案B9假设我们有以下的C+代码：inta=5,b=3,c=4;boo1res=a&b|

5、cAb&ac提示:在C+中，逻辑运算的优先级从高到低依次为：逻辑非(!)逻辑与(&)、逻辑或(II)。位运算的优先级从高到低依次为：位非()、位与(&)、位异或(人)、位或(|)。同时，双目位运算的优先级高于双目逻辑运算:逻辑非和位非优先级相同，且高于所有双目运算符AtrueBfa1seC1DO答案A10假设快速排序算法的输入是一个长度为n的己排序数组，且该快速排序算法在分治过程总是选择第1个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为？A快速排序对于此类输入的表现最好因为数组已经排序B快速排序对于此类输入的时间复杂度是O(n1ogn),C快速排序对于此类输入的时间复杂度是

6、O(M2)D快速排序无法对此类数组进行排序因为数组已经排序答案C11以下哪个命令，能将一个名为“main.cpp”的C+源文件，编译并生成一个名为main”的可执行文件？()Ag+-0mainmain.cppBg+-omain.cppmainCg+main-omain.cppDg+main.cpp-omain.cpp12在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心OA4个结点的树B6个结点的树C7个结点的树D8个结点的树答案C13如图是一张包含6个顶点的有向图，但顶点间不存在拓扑序。如果

7、要删除其中一条边，使这6个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？A1B2C3D4答案C14若n=316%i,定义f(n)=ZXo皿其中g0,1,2,3,.，15对于给定的自然数T1o存在JWJn0,n,.,nm,对于1iTn都有Tii=/(小-1)且=nm-,称nrn为九。关于f的不动点，问在IOO16到14016中，关于f的不动点是9的自然数个数是A10B11C12D13答案B15现在用如下代码来计算XAr,其时间复杂度为()doub1equick_power(doub1ex1unsignedintn)if(n=0)return1;if(n=1)returnx;ret

8、urnquick_power(x,n/2)*quick_power(x,n/2)*(n&1)?x:1);AO(n)B0(1)CO(Iogn)DO(n1ogn)答案A二、阅读程序(程序输入不超过数组成字符串定义的范围：判断题正确填，错误填X；除特殊说明外，判断题1.5分，选择题3分，共计40分)101#incTude02usingnamespacestd;0304unsignedshort!(unsignedshortx)05x=x6;06x=x8;07returnx;080910 intmain()11 unsignedshortx;12 cinx;13 unsignedshorty=f(x)

9、;14 coutyend1;15 return0;16 )假设输入的x是不超过65535的自然数，完成下面的判断题和单选题判断题16当输入非零时，输出一定不为零()答案T17将f函数的输入参数的类型改为UnSignedint,程序的输出不变()答案F18当输入为“65535”时，输出为“63”()答案T19当输入为“1”时，输山为“64”。答案F单选题20当输入为“512”时，输出为()A“33280”B“33410”C,33106D,33346答案B21当输入为“64”时，执行完第5行后X的值为()A8256,B“4130”C“4128”D“4160”答案DO1020304050607oe0

10、9io11121314151617IS19202122232425262728293031323334353637383940414243444546474S495051525354552inc1udefinc1uderinc1udeinc1udeusingnamespacestd;1ong1ongsoIve1(inn)vectorp(n*1true);vectoxf(n1r0)rg(n1r0);f1=I；forxn=2;i*i=n;1+)(if(Pi)(vectord;for(i.ntk-i;kn;k*1)d.push_back(k);reverse(d.begin()rd.end();fo

11、r(nk:d)(for(xnj-k;jn;j+k)if(pj)pjNfa1se;fJ=1；9(j=k；for(xntiaqz(n)+1;!n;i+)U(pi)f1=i;9(i=i；)1ong1ongsum1;for(mt=2;1=n;i+)f=fi/giJ*(Oi*fi-D/(fi-1);sum+fx;returnsum;1ong1ongsoIve2(xnn)1ong1ongsum-0;for(mt=1;i=n;1+)sum+=i*(n);)reurnsum;inmain()intn;c1nn;coutso1ve1(n)Cnd1;courso1ve2(n)end1;reurn0;判断题22将第

12、15行删去，输出不变()答案F23当输入为“10”时，输出的第一行大于第二行。()答案F24当输入为“1000”时，输出的第一行与第二行相等()答案T单选题25 SO1Ve1(n)的时间复杂度为()Qn1og2n)BeS)(nZon)(n1og1ogn)答案D26 SO1Ve2(n)的时间复杂度为()A0(n2)B0(n)CO(n1ogn)DO(nsqrt(n)答案B27输入为“5”时，输出的第二行为()A20B21C22D23答案BO1finc1ude02#inc1ude03#inc1udeV1oSCream0405US1ngnamespace3td;0607boo1f0(vector&a,

13、mtnrin,ck)0809101112131415inc0;for(inti=0,j=0;im)j+;3+=i-j;)return3=k;16intf(vecrcr&a,intk)；171219202122232425262728sort(a.begn),a.end();intg0;in-h=a.back)-a0;whi1e(gh)inttt=g+(-g)/2;if(f(a,m,k)(hm;e1se(g-m+1;)293031)3233intmain()343536373S394041returng;intn,k;cmnk;vectora(n,0);for(mti-0;iai;coutf(ark)end1;reurn0;判断题28将第24行的“m”改为“m-1”，输出有可能不变，而剩下情况为少1。()答案T29将第22行的“g+(h-g)2改为(h+g)T,输出不变。()答案T30当输入为“572-451-3,输出为“5。()答案T单选题31设a数组中最大值减最小值加1为A,则f函数的时间复杂度为().Q(n1ogA)Q(r1ogA)cQn1ognA)DQ(n1ogn