选择题 共15道
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15阅读程序 共17道
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32完善程序 共10道
33 34 35 36 37 38 39 40 41 42E1039 2025年CSP-J模拟卷-5-练习
选择题 共15道
01 如果 a 和 b 都是 char 类型的变量，下列哪个语句不符合 C++语法？（ ） 2分
登录后查看选项
02 泛洪填充算法属于（ ）算法。 2分
登录后查看选项
03
在下列代码的横线处填写（ ），可以使得输出是 “5 8”。
#include < bits/stdc++.h >
using namespace std;
int main()
{
int x = 8, y = 5;
__________;
x = x ^ y;
y = x ^ y;
cout << x << " " << y << endl;
return 0;
}
2分
#include < bits/stdc++.h >
using namespace std;
int main()
{
int x = 8, y = 5;
__________;
x = x ^ y;
y = x ^ y;
cout << x << " " << y << endl;
return 0;
}
登录后查看选项
04 小写字母 a 的 ASCII 码值为 97，小写字母 z 的 ASCII 码值用八进制数表示为（ ）。 2分
登录后查看选项
05 从 n 个正整数 1, 2, …, n 中任意取出两个不同的数，若取出的两数之和等于 5 的概率为 1/14，则 n 为（ ）。 2分
登录后查看选项
06 下面不可以用作 C++程序中的变量名的是（ ）。 2分
登录后查看选项
07 设有 n 个数和 m 个桶，桶排序算法（桶内采用插入排序）在最坏情况下的时间复杂度是（ ）。 2分
登录后查看选项
08 一个二维数组定义为 long long a[5][8]; ，则这个二维数组占用内存空间的大小为（ ）字节。 2分
登录后查看选项
09 下列关于 C++语言中自定义函数的叙述，正确的是（ ）。 2分
登录后查看选项
10 为了防范计算机病毒，保护个人隐私和信息安全，下列做法中正确的是（ ）。 2分
登录后查看选项
11
下列代码可以用来求最长上升子序列（LIS）的长度，如果输入是 5 1 7 3 5 9，则输出是（ ）。
#include < bits/stdc++.h >
using namespace std;
int a[2025], dp[2025];
int main()
{
int n, i, j, ret = -1;
cin >> n;
for(i=1; i<=n; ++i)
{
cin >> a[i];
dp[i] = 1;
}
for(i=1; i<=n; ++i)
for(j=1; j < i; ++j)
if(a[j] < a[i])
dp[i] = max(dp[i], dp[j]+1);
for(i=1; i<=n; ++i)
{
ret = max(ret, dp[i]);
cout << dp[i] << " ";
}
cout << ret << endl;
return 0;
}
2分
#include < bits/stdc++.h >
using namespace std;
int a[2025], dp[2025];
int main()
{
int n, i, j, ret = -1;
cin >> n;
for(i=1; i<=n; ++i)
{
cin >> a[i];
dp[i] = 1;
}
for(i=1; i<=n; ++i)
for(j=1; j < i; ++j)
if(a[j] < a[i])
dp[i] = max(dp[i], dp[j]+1);
for(i=1; i<=n; ++i)
{
ret = max(ret, dp[i]);
cout << dp[i] << " ";
}
cout << ret << endl;
return 0;
}
登录后查看选项
12 已知逻辑表达式 A=true，B=C=D=false，则以下逻辑表达式中取值为真的是（ ）。 2分
登录后查看选项
13 某二叉树的前序遍历序列为 ABDFCEGH，中序遍历序列为 BFDAGEHC，则下列说法中正确的是（ ）。 2分
登录后查看选项
14 设 p 为 2~100 范围内的质数，p^3+7p^2 为完全平方数，则 p 的取值有（ ）种不同的可能。 2分
登录后查看选项
15 在图的广度优先搜索中，既要维护一个标志数组来标志已访问的结点，还需使用（ ）结构存放结点以实现遍历。 2分
登录后查看选项
阅读程序 共17道
16
01 #include < bits/stdc++.h >
02 using namespace std;
03
04 bool isValid(string s) {
05 stack stk;
06 for (char ch: s) {
07 if (ch == '(' || ch == '[' || ch == '{') {
08 stk.push(ch);
09 } else {
10 if (stk.empty()) {
11 return false;
12 }
13 if (ch == ')' && stk.top() != '(') {
14 return false;
15 }
16 if (ch == ']' && stk.top() != '[') {
17 return false;
18 }
19 if (ch == '}' && stk.top() != '{') {
20 return false;
21 }
22 stk.pop();
23 }
24 }
25 return stk.empty();
26 }
27
28 int main() {
29 string s;
30 cin >> s;
31 if(isValid(s))
32 cout << "Valid" << endl;
33 else
34 cout << "Invalid" << endl;
35 return 0;
36 }
若程序输入为 ([{}])，则程序输出 Valid。 ( )
1.5分
01 #include < bits/stdc++.h >
02 using namespace std;
03
04 bool isValid(string s) {
05 stack stk;
06 for (char ch: s) {
07 if (ch == '(' || ch == '[' || ch == '{') {
08 stk.push(ch);
09 } else {
10 if (stk.empty()) {
11 return false;
12 }
13 if (ch == ')' && stk.top() != '(') {
14 return false;
15 }
16 if (ch == ']' && stk.top() != '[') {
17 return false;
18 }
19 if (ch == '}' && stk.top() != '{') {
20 return false;
21 }
22 stk.pop();
23 }
24 }
25 return stk.empty();
26 }
27
28 int main() {
29 string s;
30 cin >> s;
31 if(isValid(s))
32 cout << "Valid" << endl;
33 else
34 cout << "Invalid" << endl;
35 return 0;
36 }
登录后查看选项
17 若将第10~12行代码删除，则程序依然可以正常运行。 ( ) 1.5分
登录后查看选项
18 若删除头文件 <bits/stdc++.h>，则只需要添加 <iostream> 头文件就可以通过编译。 ( ) 2分
登录后查看选项
19
若输入 ((({[]}})))，则输出是什么？ ( )
3分
登录后查看选项
20 这个程序的时间复杂度是多少？ ( ) 3分
登录后查看选项
21
01 #include < bits/stdc++.h >
02 using namespace std;
03
04 int main() {
05 int n;
06 cin >> n;
07 vector a(n);
08 for(int i = 0; i < n; i++)
09 cin >> a[i];
10 vector dp(n + 1, 0);
11 for(int i = 0; i < n; i++) {
12 if(i >= 2)
13 dp[i] = max(dp[i - 1], dp[i - 2] + a[i]);
14 else
15 dp[i] += a[i];
16 if(i >= 1)
17 dp[i] = max(dp[i], dp[i - 1]);
18 }
19 int ans = 0;
20 for(int i = 0; i < n; i++) {
21 ans = max(ans, dp[i]);
22 }
23 cout << ans << endl;
24 return 0;
25 }
若输入 5 2 7 9 3 1，则输出为 12。 ( )
1.5分
01 #include < bits/stdc++.h >
02 using namespace std;
03
04 int main() {
05 int n;
06 cin >> n;
07 vector a(n);
08 for(int i = 0; i < n; i++)
09 cin >> a[i];
10 vector dp(n + 1, 0);
11 for(int i = 0; i < n; i++) {
12 if(i >= 2)
13 dp[i] = max(dp[i - 1], dp[i - 2] + a[i]);
14 else
15 dp[i] += a[i];
16 if(i >= 1)
17 dp[i] = max(dp[i], dp[i - 1]);
18 }
19 int ans = 0;
20 for(int i = 0; i < n; i++) {
21 ans = max(ans, dp[i]);
22 }
23 cout << ans << endl;
24 return 0;
25 }
登录后查看选项
22 这段代码对应的状态转移方程为 dp[i] = max(dp[i-1], dp[i-2]+a[i]), i>=2；初值为 dp[0] = a[0], dp[1] = a[1]。 ( ) 1.5分
登录后查看选项
23 （2分）在主函数中，访问 dp[n] 不会发生越界错误。 ( ) 1.5分
登录后查看选项
24 当输入的 a 数组为 {2, 1, 1, 2} 时，程序的输出为 ( )。 3分
登录后查看选项
25 若将第 13 行改为 dp[i] = max(dp[i-1], dp[i-2] - a[i]);，则当输入的 a 数组为 {10, 1, 0, 25, 3} 时，程序的输出为 ( )。 3分
登录后查看选项
26 （4分）当输入的 a 数组为 {0, 2, 3, 0, 5, 6, 0, 8, 9} 时，程序的输出为 ( )。 4分
登录后查看选项
27
01 #include < bits/stdc++.h >
02 using namespace std;
03
04 int bfs(vector>& grid) {
05 const int m = grid.size(), n = grid[0].size();
06 const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
07 using pii = pair;
08 queue q;
09 vector> vis(m + 1, vector(n + 1));
10 int ans = 0, tot = 0, cnt = 0;
11 for(int i = 0; i < m; i++) {
12 for(int j = 0; j < n; j++) {
13 if(grid[i][j] == 2)
14 q.push({i, j}), vis[i][j] = 1;
15 tot += (grid[i][j] != 0);
16 }
17 }
18 while(!q.empty()) {
19 int cur = q.size();
20 for(int i = 1; i <= cur; i++) {
21 auto u = q.front();
22 int x = u.first, y = u.second;
23 q.pop();
24 cnt++;
25 for(int j = 0; j < 4; j++) {
26 int cx = x + dx[j], cy = y + dy[j];
27 if(cx < 0 || cx >= m || cy < 0 || cy >= n ||
28 vis[cx][cy] || grid[cx][cy] == 0)
29 continue;
30 if(grid[cx][cy] == 1)
31 q.push({cx, cy}), vis[cx][cy] = 1;
32 }
33 }
34 ans++;
35 }
36 if(tot == cnt)
37 return max(0, ans - 1);
38 else
39 return -1;
40 }
41
42 int main() {
43 int m, n;
44 cin >> m >> n;
45 vector> a(m, vector(n));
46 for(int i = 0; i < m; i++)
47 for(int j = 0; j < n; j++)
48 cin >> a[i][j];
49 cout << bfs(a) << endl;
50 return 0;
51 }
当输入的 a 数组为 {{2,1,1}, {1,1,0}, {0,1,1}} 时，程序的输出为 4。 ( )
1.5分
01 #include < bits/stdc++.h >
02 using namespace std;
03
04 int bfs(vector>& grid) {
05 const int m = grid.size(), n = grid[0].size();
06 const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
07 using pii = pair;
08 queue q;
09 vector> vis(m + 1, vector(n + 1));
10 int ans = 0, tot = 0, cnt = 0;
11 for(int i = 0; i < m; i++) {
12 for(int j = 0; j < n; j++) {
13 if(grid[i][j] == 2)
14 q.push({i, j}), vis[i][j] = 1;
15 tot += (grid[i][j] != 0);
16 }
17 }
18 while(!q.empty()) {
19 int cur = q.size();
20 for(int i = 1; i <= cur; i++) {
21 auto u = q.front();
22 int x = u.first, y = u.second;
23 q.pop();
24 cnt++;
25 for(int j = 0; j < 4; j++) {
26 int cx = x + dx[j], cy = y + dy[j];
27 if(cx < 0 || cx >= m || cy < 0 || cy >= n ||
28 vis[cx][cy] || grid[cx][cy] == 0)
29 continue;
30 if(grid[cx][cy] == 1)
31 q.push({cx, cy}), vis[cx][cy] = 1;
32 }
33 }
34 ans++;
35 }
36 if(tot == cnt)
37 return max(0, ans - 1);
38 else
39 return -1;
40 }
41
42 int main() {
43 int m, n;
44 cin >> m >> n;
45 vector> a(m, vector(n));
46 for(int i = 0; i < m; i++)
47 for(int j = 0; j < n; j++)
48 cin >> a[i][j];
49 cout << bfs(a) << endl;
50 return 0;
51 }
登录后查看选项
28 bfs 函数的时间复杂度为 O(nm)。 ( ) 1.5分
登录后查看选项
29 由代码可知，格子中的一个 2 可以把八个方向上的 1 都变为 2。 ( ) 1.5分
登录后查看选项
30 当输入的 a 数组为 {{2,1,1}, {0,1,1}, {1,0,1}} 时，程序的输出为 ( )。 3分
登录后查看选项
31 （4分）如果删掉 bfs 函数中与 vis 数组相关的内容，不可能发生的结果是 ( )。 4分
登录后查看选项
32 当输入的 a 数组为 {{0,2}} 时，程序的输出为 ( )。 3分
登录后查看选项
完善程序 共10道
33
（1）题目描述：
给定一个长度小于等于 10^6 的只包含小写英文字母的字符串 s，输出有多少个子串满足以 heavy 开头并以 metal 结尾。
01 #include < bits/stdc++.h >
02 using namespace std;
03
04 int main() {
05 string s;
06 cin >> s;
07 long long cnt = ①, ans = 0;
08 for(int i = 4; i <= ②; i++) {
09 auto cur = ③;
10 if(④)
11 cnt++;
12 else if(cur == "metal")
13 ⑤;
14 }
15 cout << ans << endl;
16 return 0;
17 }
33. ①处应填 ( )。
3分
给定一个长度小于等于 10^6 的只包含小写英文字母的字符串 s，输出有多少个子串满足以 heavy 开头并以 metal 结尾。
01 #include < bits/stdc++.h >
02 using namespace std;
03
04 int main() {
05 string s;
06 cin >> s;
07 long long cnt = ①, ans = 0;
08 for(int i = 4; i <= ②; i++) {
09 auto cur = ③;
10 if(④)
11 cnt++;
12 else if(cur == "metal")
13 ⑤;
14 }
15 cout << ans << endl;
16 return 0;
17 }
登录后查看选项
34 ②处应填 ( )。 3分
登录后查看选项
35 ③处应填 ( )。 3分
登录后查看选项
36 ④处应填 ( )。 3分
登录后查看选项
37 ⑤处应填 ( )。 3分
登录后查看选项
38
（2）题目描述：
输入 l 和 r（1≤l≤r≤10^18）。如果整数 x 的首位数字等于末位数字，那么称 x 是合法数字。例如 101,477474,9 是合法数字，而 47,253,1020 不是合法数字。输出 [l, r] 中有多少个合法数字。
（提示：考虑最低位和最高位之间的关系。）
01 #include < bits/stdc++.h >
02 using namespace std;
03 long long l, r;
04 long long fir(long long g) {
05 while(g>=10) ①;
06 return g;
07 }
08 long long fin(long long g) {
09 return g%10;
10 }
11 long long solve(long long n) {
12 if(n<=9)return n;
13 else {
14 long long base=②;
15 long long first=fir(n);
16 bool flag=③;
17 return ④;
18 }
19 }
20 int main() {
21 cin>>l>>r;
22 cout << ⑤ << endl;
23 return 0;
24 }
38. ①处应填 ( )。
3分
输入 l 和 r（1≤l≤r≤10^18）。如果整数 x 的首位数字等于末位数字，那么称 x 是合法数字。例如 101,477474,9 是合法数字，而 47,253,1020 不是合法数字。输出 [l, r] 中有多少个合法数字。
（提示：考虑最低位和最高位之间的关系。）
01 #include < bits/stdc++.h >
02 using namespace std;
03 long long l, r;
04 long long fir(long long g) {
05 while(g>=10) ①;
06 return g;
07 }
08 long long fin(long long g) {
09 return g%10;
10 }
11 long long solve(long long n) {
12 if(n<=9)return n;
13 else {
14 long long base=②;
15 long long first=fir(n);
16 bool flag=③;
17 return ④;
18 }
19 }
20 int main() {
21 cin>>l>>r;
22 cout << ⑤ << endl;
23 return 0;
24 }
登录后查看选项
39 ②处应填 ( )。 3分
登录后查看选项
40 ③处应填 ( )。 3分
登录后查看选项
41 ④处应填 ( )。 3分
登录后查看选项
42 ⑤处应填 ( )。 3分
登录后查看选项