2021年 CSP-S 第一轮初赛真题
您的姓名：
一、单项选择题
（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）
1.在 Linux 系统终端中，用于列出当前目录下所含的文件和子目录的命令为（ ）。
A、ls
B、cd
C、cp
D、all
2.二进制数 00101010_2 和 00010110_2 的和为（ ）。
A、00111100₂
B、01000000₂
C、00111100₂
D、01000010₂
3.在程序运行过程中，如果递归调用的层数过多，可能会由于（ ）引发错误。
A、系统分配的栈空间溢出
B、系统分配的队列空间溢出
C、系统分配的链表空间溢出
D、系统分配的堆空间溢出
4.以下排序方法中，（ ）是不稳定的。
A、插入排序
B、冒泡排序
C、堆排序
D、归并排序
5.以比较为基本运算，对于 2n 个数，同时找到最大值和最小值，最坏情况下需要的最小的比较次数为（ ）。
A、4n-2
B、3n+1
C、3n-2
D、2n+1
6.现有一个地址区间为 0～10 的哈希表，对于出现冲突情况，会往后找第一个空的地址存储（到 10 冲突了就从 0 开始往后），现在要依次存储（0，1，2，3，4，5，6，7），哈希函数为 h(x) = x^2 mod 11。请问 7 存储在哈希表哪个地址中（ ）。
A、5
B、6
C、7
D、8
7.G 是一个非连通简单无向图（没有自环和重边），共有 36 条边，则该图至少有（ ）个点。
A、8
B、9
C、10
D、11
8.令根结点的高度为 1，则一棵含有 2021 个结点的二叉树的高度至少为（ ）。
A、10
B、11
C、12
D、2021
9.前序遍历和中序遍历相同的二叉树为且仅为（ ）。
A、只有 1 个点的二叉树
B、根结点没有左子树的二叉树
C、非叶子结点只有左子树的二叉树
D、非叶子结点只有右子树的二叉树
10.定义一种字符串操作为交换相邻两个字符。将“DACFEB”变为“ABCDEF”最少需要（ ）次上述操作。
A、7
B、8
C、9
D、6
11.有如下递归代码
则 solve(23,23) 的结果为（ ）。（）
A、1
B、7
C、12
D、22
12.斐波那契数列定义为：F1=1, F2=1, Fn = Fn-1+Fn-2 (n>=3)。现在用如下程序计算第 n 项，其时间复杂度为（ ）。
A、O(n)
B、O(n²)
C、O(2ⁿ)
D、O(n log n)
13.有 8 个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两个苹果，一共有（ ）种方案。
A、36
B、48
C、54
D、64
14.设一个三位数 n=a,b,c的平均数，a、b、c 均为 1～9 之间的整数，若以 a、b、c 作为三角形的三条边可以构成等腰三角形（包括等边），则这样的 n 有（ ）个。
A、81
B、120
C、165
D、216
15.有如下的有向图，节点为 A、B、…、J，其中每条边的长度都标在图中。则节点 A 到节点 J 的最短路径长度为（ ）。
A、16
B、19
C、20
D、22
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）
1）
16.将第 21 行中 t 的类型声明从 int 改为 double，不会影响程序运行的结果。
对
错
17.将第 26、27 行中的“/ sqrt(t) / 2”替换为“/ 2 / sqrt(t)”，不会影响程序运行的结果。
对
错
18.将第 28 行中的“x * x”改成“sq(x)”、“y * y”改成“sq(y)”，不会影响程序运行的结果。
对
错
19.（2 分）当输入为“0 0 0 1 1 0 0 1”时，输出为“1.3090”。
对
错
20.当输入为“1 1 1 1 1 1 1 2”时，输出为（ ）。
A、“3.1416”
B、“6.2832”
C、“4.7124”
D、“4.1888”
21.（2.5 分）这段代码的含义为（ ）。
A、求圆的面积并
B、求球的体积并
C、求球的体积交
D、求椭球的体积并
2）
假设输入的所有数的绝对值都不超过 1000，完成下面的判断题和单选题：
22.程序总是会正常执行并输出两行两个相等的数。
对
错
23.第 28 行与第 38 行分别有可能执行两次及以上。
对
错
24.当输入为“5 -10 11 -9 5 -7”时，输出的第二行为“7”。
对
错
25.solve1(1,n) 的时间复杂度为（ ）。
A、Θ(log n)
B、Θ(n)
C、Θ(n log n)
D、Θ(n!)
26.solve2(1,n) 的时间复杂度为（ ）。
A、Θ(log n)
B、Θ(n)
C、Θ(n log n)
D、Θ(n!)
27.当输入为“10 -3 2 10 0 -8 9 -4 -5 9 4”时，输出的第一行为（ ）。
A、“13”
B、“17”
C、“24”
D、“12”
3)
假设输入总是合法的（一个整数和一个不含空白字符的字符串，用空格隔开），完成下面的判断题和单选题：
28.程序总是先输出一行一个整数，再输出一行一个字符串。
对
错
29.对于任意不含空白字符的字符串 str1，先执行程序输入“0 str1”，得到输出的第二行记为 str2；再执行程序输入“1 str2”，输出的第二行必为 str1。
对
错
30.当输入为“1 SGVsbG93b3JsZA==”时，输出的第二行为“HelloWorld”。
对
错
31.设输入字符串长度为 n，encode 函数的时间复杂度为（ ）。
A、Θ(√n)
B、Θ(n)
C、Θ(n log n)
D、Θ(n!)
32.输出的第一行为（ ）。
A、“0xff”
B、“255”
C、“0xFF”
D、“-1”
33.（4 分）当输入为“0 CSP2021csp”时，输出的第二行为（ ）。
A、“Q1NQMjAyMWNzcAv=”
B、“Q1NQMjAyMGNzcA==”
C、“Q1NQMjAyMGNzcAv=”
D、“Q1NQMjAyMWNzcA==”
三、完善程序
（单选题，每小题 3 分，共计 30 分）
小 H 的魔法数字是 4。给定 n，他希望用若干个 4 进行若干次加法、减法和整除运算得到 n。但由于小 H 计算能力有限，计算过程中只能出现不超过 M=10000 的正整数。求至少可能用到多少个 4。
例如，当 n=2 时，有 2=(4+4)/4，用到了 3 个 4，是最优方案。
1）
34.①处应填（ ）
A、F[4] = 0
B、F[1] = 4
C、F[1] = 2
D、F[4] = 1
35.②处应填（ ）
A、!Vis[n]
B、r ＜ n
C、F[M] == INT_MAX
D、F[n] == INT_MAX
36.③处应填（ ）
A、F[i] == r
B、!Vis[i] && F[i] == r
C、F[i] ＜ F[x]
D、!Vis[i] ＆＆ F[i] ＜ F[x]
37.④处应填（ ）
A、F[i] ＜ F[x]
B、F[i] ＜= r
C、Vis[i]
D、i ＜= x
38.①处应填（ ）
A、p->son[0] = S[top--]
B、p->son[1] = S[top--]
C、S[top--]-＞son[0] = p
D、S[top--]->son[1] = p
39.②处应填（ ）
A、p->son[0] = S[top]
B、p-＞son[1] = S[top]
C、S[top]->son[0] = p
D、S[top]->son[1] = p
40.③处应填（ ）
A、x-＞dep ＜ y-＞dep
B、x ＜ y
C、x->dep > y->dep
D、x->val ＜ y->val
41.④处应填（ ）
A、A[i * b + j - 1] == A[i * b + j]->son[0]
B、A[i * b + j]->val ＜ A[i * b + j - 1]->val
C、A[i * b + j] == A[i * b + j - 1]-＞son[1]
D、A[i * b + j]->dep ＜ A[i * b + j - 1]->dep
42.⑤处应填（ ）
A、v += (S ＞＞ i ＆ 1) ? -1 : 1
B、v += (S >> i & 1) ? 1 : -1
C、v += (S >> (i - 1) & 1) ? 1 : -1
D、v += (S >> (i - 1) & 1) ? -1 : 1
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)
关闭
更多问卷
复制此问卷