A. CSP-J初赛模拟卷25-10
CSP-J初赛模拟卷25-10
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
普及组 CSP-J 2025 初赛模拟卷 10
一、单项选择题
-
以下列扩展名结尾的文件，不是多媒体文件的是（ ）。
{{ select(1) }}
- mp3
- txt
- avi
- jpg
- 以下关于链表和数组的描述中，错误的是（ ）。 {{ select(2) }}
- 数组和链表都可以排序
- 数组中查询元素的效率比较高
- 链表中插入和删除元素的效率比较高
- 向量和静态数组一样，不能动态调整数组大小
- 与 C++语言中的 cout << a > b ? 'a' : 'b'; 功能类似的是（ ）。 {{ select(3) }}
- 顺序结构
- 循环结构
- 条件结构
- 递推函数
- 下面的 C++代码中 data 占用（ ）字节内存空间。
{{ select(4) }}union Data { int no; double score; char name[6]; }; union Data data;
- 4
- 8
- 18
- 6
- 学号为 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
- 以下哪个不属于 STL 模板中队列的操作函数？（ ） {{ select(6) }}
- push
- pop
- empty
- top
- 在 C++语言中，（ ）算法的时间复杂度是 \(O(n\log n)\)。 {{ select(7) }}
- 插入排序
- 归并排序
- 选择排序
- 冒泡排序
- 以下关于字符串的判定语句中正确的是（ ） {{ select(8) }}
- 字符串一般以字符‘0’结尾
- 串的长度必须大于零
- string s; 中定义的 s 也可以看作字符数组，首字母是 s[0]
- 全部都由空格字符组成的串就是空串
- 以下算法中，（ ）算法用到了栈。 {{ select(9) }}
- BFS
- 二分查找
- DFS
- 贪心
- 32 位计算机系统中一个非负长整型指针变量 unsigned long long *p 占（ ）字节。 {{ select(10) }}
- 1
- 2
- 8
- 4
- 某山峰型数列有 1~2025 共 2025 个各不相同的数，先是奇数由小到大，后是偶数由大到小，即 1, 3, 5, 7, 9, ⋯, 2023, 2025, 2024, 2022, 2020, ⋯, 8, 6, 4, 2。现要求该数列进行检索，查找某正整数 x 的下标 (x 为 1~2025 中的某正整数，包含 1 和 2025)，最多检索（ ）次即可。 {{ select(11) }}
- 2025
- 11
- 10
- 9
- 在 C++程序中，lowbit(x)函数返回整数 x 在二进制表示下最低一位 1 以及后续 0 一起表示的数字，如 lowbit(12)=4。下面的表达式中，（ ）能得到相同的结果。 {{ select(12) }}
- x ^ (x - 1)
- x 6 (x - 1)
- x 6 (-x + 1)
- x | (x - 1)
- 某二叉树的中序遍历序列为 BDCEAFHG，后序遍历序列为 DECBHGFA，其前序遍历序列为（ ） {{ select(13) }}
- ABCDEFGH
- ABDCEFHG
- ABCDFEHG
- ABDCEFGH
- 有 5 条线段，长度分别为 1, 3, 5, 7, 9，从中任取 3 条能构成一个三角形的概率为（ ） {{ select(14) }}
- 1/2
- 3/10
- 1/5
- 2/5
- 对于非负整数组 \(\{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", 6n);
07 for (int i = 1; i <= n; i++)
08 scanf("%d", 6a[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 }
判断题
- 若将程序第 12 行中的 i 改成 i/2，程序的输出结果一定不会改变。（ ） {{ select(16) }}
- √
- ×
- （2 分）若将程序第 10 行中的 i+=2 改成 i++，程序的输出结果一定不会改变。（ ） {{ select(17) }}
- √
- ×
- 若将头文件#include <bits/stdc++.h>改成#include , 程序仍能正常运行。（ ） {{ select(18) }}
- √
- ×
选择题
- 若输入 4 1 3 6 7，则输出为（ ）。 {{ select(19) }}
- 0
- 1
- 2
- 3
- （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 >= .l) {
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 }
已知 k<=nm，保证 n,m 同阶，完成以下问题。
判断题
- 每次运行 check 时，第 7 行必定运行 n 次。（ ） {{ select(21) }}
- √
- ×
- 如果保证 m=1，则输出一定为 k。（ ） {{ select(22) }}
- √
- ×
- 若将第 21 行中的 r = mid 改成 r = mid - 1，程序输出一定不变。（ ） {{ select(23) }}
- √
- ×
- 第 24 行可以改成 cout << r << endl;。（ ） {{ select(24) }}
- √
- ×
选择题
- 该程序的时间复杂度为 ( )。 {{ select(25) }}
- \( O(n) \)
- \( O(n \log n) \)
- \( O(n^2) \)
- \( O(nk) \)
- 若输入为 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 &&tx<=n &&ty &&ty<=n &&c[tx][ty] == 1;
16 }
17 if (flag)
18 v.push_back(i*10+j),c[i][j]=1,dfs(x-1),c[i][j]='#';
19 }
20 if (!v.empty())
21 for (int i = 0; i < v.size(); ++i)
22 c[v[i] / 10][v[i] % 10] = '.';
23 }
24 int main() {
25 scanf("%d%d", &n, &m);
26 for (int i = 1; i <= n; ++i)
27 scanf("%s", c[i] + 1);
28 for (int i = 1; i <= n; ++i)
29 for (int j = 1; j <= n; ++j)
30 if (c[i][j] == '.')
31 c[i][j] = 1, dfs(m - 1), c[i][j] = '#';
32 return printf("%d\n", ans), 0;
33 }
判断题
- 将第 18 行中的 c[i][j]='#'去除，结果一定不变。（ ） {{ select(27) }}
- √
- ×
- 第 6 行运行的次数不超过 \(n^2\)。（ ） {{ select(28) }}
- √
- ×
选择题
- 若输入为 2 2 #...，则输出为（ ）。 {{ select(29) }}
- 0
- 1
- 2
- 3
- 若输入为 3 5 #.# ...#，则输出为（ ）。 {{ select(30) }}
- 2
- 3
- 4
- 5
- （4 分）若 n=3，m=3，则输出的最大值为（ ）。 {{ select(31) }}
- 16
- 18
- 22
- 26
- 若 n=4，m=13，则输出的最大值为（ ）。 {{ select(32) }}
- 488
- 496
- 512
- 560
三、完善程序
(1) 题目描述：
给定两个由小写字母构成的字符串 s1 和 s2，同时给定一个由数字 1,2,3…| operation | 组成的排列。按该排列顺序依次删除字符串 s1 相应位置上的字母，在删除过程中，约定各个字符的位置不变。请计算最多可以删除几次，字符串 s1 中仍然包含字符串 s2（即字符串 s2 仍然是字符串 s1 的子串）。
01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 2e5 + 5;
04 bool book[N];
05 char s1[N], s2[N];
06 vector <int> num;
07 int n = 1, len1, len2, ans, operation[N];
08 bool check(int x) {
09 num.clear();
10 for (int i = x + 1; i <= n; i++)
11 if (①)
12 num.push_back(operation[i]);
13 sort(num.begin(), num.end());
14 int i = 0, j = 1;
15 while (②)
16 j += ③;
17 return j == len2 + 1;
18 }
19 inline void fu(c(int l, int r) {
20 if (④) return;
21 int mid = (l + r) >> 1;
22 if (check(mid)) ans = mid, fu(c(mid + 1, r);
23 else fu(c(l, mid - 1));
24 }
25 int main() {
26 scanf("%s", s1 + 1);
27 scanf("%s", s2 + 1);
28 len1 = strlen(s1 + 1);
29 len2 = strlen(s2 + 1);
30 while (⑤) ++n;
31 n--;
32 for (int i = 1; i <= len2; i++)
33 book[int(s2[i])] = true;
34 fu(c(1, n));
35 printf("%d\n", ans);
36 return 0;
37 }
- ①处应填（ ）。 {{ select(33) }}
- book[s1[operation[i]]]
- book[s1[i]]
- !book[s1[operation[i]]]
- !book[s1[i]]
- ②处应填（ ）。 {{ select(34) }}
- i<num.size()&&j<=len2
- i<=num.size()&&j<=len2
- i<=num.size()&&j<=len2
- i<num.size()&&j<=len2
- ③处应填（ ）。 {{ select(35) }}
- s1[num[i++]]==s2[j]
- s1[num[i+1]]==s2[j]
- s1[num[i++]]==s2[j++]
- s1[num[i+1]]==s2[j++]
- ④处应填（ ）。 {{ select(36) }}
- l>=r
- l==r
- l>r
- l^r
- ⑤处应填（ ）。 {{ select(37) }}
- scanf("%d",50peration[n])
- ~scanf("%d",50peration[n])
- ~(cin>>operation[n])
- !scanf("%d",50peration[n])
（2）题目描述：
如果存在一个长度为 \( n \) 的排列（即该排列由 1, 2, 3, ..., \( n \) 这 \( n \) 个数字各出现一次组成），对于所有满足 \( 2 \leq i \leq n-1 \) 的整数 \( i \)，都有 \( p_i \leq p_{i-1}, p_i \geq p_{i+1} \)，或者 \( p_i \geq p_{i+1}, p_i \geq p_{i+1} \)，成立，则称这个序列为一个山峰山谷序列。 对所有长度为 \( n \) 的山峰山谷序列排序，求字典序第 \( k \) 大的排列。 \( dp_{i,j\neq i} \) 表示长度为 \( i \) 的排列中第一个数为 \( j \)，其中第一个数小于大于第二个数。
01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 105;
04 int n, k, dp[N][N][2], ans[N], vis[N];
05 signed main() {
06 scanf("%d%d", 6n, 6k);
07 dp[1][1][0] = dp[1][1][1] = 1;
08 dp[2][1][0] = dp[2][2][1] = 1;
09 for (int i = 2; i < n; ++i)
10 for (int j = 1; j <= i; ++j)
11 for (int k = 1; k <= i + 1; ++k)
12 if (①) dp[i + 1][k][1] += dp[i][j][0];
13 else ②;
14 for (int i = 1; i <= n; ++i) {
15 int las = 0, mk = 1;
16 if (i > 2 && ans[i - 1] < ans[i - 2])
17 mk = ③;
18 for (int j = mk; j <= n; ++j) if (!vis[j]) {
19 int cnt = 0;
20 for (int k = 1; k <= j; ++k) if (!vis[k]) cnt++;
21 int x = ④;
22 if (i == 1) x += dp[n][j][0];
23 if (x >= k) { las = j; break; }
24 ⑤;
25 }
26 ans[i] = las, vis[las] = 1;
27 }
28 for (int i = 1; i <= n; ++i)
29 printf("%d ", ans[i]);
30 return 0;
31 }
- ①处应填（ ）。 {{ select(38) }}
- j < k
- j <= k
- i < k
- i <= k
- ②处应填（ ）。 {{ 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]
- ③处应填（ ）。 {{ select(40) }}
- ans[i-1]+1
- ans[i-2]+1
- i+1
- ans[i-1]
- ④处应填（ ）。 {{ 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]
- ⑤处应填（ ）。 {{ select(42) }}
- k=x
- k=x*(n-i+1)
- k=x*cnt
- k=x*mk