4209：2025年CSP-J初赛考前冲刺卷（一）
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：155
解决：0
题目描述
## 一、单项选择题（共 15 题，每题 2 分，共计 30分）
1.以下哪一个操作系统不是基于 Unix 内核开发的（ ）。
- HormanyOS(鸿蒙)
- macOS
- Linux
- Windows
2.有 $5$ 个不同的小球，装入 $4$ 个不同的盒内，每盒至少装一个球，共有多少不同的装法（ ）。
- 240
- 480
- 60
- 120
3.有六个元素DABCFE从左至右依次顺序入栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列（ ）。
- `BACEFD`
- `DCBFAE`
- `ACDBFE`
- `FCEBAD`
4.CPU是指（ ）。
- 运算器
- 控制器
- 运算器和控制器
- 运算器、控制器和主存
5.学校现有月季花5朵，玫瑰花4朵，芍药花2朵，现在想在花坛任意摆放上一排10朵花，问有多少种不同的摆放方法（ ）。
- $6640$
- $7010$
- $5450$
- $6930$
6.关于下列算法的理解，正确的是（ ）。
- 二分法是将问题一分为二、二分为四、四分为八，再逐个解决小问题，最终解决真个问题。
- 枚举法指的是一一尝试所有可能性，可能使用 for 循环、while 循环、递归等方式实现。
- 策略类问题可以考虑使用贪心或者动态规划解决。数据范围大的时候，使用效率更高的贪心，数据范围小的时候，使用效率偏低的动态规划。
- 给定一个无向图，寻找起点到终点的最短路，可以使用深度优先搜索或广度优先搜索解决，且他们的效率相同。
7.烧烤店有三种肉串售卖，其中肉串 A 的价格是 2 元，肉串 B 是 3 元，肉串 C 是 4 元，你有 20 元，恰好将钱花光的购买方案有（ ）种。
- $12$
- $14$
- $16$
- $18$
8.一棵二叉树，前序遍历是 1243576，中序遍历是 2415736，则后序遍历是（ ）。
- `4257631`
- `4275631`
- `7425631`
- `4276531`
9.设某完全无向图中有 n 个节点，则该无向完全图中有（ ）条边。本题中的图认为是简单图（无自环、无重边）。
- $n(n-1)/2$
- $n(n-1)$
- $n^2$
- $n^2-1$
10.以下排序算法中，最坏情况下时间复杂度为 $O(n \log n)$ 的是（ ）。
- 桶排序
- 快速排序
- 归并排序
- 基数排序
11.使用冒泡排序算法对下面这个数组 `{23, 5, 11, 7, 13}` 进行从小到大排序，需要进行（ ）次相邻两数的交换操作。
- 4
- 5
- 6
- 7
12.无向图的邻接矩阵是（ ）
- 对称矩阵
- 零矩阵
- 上三角矩阵
- 对角矩阵
13.对于以下程序，说法正确的是（ ）。
```cpp
01 #include
02 using namespace std;
03 int main(){
04 string s;
05 cin >> s;
06 for(int i = 0; i < s.size() - 5; i++){
07 cout << s[i];
08 }
09 }
```
- 因为 `s.size()` 的时间复杂度为 $O(n)$，所以该程序的时间复杂度为 $O(n^2)$。
- 如果输入字符串是 `abc`，那么该程序运行时会产生段错误
- 如果输入字符串是 `abc`，那么该程序会死循环。
- 如果读入 `hello world`，那么程序会输出 `hello`。
14.你用数组实现了一个循环队列，数组大小为 n，初始元素都是0，即队列至多可以容纳 n 元素。有两个变量 front 和 rear 分别表示队首和队尾。初始 front=rear=0，每插入一个元素，则先插入到 rear 的位置，然后 rear 的值加一，每弹出一个元素，将 front 的值加一。因为是循环队列，所以 front 和 rear 的值需要随时对 n 求余。假设这个队列正常运行，并且入队的都是非0元素。请问以下说法正确的是（ ）。
- front 加一的次数可能比 rear 加一的次数多。
- 若 rear 指向的值不是0，则说明队列已满，无法再插入元素。
- front 的值应当始终小于等于 rear 的值。
- front 的值可能大于 rear 的值。
15.二进制数字 `1011.01` 的十进制表示为。
- 11.5
- 11.25
- 11.125
- 11
## 二、阅读程序（程序输入不超过数组或字符串定义范围，除特殊说明外，判断题每题 1.5 分，选择题每题 3 分，共计 40 分）
### 阅读程序1（12分）
```cpp
01 #include
02
03 using namespace std;
04
05 int cnt=0;
06
07 int f(int x=1,int y=2)
08 {
09 if(x==0)
10 {
11 cnt++;
12 return y;
13 }
14 return f(x-1,y-1)+f(x-1);
15 }
16
17 int main()
18 {
19 ios::sync_with_stdio(false); cin.tie(0);
20 cout<< f(3,3)<<'\n';
21 cout<< cnt;
22 }
```
#### 判断题：
16.求 $f$ 函数时间复杂度为 $O(N)$（ ）。
- 正确
- 错误
17.这段代码无法编译通过，因为 $f(x-1)$ 缺少了一个变量。（ ）
- 正确
- 错误
18.这段代码中f函数被调用了 $16$ 次（ ）。
- 正确
- 错误
19.程序输出的第一个数字是 $10$。（ )
- 正确
- 错误
#### 单选题：
20.程序输出的第二个数字为（ ）。
- 8
- 10
- 12
- 14
21.`f(4,3)` 是多少？（ ）。
- 16
- 17
- 18
- 19
### 阅读程序2（16分）
```
01 #include
02
03 using namespace std;
04
05 int g(unsigned long long x) {
06 const unsigned long long m1 = 0x55555555;
07 const unsigned long long m2 = 0x33333333;
08 const unsigned long long m4 = 0x0f0f0f0f;
09 const unsigned long long h01 = 0x01010101;
10 x -= (x >> 1) & m1;
11 x = (x & m2) + ((x >> 2) & m2);
12 x = (x + (x >> 4)) & m4;
13 return (x * h01) >> 24;
14 }
15
16 int main()
17 {
18 ios::sync_with_stdio(false);
19 long long x;
20 cin>>x;
21 cout<< g(x)<<'\n';
22 }
```
假设数据满足 $0≤ x≤9*10^{18}$,回答下列问题题。
#### 判断题
22.程序输入 0，程序输出 0。
- 正确
- 错误
23.程序输入1，程序输出1。
- 正确
- 错误
24.（2分）程序输出的最大值为 $2^{40}$。
- 正确
- 错误
25. （2分）在本段程序中 `g(-x) = g(~x+1)`（提示：考虑补码）
- 正确
- 错误
#### 单选题：
26.假设某组输入用八进制表示为 16，则程序输出？
- 0
- 1
- 2
- 3
27.假设输入的数字用二进制表示为 `10101101`，则程序输出为（ ）。
- 5
- 6
- 7
- 8
28.假设输入的数字是 $x$，则输出的数字（ ）。
- 小于 x
- 等于 x
- 大于 x
- 以上皆有可能
### 阅读程序3（12分）
```cpp
01 #include
02
03 using namespace std;
04
05 const int maxn=1010;
06
07 vector G[maxn];
08 int n,m,ins[maxn];
09
10 void init(int x)
11 {
12 auto lambda_expression=[&](int x,int y)->
13 void {
14 G[x].emplace_back(y);
15 };
16 for(int i=1;i<=n;i+=x)
17 {
18 lambda_expression(i,(i+x-1)%n+1);
19 }
20 }
21
22 bool dfs(int u)
23 {
24 if(ins[u]) return 1;
25 ins[u]=1;
26 bool flag=0;
27 for(auto v:G[u])
28 {
29 if(flag) return 1;
30 flag|=dfs(v);
31 }
32 return flag;
33 }
34
35 int main()
36 {
37 ios::sync_with_stdio(false);
38 cin>>n>>m;
39 for(int i=1;i<=m;i++)
40 {
41 int x;
42 cin>>x;
43 init(x);
44 }
45 cout<< dfs(1)<<'\n';
46 }
```
题目保证输入 $1≤n≤10^4,0≤m≤5*10^4,1≤x_i≤n$
#### 判断题：
29.本题时间复杂度为 $O(n^2*m)$。
- 正确
- 错误
30.程序空间复杂度为 $O(n*\sum x)$。
- 正确
- 错误
31.当 $n=1000,m=2000$ 的时候，`G[1]` 的 `size` 最大为 $2000$。
- 正确
- 错误
32.当 $n=1000,m=2000$ 的时候，dfs 最大层数为 n + 2。
- 正确
- 错误
#### 单选题：
33.程序输入
```
3 2
1 3
```
，则程序输出是什么（ ）？
- `0`
- `1`
- `True`
- `False`
34.假设 $n=8$，输入的 m 个数满足什么性质，才能保证 dfs函数返回值为 False？
- m 个相同的数
- 一个长度为 m 的排列
- 输入为小于 $7$ 的所有质数（不包括 $2$）
- 输入为任意两个不互质的数字。
## 三、完善程序（每小题 3 分，共计 30 分）
### 完善程序题1
题目描述：
班上有 $N$ 名学生，每个人分配得到了一把有编号的椅子，他们不希望自己编号与椅子编号不同，作为班主任，你可以进行操作：选择两个不同的学生，交换他们的椅子，询问你至少要多少次才能使得所有学生的编号与他们椅子编号不同本题多组数据。
```cpp
01 #include
02
03 using namespace std;
04
05 const int maxn=330;
06
07 int T,cnt;
08 int n,a[maxn];
09
10 void solve()
11 {
12 cin>>n;
13 for(int i=1;i<=n;i++) ①
14 for(int k=1;k<=n;k++)
15 for(int i=1;i<=n;i++)
16 for(int j=1;j<=n;j++)
17 {
18 if(②)
19 {
20 swap(a[i],a[j]);
21 cnt++;
22 }
23 }
24 for(int i=1;i<=n;i++)
25 {
26 if(③) cnt++;
27 }
28 cout<<④<<'\n';
29 }
30
31 int main()
32 {
33 ios::sync_with_stdio(false);
34 cin>>T;
35 while(⑤)
36 {
37 solve();
38 }
39 return 0;
40 }
```
35. ①处应填（）
- `a[i] = 0`
- `a[i] = a[i - 1] + 1`
- `a[i] = i`
- `cin>>a[i]`
36.②处应填（）
- `a[i] == i && a[j] == j`
- `a[i]==i || a[j]==j`
- `a[i]==j && a[j]==i`
- `a[i]==j || a[j]==i`
37.③处应填（）
- `a[i]=0`
- `a[i]=i`
- `a[i]!=i`
- `a[i]==i`
38.④处应填（）
- `a[1]`
- `a[n]`
- `ans`
- `cnt`
39.⑤处应填()
- `T!=0`
- `!(T==0)`
- `T--`
- `T-1`
### 完善程序2（每题3分）
题目描述:
设计一段程序，实现以下操作
1. `I x`：在当前光标前插入数字 x。
2. `D`：删除当前光标前的数字。
3. `L`：光标向前移动一个数字。
4. `R`：光标向后移动一个数字。
5. `Q k`：输出光标之前的数列 `{a1, a2, ..., an}` 中第 k 位及之前的最大前缀和，保证 k ≤ n。
```cpp
01 #include
02 #define N 1000010
03 using namespace std;
04 int s1[N],s2[N];
05 int ans[N],S[N];
06 int top1,top2,n;
07 int main()
08 {
09 scanf("%d",&n);
10 ans[0]=-(1<<30);
11 for(int i=1;i<=n;i++)
12 {
13 char fl;cin>>fl;
14 if(fl=='I')
15 {
16 int x;scanf("%d",&x);
17 ①;
18 S[top1]=S[top1-1]+x;
19 ans[top1]=max(ans[top1-1],S[top1]);
20 }
21 if(fl=='D') ②;
22 if(fl=='L') ③;
23 if(fl=='R')
24 {
25 int x=④;
26 ⑤;
27 S[top1]=S[top1-1]+x;
28 ans[top1]=max(ans[top1-1],S[top1]);
29 }
30 if(fl=='Q')
31 {
32 int x;scanf("%d",&x);
33 printf("%d\n",ans[x]);
34 }
35 }
36 return 0;
37 }
```
40. ①处应填 ( )
- `s1[++top1]=x`
- `s1[top1++]=x`
- `s2[++top2]=x`
- `s2[top2++]=x`
41.②处应填 ( )
- `top1++`
- `top2++`
- `top1--`
- `top2--`
42.③处应填 ( )
- `s1[++top1]=s2[top2--]`
- `s1[++top2]=s2[top1--]`
- `s2[++top1]=s1[top2--]`
- `s2[++top2]=s1[top1--]`
43.④处应填 ( )
- `s2[top2++]`
- `s1[top1++]`
- `s2[top2--]`
- `s1[top1--]`
44.⑤处应填 ( )
- `s1[++top1]=x`
- `s1[--top1]=x`
- `s2[++top2]=x`
- `s2[--top2]=x`