CSP-J2025 初赛模拟卷9

ID: 4327

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

bawanglong

CSP-J 2025初赛模拟卷 9

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

第 1 题 两个十六进制数 (1ACF)16 和 (0451)16 做加法的结果是（）。
{{ select(1) }}

(1F25)16
(7975)10
(17455)8
(1111100100)2

第 2 题 一个“无符号长整型变量”占用（）字节。
{{ select(2) }}

第 3 题 判断字符串 s1 是否为回文串，如果是就输出“yes”，否则输出“no”。以下代码中，正确的实现是（）。

int main() {
    string s1, s2;
    cin >> s1;
    s2 = s1;
    reverse(s1.begin(), s1.end());
    if (s1 == s2) cout << "yes";
    else cout << "no";
    return 0;
}

reverse(s1.begin(), s1.end());
reverse(s1[0], s1[s1.size()]);
s1.reverse(begin(), end());
reverse(s1, s1 + s1.size());

第 4 题 已知 x、y、z 都是 int 类型的整数，x = 1、y = 1、z = 3。那么执行 bool ans = x++ || y++ && ++z 后，x、y、z 和 ans 的值各为多少？（）
{{ select(4) }}

x = 2, y = 0, z = 4, ans = 1
x = 2, y = 1, z = 3, ans = 1
x = 2, y = 1, z = 3, ans = 0
x = 2, y = 0, z = 4, ans = 0

第 5 题 指针 p 指向变量 a，q 指向变量 c。能够把 c 插入到 a 和 b 之间并形成新链表的语句组是（）。
{{ select(5) }}

p->next = q; q->next = p->next;
p->next = &c; q->next = p->next;
(*p).next = q; (*q).next = &b;
a.next = c; c.next = b;

第 6 题 以下哪个特性是数组和链表共有的？（）
{{ select(6) }}

动态分配
元素之间的次序关系
存储连续
通过索引访问

第 7 题 下面关于哈夫曼树的描述中，正确的是（）。
{{ select(7) }}

哈夫曼树一定是完全二叉树
哈夫曼树一定是平衡二叉树
哈夫曼树中权值最小的两个结点互为兄弟结点
哈夫曼树中左子结点小于父结点，右子结点大于父结点

第 8 题 已知一棵二叉树有 2025 个结点，则其中至多有（）个结点有 2 个子结点。
{{ select(8) }}

1010
1011
1012
1013

第 9 题 下面的说法中正确的是（）。
{{ select(9) }}

计算机网络按照拓扑结构分为星型、环型、总线型等
互联网的基础是 OSI 七层协议而不是 TCP/IP 协议族
现代计算机网络主要采用电路交换技术
10.10.1.1 是 D 类 IP 地址

第 10 题 下面关于图的说法中正确的是（）。
{{ select(10) }}

所有点数为奇数的连通图，一定可以一笔画成
所有只有两个奇度点（其余均为偶度点）的连通图，一定可以一笔画成
哈密顿图一定是欧拉图，而欧拉图未必是哈密顿图
哈密顿图不一定是欧拉图，而欧拉图一定是哈密顿图

第 11 题 （）是一种选优搜索法，按选优条件向前搜索以达到目标。当搜索到某一步时，如果发现原先的选择并不优或者达不到目标，就后退一步重新选择。
{{ select(11) }}

二分算法
动态规划
回溯法
贪心算法

第 12 题 动态规划是将一个问题分解为一系列子问题后来求解，下面（）属于动态规划问题。
{{ select(12) }}

多重背包
排队打水
有序数组找数
全排列

第 13 题 设无向图 G 的邻接矩阵如下图所示，则 G 的顶点数和边数分别为（）。

4, 5
5, 8
4, 10
5, 5

第 14 题 某条道路从东到西有 8 个路灯，巡查员为了维护方便，在每根灯杆上都安装了开关，第 i 个开关能够切换前 i 个灯的状态（开或关），一开始灯全是开的。巡查员通过控制开关一共能得到（）种不同灯的开或者关的组合状态。
{{ select(14) }}

第 15 题 某四位正整数 abcd 满足如下条件（a, b, c, d 是非负整数）：abcd = 1^3 + 2^3 + ... + n^3，abcd = (1 + 2 + 3 + ... + n)^2，abcd = (ab + cd)^2，这样的正整数 abcd 共有（）个。
{{ select(15) }}

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

(1)

#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 5;
int n, c, x, y, len, l[N], r[N], cha[N];
char a[N];
int main() {
    scanf("%d%d%s", &n, &c, a + 1);
    len = n;
    for (int i = 1; i <= c; i++) {
        scanf("%d%d", &l[i], &r[i]);
        cha[i] = len - l[i] + 1;
        len += r[i] - l[i] + 1;
    }
    scanf("%d", &x);
    for (int i = c; i; i--) {
        if (x >= l[i] + cha[i] && x <= r[i] + cha[i])
            x -= cha[i];
    }
    printf("%c\n", a[x]);
    return 0;
}

判断题
16. 第 17 行最多会运行一次。（）
{{ select(16) }}

(2分) 当程序运行至第 19 行时，x 一定在 [1, n] 范围内。（）
{{ select(17) }}

若将第 3 行改成 const int N = 100;，一定不会出现数组越界问题。（）
{{ select(18) }}

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

(4分) 若输入 73 cream 23342911，则输出为（）。
{{ select(20) }}

(2)

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, ans, a[N], cnt[20];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        for (int j = 0; j <= 14; ++j) {
            cnt[j] += a[i] % 2;
            a[i] /= 2;
        }
    }
    for (int i = 1; i <= n; ++i) {
        int sum = 0, x = 1;
        for (int j = 0; j < 14; ++j) {
            if (cnt[j])
                sum += x * cnt[j];
            x *= 2;
        }
        ans += sum * sum;
    }
    return printf("%d\n", ans), 0;
}

判断题
21. 第 10 行可以写成 cnt[j] += a[i] % 2。（） {{ select(21) }}

第 21 行一定不会溢出 int 上界。（）
{{ select(22) }}

若输入为 141，则输出为 1。（）
{{ select(23) }}

若输入为 3135，则输出为 51。（） {{ select(24) }}

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

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

若输入为 212369，则程序运行至第 13 行时，cnt 数组的和为（）。
{{ select(26) }}

(3)

#include <bits/stdc++.h>
using namespace std;
const int N = 10005, M = 15;
char c[N];
int d, num[N], dp[N][M][2];
int dfs(int pos, int res, int sta) {
    if (pos == 0)
        return res == 0;
    if (dp[pos][res][sta] != -1)
        return dp[pos][res][sta];
    int ret = 0, maxx = 9;
    if (sta)
        maxx = num[pos];
    for (int i = 0; i <= maxx; i++)
        ret += dfs(pos - 1, (res + i) % d, sta && (i == maxx));
    dp[pos][res][sta] = ret;
    return ret;
}
int main() {
    scanf("%s%d", c + 1, &d);
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= strlen(c + 1); i++)
        num[i] = c[strlen(c + 1) - i + 1] - '0';
    printf("%d\n", dfs(strlen(c + 1), 0, 1) - 1);
    return 0;
}

判断题
27. 将程序中的第 2 行去除，程序依然能正常运行。（） {{ select(27) }}

该程序的时间复杂度为 O(d)。（）
{{ select(28) }}

选择题
29. 若将程序中的第 15 行去除，则程序的时间复杂度为（）。
{{ select(29) }}

O(d)
O(d * |c|)
O(d^2)
O(d^2 * |c|)

若输入为 92，则输出为（）。
{{ select(30) }}

若输入为 37 4，则输出为（）。
{{ select(31) }}

(4分) 若输入为 20256，则输出为（）。
{{ select(32) }}

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

(1) 题目描述

有一个长度为 n 的数组 a，满足 a[i] 只能是 0、1 或 2，一开始所有元素均为蓝色。可以执行如下操作：(i) 用一枚硬币，把一个蓝色元素涂成红色；(ii) 选择一个不等于 0 的红色元素和一个与其相邻的蓝色元素，将所选的红色元素减少 1，并将所选的蓝色元素涂成红色。要将所有元素涂红，最少需要多少枚硬币？

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, pre[N], a[N], dp[N][3];
int main() {
    scanf("%d", &n);
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    ①
    for (int i = 1; i <= n; i++)
        pre[i] = ②
    for (int i = 2, j; i <= n; i++) {
        dp[i][a[i]] = min({③});
        if (④)
            dp[i][a[i] - 1] = 1 + min({⑤});
    }
    printf("%d", min({dp[n][0], dp[n][1], dp[n][2]}));
    return 0;
}

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

dp[1][a[1] == 2] = 1
dp[1][a[1] == 1] = 1
dp[1][a[1] == 0] = 1
dp[1][a[1] == 1] = 2

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

a[i] ? pre[i - 1] : i
a[i] ? 1 : pre[i - 1]
a[i] == 2 ? pre[i - 1] : i
a[i] == 2 ? 1 : pre[i - 1]

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

dp[i - 1][0] + 1, dp[i - 1][1], dp[i - 1][2]
dp[i - 1][0] + 2, dp[i - 1][1] + 1, dp[i - 1][2]
dp[i - 1][0] + 2, dp[i - 1][1], dp[i - 1][2]
dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]

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

a[i]
a[i] == 2
a[i] == 1
a[i - 1]

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

dp[pre[i] - 1][0] + 1, dp[pre[i] - 1][1], dp[pre[i] - 1][2]
dp[pre[i] - 1][0] + 2, dp[pre[i] - 1][1] + 1, dp[pre[i] - 1][2]
dp[pre[i] - 1][0] + 2, dp[pre[i] - 1][1], dp[pre[i] - 1][2]
dp[pre[i] - 1][0], dp[pre[i] - 1][1], dp[pre[i] - 1][2]

(2) 题目描述

给你一个长度为 n（n ≤ 300000）的整数数组 a。你可以执行以下操作：选择数组中的一个元素，并用其邻近元素的值替换它。计算在执行上述操作最多 k（k ≤ 10）次的情况下，数组的总和可能达到的最小值。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, k, a[N], p[N][11], ans[N][11];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        ①
    }
    for (int j = 1; j <= k; j++)
        for (int i = 1; i + j <= n; i++)
            p[i][j] = min(p[i][j - 1], a[i + j]);
    for (int j = 1; j <= k; j++)
        for (int i = 1; i + j <= n; i++)
            ②
    for (int i = 1; i <= n; i++)
        ans[i][0] = ③
    for (int j = 1; j <= k; j++) {
        for (int i = 1; i <= n; i++) {
            ans[i][j] = min(ans[i - 1][j] + a[i], ans[i][j - 1]);
            for (int h = 0; ④; h++)
                ans[i][j] = min(ans[i][j], ⑤);
        }
    }
    printf("%d\n", ans[n][k]);
    return 0;
}

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

p[i][0] = i
p[i][0] = a[i]
p[i][i] = i
p[i][i] = a[i]

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

p[i][j] *= j
p[i][j] *= (j + 1)
p[i][j] *= i
p[i][j] *= (i + 1)

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

ans[i - 1][0] + a[i]
ans[i - k][0] + p[i - k + 1][k]
ans[i - 1][0] + a[i] * i
ans[i - k][0] + p[i - k + 1][k] * k

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

h < i && h < j
h < i && h <= j
h <= i && h < j
h <= i && h <= j

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

ans[i - h][j - h] + p[i - h][h]
ans[i - h][j - h] + p[i - h][h] * h
ans[i][j - h] + p[i][h]
ans[i][j - h] + p[i - h][h]

#J0009. CSP-J2025 初赛模拟卷9

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

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

(1)

(2)

(3)

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

(1) 题目描述

(2) 题目描述

登录