您好,欢迎来到筏尚旅游网。
搜索
您的当前位置:首页2021 CSP-S(提高级)认证第一轮试题及详细解析

2021 CSP-S(提高级)认证第一轮试题及详细解析

来源:筏尚旅游网
2021CSP-S(提高级)认证第一轮试题及详细解析

选择题1.在Linux系统终端中,用于列出当前目录下所含的文件和子目录的命令为()。A.lsB.cdC.cpD.all

【解析】Linux系统中:ls命令用于显示指定工作目录下之内容(列出目前工作目录所含之文件及子目录);cd命令用于切换当前工作目录;cp命令主要用于复制文件或目录;all只是用来凑数的,没什么实际意义

故选A。2.二进制数001010102和000101102的和为()。001111002D.010000102010000002A.001111002B.010000002C.【解析】这是一个最基本的二进制加法,出现了连续的进位算出来是故选B。3.在程序运行过程中,如果递归调用的层数过多,可能会由于()引发错误。A.系统分配的栈空间溢出B.系统分配的队列空间溢出C.系统分配的链表空间溢出D.系统分配的堆空间溢出【解析】递归需要使用到系统堆栈空间,如果递归层数过多,导致系统堆栈空间不足。故选A。4.以下排序方法中,()是不稳定的。A.插入排序B.冒泡排序C.堆排序D.归并排序【解析】待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前的序列中Ri领先于Rj(即imod11。请问7存储在哈希表哪个地址中()。A.5B.6C.7D.8【解析】每个都算一下。分别为故选C。7.G是一个非连通简单无向图(没有自环和重边),共有36条边,则该图至少有()个点。A.8B.9C.10D.11【解析】设有故选C。8.令根结点的高度为1,则一棵含有2021个结点的二叉树的高度至少为()。A.10B.11C.12D.20210,1,4,9,5,3,3,5。重复的调整一下0,1,4,9,5,3,6,7。n个点,除了一个孤立点外剩下点为完全图。(n−1)(n−2)/2=36解得n=10

【解析】当树为完全二叉树时的高度为最小,所以故选B。9.210≤2021<211

前序遍历和中序遍历相同的二叉树为且仅为()。A.只有1个点的二叉树B.根结点没有左子树的二叉树C.非叶子结点只有左子树的二叉树D.非叶子结点只有右子树的二叉树【解析】前序遍历:先根再左子树后右子树,中序遍历:先左子树再根后右子树。所以去掉左子树时两个相同,选择D。10.定义一种字符串操作为交换相邻两个字符。将DACFEB变为次上述操作。A.7B.8C.9D.6【解析】ADCFEB->ACDFEB->ACDEFB->ACDEBF->ACDBEF->

ABCDEF最少需要()ACBDEF->ABCDEF,共7次,故选A。11.有如下递归代码solve(t,n):ift=1return1

elsereturn5*solve(t-1,n)modn

则solve(23,23)的结果为()。A.1B.7C.12D.22【解析】程序的运行结果为522mod23,根据用费马小定理,在p为素数的情况下,ap-1≡1(modp),所以522≡1(mod23),故选A。12.斐波那契数列的定义为:F1=1,F2=1,Fn=Fn−1+Fn−2(n≥3)。现在用如下程序来计算斐波那契数列的第n项,其时间复杂度为()。F(n):

ifn<=2return1

elsereturnF(n-1)+F(n-2)

A.O(n)B.O(n2)C.O(2n)D.O(nlogn)

【解析】时间复杂度

f(n)=f(n-1)+f(n-2)每一层都包含一个加法操作

例如n=8时,T(n)=2^0+2^1+2^2+2^3+2^4+2^5+2^6=2^7-1O(n)=2^7-1=2^n

故选C。13.有8个苹果从左到右排成一排,你要从中挑选至少一个苹果,并且不能同时挑选相邻的两个苹果,一共有()种方案。A.36B.48C.D.【解析】选1个苹果,有8种结果。6+5+4+3+2+1=21种。种。选2个苹果,可以固定第一个往后,有选3个苹果,有4+3+2+1+3+2+1+2+1+1=20选4个苹果,有5种。所以总数故选C。14.设一个三位数8+21+20+5=8+21+20+5=。n=a,b,c,其中a,b,c均为1到9之间的整数,若以a,b,c作为三角形的三条边可以构成等腰三角形(包括等边),则这样的n有()个。A.81B.120C.165D.216【解析】考虑a=b≠c有几种。1,1无解。2,2有2+2−1−1=22种。同理,3,3有4种,4,4有6种,后面5到9都是所以8种。8×5+6+4+2=52。而a=b=c有9种。所以52×3+9=165。故选C。15.有如下的有向图,节点为A,B,…,J,其中每条边的长度都标在图中。则节点A到节点J的最短路径长度为()A.16B.19C.20D.22【解析】单源最短路径问题,没有负边权,可以用dijkstra算法模拟一下。故选B。首先先看一下程序,通过求t可以猜出这是三维坐标系。还有因为r可以大致猜测是球。cos60∘=0.5,而60∘在弧度制下就是π/3。π/3,所以本题和球关系很大,而d是半径。可以猜测一下,因为V=4/3πr3,r是16.将第21行中t的类型声明从int改为double,不会影响程序运行的结果。()没有任何下取整的操作,并且结果也是double不影响,故判对。17.将第26、27行中的/sqrt(t)/2替换为/2/sqrt(t),不会影响程序运行的结果。()这里sqrt是小数,若先除以2会默认下取整。故判错。18.将第28行中的x*x改成sq(x)、y*y改成sq(y),不会影响程序运行的结果。()sq()函数内是算int类型的平方,这里的x和y都是double类型。故判错。19.(2分)当输入为00011001时,输出为1.3090。()手动模拟,这个不会难算。结果为5π/12估算一下,差不多,故判对。20.当输入为11111112时,输出为()。A.3.1416B.6.2832走特判,所以C.4.7124

D.4.1888

4/3πr3直接带进去,其中r取1,故选D。21.(2.5分)这段代码的含义为()。A.求圆的面积并B.求球的体积并C.求球的体积交D.求椭球的体积并根据上面的分析和特判的min,所以判断是交,故选C。阅读程序后,发现这是在求最大子段和。先看solve2再看solve1会更轻松,不过其实把判断题带进去也很好22.程序总是会正常执行并输出两行两个相等的数。()确实。判对。23.第28行与第38行分别有可能执行两次及以上。()考虑二分到最边界,此时(n,n+1)会分成(n,n)和(n+1,n+1),相等情况被特判走了,所以不会走那两行特判。若开头输入的故判错。24.当输入为5-1011-95-7时,输出的第二行为“7”。()n=5,所以这一段的最大字段和为n<0n<0,也只会分别执行一次。11,故判错。25.solve1(1,n)的时间复杂度为()。A.O(logn)

B.O(n)

C.O(nlogn)D.O(n!)

T(n)=2T(n/2)+1T(n)=2n−1故选B。26.solve2(1,n)的时间复杂度为()。A.O(logn)B.O(n)C.O(nlogn)D.O(n!)

T(n)=2T(n/2)+nO(nlogn)故选C。27.当输入为10-32100--4-594时,输出的第一行为()。A.13B.17C.24D.12

n=10,所以最大字段和为2100--4-594,为17。(3)粗略扫过去可以发现是加密和解密过程。28.程序总是先输出一行一个整数,再输出一行一个字符串。()根据同学的说法,可能因为空串没东西,空串凭什么不是字符串(恼)。29.对于任意不含空白字符的字符串str1,先执行程序输入0str1,得到输出的第二行记为str2;再执行程序输入1str2,输出的第二行必为str1。()既然是加密和解密,这两个必然相同。故判对。30.当输入为1SGVsbG93b3JsZA==时,输出的第二行为HelloWorld。(手动模拟,判错。31.设输入字符串长度为n,encode函数的时间复杂度为()。A.Θ,O(n)B.O(n)C.O(nlogn)

D.O(n!)

看程序,是O(n)的,故选B。32.输出的第一行为()。A.0xffB.255C.0xFFD.-1

怎么说,有的人电脑是-1有的人是255。等最后官方通知。答案是D。33.(4分)当输入为0CSP2021csp时,输出的第二行为()。A.Q1NQMjAyMWNzcAv=B.Q1NQMjAyMGNzcA==C.Q1NQMjAyMGNzcAv=D.Q1NQMjAyMWNzcA==

模拟,选D。)三、完善程序(单选题,每小题3分,共计30分)(1)(魔法数字)小H的魔法数字是法和整除运算得到4。给定n,他希望用若干个4进行若干次加法、减n。但由于小H计算能力有限,计算过程中只能出现不超过M=10000

的正整数。求至少可能用到多少个4。例如,当n=2时,有2=(4+4)/4,用到了3个4,是最优方案。试补全程序。本题类似dijkstra,每次选择已经确定最小操作的数字来转移到其他数字。而vis记录已经确定不会再更改操作数的数。34.①处应填()A.F[4]=0B.F[1]=4C.F[1]=2D.F[4]=1首先4需要的操作数是1,1需要的是2。对于程序来说,都是小操作数转移到大操作数。故选D,35.②处应填()A.!Vis[n]C.F[M]==INT_MAX

B.rD.F[n]==INT_MAX

结束掉件首先肯定是n已经算出来了。但r似乎对本题没有任何影响……当Fn有值时也不一定是最优的,只有当Fn作为可以去转移别人的时候才是最优的。故选A。36.③处应填()A.F[i]==rC.F[i]B.!Vis[i]&&F[i]==rD.!Vis[i]&&F[i]这题真的很像dijkstra,选择一个没转移过的但又不会再被转移的数。选D。37.④处应填()A.F[i]两个数转移到新的数,只有当这两个数都是最优的时候,才能保证本次转移不会白转移(指其中一个数再更新本次转移作废)。故选C。(2)(RMQ区间最值问题)给定序列a1,...,an和m次询问,每次询问给定求max{a1,...,an}。为了解决该问题,有一个算法叫theMethodofFourRussians,其时间复杂度为O(n+m),步骤如下:l,r,建立Cartesian(笛卡尔)树,将问题转化为树上的LCA(最近公共祖先)问题。对于LCA问题,可以考虑其Euler序(即按照DFS过程,经过所有点,环游回根的序列),即求Euler序列上两点间一个新的RMQ问题。注意新的问题为±1RMQ,即相邻两点的深度差一定为1。下面解决这个±1RMQ问题,“序列”指Euler序列:b个分为一大块,使用ST表设t为Euler序列长度。取b=⌈log2t/2⌉。将序列每(倍增表)处理大块间的RMQ问题,复杂度O(t/blogt)=O(n)。2b−1种,(重点)对于一个块内的RMQ问题,也需要O(1)的算法。由于差分数组可以预处理出所有情况下的最值位置,预处理复杂度O(b2b),不超过O(n)。最终,对于一个查询,可以转化为中间整的大块的RMQ问题,以及两端块内的RMQ问题。试补全程序。38.①处应填()A.p->son[0]=S[top--]C.S[top--]->son[0]=p

B.p->son[1]=S[top--]D.S[top--]->son[1]=p

这部分是在建笛卡尔树,笛卡尔树就是对于序列区间然后再跑(l,r),选取最大值x做为这区间的根,(l,x−1)和(x+1,r),再和这两个区间的根连边。可以用单调栈来解决。对于栈顶小于当前元素的情况,显然可以不断弹出,使当前元素找到他最大的左二子。故38题选A。39.②处应填()A.p->son[0]=S[top]C.S[top]->son[0]=p

B.p->son[1]=S[top]D.S[top]->son[1]=p

而上述操作结束后,栈顶的元素就比当前元素大,所以可以先把栈顶的右儿子设为当前元素。若后面出现更大的也会覆盖掉。故39题选D。40.③处应填()A.x->depdepC.x->dep>y->dep

B.xD.x->valval

其实在建完笛卡尔树后,val就没有用处了。这部分的min是在处理st的时候用的,所以是考虑深度。另外都min了不可能去操作max的方法吧((故选A。41.④处应填()A.A[i*b+j-1]==A[i*b+j]->son[0]B.A[i*b+j]->valvalC.A[i*b+j]==A[i*b+j-1]->son[1]D.A[i*b+j]->depdep因为只有+1和−1两种情况,所以按照题目说法,这里的二进制也是表示这个,用来存储本块内的情况。故选D。42.⑤处应填()A.v+=(S>>i&1)?-1:1B.v+=(S>>i&1)?1:-1C.v+=(S>>(i-1)&1)?1:-1D.v+=(S>>(i-1)&1)?-1:1这里是预处理出块内所有的2b−1种情况,方便到时候O(1))算。+1。因为刚刚是后者小于前者时为1。所以为1的时候应该−1,反之另外注意一下i是从1开始的。故选D。43.⑥处应填()A.(Dif[p]>>(r-p*b))&((1<<(r-l))-1)B.Dif[p]

C.(Dif[p]>>(l-p*b))&((1<<(r-l))-1)

D.(Dif[p]>>((p+1)*b-r))&((1<<(r-l+1))-1)

对于一个块内的查询(l,r)。这里的S是要确认本区间的状态。而刚刚的Dif已经预处理好了,p是块的位置。所以选C。

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- efsc.cn 版权所有 赣ICP备2024042792号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务