(CSP-J) 入门级 C++ 语言试题

认证时间：2025 年 9 月 20 日 09:30-11:30

考生注意事项：

• 试题共有 9 页，答题纸共有 1 页，满分 100 分，请在答题纸上作答，写在试题纸上的一律无效。
• 不得使用任何电子设备（计算器、手机、电子词典、电子手表等）或查阅任何书籍资料。

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

1. 一个 32 位无符号整数可以表示的最大值，最接近下列哪个选项？（ ） {{ select(2) }}

• $4×10^9$
• $3×10^{10}$
• $2×10^9$
• $2×10^{10}$

2. 在 C++ 中，执行int x = 25; cout << (x & (x-1));后，输出的结果是？（ ） {{ select(2) }}

• 255
• 254
• 128
• 0

3. 函数calc(n)定义如下，则calc(5)的返回值是多少？（）

int calc(int n) {
    if (n == 1) return 1;
    if (n == 2) return 1;
    else return calc(n / 2 + 1) + calc(n - 2);
}

{{ select(3) }}

• 5
• 6
• 7
• 8

4. 用 5 个权值 19、15、28、25、10 构造一棵二叉树，该树的带权路径长度是多少？（） {{ select(4) }}

• 176
• 182
• 196
• 206

5. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于（） {{ select(5) }}

• 顶点数
• 边数
• 顶点数 + 边数
• 顶点数 × 2

6. 从 5 位男生和 4 位女生中选出 4 人组成一个学习小组，要求学习小组中男生和女生都有，有多少种不同的选法？（） {{ select(6) }}

• 126
• 121
• 128
• 109

7. 假设 a，b，c 都是布尔变量，逻辑表达式(a && b) || (!c && a)的值与下列哪个表达式不始终相等？（） {{ select(7) }}

• a && (b || !c)
• (a ||!c) && (b ||!c) && (a || a)
• a && (!b ∣∣ c)
• !(!a ||!b) || (a && !c)

8. 已知f(0)=1，f(1)=1 并且对于所有n≥2有f(n)=f(n-1)+f(n-2)%7，那么f(2025)的值是多少？（） {{ select(8) }}

• 2
• 4
• 5
• 6

9. 下列关于 C++ string 类的说法，正确的是？（） {{ select(9) }}

• string`对象的长度在创建后不能改变。
• 可以用+运算符直接连接一个string对象和一个char类型的字符。
• string的length()和size()`方法返回的值可能不同。
• string 对象必须以'\0'结尾，且这个结尾计入length()`。

10. 考虑以下 C++ 函数：

void solve(int &a, int &b) {
    a = a + b;
    b = a - b;
    a = a - b;
}
int main() {
    int x = 5, y = 10;
    solve(x, y);
}

在main函数调用solve后，x 和 y 的值分别是？（） {{ select(10) }}

• 5，10
• 10，5
• 10，10
• 5，5

11. 一个8 x 8的棋盘，左上角坐标为（1，1），一个机器人从 (1,1) 出发，每次只能向右或向下走一格，要到达 (4,5)，有多少种不同的路径？（） {{ select(11) }}

• 28
• 35
• 56
• 70

12. 某同学用冒泡排序对数组 {6,1,5,2,4} 进行升序排序，请问需要进行多少次元素交换？（） {{ select(12) }}

• 5
• 6
• 7
• 8

13. 十进制数 720₁₀和八进制数 270₈的和用十六进制表示是多少？（） {{ select(13) }}

• 388₁₆
• 3DE₁₆
• 288₁₆
• 990₁₆

14. 一棵包含 1000 个结点的完全二叉树，其叶子结点的数量是多少？（） {{ select(14) }}

• 499
• 512
• 500
• 501

15. 给定一个初始为空的整数栈 S 和一个空的队列 P，我们按顺序处理输入的数据队列 A：7,5,8,3,1,4,2。对于队列 A 中的每一个数，执行以下规则：如果该数是奇数，则将其压入栈 S；如果该数是偶数，且栈 S 非空，则弹出一个栈顶元素，并加入到队列 P 的末尾；如果该数是偶数，且栈 S 为空，则不进行任何操作。当队列 A 中的所有数都处理完毕后，队列 P 的内容是什么？（） {{ select(15) }}

• 5，1，3
• 7，5，3
• 3，1，5
• 5，1，3，7

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填 ×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

(1)

• 判断题 16.（1 分）当输入为 2 时，程序并不会执行第 16 行的判断语句。（） {{ select(16) }}

• 对
• 错

17. 将第 16 行中的 “&& gcd(j,k)==1” 删去不会影响程序运行结果。（） {{ select(17) }}

• 对
• 错

18. 当输入的n≥3的时候，程序总是输出一个正整数。（） {{ select(18) }}

• 对
• 错

• 单选题

19. 将第 7 行的 “gcd(b,a%b)” 改为 “gcd(a,a%b)” 后，程序可能出现的问题是（）。 {{ select(19) }}

• 输出的答案大于原答案。
• 输出的答案小于原答案。
• 程序有可能陷入死循环。
• 可能发生整型溢出问题。

20. 当输入为 8 时，输出为（ ）。 {{ select(20) }}

• 37
• 42
• 35
• 25

21. 调用gcd(36,62)会返回（）。 {{ select(21) }}

• 6
• 252
• 3
• 2

(2)

• 判断题

22. 当输入为 “3 1 3 2 1” 时，输出结果为 2。（） {{ select(22) }}

• 对
• 错

23. 即使输入的 n 为五位数，输出的答案一定小于等于 n，大于等于 1。（） {{ select(23) }}

• 对
• 错

24. 将第 14 行的 “n = unique(a+1,a+n+1)-a-1;” 删去后，有可能出现与原代码不同的输出结果。（） {{ select(24) }}

• 对
• 错

• 单选题

25. 假设输入的 a 数组和 k 均为正整数，执行第 18 行代码时，一定满足的条件不包括（）。 {{ select(25) }}

• j <= i
• a[i] - a[j] > k
• j <= n
• a[j] < a[i]

26. 当输入为 “100 10 1 2 … 100” 时，输出为（ ）。 {{ select(26) }}

• 34
• 100
• 50
• 33

27. 假设输入的 a 数组和 k 均为正整数，但有可能出现的问题有，则若删去第 13 行的std::sort(a+1,a+n+1);程序（ ）。 {{ select(27) }}

• 输出的答案比原答案更大
• 输出的答案比原答案更小
• 出现死循环行为
• 以上均可能发生

(3)

• 判断题

28. 当输入 “4 1 2 3 4 1 3 2 2” 时，输出为 2。（） {{ select(28) }}

• 对
• 错

29. 当程序运行完毕后，对所有的1<= i , j<=n, 都一定有 f[i][j] < f[n][n] 。（） {{ select(29) }}

• 对
• 错

30. 将第 18 行的 “f[i][j]=std::max(f[i][j],std::max(f[i-1][j],f[i][j-1] ));” 删除后，并不影响程序运行结果。（）。（） {{ select(30) }}

• 对
• 错

• 单选题

31. 输出的答案满足的性质有（）。 {{ select(31) }}

• 大于等于 n
• 大于等于 0
• 不一定大于等于 1
• 以上均是

32. 如果在第 16 行的循环前加上以下两行：sort(a+1,a+n+1); sort(b+1,b+n+1);，则答案会（）。 {{ select(32) }}

• 变大或不变
• 变小或不变
• 一定变大
• 不变

33. 如果输入的 a 是 {1,2,…,n}，而且 b 数组中数字均为 1~n 的正整数，则上述代码等价于下面哪个问题。（） {{ select(33) }}

• 求b数组去重后的长度
• 求b数组的最长上升子序列
• 求b数组的长度
• 求b数组的最大值

三、完善程序（单选题，每小题 3 分，共计 30 分）

(1)（字符串压缩）

行程长度编程（Run-Length Encoding）是一种无损压缩编码，用于压缩重复字符较多的字符串，以减少存储空间。假设原始字符串中不包含数字字符。压缩规则如下：

1. 如果原始字符串中一个字符连续出现 N 次（N≥2），在压缩字符串中被表示为 “字符 + 数字 N”。例如，编码 “A12” 代表 12 个连续的字符 A。
2. 如果原始字符串中一个字符只出现一次，在压缩字符串中直接表示为该字符。例如，编码 “B” 代表 1 个字符 B。

以下程序实现读取压缩字符串并输出其解码、解压后的形式。试补全程序。

34. ①处应填（） {{ select(34) }}

• i < z.length()
• i - 1 >= 0
• i + 1 < z.length()
• isdigit(z[i])

35. ②处应填（） {{ select(35) }}

• count + (z[i] - '0')
• count * 10 + (z[i] - '0')
• z[i] - '0'
• count + 1

36. ③处应填（） {{ select(36) }}

• count - 1
• count
• 10
• z[i] − '0'

37. ④处应填（） {{ select(37) }}

• z[i + 1]
• ch
• z.back()
• (char) z[i] + 1

38. ⑤处应填（） {{ select(38) }}

• i--
• i=i+2
• i++
• // 不执行任何操作

(2)（精明与糊涂）

有 N 个人，分为两类：1. 精明人：永远能正确判断其他人是精明还是糊涂；2. 糊涂人：判断不可靠，会给出随机的判断。已知精明人严格占多数，即如果精明人有 k 个，则满足k>N/2。现在需要从这 N 个人中找出至少一个精明人。你只能通过函数query(i,j)来判断，该函数的作用是：通过这两个人互相询问并给出判断，返回值为 true 表示这两个人都是精明人，否则为 false。你不能同时询问同一个人超过两次，同时，你无法关心query(i,j)的内部实现，只需要知道当且仅当这两个人都是精明人时返回 true，否则返回 false。现在有一个机会，你可以选择一个人作为 “候选人”，然后依次询问候选人与其他人的情况，从而确定候选人是否为精明人。

例如，假设有 8 个人，其中有 5 个精明人，3 个糊涂人，现在你选择候选人 i，那么只需要询问 i 和其他 7 个人各一次，根据返回结果即可判断 i 是否为精明人。

试补全程序。

39. ①处应填（） {{ select(39) }}

• 0
• 1
• N
• -1

40. ②处应填（） {{ select(40) }}

• count<0
• count==1
• count==0
• query(candidate,i)==false

41. ③处应填（） {{ select(41) }}

• query(candidate, i)==false
• query(i, candidate)==true
• query(candidate, i) == false && query(i, candidate) == false
• query(candidate, i) == false ∣∣query(i, candidate) == false

42. ④处应填（） {{ select(42) }}

• count−−
• break
• count++
• candidate=i

43. ⑤处应填（） {{ select(43) }}

• N-1
• count
• candidate
• 0