2022 CCF非专业级别软件能力认证第一轮

（CSP-S1）提高级C++语言试题及答案

认证时间：2022年9月18日14:30-16:30

一、单项选择

1.答案：B

解析：考查Linux命令，其中，“cd”为切换目录命令。

2.答案：A

解析：考查Linux下的time命令。其中，“real”为实际时间，“user”为用户CPU时间，“sys”为系统CPU时间。

3.答案：D

解析：考查栈的基本操作。

4.答案：C

解析：考查排序的时间复杂度。

5.答案：A

解析：考查基数排序。

6.答案：B

解析：计算机内存存储的基本知识。

7.答案：C

解析：对于多叉树，前序遍历为先遍历根节点，然后对子节点按照从左至右的顺序依次访问。

8.答案：B

解析：强连通图是指在有向图中，任意两点之间都存在路径。

9.答案：D

解析：考查欧拉回路以及排列计算。

10.答案：A

解析：组合数学计算题。

11.答案：C

解析：考查乘法原理。

12.答案：D

解析：哈希表冲突解决问题。

13.答案：B

解析：考试原题有错误，“j=0”改为“j=1”。

考查时间复杂度。

14.答案：B

解析：线性序列找最大值/最小值问题。

15.答案：B

解析：递归模拟计算题。

二、阅读程序

（1）

16. 答案：T

解析：字符串匹配。

17. 答案：F

解析：第18行，下标i是从0开始的。

18. 答案：T

解析：模拟即可。

19. 答案：D

解析：考查最坏情况下时间复杂度评估，代入一个特例。

20. 答案：A

解析：在字符串a中找字符串b第一次出现的位置。

21. 答案：B

解析：模拟即可。

（2）

这道题是k进制下的基数排序。

22. 答案：F

解析：基数排序是稳定的排序算法。

23. 答案：F

解析：空间复杂度是O(n+k)。

24. 答案：T

解析：考查时间复杂度的评估。

25. 答案：D

解析：模拟即可。

26. 答案：D

解析：运算次数还和n有关。

27. 答案：C

解析：代入一个特例。

（3）

28. 答案：T

解析：考查时间复杂度评估。

29. 答案：F

解析：考查语法知识。

30. 答案：T

解析：根据程序的含义进行推导。

31. 答案：A

解析：模拟即可。

32. 答案：B

解析：模拟即可。

33. 答案：B

解析：模拟即可。

三、完善程序

（1）

34. 答案：C

解析：记录合并数组的当前位置的下标。

35. 答案：B

解析：比较待归并的两个数组的当前元素的大小。

36. 答案：C

解析：根据程序明确left1和right1的含义。

37. 答案：C

解析：确定a2数组对应的下标。

38. 答案：A

解析：确定a1数组对应的下标。

（2）

39. 答案：A

解析：根据题意作答，容器2中的水倒入容器1。

40. 答案：C

解析：容器1中的水倒入容器2。

41. 答案：A

解析：判断是否已有C升水。

42. 答案：A

解析：判断接下来是否将容器2中的水倒入容器1。

43. 答案：C

解析：判断接下来是否将容器1中的水倒入容器2。