CSP-J 2025 · 入门级第一轮真题

一个 $32$ 位无符号整数可以表示的最大值，最接近下列哪个选项？（ ）

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

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

1  int calc(int n) {
2      if (n <= 1) return 1;
3      if (n % 2 == 0) return calc(n / 2) + 1;
4      else return calc(n - 1) + calc(n - 2);
5  }

用 $5$ 个权值 $10, 12, 15, 20, 25$ 构造哈夫曼树，该树的带权路径长度是多少？（ ）

在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于？（ ）

从 $5$ 位男生和 $4$ 位女生中选出 $4$ 人组成一个学习小组，要求学习小组中男生和女生都有。有多少种不同的选举方法？（ ）

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

已知 $f[0] = 1 , f[1] = 1$，并且对于所有 $n \geq 2$ 有 $f[n] = (f[n-1] + f[n-2]) \% 7$。那么 $f[2025]$ 的值是多少？（ ）

下列关于 C++ string 类的说法，正确的是？（ ）

考虑以下 C++ 函数：

1  void solve(int &a, int b) {
2      a = a + b;
3      b = a - b;
4      a = a - b;
5  }
6  int main() {
7      int x = 5, y = 10;
8      solve(x, y);
9  }

在 $main$ 函数调用 $solve$ 后，$x$ 和 $y$ 的值分别是？（ ）

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

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

十进制数 $720_{10}$ 和八进制数 $270_8$ 的和用十六进制表示是多少？（ ）

一棵包含 $1000$ 个结点的完全二叉树，其叶子结点的数量是多少？（ ）

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

1  #include <algorithm>
2  #include <cstdio>
3  #include <cstring>
4  inline int gcd(int a, int b) {
5      if (b == 0)
6      return a;
7      return gcd(b, a % b);
8  }
9  int main() {
10      int n;
11      scanf("%d", &n);
12      int ans = 0;
13      for (int i = 1; i <= n; ++i) {
14          for (int j = i + 1; j <= n; ++j) {
15              for (int k = j + 1; k <= n; ++k) {
16                  if (gcd(i, j) == 1 && gcd(j, k) == 1
17                  && gcd(i, k) == 1) {
18                      ++ans;
19                  }
20              }
21          }
22      }
23      printf("%d\n", ans);
24      return 0;
25  }

1  #include <algorithm>
2  #include <cstdio>
3  #include <cstring>
4  #define ll long long
5 
6  int n, k;
7  int a[200007];
8  int ans[200007];
9 
10  int main() {
11      scanf("%d%d", &n, &k);
12      for (int i = 1; i <= n; ++i) {
13          scanf("%d", &a[i]);
14      }
15      std::sort(a + 1, a + n + 1);
16      n = std::unique(a + 1, a + n + 1) - a - 1;
17      for (int i = 1, j = 0; i <= n; ++i) {
18          for (; j < i && a[i] - a[j + 1] > k; ++j)
19          ;
20          ans[i] = ans[j] + 1;
21      }
22      printf("%d\n", ans[n]);
23      return 0;
24  }

1  #include <algorithm>
2  #include <cstdio>
3  #include <cstring>
4  #define ll long long
5  int f[5007][5007];
6  int a[5007], b[5007];
7  int n;
8  int main(){
9      scanf("%d", &n);
10      for (int i = 1; i <= n; ++i) {
11          scanf("%d", &a[i]);
12      }
13      for (int i = 1; i <= n; ++i) {
14          scanf("%d", &b[i]);
15      }
16      for (int i = 1; i <= n; ++i) {
17          for (int j = 1; j <= n; ++j) {
18              f[i][j] = std::max(f[i][j], std::max(f[i - 1][j], f[i][j - 1]));
19              if (a[i] == b[j]) {
20                  f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1);
21              }
22          }
23      }
24      printf("%d\n", f[n][n]);
25      return 0;
26  }

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

i) 如果原始字符串中一个字符连续出现 $N$ 次（$N > 2$），在压缩字符串中它被表示为“字符 + 数字 $N$”。例如，编码 A12 代表 $12$ 个连续的字符 A。

ii) 如果原始字符串中一个字符只出现 $1$ 次，在压缩字符串中它就表示为该字符本身。例如，编码 B 代表 $1$ 个字符 B。

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

1  #include <cctype>
2  #include <iostream>
3  #include <string>
4  using namespace std;
5 
6  int main() {
7      string z;
8      cin >> z;
9      string s = "";
10 
11      for (int i = 0; i < z.length(); ) {
12          char ch = z[i];
13 
14          if (___①___ && isdigit(z[i + 1])) {
15              i++;
16              int count = 0;
17              while (i < z.length() && isdigit(z[i])) {
18                  count = ___②___;
19                  i++;
20              }
21              for (int j = 0; j < ___③___; ++j) {
22                  s += ch;
23              }
24          } else {
25              s += ___④___;
26              ___⑤___;
27          }
28      }
29 
30      cout << s << endl;
31      return 0;
32  }

（精明与糊涂）有 $N$ 个人，分为两类：

i) 精明人：永远能正确判断其他人是精明还是糊涂。

ii) 糊涂人：判断不可靠，会给出随机的判断。

已知精明人严格占据多数，即如果精明人有 $k$ 个，则满足 $k > \frac{N}{2}$。

你只能通过函数 query(i, j) 让第 $i$ 个人判断第 $j$ 个人：返回 true 表示判断结果为“精明人”；返回 false 表示判断结果为“糊涂人”。你的目标是，通过这些互相判断，找出至少一个百分之百能确定的精明人。同时，你无需关心 query(i, j) 的内部实现。

以下程序利用“精明人占多数”的优势。设想一个“消除”的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选者必然属于多数派，即精明人。

例如，假设有三个人 $0$、$1$、$2$。如果 $0$ 说 $1$ 是糊涂人，而 $1$ 也说 $0$ 是糊涂人，则 $0$ 和 $1$ 至少有一个是糊涂人。程序将同时淘汰 $0$ 和 $1$。由于三人里至少有两个精明人，我们确定 $2$ 是精明人。试补全程序。

1  #include <iostream>
2  #include <vector>
3  using namespace std;
4 
5  int N;
6  bool query(int i, int j);
7 
8  int main() {
9      cin >> N;
10 
11      int candidate = 0;
12      int count = ___①___;
13 
14      for (int i = 1; i < N; ++i) {
15          if (___②___) {
16              candidate = i;
17              count = 1;
18          } else {
19              if (___③___) {
20                  ___④___;
21              } else {
22                  count++;
23              }
24          }
25      }
26 
27      cout << ___⑤___ << endl;
28      return 0;
29  }