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

该【2023年信息学CSP-S组初赛真题及参考答案 】是由【青山代下】上传分享，文档一共【15】页，该文档可以免费在线阅读，需要了解更多关于【2023年信息学CSP-S组初赛真题及参考答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..CSP-S组初赛真题及参考答案一、单项选择题(共15题,每题2分,共计30分:每题有且仅有一个正确选项)在Linux系统终端中,以下那个命令用于创建一个新的目录()AnewdirBmkdirCcreateDmkfold答案B2由0,1,2,3,4中选取4个数字,能组成()个不同四位数注:最小的四位数是1000最大的四位数是9999A96B18C120D84答案A3假设n是图的顶点的个数,m是图的边的个数,为求解某一问题有下面四种不同时间复杂度的算法,对于m=O(n)的稀疏图而言下面的四个选项,哪一项的渐近时间复杂度最小AO(m*sqrt(logn)*loglogn)BO(n^2+m)CO(n^2/logm+mlogn):..A4假设有n根柱子,需要按照以下规则依次放置编号为1、2、3、...的圆环:每根柱子的底部固定,顶部可以放入圆环,每次从柱子顶部放入圆环时,需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有4根柱子时,最多可以放置()个圆环A7B9C11D5答案C5以下对数据结构的表述不恰当的一项是A队列是一种先进先出(FIFO)的线性结构B哈夫曼树的构造过程主要是为了实现图的深度优先搜索C散列表是一种通过散列函数将关键字映射到存储位置的数据结构D二又树是一种每个结点最多有两个子结点的树结构答案B6以下连通无向图中,()一定可以用不超过两种颜色进行染色A完全三叉树B平面图C边双连通图D欧拉图答案A:..:给定两个序列X={x1,x2,x3,...xm}和Y={y1,y2,y3...yn},最长公共子序列(LCS)问题的目标是找到一个最长的新序列Z={z1,z2,z3...zk},使得序列既是序列X的子序列,又是序列Y的子序列,且序列Z的长度k在满足上述条件的序列里是最大的。(注:序列A是序列B的子序列,当且仅当在保持序列B元素顺序的情况下,从序列B中删除若千个元素,可以使得剩余的元素构成序列A。测序列和“ABABCBABA”的最长公共子序列长度为()A4B5C6D7答案C8一位玩家正在玩一个特殊的掷骰子的游戏,游戏要求连续掷两次骰子,收益规则如下:玩家第一次掷出x点,得到2x元;第二次掷出y点,当y=x时玩家会失去之前得到的2x元而当y!=x时玩家能保住第一次获得的2x元。上述x,y[1,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;boolres=a&b||c^b&&a|c:..在C++中,逻辑运算的优先级从高到低依次为:逻辑非(!)逻辑与(&&)、逻辑或(||)。位运算的优先级从高到低依次为:位非(~)、位与(&)、位异或(^)、位或(|)。同时,双目位运算的优先级高于双目逻辑运算:逻辑非和位非优先级相同,且高于所有双目运算符AtrueBfalseC1D0答案A10假设快速排序算法的输入是一个长度为n的已排序数组,且该快速排序算法在分治过程总是选择第1个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?A快速排序对于此类输入的表现最好因为数组已经排序B快速排序对于此类输入的时间复杂度是O(nlogn)。C快速排序对于此类输入的时间复杂度是O(n^2)D快速排序无法对此类数组进行排序因为数组已经排序答案C11以下哪个命令,能将一个名为的C++源文件,编译并生成一个名为的可执行文件?()Ag++-++-++main-++-**答案A**:..点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心()A4个结点的树B6个结点的树C7个结点的树D8个结点的树答案C13如图是一张包含6个顶点的有向图,但顶点间不存在拓扑序。如果要删除其中一条边,使这6个顶点能进行拓扑排序,请问总共有多少条边可以作为候选的被删除边?A1B2C3D4答案C14:..B11C12D13B15现在用如下代码来计算x^n,其时间复杂度为()doublequick_power(doublex,unsignedintn){if(n==0)return1;if(n==1)returnx;returnquick_power(x,n/2)*quick_power(x,n/2)*((n&1)?x:1);}AO(n)BO(1)CO(logn)DO(nlogn)答案A二、阅读程序(程序输入不超过数组成字符串定义的范围:判断题正确填,错误填×;除特殊说明外,,选择题3分,共计40分)101#incTude<iostream>02usingnamespacestd;0304unsignedshortf(unsignedshortx){:..06x^=x>>8;07returnx;08}0910intmain(){11unsignedshortx;12cin>>x;13unsignedshorty=f(x);14cout<<y<<end1;15return0;16}x是不超过65535的自然数,完成下面的判断题和单选题判断题16当输入非零时,输出一定不为零()答案T17将f函数的输入参数的类型改为unsignedint,程序的输出不变()答案F18当输入为时,输出为“63”()答案T19当输入为“1”时,输山为“64”。答案F单选题20当输入为“512”时,输出为()答案B:..时,执行完第5行后x的值为()答案D2:..22将第15行删去,输出不变()答案F23当输入为时,输出的第一行大于第二行。()答案F24当输入为“1000”时,输出的第一行与第二行相等()答案T单选题25solve1(n)的时间复杂度为()答案D26solve2(n)的时间复杂度为()AO(n^2)BO(n)CO(nlogn)DO(nsqrt(n))答案B27输入为”5”时,输出的第二行为()A20B21C22D23答案B3:..28将第24行的改为“m-1”,输出有可能不变,而剩下情况为少1。()答案T29将第22行的“g+(h-g)/2改为“(h+g)>>1”,输出不变。()答案T30当输入为“572-451-3”,输出为”5”。()答案T:..31设a数组中最大值减最小值加1为A,则f函数的时间复杂度为()答案C32将第10行中的替换为”>=”,那么原输出与现输出的大小关系为()A一定小于B一定小于等于且不一定小于C一定大于等于且不一定大于D以上三种情况都不对答案B33当输入为“582-538-12”时,输出为()答案B三、完善程序(单选题,每小题3分,共计3分)1第k小路径给定一张n个点m条边的有向无环图,顶点编号从0到n-1。对于一条路径,我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中,“路径序列”字典序第k小的路径。保证存在至少k条路径,上述参数满足1<=n,m<=10^5和1<=k<=10^,我们求出从每个点出发的路径数量。超过10^18的数都用10^18表示。然后我们根据k的值和每个顶点的路径数量,确定路径的起点,然后可以类似地依次求出路径中的每个点。试补全程序。:..34)答案B35②处应该填写():..A36处应该填写()Astd::min(f[u]+f[v],LIM)Bstd::min(f[u]+f[v]+1,LIM)Cstd::min(f[u]*f[v],LIM)Dstd::min(f[u]*(f[v]+1),LIM)答案A37④处应该填写()Au!=1B!E[u].empty()Ck>0Dk>1答案D38⑤处应该填写()Ak+=f[u]Bk-=f[u]C--kD++k答案C2最大值之和给定整数序列a0...an-1,求该序列所有非空连续子序列的最大值之和。上述参数满足1<=n<=10^5和1<=ai<=10^8一个序列的非空连续子序列可以用两个下标l和r(其中0<=l<=r<=n)表示,对应的序列为al,al+1,...ar。两个非空连续子序列不同,当且仅当下标不同例如,当原序列为[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]虽然是原序列的子序列,但不是连续子序列,所以不应该被计算。另外,注意其中有一些值相同的子序列,但由于他们在原序列中的下标不同,属于不同的非空连续子序列,,以下程序使用分治算法时间复杂度O(nlogn)。:..39处应填()Apre[i]=std::max(pre[i-1],a[i-1])Bpre[i+1]=std::max(pre[il,pre[i+1])Cpre[i]=std::max(pre[i-1],a[i])Dpre[i]=std::max(pre[i],pre[i-1])答案D40②处应填():..Ba[j]<a[i]Cpre[j-mid]<maxDpre[j-mid]>maxB41处应填()A(longlong)(j-mid)*maxB(longlong)(j-mid)*(i-l)*maxCsum[j-mid]Dsum[j-mid]*(i-l)答案A42④处应填()A(longlong)(r-j)*maxB(longlong)(r-j)*i*(mid-i)*maxCsum[r-mid]-sum[j-mid]D(sum[r-mid]-sum[j-mid])*(mid-i)答案C43⑤处应填()Asolve(0,n)Bsolve(0,n-1)Csolve(1,1)Dsolve(1,n-1)