该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

CSP-S真题2021

考生注意事项：

• 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
• 考试时间2小时，满分100分。

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

1. 在 Linux 系统终端中，用于列出当前目录下所含的文件和子目录的命令为（ ）。

{{ select(1) }}

• ls
• cd
• cp
• all

2. 二进制数 $00101010_2$ 和 $00010110_2$的和为（）。

{{ select(2) }}

• 00111100
• 01000000
• 00111100
• 01000010

3. 在程序运行过程中，如果递归调用的层数过多，可能会由于（ ）引发错误。

{{ select(3) }}

• 系统分配的栈空间溢出
• 系统分配的队列空间溢出
• 系统分配的链表空间溢出
• 系统分配的堆空间溢出

4. 以下排序方法中，（ ）是不稳定的。

{{ select(4) }}

• 插入排序
• 冒泡排序
• 堆排序
• 归并排序

5. 以比较为基本运算，对于$2n$个数，同时找到最大值和最小值，最坏情况下需要的最小的比 较次数为（ ）。

{{ select(5) }}

• 4n−2
• 3n+1
• 3n−2
• 2n+1

6. 现有一个地址区间为 0∼10 的哈希表，对于出现冲突情况，会往后找第一个空的地址存储 （到 10冲突了就从 0 开始往后），现在要依次存储 (0,1,2，3,4,5,6,7)，哈希函数为$h(x)=x^2mod11$。请问 7存储在哈希表哪个地址中（ ）。

{{ select(6) }}

• 5
• 6
• 7
• 8

7. $G$是一个非连通简单无向图（没有自环和重边），共有 $36$条边，则该图至少有（ ）个点。

{{ select(7) }}

• 8
• 9
• 10
• 11

8. 令根结点的高度为 1，则一棵含有 2021个结点的二叉树的高度至少为（ ）。

{{ select(8) }}

• 10
• 11
• 12
• 2021

9. 前序遍历和中序遍历相同的二叉树为且仅为（ ）

{{ select(9) }}

• 只有1个点的二叉树
• 根结点没有左子树的二叉树
• 非叶子结点只有左子树的二叉树
• 非叶子结点只有右子树的二叉树

10. 定义一种字符串操作为交换相邻两个字符。将 DACFEB 变为 ABCDEF最少需要 ( ) 次上述操作。

{{ select(10) }}

• 7
• 8
• 9
• 6

11. 有如下递归代码

solve(t, n):
  if t=1 return 1
  else return 5*solve(t-1,n) mod n

则 solve(23,23) 的结果为（ ）。

{{ select(11) }}

• 1
• 7
• 12
• 22

12. 斐波那契数列的定义为： $F_1=1，F_2=1，F_n=F_{n−1}+F_{n−2} (n≥3)$ 。现在用如下程序来计算斐波那契数列的第 n 项，其时间复杂度为（ ）。

F(n):
  if n<=2 return 1
  else return F(n-1) + F(n-2)

{{ select(12) }}

• $O(n)$
• $O(n^2)$
• $O(2^n)$
• $O(nlogn)$

13.有 8个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两个苹果，一共有（ ）种方案。

{{ select(13) }}

• 36
• 48
• 54
• 64

14. 设一个三位数 n=abc，a,b,c均为 1∼9之间的整数，若以 a、 b、 c作为三角形的三条边可以构成等腰三角形（包括等边），则这样的 n 有（ ）个。

{{ select(14) }}

• 81
• 120
• 165
• 216

15. 有如下的有向图，节点为 A,B,⋯,J, 其中每条边的长度都标在图中。则节点 A到节点 J的最短路径长度为（ ）。

{{ select(15) }}

• 16
• 19
• 20
• 22

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特

殊说明外，判断题1.5分，选择题3分，共计40分）

（1）

16. 将第 21 行中 t 的类型声明从 int 改为 double， 不会 影响程序运行的结果。（）

{{ select(16) }}

• 正确
• 错误

17. 将第 26、27 行中的 / sqrt(t) / 2替换为/ 2 / sqrt(t)，不会影响程序运行的结果。（ ）

{{ select(17) }}

• 正确
• 错误

18. 将第 28 行中的 x * x 改成 sq(x)、y * y 改成 sq(y)，不会影响程序运行的结果。（ ）

{{ select(18) }}

• 正确
• 错误

19. （2 分） 当输入为 0 0 0 1 1 0 0 1 时，输出为 1.3090

{{ select(19) }}

• 正确
• 错误

20. 当输入为 1 1 1 1 1 1 1 2 时，输出为（ ）。

{{ select(20) }}

• 3.1416
• 6.2832
• 4.7124
• 4.1888

21. （2.5 分）这段代码的含义为（ ）。

{{ select(21) }}

• 求圆的面积并
• 求球的体积并
• 求球的体积交
• 求椭球的体积并

（2）

22. 程序总是会正常执行并输出两行两个相等的数。（ ）

{{ select(22) }}

• 正确
• 错误

23. 第 28 行与第 38 行分别有可能执行两次及以上。（ ）

{{ select(23) }}

• 正确
• 错误

24. 当输入为 5 -10 11 -9 5 -7 时，输出的第二行为 7。( )

{{ select(24) }}

• 正确
• 错误

25. solve1(1, n) 的时间复杂度为（ ）。

{{ select(25) }}

• $O(logn)$
• $O(n)$
• $O(nlogn)$
• $O(n^2)$

26. solve2(1, n) 的时间复杂度为（ ）。

{{ select(26) }}

• $O(logn)$
• $O(n)$
• $O(nlogn)$
• $O(n^2)$

27. 当输入为 10 -3 2 10 0 -8 9 -4 -5 9 4 时，输出的第一行为（ ）。

{{ select(27) }}

• 13
• 17
• 24
• 12

（3）

28. 程序总是先输出 一行 一个整数，再输出 一行 一个字符串。（ ）

{{ select(28) }}

• 正确
• 错误

29. 对于任意不含空白字符的字符串 str1，先执行程序输入0 str1，得到输出的第二行记为 str2 再执行程序输入1 str2，输出的第二行必为 str1。（ ）

{{ select(29) }}

• 正确
• 错误

30. 当输入为1 SGVsbG93b3JsZA==时，输出的第二行为HelloWorld。( )

{{ select(30) }}

• 正确
• 错误

31. 设输入字符串长度为 $n$，encode 函数的时间复杂度为（ ）。

{{ select(31) }}

• $O(sqrt(n))$
• $O(n)$
• $O(nlogn)$
• $O(n^2)$

32. 输出的第一行为（ ）。

{{ select(32) }}

• 0xff
• 255
• 0xFF
• -1

33. （4 分） 当输入为 0 CSP2021csp 时，输出的第二行为（ ）。

{{ select(33) }}

• Q1NQMjAyMWNzcAv=
• Q1NQMjAyMGNzcA==
• Q1NQMjAyMGNzcAv=
• Q1NQMjAyMWNzcA==

三、完善程序

(1) （魔法数字） 小 H 的魔法数字是 4。给定n， 他希望用若干个4进行若干次加法、减法和整除运算得到 n。但由于小 H 计算能力有限，计算过程中只能出现不超过 N<=10000 的正整数。求至少可能用到多少个 4。

例如，当n=2 时，有 2=(4+4)/4，用到了 3 个 4，是最优方案。

34. ①处应填（ ）

{{ select(34) }}

• F[4] = 0
• F[1] = 4
• F[1] = 2
• F[4] = 1

35. ②处应填（ ）

{{ select(35) }}

• !Vis[n]
• r < n
• F[M] == INT_MAX
• F[n] == INT_MAX

36. ③处应填（ ）

{{ select(36) }}

• F[i] == r
• !Vis[i] && F[i] == r
• F[i] < F[x]
• !Vis[i] && F[i] < F[x]

37. ④处应填（ ）

{{ select(37) }}

• F[i] < F[x]
• F[i]<=r
• Vis[i]
• i <= x

38. ①处应填（ ）

{{ select(38) }}

• p->son[0] = S[top--]
• p->son[1] = S[top--]
• S[top--]->son[0] = p
• S[top--]->son[1] = p

39. ②处应填（ ）

{{ select(39) }}

• p->son[0] = S[top]
• p->son[1] = S[top]
• S[top]->son[0] = p
• S[top]->son[1] = p

40. ③处应填（ ）

{{ select(40) }}

• x->dep < y->dep
• x < y
• x->dep > y->dep
• x->val < y->val

41. ④处应填（ ）

{{ select(41) }}

• A[i * b + j - 1] == A[i * b + j]->son[0]
• A[i * b + j]->val < A[i * b + j - 1]->val
• A[i * b + j] == A[i * b + j - 1]->son[1]
• A[i * b + j]->dep < A[i * b + j - 1]->dep

42. ⑤处应填（ ）

{{ select(42) }}

• v += (S >> i & 1) ? -1 : 1
• v += (S >> i & 1) ? 1 : -1
• v += (S >> (i - 1) & 1) ? 1 : -1
• v += (S >> (i - 1) & 1) ? -1 : 1

43. ⑥处应填（ ）

{{ select(43) }}

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