#76. 普及组CSP-J2025初赛模拟卷9
-
ID: 76
Type: Objective
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
jike1994
Tags> 普及组CSP-J2025初赛模拟卷9
普及组CSP-J2025初赛模拟卷9
一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
- （1ACF）16和（0456）16这两个十六进制数做加法的结果是（ ） {{ select(1) }}
- (1F25)16
- (7975)10
- (17455)8
- (111110010011)2
- 一个64位无符号长整型变量占用（ ）字节。 {{ select(2) }}
- 32
- 4
- 16
- 8
- 下列选项中，（ ）判断字符串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());
- 已知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
- 指针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;
- 以下哪个特性是数组和链表共有的？（ ） {{ select(6) }}
- 动态分配
- 元素之间的次序关系
- 通过索引访问
- 存储连续
- 下面关于哈夫曼树的描述中，正确的是（ ） {{ select(7) }}
- 哈夫曼树一定是完全二叉树
- 哈夫曼树一定是平衡二叉树
- 哈夫曼树中权值最小的两个结点互为兄弟结点
- 哈夫曼树中左子结点小于父结点，右子结点大于父结点
- 已知一棵二叉树有2025个结点，则其中至多有（ ）个结点有2个子结点。 {{ select(8) }}
- 1010
- 1011
- 1012
- 1013
- 下面的说法中正确的是（ ） {{ select(9) }}
- 计算机网络按照拓扑结构分为星型、环型、总线型等
- 互联网的基础是OSI七层协议而不是TCP/IP协议族
- 现代计算机网络主要采用电路交换技术
- 10.10.1.1是D类IP地址
- 下面关于图的说法中正确的是（ ） {{ select(10) }}
- 所有点数为奇数的连通图，一定可以一笔画成
- 所有只有两个奇度点[其余均为偶度点]的连通图，一定可以一笔画成
- 哈密顿图一定是欧拉图，而欧拉图未必是哈密顿图
- 哈密顿图不一定是欧拉图，而欧拉图一定是哈密顿图
- （ ）是一种选优搜索法，按选优条件向前搜索以达到目标。当搜索到某一步时，如果发现原先的选择并不优或者达不到目标，就后退一步重新选择。 {{ select(11) }}
- 二分算法
- 动态规划
- 回溯法
- 贪心算法
- 动态规划是将一个问题分解为一系列子问题来求解，下面（ ）属于动态规划问题。 {{ select(12) }}
- 多重背包
- 排队打水
- 有序数组找数
- 全排列
- 设无向图G的邻接矩阵如下图所示，则G的顶点数和边数分别为（ ）
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
{{ select(13) }}
- 4,5
- 5,8
- 4,10
- 5,5
- 某条道路从东到西有8个路灯，巡查员为了维护方便，在每根灯杆上都安装了开关，第t个开关能够切换前t个灯的状态（t=1~8，灯开或关），一开始灯全是开的。巡查员通过控制开关一共能得到（ ）种不同灯的开或者关的组合状态。 {{ select(14) }}
- 128
- 256
- 127
- 255
- 某四位正整数abcd满足如下条件（a,n也是正整数，b,c,d是非负整数）：abcd=1^3+2^3+...+n^3, abcd=(1+2+3+...+n)^2, abcd=(ab+cd)^2, 这样的正整数abcd共有（ ）个。 {{ select(15) }}
- 0
- 1
- 2
- 3
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）
(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 }
判断题
- 第17行最多会运行一次。（ ） {{ select(16) }}
- 正确
- 错误
- （2分）当程序运行至第19行时，x一定在[1,n]范围内。（ ） {{ select(17) }}
- 正确
- 错误
- 若将第3行改成
const int N = 100;，一定不会出现数组越界问题。（ ） {{ select(18) }}
- 正确
- 错误
选择题
- 若输入
4 2 mark 1 4 5 7 10，则输出为（ ） {{ select(19) }}
- m
- a
- r
- k
- （4分）若输入
7 3 creamii 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 }
判断题
- 第10行可以写成
cnt[j] += a[i] % 2。（ ） {{ select(21) }}
- 正确
- 错误
- 第21行一定不会溢出
int上界。（ ） {{ select(22) }}
- 正确
- 错误
- 若输入为
1 q，则输出为q^2。（ ） {{ select(23) }}
- 正确
- 错误
- 若输入为
3 1 3 5，则输出为51。（ ） {{ select(24) }}
- 正确
- 错误
选择题
- 该程序的时间复杂度为（ ） {{ select(25) }}
- O(n)
- O(nlogn)
- O(n^2)
- O(nlog^2 * n)
- 若输入为
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 }
判断题
- 将程序中的第2行去除，程序依然能正常运行。（ ） {{ select(27) }}
- 正确
- 错误
- 该程序的时间复杂度为O(|c|2)。（ ） {{ select(28) }}
- 正确
- 错误
选择题
- 若将程序中的第15行去除，则程序的时间复杂度为（ ） {{ select(29) }}
- O(10^(|c|) )
- O(100d * |c|)
- O(10d * |c|)
- O(10^(d|c|) )
- 若输入为
9 2，则输出为（ ） {{ select(30) }}
- 1
- 2
- 4
- 7
- 若输入为
30 4，则输出为（ ） {{ select(31) }}
- 3
- 4
- 6
- 7
- （4分）若输入为
2025 6，则输出为（ ） {{ select(32) }}
- 240
- 256
- 280
- 338
三、完善程序（单选题，每小题3分，共计30分）
(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 = 2e5 + 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; i <= n; i++)
15 dp[i][a[i]] = min({③});
16 if (④)
17 dp[i][a[i] - 1] = 1 + min({⑤});
18 printf("%d", min({dp[n][0], dp[n][1], dp[n][2]}));
19 return 0;
20 }
- ①处应填（ ） {{ 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
- ②处应填（ ） {{ select(34) }}
- a[i] ? pre[i - 1] : i
- a[i] ? i : pre[i - 1]
- a[i] == 2 ? pre[i - 1] : i
- a[i] == 2 ? i : 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）次的情况下，数组的总和可能达到的最小值。
01 #include<bits/stdc++.h>
02 using namespace std;
03 const int N = 3e5 + 5;
04 int n, k, a[N], p[N][11], ans[N][11];
05 int main(){
06 scanf("%d%d", &n, &k);
07 for (int i = 1; i <= n; i++){
08 scanf("%d", &a[i]);
09 ①;
10 }
11 for (int j = 1; j <= k; j++)
12 for (int i = 1; i + j <= n; i++)
13 p[i][j] = min(p[i][j - 1], a[i + j]);
14 for (int j = 1; j <= k; j++)
15 for (int i = 1; i + j <= n; i++)
16 ②;
17 for (int i = 1; i <= n; i++){
18 ans[i][0] = ③;
19 for (int j = 1; j <= k; j++){
20 ans[i][j] = min(ans[i - 1][j] + a[i], ans[i][j - 1]);
21 for (int h = 0; ④; h++)
22 ans[i][j] = min(ans[i][j], ⑤);
23 }
24 }
25 printf("%d\n", ans[n][k]);
26 return 0;
27 }
- ①处应填（ ） {{ 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 - 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]