2021 CSP-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。