#9652. CSP-J2025 初赛模拟卷10

CSP-J2025 初赛模拟卷10

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];
} 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 到 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

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

(1)

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5, inf = 2e9 + 7;
int n, a[N], ans = inf;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    for (int i = 2; i <= n; i += 2) {
        int mi = inf, ma = -inf, x = 0;
        for (int j = 1; j <= i; ++j) {
            x = a[j] + a[i - j + 1];
            mi = min(mi, x), ma = max(ma, x);
        }
        if (i != n)
            ans = min(ans, max(a[n], ma) - min(a[i + 1], mi));
        else
            ans = min(ans, ma - mi);
    }
    return printf("%d\n", ans), 0;
}

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

  • 对
  • 错
  1. (2分) 若将程序第 10 行中的 i += 2 改成 i++，程序的输出结果一定不会改变。（ ）
    {{ select(17) }}
  • 对
  • 错
  1. 若将头文件 <bits/stdc++.h> 改成 <iostream>，程序仍能正常运行。（ ）
    {{ select(18) }}
  • 对
  • 错

选择题
19. 若输入 41367，则输出为（ ）。
{{ select(19) }}

  • 0
  • 1
  • 2
  • 3
  1. (4分) 若输入 728915171816，则输出为（ ）。
    {{ select(20) }}
  • 2
  • 3
  • 4
  • 5

(2)

#include <bits/stdc++.h>
using namespace std;
int n, m, k, l, r, mid;
bool check(int g) {
    int st = 1, ed = m, cnt = 0;
    while (st <= n && ed >= 1) {
        if (st * ed > g)
            ed--;
        else {
            cnt += ed;
            st++;
        }
    }
    return cnt >= k;
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    l = 1, r = n * m;
    while (l < r) {
        mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

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

  • 对
  • 错
  1. 如果保证 m = 1，则输出一定为 k。（ ）
    {{ select(22) }}
  • 对
  • 错
  1. 若将第 21 行中的 r = mid 改成 r = mid - 1，程序输出一定不变。（ ）
    {{ select(23) }}
  • 对
  • 错
  1. 第 24 行可以改成 cout << r << endl;。（ ）
    {{ select(24) }}
  • 对
  • 错

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

  • O(n)
  • O(n log n)
  • O(n^2)
  • O(n^3)
  1. 若输入为 234，则输出为（ ）。
    {{ select(26) }}
  • 1
  • 2
  • 3
  • 6

(3)

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int dx[10] = {0, 1, 0, -1}, dy[10] = {1, 0, -1, 0};
int n, m, ans;
char c[N][N];
void dfs(int x) {
    if (!x)
        return ++ans, void();
    vector<int> v;
    v.clear();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (c[i][j] == '1') {
                bool flag = 0;
                for (int k = 1; k <= 4; ++k) {
                    int tx = i + dx[k], ty = j + dy[k];
                    flag |= tx >= 1 && tx <= n && ty >= 1 && ty <= n && c[tx][ty] == '1';
                }
                if (flag)
                    v.push_back(i * 10 + j), c[i][j] = '0', dfs(x - 1), c[i][j] = '1';
            }
    if (!v.empty())
        for (int i = 0; i < v.size(); ++i)
            c[v[i] / 10][v[i] % 10] = '0';
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%s", c[i] + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (c[i][j] == '1')
                c[i][j] = '0', dfs(m - 1), c[i][j] = '1';
    return printf("%d\n", ans), 0;
}

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

  • 对
  • 错
  1. 第 6 行运行的次数不超过 ( n^2 )。（ ）
    {{ select(28) }}
  • 对
  • 错

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

  • 0
  • 1
  • 2
  • 3
  1. 若输入为 35#...#...#，则输出为（ ）。
    {{ select(30) }}
  • 2
  • 3
  • 4
  • 5
  1. (4分) 若 n = 3, m = 3，则输出的最大值为（ ）。
    {{ select(31) }}
  • 16
  • 18
  • 22
  • 26
  1. 若 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 (②)
        if (s1[num[i++]] == s2[j++])
            j++;
    return j == len2 + 1;
}
void func(int l, int r) {
    if (④)
        return;
    int mid = (l + r) / 2;
    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++;
    for (int i = 1; i <= len2; i++)
        book[int(s2[i])] = true;
    func(1, n);
    printf("%d\n", ans);
    return 0;
}
  1. ①处应填（ ）。
    {{ select(33) }}
  • book[s1[operation[i]]]
  • book[s1[i]]
  • !book[s1[operation[i]]]
  • !book[s1[i]]
  1. ②处应填（ ）。
    {{ select(34) }}
  • i < num.size() && j < len2
  • i < num.size() && j <= len2
  • i <= num.size() && j < len2
  • i < num.size() && j <= len2
  1. ③处应填（ ）。
    {{ select(35) }}
  • s1[num[i++]] == s2[j]
  • s1[num[++i]] == s2[j]
  • s1[num[i++]] == s2[++j]
  • s1[num[++i]] == s2[++j]
  1. ④处应填（ ）。
    {{ select(36) }}
  • l > r
  • l == r
  • l >= r
  • l != r
  1. ⑤处应填（ ）。
    {{ 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 ≤ i ≤ n - 1 的整数 i，都有 a[i-1] ≤ a[i] ≤ a[i+1] 或者 a[i-1] ≥ a[i] ≥ a[i+1] 成立，则称这个序列为一个山峰山谷序列。对所有长度为 n 的山峰山谷序列排序，求字典序第 k 大的排列。

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
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 - 2] < ans[i - 1])
            mk = 0;
        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 = cnt;
                if (i == 1)
                    x += dp[n][j][0];
                if (x >= k) {
                    las = j;
                    break;
                }
                k -= x;
            }
        int cnt = 0;
        for (int k = 1; k <= las; ++k)
            if (!vis[k])
                cnt++;
        ④;
        ans[i] = las, vis[las] = 1;
    }
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);
    return 0;
}
  1. ①处应填（ ）。
    {{ select(38) }}
  • j < k
  • j <= k
  • i < k
  • i <= k
  1. ②处应填（ ）。
    {{ 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]
  1. ③处应填（ ）。
    {{ select(40) }}
  • ans[i - 1] + 1
  • ans[i - 2] + 1
  • i + 1
  • ans[i - 1]
  1. ④处应填（ ）。
    {{ select(41) }}
  • dp[n - i + 1][cnt][ans[i - 1]]
  • dp[n - i + 1][cnt][ans[i - 1]]
  • dp[n - i + 1][j - cnt][ans[i - 1]]
  • dp[n - i + 1][j - cnt][ans[i - 1]]
  1. ⑤处应填（ ）。
    {{ select(42) }}
  • k -= x
  • k -= x * (n - i + 1)
  • k -= x * cnt
  • k -= x * mk
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 陕ICP备2025061476号
  3. Worker 0, 59ms
  4. Powered Dong Dong