2023年_CSP-S1初赛试卷

__SECTIONS__:[{"name": "单选题", "count": 15}, {"name": "阅读程序", "count": 18}, {"name": "完善程序", "count": 10}] 从PDF导入：2023年_CSP-S _初赛试卷

C++ 120分钟 总分 99.0 43 题
试卷题目预览
第1题 中级 2.0分 单选
在Linux系统终端中，以下哪个命令用于创建一个新的目录？（ ）
A. newdir
B. mkdir
C. create
D. mkfolder
第2题 中级 2.0分 单选
0，1，2，3，4中选取4个数字，能组成（ ）个不同四位数。（注：最小的四位数是1000，最大的四位数是9999）
A. 96
B. 18
C. 120
D. 84
第3题 中级 2.0分 单选
假设n是图的顶点的个数，m是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于m=Theta(n)的稀疏图而言，哪一项的渐近时间复杂度最小？（
A. O(m*sqrt(logn)*loglogn)
B. O(n^2+m)
C. O(n^2/logm+mlogn)
D. O(m+nlogn)
第4题 中级 2.0分 单选
假设有n根柱子，需要按照规则放置编号为1、2、3...的圆环：相邻圆环编号之和是完全平方数。当有4根柱子时，最多可以放置（ ）个圆环。
A. 7
B. 9
C. 11
D. 5
第5题 中级 2.0分 单选
以下对数据结构的表述不恰当的一项是：（ ）
A. 队列是一种先进先出（FIFO）的线性结构
B. 哈夫曼树的构造过程主要是为了实现图的深度优先搜索
C. 散列表是一种通过散列函数将关键字映射到存储位置的数据结构
D. 二叉树是一种每个结点最多有两个子结点的树结构
第6题 中级 2.0分 单选
以下连通无向图中，（ ）一定可以用不超过两种颜色进行染色。
A. 完全三叉树
B. 平面图
C. 边双连通图
D. 欧拉图
第7题 中级 2.0分 单选
序列ABCAAAABA和ABABCBABA的最长公共子序列长度为（ ）。
A. 4
B. 5
C. 6
D. 7
第8题 中级 2.0分 单选
掷骰子游戏：第一次掷x点得2x元，第二次掷y点，若y=x则失去2x元，若y不等于x则保留2x元。收益的平均值是多少？（ ）
A. 7元
B. 35/6元
C. 16/3元
D. 19/3元
第9题 中级 2.0分 单选
C++代码：int a=5,b=3,c=4; bool res=a&b||c^b&&a|c; res的值是？（ ）
A. true
B. false
C. 1
D. 0
第10题 中级 2.0分 单选
快速排序对已排序数组，选择第一个元素作为基准，时间复杂度是？（ ）
A. 表现最好
B. O(nlogn)
C. O(n^2)
D. 无法排序
第11题 中级 2.0分 单选
将main.cpp编译为main可执行文件的命令是？（ ）
A. g++ -o main main.cpp
B. g++ -o main.cpp main
C. g++ main -o main.cpp
D. g++ main.cpp -o main.cpp
第12题 中级 2.0分 单选
哪种树一定只有一个重心？（ ）
A. 4个结点的树
B. 6个结点的树
C. 7个结点的树
D. 8个结点的树
第13题 中级 2.0分 单选
有向图6个顶点无拓扑序，删除几条边可使其有拓扑序？（ ）
A. 1
B. 2
C. 3
D. 4
第14题 中级 2.0分 单选
十六进制100到1A0中，关于f的不动点为9的自然数个数是？（ ）
A. 10
B. 11
C. 12
D. 13
第15题 中级 2.0分 单选
递归计算x^n的时间复杂度是？（ ）（T(n)=2T(n/2)）
A. O(n)
B. O(1)
C. O(logn)
D. O(nlogn)
第16题 中级 1.5分 判断
当输入非零时，输出一定不为零。（ ）
T. 正确
F. 错误
第17题 中级 1.5分 判断
（2分）将f函数的输入参数的类型改为unsigned int，程序的输出不变。（ ）
T. 正确
F. 错误
第18题 中级 1.5分 判断
当输入为65535时，输出为63。（ ）
T. 正确
F. 错误
第19题 中级 1.5分 判断
当输入为1时，输出为64。（ ）
T. 正确
F. 错误
第20题 中级 3.0分 单选
当输入为512时，输出为（ ）。
A. 33280
B. 33410
C. 33106
D. 33346
第21题 中级 3.0分 单选
当输入为64时，执行完第5行后x的值为（ ）。
A. 8256
B. 4130
C. 4128
D. 4160
第22题 中级 1.5分 判断
将第15行删去，输出不变。（ ）
T. 正确
F. 错误
第23题 中级 1.5分 判断
当输入为10时，输出的第一行大于第二行。（ ）
T. 正确
F. 错误
第24题 中级 1.5分 判断
（2分）当输入为1000时，输出的第一行与第二行相等。（ ）
T. 正确
F. 错误
第25题 中级 3.0分 单选
solve1(n)的时间复杂度为（ ）。
A. Theta(nlog^2 n)
B. Theta(n)
C. Theta(nlogn)
D. Theta(nloglogn)
第26题 中级 3.0分 单选
solve2(n)的时间复杂度为（ ）。
A. Theta(n^2)
B. Theta(n)
C. Theta(nlogn)
D. Theta(n*sqrt(n))
第27题 中级 3.0分 单选
输入为5时，输出的第二行为（ ）。
A. 20
B. 21
C. 22
D. 23
第28题 中级 1.5分 判断
将第24行的m改为m-1，输出有可能不变，而剩下情况为少1。（ ）
T. 正确
F. 错误
第29题 中级 1.5分 判断
将第22行的g+(h-g)/2改为(h+g)>>1，输出不变。（ ）
T. 正确
F. 错误
第30题 中级 1.5分 判断
当输入为5 7 2 -4 5 1 -3，输出为5。（ ）
T. 正确
F. 错误
第31题 中级 3.0分 单选
设a数组中最大值减最小值加1为A，则f函数的时间复杂度为（ ）。
A. Theta(nlogA)
B. Theta(n^2 logA)
C. Theta(nlog(nA))
D. Theta(nlogn)
第32题 中级 3.0分 单选
将第10行中的>替换为>=，原输出与现输出的大小关系为（ ）。
A. 一定小于
B. 一定小于等于且不一定小于
C. 一定大于等于且不一定大于
D. 以上三种情况都不对
第33题 中级 3.0分 单选
当输入为5 8 2 -5 3 8 -12时，输出为（ ）。
A. 13
B. 14
C. 8
D. 15
第34题 中级 3.0分 单选
第k小路径问题，①处应填（ ）
A. k>=f[u]
B. k<=f[u]
C. k>f[u]
D. k
第35题 中级 3.0分 单选
②处应填（ ）
A. deg[v]==1
B. deg[v]==0
C. deg[v]>1
D. deg[v]>0
第36题 中级 3.0分 单选
③处应填（ ）
A. std::min(f[u]+f[v],LIM)
B. std::min(f[u]+f[v]+1,LIM)
C. std::min(f[u]*f[v],LIM)
D. std::min(f[u]*(f[v]+1),LIM)
第37题 中级 3.0分 单选
④处应填（ ）
A. u!=-1
B. !E[u].empty()
C. k>0
D. k>1
第38题 中级 3.0分 单选
⑤处应填（ ）
A. k+=f[u]
B. k-=f[u]
C. --k
D. ++k
第39题 中级 3.0分 单选
最大值之和问题，①处应填（ ）
A. pre[i]=std::max(pre[i-1],a[i-1])
B. pre[i+1]=std::max(pre[i],pre[i+1])
C. pre[i]=std::max(pre[i-1],a[i])
D. pre[i]=std::max(pre[i],pre[i-1])
第40题 中级 3.0分 单选
②处应填（ ）
A. a[j]
B. a[j]
C. pre[j-mid]
D. pre[j-mid]>max
第41题 中级 3.0分 单选
③处应填（ ）
A. (long long)(j-mid)*max
B. (long long)(j-mid)*(i-l)*max
C. sum[j-mid]
D. sum[j-mid]*(i-l)
第42题 中级 3.0分 单选
④处应填（ ）
A. (long long)(r-j)*max
B. (long long)(r-j)*(mid-i)*max
C. sum[r-mid]-sum[j-mid]
D. (sum[r-mid]-sum[j-mid])*(mid-i)
第43题 中级 3.0分 单选
⑤处应填（ ）
A. solve(0,n)
B. solve(0,n-1)
C. solve(1,n)
D. solve(1,n-1)
💬