CSP-J 2025初赛模拟卷 10

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

第 1 题 以下扩展名结尾的文件，不是多媒体文件的是（ ）。
{{ select(1) }}

• mp3
• txt
• avi
• jpg

第 2 题 以下关于链表和数组的描述中，错误的是（ ）。
{{ select(2) }}

• 数组和链表都可以排序
• 数组中查询元素的效率比较高
• 链表中插入和删除元素的效率比较高
• 向量和静态数组一样，不能动态调整数组大小

第 3 题 与 $C$++ 语言中的 cout << (a > b ? 'a' : 'b'); 功能类似的是（ ）。
{{ select(3) }}

• 顺序结构
• 循环结构
• 条件结构
• 递推函数

第 4 题 下面的 $C$++ 代码中 data 占用（ ）字节内存空间。

union Data {
    int no;
    double score;
    char name[6];
};
union Data data;

{{ select(4) }}

• $4$
• $8$
• $18$
• $6$

第 5 题 学号为 $1$ 到 $30$ 的幼儿园小朋友顺时针围成一圈，从 $1$ 号小朋友开始按顺时针方向报数，报数从 $0$ 开始，依次为 $0, 1, 2, 3, ..., 28, 29, 30, 31, 32, ...$ 一圈又一圈，问数到数字 $n$ 的小朋友的学号是多少？（ ）
{{ select(5) }}

• n % 30 + 1
• (n + 1) % 30
• (n + 1) % 30 + 1
• n % 30

第 6 题 以下哪个不属于 $STL$ 模板中队列的操作函数？（ ）
{{ select(6) }}

• push
• pop
• empty
• top

第 7 题 在 $C$++ 语言中，（ ）算法的时间复杂度是 $O(n log n)$。
{{ select(7) }}

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

第 8 题 以下关于字符串的判定语句中正确的是（ ）。
{{ select(8) }}

• 字符串一般以字符 '0' 结尾
• 字符串的长度必须大于零
• string s; 中定义的 s 也可以看作字符数组，首字母是 s[0]
• 全部都由空格字符组成的串就是空串

第 9 题 以下算法中，（ ）算法用到了栈。
{{ select(9) }}

• $BFS$
• 二分查找
• $DFS$
• 贪心

第 10 题 $32$ 位计算机系统中一个非负长整型指针变量 unsigned long long *p 占（ ）字节。
{{ select(10) }}

• $1$
• $2$
• $8$
• $4$

第 11 题 某山峰型数列共有 $2025$ 个各不相同的数，先是奇数由小到大，后是偶数由大到小，即 $1, 3, 5, 7, 9, ..., 2023, 2025, 2024, 2022, ..., 8, 6, 4, 2$。现要对该数列进行检索，查找某正整数 $x$ 的下标（$x$ 为 $1\sim 2025$ 中的某正整数，包含 $1$ 和 $2025$），最多检索（ ）次即可。
{{ select(11) }}

• $2025$
• $11$
• $10$
• $9$

第 12 题 在 C++ 程序中，lowbit(x) 函数返回整数 x 在二进制表示下最低一位 $1$ 以及后续 $0$ 一起表示的数字，如 lowbit(12) = 4。下面的表达式中，（ ）能得到相同的结果。
{{ select(12) }}

• x ^ (x - 1)
• x & (x - 1)
• x & (~x + 1)
• x | (x - 1)

第 13 题 某二叉树的中序遍历序列为 BDCEAFHG，后序遍历序列为 DECBHGFA，其前序遍历序列为（ ）。
{{ select(13) }}

• ABCDEFGH
• ABDCEFHG
• ABCDFEHG
• ABDCEFGH

第 14 题 有 $5$ 条线段，长度分别为 $1, 3, 5, 7, 9$，从中任取 $3$ 条能构成一个三角形的概率为（ ）。
{{ select(14) }}

• $1/2$
• $3/10$
• $1/5$
• $2/5$

第 15 题 对于非负整数组 {x, y, z}，满足 x + 2y + 3z = 100 的非负整数解组数为（ ）个。
{{ select(15) }}

• $886$
• $885$
• $884$
• $883$

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 2e4 + 5, inf = 2e9 + 7;
04 int n, a[N], ans = inf;
05 int main() {
06    scanf("%d", &n);
07    for (int i = 1; i <= n; i++)
08        scanf("%d", &a[i]);
09    sort(a + 1, a + n + 1);
10    for (int i = 2; i <= n; i += 2) {
11        int mi = inf, ma = -inf, x = 0;
12        for (int j = 1; j <= i; ++j) {
13            x = a[j] + a[i - j + 1];
14            mi = min(mi, x), ma = max(ma, x);
15        }
16        if (i ^ n)
17            ans = min(ans, max(a[n], ma) - min(a[i + 1], mi));
18        else
19            ans = min(ans, ma - mi);
20    }
21    return printf("%d\n", ans), 0;
22 }

判断题

16. 若将程序第 $12$ 行中的 i 改成 i / 2，程序的输出结果一定不会改变。（ ）
    {{ select(16) }}

• 对
• 错

17. ($2$ 分) 若将程序第 $10$ 行中的 i += 2 改成 i++，程序的输出结果一定不会改变。（ ）
    {{ select(17) }}

• 对
• 错

18. 若将头文件 <bits/stdc++.h> 改成 <iostream>，程序仍能正常运行。（ ）
    {{ select(18) }}

• 对
• 错

选择题

19. 若输入 4 1 3 6 7，则输出为（ ）。
    {{ select(19) }}

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

20. ($4$ 分) 若输入 7 2 8 9 15 17 18 16，则输出为（ ）。
    {{ select(20) }}

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

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 int n, m, k, l, r, mid;
04 int check(int g) {
05    int st = 1, ed = m, cnt = 0;
06    while (st <= n && ed >= 1) {
07        if (st * ed > g)
08            ed--;
09        else {
10            cnt += ed;
11            st++;
12        }
13    }
14    return cnt >= k;
15 }
16 int main() {
17    scanf("%d%d%d", &n, &m, &k);
18    l = 1, r = n * m;
19    while (l < r) {
20        mid = (l + r) / 2;
21        if (check(mid)) r = mid;
22        else l = mid + 1;
23    }
24    cout << l << endl;
25    return 0;
26 }

判断题

21. 每次运行 check 时，第 $7$ 行必定运行 $n$ 次。（ ）
    {{ select(21) }}

• 对
• 错

22. 如果保证 m = 1，则输出一定为 $k$。（ ）
    {{ select(22) }}

• 对
• 错

23. 若将第 $21$ 行中的 r = mid 改成 r = mid - 1，程序输出一定不变。（ ）
    {{ select(23) }}

• 对
• 错

24. 第 $24$ 行可以改成 cout << r << endl;。（ ）
    {{ select(24) }}

• 对
• 错

选择题
25. 该程序的时间复杂度为（ ）。
{{ select(25) }}

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

26. 若输入为 2 3 4，则输出为（ ）。
    {{ select(26) }}

• $1$
• $2$
• $3$
• $6$

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 10, dx[10] = {0, 1, 0, -1, 0}, dy[10] = {0, 0, 1, 0, -1};
04 int n, m, ans;
05 char c[N][N];
06 void dfs(int x) {
07    if (!x) return ++ans, void();
08    vector<int> v; v.clear();
09    for (int i = 1; i <= n; ++i)
10        for (int j = 1; j <= n; ++j)
11            if (c[i][j] == '.') {
12                bool flag = 0;
13                for (int k = 1; k <= 4; ++k) {
14                    int tx = i + dx[k], ty = j + dy[k];
15                    flag |= tx>=1 && tx<=n && ty>=1 && ty<=n && c[tx][ty] == 1;
16                }
17                if (flag){
18				  	v.push_back(i * 10 + j);
19					c[i][j] = 1;
20					dfs(x - 1);
21					c[i][j] = '#';
22				  }
23			  }
24    if (!v.empty())
25        for (int i = 0; i < v.size(); ++i)
26            c[v[i] / 10][v[i] % 10] = '.';
27 }
28 int main() {
29    scanf("%d%d", &n, &m);
30    for (int i = 1; i <= n; ++i)
31        scanf("%s", c[i] + 1);
32    for (int i = 1; i <= n; ++i)
33        for (int j = 1; j <= n; ++j)
34            if (c[i][j] == '.'){
35    				c[i][j] = 1;
36    				dfs(m - 1);
37    				c[i][j] = '#';
38			  }
39     return printf("%d\n", ans), 0;
40 }

判断题
27. 将第 $21$ 行的 c[i][j] = '#' 去除，结果一定不变。（ ）
{{ select(27) }}

• 对
• 错

28. 第 $6$ 行运行的次数不超过 $n^24^m$。（ ）
    {{ select(28) }}

• 对
• 错

选择题
29. 若输入为 2 2 #. .. ，则输出为（ ）。
{{ select(29) }}

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

30. 若输入为 3 5 #.# ... .#.，则输出为（ ）。
    {{ select(30) }}

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

31. ($4$ 分) 若 n = 3, m = 3，则输出的最大值为（ ）。
    {{ select(31) }}

• $16$
• $18$
• $22$
• $26$

32. 若 n = 4, m = 13，则输出的最大值为（ ）。
    {{ select(32) }}

• $488$
• $496$
• $512$
• $560$

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

(1) 题目描述

给定两个由小写字母构成的字符串 s1 和 s2，同时给定一个由数字 $1, 2, 3...$ 组成的操作序列。

按该排列顺序依次删除字符串 s1 相应位置上的字母，在删除过程中，约定各个字符的位置不变。

请计算最多可以删除几次，字符串 s1 中仍然包含字符串 s2（即字符串 s2 仍然是字符串 s1 的子串）。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
bool book[N];
char s1[N], s2[N];
vector<int> num;
int n = 1, len1, len2, ans, operation[N];
bool check(int x) {
    num.clear();
    for (int i = x + 1; i <= n; i++)
        if ( ① )
            num.push_back(operation[i]);
    sort(num.begin(), num.end());
    int i = 0, j = 0;
    while ( ② )
            j += ③ ;
    return j == len2 + 1;
}
void func(int l, int r) {
    if ( ④ ) return;
    int mid = (l + r) >> 1;
    if (check(mid))
        ans = mid, func(mid + 1, r);
    else
        func(l, mid - 1);
}
int main() {
    scanf("%s", s1 + 1);
    scanf("%s", s2 + 1);
    len1 = strlen(s1 + 1);
    len2 = strlen(s2 + 1);
    while (⑤)
        n++;
    n--;
    for (int i = 1; i <= len2; i++)
        book[int(s2[i])] = true;
    func(1, n);
    printf("%d\n", ans);
    return 0;
}

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

• book[s1[operation[i]]]
• book[s1[i]]
• !book[s1[operation[i]]]
• !book[s1[i]]

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

• i < num.size() && j <= len2
• i <= num.size() && j <= len2
• i <= num.size() && j < len2
• i < num.size() && j < len2

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

• s1[num[i++]] == s2[j]
• s1[num[++i]] == s2[j]
• s1[num[i++]] == s2[j++]
• s1[num[++i]] == s2[j++]

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

• l >= r
• l == r
• l > r
• l ^ r

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

• scanf("%d", &operation[n])
• ~scanf("%d", &operation[n])
• ~(cin >> operation[n])
• !scanf("%d", &operation[n])

(2) 题目描述

​ 如果存在一个长度为 $n$ 的排列（即该排列由 $1, 2, 3, ..., n$ 这 $n$ 个数字各出现一次组成），对于所有满足 $2 \le i \le n - 1$ 的整数 $i$，都有 $p_i\le p_{i-1},p_i\le p_{i+1}$ 或者 $p_i\ge p_{i-1},p_i\ge p_{i+1}$ 成立，则称这个序列为一个山峰山谷序列。

​ 对所有长度为 $n$ 的山峰山谷序列排序，求字典序第 $k$ 大的排列。

​ $dp_{i,j,0/1}$ 表示长度为 $i$ 的排列中第 $1$ 个数为 $j$ , 其中第一个数小于/大于第二个数。

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, k, dp[N][N][2], ans[N], vis[N];
int main() {
    scanf("%d%d", &n, &k);
    dp[1][1][0] = dp[1][1][1] = 1;
    dp[2][1][0] = dp[2][2][1] = 1;
    for (int i = 2; i < n; ++i)
        for (int j = 1; j <= i; ++j)
            for (int k = 1; k <= i + 1; ++k)
                if ( ① ) dp[i + 1][k][1] += dp[i][j][0];
                else ②;
    for (int i = 1; i <= n; ++i) {
        int las = 0, mk = 1;
        if (i > 2 && ans[i - 1] < ans[i - 2])
            mk = ③;
        for (int j = mk; j <= n; ++j)
            if (!vis[j]) {
                int cnt = 0;
                for (int k = 1; k <= j; ++k)
                    if (!vis[k]) cnt++;
                int x = ④;
                if (i == 1) x += dp[n][j][0];
                if (x >= k) {
                    las = j;
                    break;
                }
                ⑤;
            }
        ans[i] = las, vis[las] = 1;
    }
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);
    return 0;
}

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

• j < k
• j <= k
• i < k
• i <= k

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

• dp[i + 1][k][1] += dp[i][j][0]
• dp[i + 1][k][0] += dp[i][j][1]
• dp[i + 1][j][1] += dp[i][k][0]
• dp[i + 1][j][0] += dp[i][k][1]

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

• ans[i - 1] + 1
• ans[i - 2] + 1
• i + 1
• ans[i - 1]

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

• dp[n - i + 1][cnt][ans[i - 1]<j]
• dp[n - i + 1][cnt][ans[i - 1]>j]
• dp[n - i + 1][j - cnt][ans[i - 1]>j]
• dp[n - i + 1][j - cnt][ans[i - 1]<j]

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

• k -= x
• k -= x * (n - i + 1)
• k -= x * cnt
• k -= x * mk