A. CSP-J初赛模拟卷25-9

A
    客观题

CSP-J初赛模拟卷25-9

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

普及组 CSP-J 2025 初赛模拟卷 9

一、单项选择题

  1. \((\text{IACF})_{16}\) 和 \((0456)_{16}\) 这两个十六进制数做加法的结果是（ ）。 {{ select(1) }}
  • \((\text{IF25})_{16}\)
  • \((7975)_{10}\)
  • \((17455)_{8}\)
  • \((1111100100111)_{2}\)
  1. 一个 64 位无符号长整型变量占用（ ）字节。 {{ select(2) }}
  • 32
  • 4
  • 16
  • 8
  1. 下列选项中，（ ）判断字符串 s1 是否为回文串，如果是就输出 “yes”，否则输出 “no”。
int main()
{
    string s1, s2;
    cin>>s1;
    s2 = s1;
    ______;
    if(s1 == s2)
        cout<<"yes";
    else
        cout<<"no";
    return 0;
}

{{ select(3) }}

  • reverse(s1.begin(), s1.end());
  • reverse(s1[0], s1[s1.size()]);
  • s1.reverse(begin(), end());
  • reverse(s1, s1+s1.size());
  1. 已知 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
  1. 指针 p 指向变量 a, q 指向变量 c。能够把 c 插入到 a 和 b 之间并形成新链表的语句组是（ ）。

image

{{ 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;
  1. 以下哪个特性是数组和链表共有的？（ ） {{ select(6) }}
  • 动态分配
  • 元素之间的次序关系
  • 通过索引访问
  • 存储连续
  1. 下面关于哈夫曼树的描述中，正确的是（ ） {{ select(7) }}
  • 哈夫曼树一定是完全二叉树
  • 哈夫曼树一定是平衡二叉树
  • 哈夫曼树中权值最小的两个结点互为兄弟结点
  • 哈夫曼树中左子结点小于父结点，右子结点大于父结点
  1. 已知一棵二叉树有 2025 个结点，则其中至多有（ ）个结点有 2 个子结点。 {{ select(8) }}
  • 1010
  • 1011
  • 1012
  • 1013
  1. 下面的说法中正确的是（ ） {{ select(9) }}
  • 计算机网络按照拓扑结构分为星型、环型、总线型等
  • 互联网的基础是 OSI 七层协议而不是 TCP/IP 协议族
  • 现代计算机网络主要采用电路交换技术
  • 10.10.1.1 是 D 类 IP 地址
  1. 下面关于图的说法中正确的是（ ） {{ select(10) }}
  • 所有点数为奇数的连通图，一定可以一笔画成
  • 所有只有两个奇度点(其余均为偶度点)的连通图，一定可以一笔画成
  • 哈密顿图一定是欧拉图，而欧拉图未必是哈密顿图
  • 哈密顿图不一定是欧拉图，而欧拉图一定是哈密顿图
  1. （ ）是一种选优搜索法，按选优条件向前搜索以达到目标。当搜索到某一步时，如果发现原先的选择并不优或者达不到目标，就后退一步重新选择。 {{ select(11) }}
  • 二分算法
  • 动态规划
  • 回溯法
  • 贪心算法
  1. 动态规划是将一个问题分解为一系列子问题后来求解，下面（ ）属于动态规划问题。 {{ select(12) }}
  • 多重背包
  • 排队打水
  • 有序数组找数
  • 全排列
  1. 设无向图 G 的邻接矩阵如下图所示，则 G 的顶点数和边数分别为（ ）。
$$\begin{bmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ \end{bmatrix} $$

{{ select(13) }}

  • 4, 5
  • 5, 8
  • 4, 10
  • 5, 5
  1. 某条道路从东到西有 8 个路灯，巡查员为了维护方便，在每根灯杆上都安装了开关，第 t 个开关能够切换前 t 个灯的状态（t=1~8，灯开或关），一开始灯全是开的。巡查员通过控制开关一共能得到（ ）种不同灯的开或者关的组合状态。 {{ select(14) }}
  • 128
  • 256
  • 127
  • 255
  1. 某四位正整数 abcd 满足如下条件（a,n 也是正整数，b,c,d 是非负整数）：abcd=13+23+⋯+n3 abcd=1^3+2^3+\cdots+n^3 ， abcd=(1+2+3+⋯+n)2 abcd=(1+2+3+\cdots+n)^2 ，abcd=(ab+cd)2 abcd=(ab+cd)^2 ，这样的正整数 abcd 共有（ ）个。 {{ select(15) }}
  • 0
  • 1
  • 2
  • 3

二、阅读程序

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 100 + 5;
04 int n, c, x, y, len, l[N], r[N], cha[N];
05 char a[N];
06 int main() {
07     scanf("%d%d%s", &n, &c, a + 1);
08     len = n;
09     for (int i = 1; i <= c; i++) {
10         scanf("%d%d", &l[i], &r[i]);
11         cha[i] = len - l[i] + 1;
12         len += r[i] - l[i] + 1;
13     }
14     scanf("%d", &x);
15     for (int i = c; i; i--)
16         if (x >= l[i] + cha[i] && x <= r[i] + cha[i])
17             x -= cha[i];
18     printf("%c\n", a[x]);
19     return 0;
20 }

输入保证 \(1 \leq I_i \leq n \leq 100\), \(1 \leq c \leq 100\)。回答以下问题。

■ 判断题

  1. 第17行最多会运行一次。 （ ） {{ select(16) }}
  • √
  • ×
  1. （2分）当程序运行至第19行时，x一定在[1,n]范围内。 （ ） {{ select(17) }}
  • √
  • ×
  1. 若将第3行改成 const int N = 100；一定不会出现数组越界问题。 （ ） {{ select(18) }}
  • √
  • ×

■ 选择题

  1. 若输入4 2 mark 1 4 5 7 10，则输出为（ ）。 {{ select(19) }}
  • m
  • a
  • r
  • k
  1. （4分）若输入7 3 creami 2 3 3 4 2 9 11，则输出为（ ）。 {{ select(20) }}
  • m
  • e
  • a
  • i

(2)

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

已知 \(1 \leq n, a < 2^{15}\)，完成下列各题。

■ 判断题

  1. 第 10 行可以写成 cnt[j] += a[i] % 2。 （ ） {{ select(21) }}
  • √
  • ×
  1. 第 21 行一定不会溢出 int 上界。 （ ） {{ select(22) }}
  • √
  • ×
  1. 若输入为 1 a，则输出为 \(a_0^2\)。 （ ） {{ select(23) }}
  • √
  • ×
  1. 若输入为 3 1 3 5，则输出为 51。 （ ） {{ select(24) }}
  • √
  • ×

■ 选择题

  1. 该程序的时间复杂度为（ ）。 {{ select(25) }}
  • \(O(n)\)
  • \(O(n\log n)\)
  • \(O(n^2)\)
  • \(O(n\log^2 n)\)
  1. 若输入为 2 123 69，则程序运行至第 13 行时，cnt 数组的和为（ ）。 {{ select(26) }}
  • 6
  • 7
  • 9
  • 10

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 10005, M = 15;
04 char c[N];
05 int d, num[N], dp[N][M][2];
06 int dfs(int pos, int res, int sta) {
07     if (pos == 0)
08         return res == 0;
09     if (dp[pos][res][sta] != -1)
10         return dp[pos][res][sta];
11     int ret = 0, maxx = 9;
12     if (sta) maxx = num[pos];
13     for (int i = 0; i <= maxx; i++)
14         ret += dfs(pos - 1, (res + i) % d, sta && (i == maxx));
15     dp[pos][res][sta] = ret;
16     return ret;
17 }
18 int main() {
19     scanf("%s%d", c + 1, &d);
20     memset(dp, -1, sizeof(dp));
21     for (int i = 1; i <= strlen(c + 1); i++)
22         num[i] = c[strlen(c + 1) - i + 1] - '0';
23     printf("%d\n", dfs(strlen(c + 1), 0, 1) - 1);
24     return 0;
25 }

已知1≤d<10，1≤|c|≤10 000，完成下列各题。

■ 判断题

  1. 将程序中的第2行去除，程序依然能正常运行。 （ ） {{ select(27) }}
  • √
  • ×
  1. 该程序的时间复杂度为 \(O(|c|^2)\)。 （ ） {{ select(28) }}
  • √
  • ×

■ 选择题

  1. 若将程序中的第15行去除，则程序的时间复杂度为（ ）。 {{ select(29) }}
  • \(O(10^{|c|})\)
  • \(O(100d|c|)\)
  • \(O(10d|c|)\)
  • \(O(10^{d|c|})\)
  1. 若输入为9 2，则输出为（ ）。 {{ select(30) }}
  • 1
  • 2
  • 4
  • 7
  1. 若输入为30 4，则输出为（ ）。 {{ select(31) }}
  • 3
  • 4
  • 6
  • 7
  1. （4分）若输入为 2025 6，则输出为（ ）。 {{ select(32) }}
  • 240
  • 256
  • 280
  • 338

三、完善程序

（1）题目描述：

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

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 265 + 5;
04 int n, pre[N], a[N], dp[N][3];
05 int main() {
06     scanf("%d", &n);
07     memset(dp, 0x3f, sizeof dp);
08     dp[0][0] = dp[0][1] = dp[0][2] = 0;
09     for (int i = 1; i <= n; i++)
10         scanf("%d", &a[i]);
11     ①;
12     for (int i = 1; i <= n; i++)
13         pre[i] = ②;
14     for (int i = 2, j; i <= n; i++)
15         dp[i][a[i]] = min([③]);
16     if (④)
17         dp[i][a[i] - 1] = 1 + min([⑤]);
18     }
19     printf("%d", min([ dp[n][0], dp[n][1], dp[n][2] ]));
20 }
  1. ①处应填（ ）。 {{ select(33) }}
  • dp[i][a[i]==2]=1
  • dp[i][a[i]==1]=1
  • dp[i][a[i]==0]=1
  • dp[i][a[i]]=1
  1. ②处应填（ ）。 {{ select(34) }}
  • pre[i-1] + a[i]
  • a[i] + a[i-1]
  • pre[i-1] + 1
  • 此处无法确定，需要更多上下文
  1. ③处应填（ ）。 {{ select(35) }}
  • dp[i-1][0], dp[i-1][1], dp[i-1][2]
  • dp[i][0], dp[i][1], dp[i][2]
  • dp[i-1][a[i-1]] + (a[i] != a[i-1])
  • 此处无法确定，需要更多上下文
  1. ④处应填（ ）。 {{ select(36) }}
  • a[i] > 0
  • a[i] >= 1
  • a[i] == 2
  • 此处无法确定，需要更多上下文
  1. ⑤处应填（ ）。 {{ select(37) }}
  • dp[i-1][0], dp[i-1][1], dp[i-1][2]
  • dp[i][0], dp[i][1], dp[i][2]
  • dp[i-1][a[i-1]] + 1
  • 此处无法确定，需要更多上下文

（2）题目描述：

给定一个长度为 n 的数组 a 和一个整数 k，最多可以修改 k 个元素的值（可以修改成任意值），求修改后可能的最小极差（最大值减最小值）。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 1005;
04 int n, k, a[N], p[N][N], ans[N][N];
05 int main() {
06     scanf("%d%d", &n, &k);
07     for (int i = 1; i <= n; i++)
08         scanf("%d", &a[i]);
09     sort(a + 1, a + n + 1);
10     for (int i = 1; i <= n; i++)
11         ①;
12     for (int j = 1; j <= k; j++)
13         for (int i = 1; i + j <= n; i++)
14             p[i][j] = min(p[i][j - 1], a[i + j]);
15     for (int j = 1; j <= k; j++)
16         for (int i = 1; i + j <= n; i++)
17             ②;
18     for (int i = 1; i <= n; i++) {
19         ans[i][0] = ③;
20         for (int j = 1; j <= k; j++) {
21             ans[i][j] = min(ans[i - 1][j] + a[i], ans[i][j - 1]);
22             for (int h = 0; ④; h++)
23                 ans[i][j] = min(ans[i][j], ⑤);
24         }
25     }
26     printf("%d\n", ans[n][k]);
27     return 0;
28 }
  1. ①处应填（ ）。 {{ select(38) }}
  • p[i][0]=i
  • p[i][0]=a[i]
  • p[i][i]=i
  • p[i][i]=a[i]
  1. ②处应填（ ）。 {{ select(39) }}
  • p[i][j] *=j
  • p[i][j] *=(j+1)
  • p[i][j] *=i
  • p[i][j] *=(i+1)
  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
  1. ④处应填（ ）。 {{ select(41) }}
  • h<=i&&h<=j
  • h<i&&h<=j
  • h<i&&h<j
  • h<=i&&h<j
  1. ⑤处应填（ ）。 {{ select(42) }}
  • ans[i-h-1][j-h]+p[i-h][h]
  • ans[i-h][j-h]+p[i-h][h]
  • ans[i][j-h]+p[i][h]
  • ans[i][j-h]+p[i-h][h]

CSP-J初赛模拟卷25-9

未参加
状态
已结束
规则
IOI(严格)
题目
1
开始于
2025-9-12 0:00
结束于
2025-10-2 20:00
持续时间
2 小时
主持人
参赛人数
0
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 129ms
  4. Powered by Hydro v5.0.0-beta.9 Community