CSP-J 2025初赛模拟卷 5

一、单项选择题（每题 2 分，共 30 分）

第 1 题 十进制数 $2025$ 的十六进制表示是（ ）。
{{ select(1) }}

• $07D9$
• $07E9$
• $07F9$
• $07F1$

第 2 题 以下关于计算机竞赛 $IOI$ 的描述正确的是（ ）。
{{ select(2) }}

• $IOI$ 非英语国家参赛选手可以在比赛中携带电子词典
• $IOI$ 参赛选手可携带已关机的手机放在自己座位后面的包里
• $IOI$ 参赛选手在比赛时间内去厕所的时候可携带手机
• $IOI$ 全称是国际信息学奥林匹克竞赛

第 3 题 以下不能用 $ASCII$ 码表示的字符是（ ）。
{{ select(3) }}

• @
• ①
• ^
• ~

第 4 题 设变量 $s$ 为 $double$ 型且已赋值，下列哪条语句能将 $s$ 中的数值保留到小数点后一位，并将第二位四舍五入？（ ）。
{{ select(4) }}

• s = (x * 10 + 0.5) / 10.0
• s = s * 10 + 0.5 / 10.0
• s = (s / 10 + 0.5) * 10.0
• s = (int)(s * 10 + 0.5) / 10.0

第 5 题 以下不属于 $STL$ 链表中的函数的是（ ）。
{{ select(5) }}

• sort()
• empty()
• push_back()
• resize()

第 6 题 小明写了一个程序，在这里用到的数据结构是（ ）。

#include <iostream>
using namespace std;
int k;
int f(int a) {
    if (a - k > 0 && (a - k) % 2 == 0)
        return f((a + k) / 2) + f((a - k) / 2);
    else
        return 1;
}
int main() {
    int n;
    cin >> n >> k;
    if ((n + k) & 1 == 0)
    {
        cout << 1 << endl;
    	return 0;
    }
    cout << f(n);
    return 0;
}

{{ select(6) }}

• 树
• 栈
• 链表
• 队列

第 7 题 小明想求 $n$ 个不同正整数的全排列，他设计的程序采用 $DFS$ 方法的时间复杂度是（ ）。
{{ select(7) }}

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

第 8 题 在下列排序算法中，（ ）是不稳定的排序算法。
{{ select(8) }}

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

第 9 题 一台 $32$ 位操作系统的计算机运行 $C$++，下列说法中错误的是（ ）。
{{ select(9) }}

• double 类型的变量占用 $8$ 字节内存空间
• bool 类型的变量占用 $1$ 字节内存空间
• long long 类型变量的取值范围比 int 类型变量的大一倍
• char 类型的变量也可以作为循环变量

第 10 题 若整型变量 $n$ 的值为 $25$，则表达式 n&(n+1>>1) 的值是（ ）。
{{ select(10) }}

• $25$
• $26$
• $9$
• $16$

第 11 题 一群学生参加学科夏令营，每名同学至少参加一个学科的考试。已知有 $100$ 名学生参加了数学考试，$50$ 名学生参加了物理考试， $48$ 名学生参加了化学考试，学生总数是参加至少两门考试学生的两倍，也是参加三门考试学生数的三倍，则学生总数为（ ）。
{{ select(11) }}

• $90$
• $96$
• $108$
• $120$

第 12 题 以下不是 $C$++ 中的循环语句的是（ ）。
{{ select(12) }}

• while
• do...while
• for
• switch...case

第 13 题 二叉树 $T$，已知其后序遍历序列为 4 2 7 5 6 3 1，中序遍历序列为 4 2 1 5 7 3 6，则其前序遍历序列为（ ）。
{{ select(13) }}

• 1 2 5 7 6 3 4
• 1 2 4 3 5 7 6
• 1 4 2 7 5 3 6
• 1 4 7 2 3 5 6

第 14 题 一个六位数是完全平方数，且最后三位数字都是 $4$，这样的六位数有（ ）个。
{{ select(14) }}

• $2$
• $3$
• $4$
• $5$

第 15 题 用三种颜色给 1×4 的长方形方格区域涂色，在每种颜色至少用 $1$ 次的前提下，相邻方格不涂同一种颜色的概率为（ ）。
{{ select(15) }}

• $\frac{1}{3}$
• $\frac{2}{3}$
• $\frac{1}{2}$
• $\frac{4}{9}$

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 int solve(vector<int> nums) {
05    map<int, int> cnt;
06    int tot = 0;
07    for (auto v : nums) {
08        cnt[v]++;
09        tot += v;
10    }
11    int ans = -1E5;
12    for (auto v : nums) {
13        cnt[v]--;
14        if ((tot - v) % 2 == 0 && cnt[(tot - v) / 2] > 0)
15            ans = max(ans, v);
16        cnt[v]++;
17    }
18    return ans;
19 }
20
21 int main() {
22    int n;
23    cin >> n;
24    vector<int> a(n);
25    for (int i = 0; i < n; i++)
26        cin >> a[i];
27    cout << solve(a) << endl;
28    return 0;
29 }

判断题

16. 若程序输入 5 -2 -1 -3 -6 4，则程序输出 4。（ ）
    {{ select(16) }}

• 对
• 错

17. 对于第 $14$ 行的代码，如果不判断 (tot - v) % 2 == 0，则程序依然可以得到正确结果。（ ）
    {{ select(17) }}

• 对
• 错

18. 若将头文件 <bits/stdc++.h> 换为 <iostream>，程序依然可以正常运行。（ ）
    {{ select(18) }}

• 对
• 错

选择题

19. 若输入 8 6 -31 50 -35 41 37 -42 13，则输出是（ ）。
    {{ select(19) }}

• $13$
• $-35$
• $-31$
• $-100000$

20. 如果去除第 $16$ 行的代码，对于输入 4 2 3 5 10，则输出是（ ）。
    {{ select(20) }}

• $2$
• $5$
• $10$
• $-100000$

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int inf = 0x3f3f3f3f;
05
06 int solve(vector<string> &words, string target) {
07    const int n = target.length();
08    set<string> s;
09    for (auto v : words)
10        for (int i = 1; i <= v.length(); i++)
11            s.insert(v.substr(0, i));
12    vector<int> dp(n + 1, inf);
13    dp[0] = 0;
14    for (int i = 0; i < n; i++)
15        for (int j = 0; j <= i; j++)
16            if (s.find(target.substr(j, i - j + 1)) != s.end())
17                dp[i + 1] = min(dp[i + 1], dp[j] + 1);
18    return dp[n] != inf ? dp[n] : -1;
19 }
20
21 int main() {
22    int n;
23    cin >> n;
24    vector<string> a(n);
25    for (int i = 0; i < n; i++)
26        cin >> a[i];
27    string t;
28    cin >> t;
29    cout << solve(a, t) << endl;
30    return 0;
31 }

假设第 $16$ 行 $find$ 函数的时间复杂度为 $O(logn)$, $substr$ 函数的时间复杂度视为 $O(1)$ 。完成下面的问题。

判断题

21. 若输入 3 abc aaaaa bcdef aabcdabc，则输出为 2。（ ）
    {{ select(21) }}

• 对
• 错

22. 若将第 $17$ 行中的 $dp[i + 1]$ 改为 $dp[i]$，则可能出现编译错误。（ ）
    {{ select(22) }}

• 对
• 错

23. (2分) 该程序的输出一定小于或等于输入的 $n$。（ ）
    {{ select(23) }}

• 对
• 错

选择题

24. 当输入的 $a$ 数组为{"abababab", "ab"} , t = "ababaababa" 时，程序的输出为（ ）。
    {{ select(24) }}

• $0$
• $1$
• $2$
• $3$

25. 若删除第 $16$ 行的代码，则当输入的 $a$ 数组为 {"abababab", "ab"} , t = "ababa" 时，程序的输出为（ ）。
    {{ select(25) }}

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

26. (4分) 这段代码的时间复杂度为（ ）。
    {{ select(26) }}

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

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int calc(int n, int presses) {
05    set<int> seen;
06    for (int i = 0; i < (1 << 4); i++) {
07        vector<int> pressArr(4);
08        for (int j = 0; j < 4; j++)
09            pressArr[j] = (i >> j) & 1;
10        int sum = 0;
11        for (int j = 0; j < 4; j++)
12            sum += pressArr[j];
13        if (sum % 2 == presses % 2 && sum <= presses) {
14            int status = pressArr[0] ^ pressArr[2] ^ pressArr[3];
15            if (n >= 2)
16                status |= (pressArr[0] ^ pressArr[1]) << 1;
17            if (n >= 3)
18                status |= (pressArr[0] ^ pressArr[2]) << 2;
19            if (n >= 4)
20                status |= (pressArr[0] ^ pressArr[1] ^ pressArr[3]) << 3;
21            seen.insert(status);
22        }
23    }
24    return seen.size();
25 }
26
27 int main() {
28    int n, presses;
29    cin >> n >> presses;
30    cout << calc(n, presses) << endl;
31    return 0;
32 }

假设 $1\le n,presses\le 4$, 回答下面问题。

判断题

27. 若输入为 2 1，则程序的输出为 3。（ ）
    {{ select(27) }}

• 对
• 错

28. 对于第 $6$ 行代码，变量 $i$ 的上界为 $16$。（ ） {{ select(28) }}

• 对
• 错

29. 对于任意的输入，程序的输出不会大于 $8$。（ ）
    {{ select(29) }}

• 对
• 错

选择题

30. 当输入为 n = 3, presses = 2 时，程序的输出为（ ）。
    {{ select(30) }}

• $5$
• $6$
• $7$
• $8$

31. (4分) 若删除第 $15\sim 16$ 行的代码，当输入为 n = 3, presses = 2 时，程序的输出为（ ）。
    {{ select(31) }}

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

32. 上述代码的时间复杂度为（ ）。
    {{ select(32) }}

• $O(1)$
• $O(log n)$
• $O(n)$
• $O(n log n)$

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

(1) 题目描述

输入 $n\ (1 \le n \le 2 \times 10^5)$ 和长为 $n$ 的数组 $a\ (1 ≤ a[i] ≤ n)$。你可以多次执行如下操作：

• 选择两个下标 $i$ 和 $j$，满足 $a[i] = a[j]$。删除下标 $[i, j]$ 中的元素。删除后，数组长度减小 $i - j + 1$。

输出你最多可以删多少个数。

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<int> dp(n + 1), ①;
    for (int i = 1; i <= n; i++) {
        dp[i] = max(dp[i], ②);
        dp[i] = max(dp[i], ③);
        lst[a[i]] = max(lst[a[i]], ④);
    }
    cout << ⑤ << endl;
}

int main() {
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

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

• lst(n + 1)
• lst(n + 1, 0)
• lst(n + 1, inf)
• lst(n + 1, -inf)

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

• dp[i - 1]
• dp[i] - 1
• dp[i + 1]
• dp[i] + 1

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

• lst[a[i]]
• lst[a[i]] + i + 1
• lst[a[i]] + i
• lst[i] + i

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

• dp[i - 1] - i
• dp[i - 1] + i
• dp[i + 1] - i
• dp[i + 1] + i

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

• dp[1]
• dp[0]
• dp[n - 1]
• dp[n]

(2) 题目描述

输入 $n\ (1 \le n \le 1 × 10^5)$ 和长为 $n$ 的数组 $a\ (0 ≤ a[i] < 2^{20})$。

输出最小的正整数 $k$，使得 $a$ 的所有长为 $k$ 的连续子数组的 $OR$ 都相同。

注意答案是一定存在的，因为 $k = n$ 一定满足要求。

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 0;
    for (int i = 0; ①; i++) {
        int cnt = 0, lst = 0;
        for (int j = 1; j <= n; j++) {
            if (②)
                cnt++;
            else
                lst = ③, cnt = 0;
        }
        lst = max(lst, cnt);
        if (④)
            continue;
        ans = max(ans, lst + 1);
    }
    cout << ⑤ << endl;
}

int main() {
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

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

• i < 20
• i <= 20
• i > 20
• i != 20

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

• !(a[i] & (1 << j))
• a[i] & (1 << j)
• a[j] & (1 << i)
• !(a[j] & (1 << i))

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

• min(lst, cnt)
• max(lst, cnt)
• cnt
• lst + cnt

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

• lst < n
• lst != n
• lst == n
• lst > n

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

• ans
• min(ans, n)
• min((ans == 0 ? 1 : ans), n)
• (ans == 0 ? 1 : ans)