ID: 71

Type: Objective

Difficulty: (None)

Uploaded By:

jike1994

Tags>

CSP通关之路

普及组CSP-J2025初赛模拟卷4

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

正整数2025与1800的最大公约数是（）。 {{ select(1) }}

15
25
45
225

表达式(('0' == 0) + 's' + 5 + 2.0)的结果类型为（）。 {{ select(2) }}

double
int
char
bool

对一个int类型的值，执行以下哪个操作后，一定会变回原来的值？（） {{ select(3) }}

左移5位，再右移5位
右移5位，再左移5位
按位或15，再按位与15
按位异或15，再按位异或15

在数组H[x]中，若存在(i < j) && (H[i] > H[j])，则称(H[i], H[j])为数组H[x]的一个逆序对。对于序列27, 4, 1, 59, 3, 26, 38, 15，在不改变顺序的情况下，去掉（）会使逆序对的个数减少4。 {{ select(4) }}

1
3
26
15

如果字符串s在字符串str中出现，则称字符串s为字符串str的子串。设字符串str = "oiers"，则str的非空子串的数目是（）。 {{ select(5) }}

17
16
15
14

以下哪种排序算法的平均时间复杂度最好？（） {{ select(6) }}

插入排序
归并排序
选择排序
冒泡排序

如果x和y均为int类型的变量，且y的值不为0，那么能正确判断"x是y的2倍"的表达式是（）。 {{ select(7) }}

(x >> 2 == y)
(x - 2 * y) % 2 != 0
(x / y == 2)
(x == 2 * y)

表达式a * (b + c) - d的后缀表达式为（）。 {{ select(8) }}

abcd*+ -
abc+*d -
abc*+d -
-+*abcd

关于计算机网络，下列说法中正确的是（）。 {{ select(9) }}

SMTP和POP3都是电子邮件发送协议
IPv6地址是从IPv4、IPv5一路升级过来的
计算机网络是一个在协议控制下的多机互连系统
192.168.0.1是A类地址

下列哪种语言不是面向对象的语言？（） {{ select(10) }}

Java
C++
Python
Fortran

信息学奥赛的所有课程和课程间的先修关系构成一个有向图G，我们用有向边<A, B>表示课程A是课程B的先修课，则要找到某门课程C的全部先修课，下面哪种方法不可行？（） {{ select(11) }}

BFS
DFS
枚举
BFS+DFS

一个字长为8位的整数的补码为11111001，则它的原码是（）。 {{ select(12) }}

00000111
10000110
10000111
11111001

元素A、B、C、D、E、F入栈的顺序为A, B, C, D, E, F，如果第一个出栈的是C，则最后一个出栈的不可能是（）。 {{ select(13) }}

一个三位数等于它的各位数字的阶乘之和，则此三位数的各位数字之和为（）。 {{ select(14) }}

9
10
11
多于一种情况

在一个非连通无向图G中有36条边，则该图至少有（）个顶点。 {{ select(15) }}

8
9
10
7

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 using i64 = long long;
05 
06 const i64 k = 3;
07 const i64 mod = 8;
08 
09 i64 toint(string s) {
10     sort(s.begin(), s.end());
11     i64 ans = 0;
12     for (int i = 0; i < s.length(); i++)
13         ans = (ans * k + (s[i] - 'a' + 1)) % mod;
14     return ans;
15 }
16 
17 vector<vector<string>> solve(vector<string> strs) {
18     map<i64, vector<string>> mp;
19     for (auto s : strs)
20         mp[toint(s)].push_back(s);
21     vector<vector<string>> ans;
22     for (auto v : mp)
23         ans.push_back(v.second);
24     return ans;
25 }
26 
27 int main() {
28     int n;
29     cin >> n;
30     vector<string> vec(n);
31     for (int i = 0; i < n; i++)
32         cin >> vec[i];
33     auto ans = solve(vec);
34     for (auto v : ans)
35         for (int i = 0; i < v.size(); i++)
36             cout << v[i] << " \n"[i == v.size() - 1];
37     return 0;
38 }

判断题

若程序输入6 eat tea tan ate nat bat，则程序输出bat（换行）eat tea ate（换行）tan ate（换行）。（） {{ select(16) }}

正确
错误

对于这段代码，toint("aaf") != toint("atmoa")。（） {{ select(17) }}

正确
错误

若将头文件#include <bits/stdc++.h>换为#include <iostream>，程序依然可以正常运行。（） {{ select(18) }}

正确
错误

选择题

若输入4 aad zpf zpz yyl，则输出是什么？（） {{ select(19) }}

aad（换行）zpf（换行）zpz（换行）yyl（换行）
aad zpf（换行）zpz yyl（换行）
aad zpf zpz（换行）yyl（换行）
aad zpf zpz yyl（换行）

这个程序的时间复杂度是多少？（） {{ select(20) }}

O(n)
O(n^2)
O(nlogn)
O(n^2logn)

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 int calc(vector<vector<int>>& grid) {
05     int n = grid.size(), m = grid[0].size();
06     vector<int> dp(m);
07     dp[0] = (grid[0][0] == 0);
08     for (int i = 0; i < n; i++)
09         for (int j = 0; j < m; j++) {
10             if (grid[i][j] == 1) {
11                 dp[j] = 0;
12                 continue;
13             }
14             if (j - 1 >= 0 && grid[i][j - 1] == 0)
15                 dp[j] += dp[j - 1];
16         }
17     return dp[m - 1];
18 }
19 
20 int main() {
21     int n, m;
22     cin >> n >> m;
23     vector<vector<int>> a(n, vector<int>(m));
24     for (int i = 0; i < n; i++)
25         for (int j = 0; j < m; j++)
26             cin >> a[i][j];
27     cout << calc(a) << endl;
28     return 0;
29 }

判断题

若输入3 3 0 0 0 0 1 0 0 0 0，则输出为2。（） {{ select(21) }}

正确
错误

若f[i][j]表示从(0,0)走到(i, j)的路径数，则在第10~19行的循环中，f[i][j] = dp[j]。（） {{ select(22) }}

正确
错误

（2分）若将第23行的代码改为vector<vector<int>> a(n + 1, vector<int>(m + 1))，则当输入的n = 3，m = 3时，calc函数中的n = 3，m = 3。（） {{ select(23) }}

正确
错误

选择题

当输入的a数组为{{0, 0, 1}, {1, 1, 0}, {0, 1, 0}, {1, 0, 1}, {0, 0, 0}}时，程序的输出为（）。 {{ select(24) }}

若删除第10~13行的代码，则当输入的a数组为{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}时，程序的输出为（）。 {{ select(25) }}

（4分）当输入的a数组为{{0, 0, 2}, {0, 1, 2}, {5, 3, 4}}时，程序的输出为（）。 {{ select(26) }}

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 using i64 = long long;
05 
06 int cmp(string v1, string v2) {
07     int i = 0, j = 0;
08     while (i < v1.length() || j < v2.length()) {
09         i64 num1 = 0, num2 = 0;
10         while (i < v1.length() && v1[i] != '.') {
11             num1 = num1 * 10 + (v1[i++] - '0');
12         }
13         while (j < v2.length() && v2[j] != '.') {
14             num2 = num2 * 10 + (v2[j++] - '0');
15         }
16         if (num1 > num2)
17             return 1;
18         else if (num1 < num2)
19             return -1;
20         i++, j++;
21     }
22     return 0;
23 }
24 
25 int main() {
26     int n;
27     cin >> n;
28     vector<string> s(n);
29     for (int i = 0; i < n; i++){
30         cin >> s[i];
31         if (s[i][0] == '.'){
32             cout << "err" << endl;
33             return 0;
34          }
35     }
36     for (int i = 0; i < n; i++)
37         for (int j = 0; j < n; j++)
38             cout << cmp(s[i], s[j]) << " \n"[j == n - 1];
39 
40     return 0;
41 }

判断题

任取0 <= i < n，都有f[i][i] = 0。（） {{ select(27) }}

正确
错误

若输入3 1.0.1 2.1 1.1.0，则f[0][1] = 1。（） {{ select(28) }}

正确
错误

任取0 <= i, j < n，都有f[i][j] + f[j][i] = 0。（） {{ select(29) }}

正确
错误

选择题

当输入的s数组为{"1.2.3", "4.5", ".2"}时，程序输出中第一行第二个数为（）。 {{ select(30) }}

-1
0
1
不存在

（4分）若删除第31~34行代码，则当输入的s数组为{"1.2.3", "4.5", ".2"}时，f[0][2]的值为（）。 {{ select(31) }}

-1
0
1
未计算

阅读代码可知，当两个点之间的数为（）时，cmp函数将无法得到正确的结果。 {{ select(32) }}

1 * 10^9
2 * 10^9
4 * 10^18
-1

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

(1) 题目描述：

输入n（3 ≤ n ≤ 2 × 10^5）和长为n的数组a（1 ≤ a[i] ≤ 1 × 10^9）。你需要从a中恰好删除一个数，得到长为n-1的数组a'。然后生成一个长为n-2的数组b，其中b[i] = GCD(a'[i], a'[i+1])。你需要让数组b是非降序列，即b[i] ≤ b[i+1]。能否做到？输出YES或NO。 (提示：枚举i，考察删除a[i]后对数组产生的影响。)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 int gcd(int x, int y) {
05     return !y ? x : gcd(y, x % y);
06 }
07 
08 void solve() {
09     int n;
10     cin >> n;
11     vector<int> a(n + 1), b(n + 2);
12     for (int i = 1; i <= n; i++)
13         cin >> a[i];
14     b[n] = b[n + 1] = ①;
15     for (int i = 1; i < n; i++)
16         b[i] = gcd(a[i], a[i + 1]);
17     vector<int> pre(n + 1), suf(n + 2);
18     pre[0] = 1;
19     for (int i = 1; i <= n; i++)
20         pre[i] = pre[i - 1] & (②);
21     suf[n + 1] = 1;
22     for (int i = n; i > 1; i--)
23         suf[i] = suf[i + 1] & (b[i] <= b[i + 1]);
24     bool flag = ③;
25     for (int i = 2; i < n; i++) {
26         int cur = ④;
27         if (⑤ && b[i - 2] <= cur && cur <= b[i + 1])
28             flag = true;
29     }
30     cout << (flag ? "YES\n" : "NO\n");
31     return;
32 }
33 
34 int main() {
35     int t=1;
36     //cin >> t;
37     while (t--)
38         solve();
39     return 0;
40 }

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

0
3E9
-1E9
2E9

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

b[i] >= b[i - 1]
b[i] <= b[i - 1]
b[i] > b[i - 1]
b[i] < b[i - 1]

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

pre[n - 2] & suf[2]
pre[n - 2] | suf[2]
pre[n - 2] ^ suf[2]
pre[n - 2] - suf[2]

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

gcd(a[i], b[i])
gcd(a[i], a[i + 1])
gcd(a[i - 1], a[i + 1])
gcd(a[i - 1], a[i])

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

pre[i - 2] && suf[i + 1]
pre[i - 1] && suf[i + 1]
pre[i - 2] || suf[i + 1]
pre[i - 1] || suf[i + 1]

(2) 题目描述：

输入n（1 ≤ n ≤ 2 × 10^5）和长为n的数组a（1 ≤ a[i] ≤ 1 × 10^6）。对于数组B，如果满足B[0] + 1 = len(B)，那么称数组B为"块"。对于数组A，如果可以将其划分成若干个"块"，那么称数组A是合法的。例如A = [3, 3, 4, 5, 2, 6, 1]是合法的，因为A = [3, 3, 4, 5] + [2, 6, 1]，这两段都是块。把数组a变成合法数组，至少要删除多少个元素？ (提示：令dp[i]表示将 a[i]到a[n]变成合法数组最少要删除的元素个数。)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int inf = 0x3f3f3f3f;
05 
06 int main() {
07     int n;
08     cin >> n;
09     vector<int> a(n + 1), dp(①, inf);
10     for (int i = 1; i <= n; i++)
11         cin >> a[i];
12     dp[n + 1] = ②;
13     for (int i = n; i >= 1; i--) {
14         dp[i] = ③;
15         if (i + a[i] + 1 <= n + 1)
16             dp[i] = min(dp[i], ④);
17     }
18     cout << ⑤ << endl;
19     return 0;
20 }

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

n - 1
n
n + 1
n + 2

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

0
1
-1
inf

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

dp[i + 1]
dp[i - 1]
dp[i + 1] + 1
dp[i - 1] + 1

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

dp[i + a[i] + 1]
dp[i + a[i]]
dp[a[i] + 1]
dp[i + a[i] - 1]

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

dp[n]
dp[1]
dp[n - 1]
dp[0]

#71. 普及组CSP-J2025初赛模拟卷4

普及组CSP-J2025初赛模拟卷4

普及组CSP-J2025初赛模拟卷4

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）

(1)

判断题

选择题

(2)

判断题

选择题

(3)

判断题

选择题

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

(1) 题目描述：

(2) 题目描述：

Status

Development

Support

#71. 普及组CSP-J2025初赛模拟卷4

普及组CSP-J2025初赛模拟卷4

普及组CSP-J2025初赛模拟卷4

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）

(1)

判断题

选择题

(2)

判断题

选择题

(3)

判断题

选择题

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

(1) 题目描述：

(2) 题目描述：

Status

Development

Support

SIGN IN