5514：2026 CSP-J TP原创初赛模拟卷2
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：14
解决：0
题目描述
## 单项选择题15题（每题2分），阅读程序17题（共40分），完善程序10题（每题3分），共100分
## 一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）
1、**八进制数 2025 用二进制表示是（ ）。**
- `10000000101`
- `10000010101`
- `10000001101`
- `10000100101`
2、**在 C++ 中，下面哪个关键字用于声明变量时必须赋值（ ）。**
- `double`
- `long long`
- `static`
- `const`
3、**以下设备中，（ ）不是输出设备。**
- 扫描仪
- 触摸屏
- 绘图仪
- 音箱
4、**当执行以下 C++ 程序段后输出结果为（ ）。**
```cpp
char c1 = '2' + '0';
char c2 = '2' + '6';
cout << c1 < c2 << endl;
```
- 2026
- 28
- bh
- ci
5、**应用二分算法的思想，在一个有 $n$ 个数的有序序列中查找某个指定的数 $m$，其程序时间复杂度为（ ）。**
- $O(n\log n)$
- $O(n)$
- $O(\log n)$
- $O(m\log n)$
6、**计算机界的最高奖是（ ）。**
- 诺贝尔奖
- 奥斯卡奖
- 菲尔兹奖
- 图灵奖
7、**下列关于栈与队列描述错误的是（ ）。**
- 只要确定了入栈次序，即可确定出栈次序
- 栈只允许在栈顶的一端进行入栈与出栈的操作
- 队列进行删除操作总是删除最早入队的元素
- 队列只允许在表的一端进行插入，而在表的另外一端进行删除的线性表
8、**小明买了一块 1TB 的固态硬盘，相当于（ ）MB 的存储容量。**
- $2^{10}$
- $2^{20}$
- $2^{30}$
- $2^{40}$
9、**在一棵度为 3 的树 $T$ 中，若有 10 个度为 3 的结点，7 个度为 2 的结点，2 个度为 1 的结点，树中的叶子结点个数为（ ）。**
- 25
- 26
- 27
- 28
10、**下列选项中（ ）不是 C++ 标准库 `string` 类的函数。**
- `substr`
- `size`
- `replace`
- `strcmp`
11、**有一个 2025 位的正整数，它的各位数字按照如下规则排列：`123456789123456789123456789...`，请问这个数被 9 除的余数是多少？（ ）**
- 3
- 2
- 0
- 1
12、**九宫格数独游戏是一种训练推理能力的数字谜题游戏。九宫格分为九个小宫格，某小九宫格如下图所示，小明需要在 9 个小格子中填上 1 至 9 中不重复的整数。小明通过推理已经得到了 4 个小格子中的准确数字，其中，a、b、c、d、e 这 5 个数字未知，且 b 和 d 为奇数，则 `a + b > 5` 的概率为（ ）。**
| **9** | **a** | **7** |
| ----- | ----- | ----- |
| b | c | d |
| 4 | e | 5 |
- 3/5
- 1/2
- 2/3
- 1/3
13、**四位同学进行篮球传球练习，要求每个人接球后再传给别人。开始时甲同学发球，并作为第一次传球，第五次传球后，球又回到甲同学手中，则不同的传球方法有（ ）种。**
- 60
- 65
- 70
- 75
14、**字符串 `CCCSSSPPP` 共有（ ）种不同的非空子串。**
- 45
- 36
- 37
- 39
15、**向一个不带头结点、栈顶指针为 `head` 的链式栈中插入一个指针 `p` 指向的结点时，应执行以下哪一段代码（ ）。**
- `head->next = p;`
- `p->next = head; head = p;`
- `p->next = head->next; head->next = p;`
- `p->next = head; head = head->next;`
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题每题 1.5 分，选择题每题 3 分，共计 40 分）
### 阅读程序（一）
```cpp
01 #include
02 using namespace std;
03
04 int t, p, a, b, c;
05
06 int f(int a, int b) {
07 if (a % b == 0) return 0;
08 return b - a % b;
09 }
10
11 void solve() {
12 scanf("%d%d%d%d", &p, &a, &b, &c);
13 printf("%d\n", min(min(f(p, a), f(p, b)), f(p, c)));
14 }
15
16 int main() {
17 scanf("%d", &t);
18 while (t--) {
19 solve();
20 }
21 return 0;
22 }
```
**判断题**
16、若程序输入 `1 2 6 10 9`，则最终输出为 `4`。（ ）
- 正确
- 错误
17、（2 分）若将第 7 行删除，程序的输出结果一定不会改变。（ ）
- 正确
- 错误
18、若将第一行修改成 `#include `，程序能正常运行。（ ）
- 正确
- 错误
**单项选择题**
19、若程序输入 `2 9 5 4 8 10 9 9 9`，则输出是（ ）。
- 1 8
- 1 1
- 0 8
- 0 1
20、（4 分）若将第 13 行的输出内容改为 `f(f(f(p, a), b), c)`，则输入 `1 2 6 10 9` 时，输出是（ ）。
- 3
- 4
- 5
- 6
### 阅读程序（二）
```cpp
01 #include
02 using namespace std;
03 bool check(int n){
04 for(int i = 2; i < n; i++)
05 if(n%i == 0) return 0;
06 return 1;
07 }
08 int solve(int n){
09 int res = 0;
10 while(n > 0){
11 res = res + (n&1);
12 n >>= 1;
13 }
14 return res;
15 }
16 int main(){
17 int n, tot = 0;
18 cin >> n;
19 for(int i = 2; i <= n; i++)
20 if(check(i)) tot += solve(i);
21 cout << tot;
22 return 0;
23 }
```
**判断题**
21、若程序输入 6，则最终输出 5。（ ）
- 正确
- 错误
22、将程序的第 4 行修改成 `for(int i = 2 ; i <= n / i ; i++)` 后，程序的结果一定不会发生变化。（ ）
- 正确
- 错误
23、将程序的第 1 行修改成 `#include ` 程序的结果一定不会发生变化。（ ）
- 正确
- 错误
24、该算法的时间复杂度为 $O(n \log n)$。（ ）
- 正确
- 错误
**单项选择题**
25、输入 20，则输出是什么？ （ ）
- 17
- 18
- 19
- 20
26、若将第 11 行修改成 $res = res \wedge n$，输入 15，输出的是什么（ ）
- 38
- 26
- 50
- 68
### 阅读程序（三）
```cpp
01 #include
02 using namespace std;
03 const int N = 2e5 + 5;
04 int n, m, ans, pos[2][N];
05 char a[N], b[N];
06 int main() {
07 scanf("%d%d%s%s", &n, &m, a, b);
08 reverse(a, a + n); reverse(b, b + m);
09 for (int i = 0, now = 0; i < n && now < m; ++i)
10 if (a[i] == b[now])
11 pos[0][now++] = i;
12 for (int i = n - 1, now = m - 1; ~i && ~now; --i)
13 if (a[i] == b[now])
14 pos[1][now--] = i;
15 for (int i = 1; i < m; ++i)
16 ans = max(pos[1][i] - pos[0][i - 1], ans);
17 printf("%d", ans);
18 return 0;
19 }
```
假设 $m \le n \le 200000$，完成下列各题。
**判断题**
27、若 `m` 不为 `n` 的子序列，则输出必定为 `0`。（ ）
- 正确
- 错误
28、若将第 8 行删除，程序输出结果一定不会改变。（ ）
- 正确
- 错误
**单项选择题**
29、若输入为 `5 3 abaab abb`，则输出为（ ）。
- 1
- 2
- 3
- 4
30、若 `a = "ababcdc"`，`b` 的长度为 `5`，则使答案取到最大值的 `b` 可能有（ ）个。
- 3
- 4
- 6
- 7
31、（4 分）当 `a = "1010101"` 时，`b` 的长度为 `3`，`b` 的每一位上要么是 `0`，要么是 `1`。总共有 `8` 种情况，对应 `8` 个输出。这 `8` 个输出的和为（ ）。
- 18
- 24
- 30
- 36
32、当 `a = "1010101"` 时，`b` 的长度为 `4`，`b` 的每位上要么是 `0`，要么是 `1`。总共有 `16` 种情况，对应 `16` 个输出。这 `16` 个输出的和为（ ）。
- 32
- 38
- 46
- 52
## 三、完善程序（单选题，每小题 3 分，共计 30 分）
### 完善程序（一）
题目描述：
给定一个数组 `{a}` 表示一排蘑菇的数量。有一个篮子。每次到一个新的 $a_i$ 时，篮子中会增加 $a_i$ 个蘑菇。如果篮子里的蘑菇超过 `x` 个，则篮子里的蘑菇会清空。询问有多少组 `[L, R]`，使得从 `L` 采摘到 `R`，蘑菇数量不为 `0`。
```cpp
01 #include
02 using namespace std;
03 const int N = 2e5 + 5;
04 int n, x, a[N], cnt[N], dp[N];
05 int main() {
06 cin >> n >> x;
07 for (int i = 1; i <= n; i++)
08 cin >> a[i];
09 int l = 1, r = 0, sum = 0;
10 while (l <= n) {
11 while ([1])
12 [2]
13 cnt[l] = r;
14 [3]
15 }
16 sum = 0;
17 for (int i = n; i >= 1; i--) {
18 if (cnt[i] == n + 1) continue;
19 dp[i] = [4];
20 sum += dp[i];
21 }
22 cout << [5] << endl;
23 return 0;
24 }
```
33、[1] 处应填（ ）。
- `r <= n && sum <= x`
- `l <= n && sum > x`
- `sum <= x`
- `sum > x`
34、[2] 处应填（ ）。
- `sum += a[++r]`
- `sum += a[r++]`
- `sum -= a[++l]`
- `sum -= a[l++]`
35、[3] 处应填（ ）。
- `sum -= a[r--]`
- `sum -= a[--r]`
- `sum -= a[++l]`
- `sum -= a[l++]`
36、[4] 处应填（ ）。
- `dp[cnt[i]] + 1`
- `dp[cnt[i] + 1] + 1`
- `dp[cnt[i + 1]] + 1`
- `dp[cnt[i + 1] + 1] + 1`
37、[5] 处应填（ ）。
- `dp[1]`
- `n - dp[1]`
- `n * (n + 1) / 2 - sum`
- `sum`
### 完善程序（二）
题目描述：
一个字符串 `s`（$|s| \le 5000$）由小写字母组成，有 `g`（$g \le 10^6$）组询问，每组询问给你两个数 `l` 和 `r`，问：在字符串区间 `[l, r]` 的子串中包含多少回文串？
```cpp
01 #include
02 using namespace std;
03 const int N = 5005;
04 char s[N];
05 int n, f[N][N], dp[N][N];
06 bool check(int l, int r) {
07 if ([1]) return f[l][r];
08 if (l >= r) return f[l][r] = 1;
09 if (s[l] ^ s[r]) return f[l][r] = 0;
10 return f[l][r] = [2];
11 }
12
13 int main() {
14 memset(f, -1, sizeof(f));
15 scanf("%s", s + 1);
16 n = strlen(s + 1);
17 for (int i = 1; i <= n; ++i) [3] ;
18 for (int l = 2; l <= n; ++l) {
19 for (int i = 1; i <= n - l + 1; ++i) {
20 int j = i + l - 1;
21 dp[i][j] = [4];
22 if (check(i, j)) [5];
23 }
24 }
25 int T; scanf("%d", &T);
26 while (T--) {
27 int x, y; scanf("%d%d", &x, &y);
28 printf("%d\n", dp[x][y]);
29 }
30 return 0;
31 }
```
38、[1] 处应填（ ）。
- `~f[l][r]`
- `!f[l][r]`
- `r > l`
- `r - l > 1`
39、[2] 处应填（ ）。
- `check(l + 1, r - 1)`
- `check(l + 1, r) + 1`
- `f[l + 1][r - 1] + 1`
- `f[l + 1][r] + 1`
40、[3] 处应填（ ）。
- `dp[i][i] = 1`
- `dp[i][i + 1] = 1`
- `dp[i][i + 1] = (s[i] == s[i + 1]) + 2`
- `dp[i][i + 1] = s[i] == s[i + 1]`
41、[4] 处应填（ ）。
- `dp[i + 1][j] + dp[i][j - 1] + dp[i + 1][j - 1]`
- `dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]`
- `dp[i + 1][j] + dp[i][j - 1] + (s[i] == s[j])`
- `dp[i + 1][j] + dp[i][j - 1] - (s[i] == s[j])`
42、[5] 处应填（ ）。
- `dp[i][j]++`
- `dp[i][j] += dp[i + 1][j - 1]`
- `dp[i][j]--`
- `dp[i][j] -= dp[i + 1][j - 1]`