2025 CSP-J 初赛模拟题 1 - 题目

时间限制：1000 ms 内存限制：512 MB 类型：传统评测：文本比较上传者： cwc

提交提交记录统计讨论

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

1. 电子邮件地址中的用户名与网络服务器主机名之间的连接符号为（）。

A. #

B. $

C. @

D. &

2. 计算的结果，并选择答案的十进制：（）

3. 下列数值中与不等价的为（）。

4. 现有幅分辨率为像素的位真彩色图像，大约需要（）存储空间。

A. GB

B. GB

C. GB

D. GB

5. 一个栈的入栈序列为 ABCDE，则不可能的出栈序列为（）。

A. CDEBA

B. ABECD

C. BDECA

D. ACDEB

6. 一棵完全二叉树的节点总数为，设根节点高度为，这棵树的高度为（）。

7. 已知二叉树的中序遍历为 AFBEDC，后序遍历为 AFECDB，则该二叉树的前序遍历为（）。

A. BAFEDC

B. BFAEDC

C. BAFDEC

D. BFADEC

8. 以下（）数据不能用 char 类型存储。

9. 下列对各种排序的表述不正确的是（）。

A. 简单选择排序是稳定的排序算法

B. 冒泡排序是稳定的排序算法

C. 简单插入排序需要进行关键字比较操作

D. 归并排序需要进行关键字比较操作

10. 运行以下代码片段，会输出（）。

int a[2] = {20, 25};
int *p = a;
int *q = p;
p++;
cout << *p << " " << *q << endl;

11. 下列对数组与链表的表述不正确的是（）。

A. 数组需事先估计存储空间；链表则不必，链表的大小可动态调整

B. 数组可随机访问任一元素，链表不支持随机访问

C. 插入删除元素时，数组需要移动元素，而链表不需要移动元素

D. 数组可以排序，链表不能排序

12. 个班分配个三好学生名额，每个班至少有一个名额，一共有（）种分配方案。

13. 由个 a，个 b，个 c 构成的所有字符串中，包含子串 abc 的共有（）个。

14. 假设有一组字符 a,b,c,d,e,f，对应的频率分别为 , , , , , 。请问以下（）选项是字符 abcdef 分别对应的一组哈夫曼编码。

15. 考虑一个无向图，度数为的点有 x 个，剩余 y 个点度数为，问这个图有（）条边。

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

（1）

01 #include <iostream>
02 #include <string>
03 using namespace std;
04 int cnt['z' + 1];
05 int main() {
06     string s;
07     cin >> s;
08     int len = s.size();
09     for (int i = 0; i < len; i++) {
10         cnt[s[i]]++;
11     }
12     int Min = 100, Max = 0;
13     for (char ch = 'a'; ch <= 'z'; ch++) {
14         if (cnt[ch] > Max) Max = cnt[ch];
15         if (cnt[ch] && cnt[ch] < Min) Min = cnt[ch];
16     }
17     cout << Min << " " << Max << endl; 
18     return 0;
19 }

输入的字符串只含小写英文字母且长度不超过，完成下面的判断题和单选题。

判断题

第行 int cnt['z' + 1]; 可以修改为 int cnt['Z' + 1]; 而不影响程序的正常运行。（）
当输入为 helloworld 时，程序的输出为。（）
（2 分）如果把第行 if 修改为 else if，输入 helloworld 后程序的输出为。（）

单选题

（4 分）如果把第行 if (cnt[ch] && cnt[ch] < Min) 修改为 if (cnt[ch] < Min)，输入 bookkeeper 后程序的输出为（）。

A.

B.

C.

D.
下面哪一项修改会影响原程序的输出（）。

A. 将第行 for (char ch = 'a'; ch <= 'z'; ch++) 修改为 for (int ch = 'a'; ch <= 'z'; ch++)

B. 将第行 Min = 100 修改为 Min = 1000

C. 将第行 int i = 0; i < len 修改为 int i = 1; i <= len

D. 交换第行和第行的代码

（2）

01 #include <iostream>
02 using namespace std;
03 
04 int f(int n) {
05     if (n == 1) return 1;
06     int ans = 0;
07     for (int i = 1; i < n; i *= 2) {
08         ans += f(i);
09     } 
10     return ans;
11 }
12 
13 int g(int n) {
14     if ((n & (n - 1)) == 0) return n / 2;
15     while (n - (n & -n) > 0) {
16         n -= n & -n;
17     }
18     return n;
19 }
20 
21 int main() {
22     int n;
23     cin >> n;
24     cout << f(n) << endl;
25     cout << g(n) << endl;
26     return 0;
27 }

输入的 n 满足，完成下面的判断题和单选题。

判断题

如果输入的 n 等于，输出的第一行等于。（）
（2 分）如果输入的 n 等于，输出的第二行等于。（）
（2 分）输出两行的结果一致。（）
对于 f 函数而言，由于递归层数可能比较多，得到的结果比较大，因此需要将变量 ans 和函数返回值类型修改为 long long 类型。（）

选择题

如果输入的 n 等于，输出的第一行等于（）。

A.

B.

C.

D.
如果输入的 n 等于，输出的第二行等于（）。

A.

B.

C.

D.

(3)

01 #include <iostream>
02 #include <string>
03 #include <vector>
04 using namespace std;
05 
06 int dp_min_flips(const string &s) {
07     int n = s.size();
08     vector<vector<int>> dp(n, vector<int>(3, INT_MAX));
09     dp[0][0] = (s[0] == '1'); 
10     dp[0][1] = (s[0] == '0'); 
11     dp[0][2] = INT_MAX;
12 
13     for (int i = 1; i < n; ++i) {
14         dp[i][0] = dp[i - 1][0] + (s[i] == '1');
15         dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + (s[i] == '0');
16         dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + (s[i] == '1');
17     }
18 
19     return min(dp[n - 1][1], dp[n - 1][2]);
20 }
21 
22 int greedy_min_flips(const string &s) {
23     int res = s.size(), cnt = 0, sum = 0;
24     for (char c : s) cnt += c == '1';
25     for (char c : s) {
26         if (c == '1') ++sum;
27         else --sum;
28         sum = max(0, sum);
29         res = min(res, cnt - sum);
30     }
31     return res;
32 }
33 
34 int main() {
35     string s;
36     cin >> s;
37     int dp_result = dp_min_flips(s);
38     int greedy_result = greedy_min_flips(s);
39     cout << dp_result << " " << greedy_result << endl;
40     return 0;
41 }

输入字符串 s 的长度 n 满足，且字符类型为 '0' 或 '1'，完成下面的判断题和单选题。

判断题

（2 分）设字符串 s = "1010" ，函数 dp_min_flips(s) 返回值为。（）
（2 分）若字符串 s 中的字符类型全为 '0' 或全为 '1'，则函数 greedy_min_flips(s) 的返回值一定为。（）
（2 分）对于满足题目要求的任意输入字符串 s，程序中第行输出的变量 dp_result 与 greedy_result，两者值一定相同。（）

单选题

若输入1010011110，则程序第行输出的结果为（）。

A. 2 2

B. 3 2

C. 3 4

D. 4 4
如果将程序中第行的 if (c == '1') ++sum; 修改为 if (c == '0') ++sum;，第行输出的 greedy_result 数值会（）。

A. 不变

B. 变大

C. 变小

D. 以上都不正确
如果将函数 dp_min_flips 中第行的代码 dp[0][2] = INT_MAX; 修改为 dp[0][2] = (s[0] == '1');，则修改后函数 dp_min_flips() 的运行结果会（）。

A. 与修改前的 dp_min_flips() 和 greedy_min_flips() 都一定相同

B. 与修改前的 dp_min_flips() 可能不同，与 greedy_min_flips() 一定相同

C. 与修改前的 dp_min_flips() 一定相同，与 greedy_min_flips() 可能不同

D. 与修改前的 dp_min_flips() 和 greedy_min_flips() 都可能不同

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

（1）判定半素数

问题：判定正整数 x 是否半素数（半素数：如果正整数 n 可以表示成两个素数相乘的形式，那么 n 是一个半素数）。如果是，还需输出 x 可以由哪两个素数相乘得到（输出其中一种方案即可）。

试补全程序。

01 #include <iostream>
02 using namespace std;
03
04 bool isPrime(int n) {
05     if (/*____1____*/) return false;
06     for (/*____2____*/) {
07         if (n % i == 0) return false;
08     }	
09     return true;
10 } 
11 
12 /*____3____*/ isSemiprime(int n) {
13     for (int i = 1; i <= n; i++) {
14         if (/*____4____*/) {
15             return i;
16         }
17     }
18     return /*____5____*/;
19 }
20 
21 int main() {
22     int x;
23     cin >> x;
24     int p = isSemiprime(x);
25     if (p) {
26         cout << x << " is a semiprime" << endl;
27         cout << x << " = " <<  p << " * " << x / p << endl;
28     } else {
29         cout << x << " is not a semiprime" << endl;
30     }
31     return 0;
32 }

/*____1____*/ 处应填（）

A. n < 0

B. n <= 2

C. n == 1

D. n < 1
/*____2____*/ 处应填（）

A. int i = 0; i < n; i++

B. int i = 1; i <= n; i++

C. int i = 2; i < n; i++

D. int i = 1; i * i <= n; i++
/*____3____*/ 处应填（）

A. bool

B. int

C. void

D. string
/*____4____*/ 处应填（）

A. n % i == 0 && isPrime(n / i) && isPrime(i)

B. n % i == 0 && isPrime(i) && isPrime(n)

C. isPrime(n) && isPrime(i) && isPrime(n / i)

D. isPrime(i) && isPrime(n / i)
/*____5____*/ 处应填（）

A. n

B. 1

C. 0

D. i

（2）加法与乘法

问题：给定正整数和长度为的正整数序列，定义整数序列，对于，即。求，即的值。

老师将这道题布置给小图计算，小图在列竖式进行笔算的过程中发现由于的长度是，直接简单地模拟一项项乘法和加法进行计算太慢，复杂度是，聪明的他想到了的算法。

试补全程序。

01 #include <iostream>
02 #include <algorithm>
03 #include <string>
04 #include <vector>
05 using namespace std;
06 
07 int main() {
08     int n;
09     cin >> n;
10     vector<int> a(n + 2);
11     for (int i = 1; i <= n; i++) cin >> a[i];
12     for (int i = n; i >= 1; i--) {
13         a[i] = /*____1____*/;
14     }
15     /*____2____*/;
16     int carry = 0;
17     for (int i = 1; i <= n; i++) {
18         carry += a[i];
19         ans += /*____3____*/;
20         /*____4____*/;
21     }
22     ans += (char)(carry + '0');
23     while (ans.back() == '0') /*____5____*/;
24     reverse(ans.begin(), ans.end());
25     cout << ans << endl;
26     return 0;
27 }

/*____1____*/ 处应填（）

A. a[i-1] + a[i]

B. a[i+1] + a[i]

C. a[i] * pow(1, i)

D. a[i+1] * 10 + a[i]
/*____2____*/ 处应填（）

A. long long ans = 0

B. double ans = 0

C. string ans

D. vector<char> ans
/*____3____*/ 处应填（）

A. carry % 10

B. (char)(carry % 10 + '0')

C. carry

D. (char)(carry + '0')
/*____4____*/ 处应填（）

A. carry /= 10

B. carry %= 10

C. carry = carry * 10

D. carry = carry * 10 + 1
/*____5____*/ 处应填（）

A. swap(ans.front(), ans.back())

B. ans -= '0'

C. ans.substr(1, ans.size() - 1)

D. ans.pop_back()

编辑器加载中 …

或者，上传代码文件

#91611. 2025 CSP-J 初赛模拟题 1

题目描述

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

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

（1）

判断题

单选题

（2）

判断题

选择题

(3)

判断题

单选题

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

（1）判定半素数

（2）加法与乘法