信息学奥赛 CSP-J 2025 初赛模拟卷 1

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

第 1 题 在标准 $ASCII$ 码表中，已知英文字母 c 的 ASCII 码十进制表示是 $99$，那么英文字母 x 的 ASCII 码十六进制表示是 ( )。 {{ select(1) }}

• $77$
• $78$
• $79$
• $7A$

第 2 题 以下关于 $CSP$ 与 $GESP$ 的描述正确的是 ( )。 {{ select(2) }}

• $CSP-J/CSP-S$ 属于非专业级别软件能力认证，只有中小学生才能参加
• $CSP$ 是中国通信学会举办的程序设计竞赛
• $GESP$ 是中国电子学会举办的程序设计竞赛
• $GESP\ C$++ 七级成绩 $80$ 分及以上或者八级成绩 $60$ 分及以上，可以申请免 $CSP-J$ 初赛

第 3 题 以下可以用作 $C$++ 程序中的变量名的是 ( )。 {{ select(3) }}

• _x1
• new
• class
• public

第 4 题 以下不属于桌面或者手机操作系统的是 ( )。 {{ select(4) }}

• Linux
• Android
• MATLAB
• Windows 11

第 5 题 $C$++ 中使用输入和输出函数 cin 和 cout 会用到 ( ) 头文件。 {{ select(5) }}

• iostream
• cmath
• cstdio
• algorithm

第 6 题 寻找最短路径的广度优先搜索算法经常用到的数据结构是 ( )。 {{ select(6) }}

• 栈
• 链表
• 向量
• 队列

第 7 题 以下哪个域名后缀不属于中华人民共和国管辖？( ) {{ select(7) }}

• $cn$
• $uk$
• $hk$
• $mo$

第 8 题 下列排序算法中，平均情况下 ( ) 算法的时间复杂度最小。 {{ select(8) }}

• 插入排序
• 选择排序
• 归并排序
• 冒泡排序

第 9 题 关于计算机网络，下面的说法中正确的是 ( )。 {{ select(9) }}

• $TCP$ 是网络层协议
• 计算机病毒只能通过 $U$ 盘等介质传播，不能通过计算机网络传播
• 计算机网络可以实现资源共享
• 公司内部的几台计算机组成的网络规模太小，不能称为计算机网络

第 10 题 序列 7, 5, 1, 12, 3, 6, 9, 4 的逆序对有 ( ) 个。 {{ select(10) }}

• $15$
• $12$
• $13$
• $14$

第 11 题 下列属于图像文件格式的是 ( )。 {{ select(11) }}

• $MPEG$
• $DOCX$
• $JPEG$
• $WMV$

第 12 题 不管 P、Q 如何取值，以下逻辑表达式中取值恒为假的是 ( )。 {{ select(12) }}

• (¬Q∧P)∨(Q∧¬P)
• ((¬P∨Q)∨(P∨¬Q))∧P∧¬Q
• ¬P∧((¬Q∨P)∨(Q∨¬P))∧P
• ((¬P∨Q)∨(Q∨¬P))∧Q∧¬P

第 13 题 树的根结点的高度为 $1$，某完全二叉树有 $2025$ 个结点，其高度是 ( )。 {{ select(13) }}

• $10$
• $11$
• $12$
• $13$

第 14 题 现有 $9$ 个苹果，要放入 $5$ 个不同的盘子，允许有的盘子中放 $0$ 个苹果，则不同的放法共有 ( ) 种。 {{ select(14) }}

• $720$
• $715$
• $126$
• $252$

第 15 题 $G$ 是一个非连通无向图（没有重边和自环），共有 $36$ 条边，则该图至少有 ( ) 个顶点。 {{ select(15) }}

• $6$
• $9$
• $10$
• $8$

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

程序 (1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 using i64 = long long;
04
05 int popcount(i64 x) {
06    int res = 0;
07    while (x) {
08        if (x & 1 == 1) 
09          res++;
10        x >>= 1;
11    }
12    return res;
13 }
14
15 int calc(i64 x) {
16    int sum = 0;
17    for (i64 i = 1; i <= x; i++)
18        sum += popcount(i);
19    return sum;
20 }
21
22 int sum(i64 l, i64 r) {
23    return calc(r) - calc(l);
24 }
25
26 int main() {
27    i64 l, r;
28    cin >> l >> r;
29    cout << calc(l) << ' ' << sum(l, r) << endl;
30    return 0;
31 }

判断题 16 若程序输入为 5 8，则程序输出 7 6。 ( ) {{ select(16) }}

• 对
• 错

判断题 17 若将第 $8$ 行中的 & 符号改为 ^ 符号，程序输出结果一定不会改变。 ( ) {{ select(17) }}

• 对
• 错

判断题 18 若将头文件 #include <bits/stdc++.h> 改成 #include <stdio.h>，程序仍能正常运行。 ( ) {{ select(18) }}

• 对
• 错

选择题 19 若输入为 1 12，则输出是什么？( ) {{ select(19) }}

• 1 21
• 1 20
• 1 22
• 2 22

选择题 20 程序中的 sum 函数实现了什么功能？( ) {{ select(20) }}

• 计算了 [l, r] 区间内的每个数二进制位上 $1$ 的个数之和
• 计算了 [l, r] 区间内的每个数二进制位上 $0$ 的个数之和
• 计算了 (l, r] 区间内的每个数二进制位上 $1$ 的个数之和
• 计算了 (l, r] 区间内的每个数二进制位上 $0$ 的个数之和

程序 (2)

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 const int inf = 0x3f3f3f3f;
05
06 int solve(vector<int> &cur) {
07    int n = cur.size();
08    vector<vector<int>> dp(n + 1, vector<int>(n + 1, inf));
09    for (int i = 0; i <= n; i++) {
10        dp[0][i] = dp[i][0] = 0;
11    }
12    for (int i = 1; i <= n; i++) {
13        dp[i][i] = cur[i - 1];
14    }
15    for (int i = 1; i <= n; i++) {
16        for (int j = 1; j <= n; j++) {
17            if (i != j) {
18                dp[i][j] = min(dp[i][j], dp[i - 1][j] + dp[i][j - 1]);
19            }
20        }
21    }
22    int ans = 0;
23    for (int i = 1; i <= n; i++) {
24        ans = max(ans, dp[n][i]);
25    }
26    return ans;
27 }
28
29 int main() {
30    int n;
31    cin >> n;
32    vector<int> cost(n);
33    for (int i = 0; i < n; i++) {
34        cin >> cost[i];
35    }
36    cout << solve(cost) << endl;
37    return 0;
38 }

判断题 21 若输入为 3 1 2 3，则输出为 3。 ( ) {{ select(21) }}

• 对
• 错

判断题 22 计算 dp 数组的时间复杂度为 $O(n^2)$。 ( ) {{ select(22) }}

• 对
• 错

判断题 23 ($2$分) 若将第 $32$ 行改为 vector<int> cost(n + 1)，则当输入 3 1 2 3 时，solve 函数中的 n = 3。 ( ) {{ select(23) }}

• 对
• 错

选择题 24 当输入的 cost 数组为 {4, 0, 0, 5, 6} 时，程序的输出为 ( )。 {{ select(24) }}

• $23$
• $25$
• $24$
• $22$

选择题 25 若将第 $18$ 行改为 dp[i][j] = min(dp[i][j], dp[i - 1][j] - dp[i][j - 1]);，则当输入的 cost 数组为 {4, 0, 0, 5, 6} 时，程序的输出为 ( )。 {{ select(25) }}

• $20$
• $21$
• $22$
• $23$

选择题 26 ($4$分)当输入的 cost 数组为 {4, 0, 0, 5, 6} 时，在 solve 函数中，dp[2][3] 的值为 ( )。 {{ select(26) }}

• $1$
• $2$
• $3$
• $4$

程序 (3)

01 #include <iostream>
02 using namespace std;
03
04 int func(int a, int b) {
05    if (a == 0) return b;
06    if (b == 0) return a;
07    return a + func(b, a % b);
08 }
09 
10 int main() {
11    int x, y;
12    cin >> x >> y;
13    cout << func(x, y) << endl;
14    return 0;
15 }

假设输入为非负整数 完成下面的问题。

判断题 27 当输入为 2 3 时，程序的输出为 5。 ( ) {{ select(27) }}

• 对
• 错

判断题 28 若输入只有一个为 0，则程序的输出为输入的另一个数字。 ( ) {{ select(28) }}

• 对
• 错

判断题 29 当输入为 6 8 时，func 函数将会被进入 $4$ 次。 ( ) {{ select(29) }}

• 对
• 错

选择题 30 当输入为 6 8 时，程序的输出为 ( )。 {{ select(30) }}

• $20$
• $21$
• $22$
• $23$

选择题 31 当输入为 3 5 时，func 函数的调用顺序是 ( )。 {{ select(31) }}

• func(3, 5) -> func(5, 3) -> func(3, 2) -> func(2, 1) -> func(1, 0)
• func(3, 5) -> func(5, 3) -> func(3, 2) -> func(2, 1) -> func(1, 1) -> func(1, 0)
• func(3, 5) -> func(5, 2) -> func(2, 1) -> func(1, 1) -> func(1, 0)
• func(3, 5) -> func(5, 2) -> func(2, 1) -> func(1, 0)

选择题 32 若将第 $7$ 行的代码改为 return a + func(b, a - b);，则当输入为 3 5 时，得到的输出为 ( )。 {{ select(32) }}

• $14$
• $8$
• $6$
• 产生未定义行为，结果未知

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

(1)题目描述：

给定一个整数数组 colors 和一个整数 k，其中 colors 表示一个由红色瓷砖和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i]（$1$ 代表红色，$0$ 代表蓝色）。环中连续 k 块瓷砖的颜色如果是交替颜色（除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它左边瓷砖和右边瓷砖的颜色都不同），那么它被称为一个交替组。

现在，请你找出交替组的个数。

#include <iostream>
#include < ① >
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> colors(n);
    for (int i = 0; i < n; i++) {
        cin >> colors[i];
    }
    int ans = 0, cnt =  ②;
    for (int i = 0; i < ③; i++) {
        if (i > 0 && ④ ) {
            cnt = 0;
        }
        cnt++;
        ans += (⑤ && cnt >= k);
    }
    cout << ans << endl;
    return 0;
}

选择题 33 ①处应填 ( ) {{ select(33) }}

• vector
• set
• string
• map

选择题 34 ②处应填 ( ) {{ select(34) }}

• -1
• 0
• 1
• 2

选择题 35 ③处应填 ( ) {{ select(35) }}

• n
• n - 1
• 2 * n
• 2 * (n - 1)

选择题 36 ④处应填 ( ) {{ select(36) }}

• colors[i] == colors[i - 1]
• colors[i] != colors[i - 1]
• colors[i % n] == colors[(i - 1) % n]
• colors[i % n] != colors[(i - 1) % n]

选择题 37 ⑤处应填 ( ) {{ select(37) }}

• i > n
• i >= n
• i < n
• i <= n

(2)题目描述：

在国际象棋中，马的移动规则是：垂直移动两个方格后再水平移动一个方格，或者水平移动两个方格后再垂直移动一个方格（两者都形成一个 $L$ 的形状）。

现在，我们有一个马和一个电话垫（如下所示），马只能站在数字单元格上。你可以将马放置在任何数字单元格上，然后执行 $n-1$ 次移动来获得长度为 $n$ 的号码。马的所有移动应该是符合规则的有效移动。马在一次移动的过程中可以经过符号单元格，但必须保证这次移动结束后马站在数字单元格上。

给定一个整数 $n$，请你计算可以得到多少个长度为 $n$ 的数字串。由于答案可能很大，请你输出答案对 $10^9 + 7$ 取模后的结果。

#include <iostream>
#include <vector>
using namespace std;

const int mod = 1e9 + 7;
vector<vector<int>> pos = {
    {4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {①}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}};

int main() {
    int n;
    cin >> n;
    vector<vector<int>> dp(10, vector<int>(n + 1, 0));
    for (int i = 0; i < 10; i++) {
        ② = 1;
    }
    for (int j = 2; j <= n; j++) {
        for (int i = 0; i < 10; i++) {
            for (int k = 0; k < pos[i].size(); k++) {
                dp[i][j] += dp[ ③ ][j - 1];
                ④;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 10; i++) {
      	⑤;
      	ans %= mod;
    }    
    cout << ans << endl;
    return 0;
}

选择题 38 ①处应填 ( ) {{ select(38) }}

• {1, 3, 7, 9}
• {*, #}
• {2, 8, 0}
• {}

选择题 39 ②处应填 ( ) {{ select(39) }}

• dp[i][1]
• dp[1][i]
• dp[i][0]
• dp[0][i]

选择题 40 ③处应填 ( ) {{ select(40) }}

• k
• pos[k][i]
• pos[i][k]
• pos[i-1][K]

选择题 41 ④处应填 ( ) {{ select(41) }}

• dp[i][k] %= mod
• dp[j][i] -= mod
• dp[i][j] %= mod
• dp[i][j] -= mod

选择题 42 ⑤处应填 ( ) {{ select(42) }}

• ans += dp[i][n]
• ans += dp[i][n-1]
• ans += dp[n][i]
• ans += dp[n - 1][i]