2025年CSP-J第一轮笔试模拟试卷（二）

一、单项选择题（共15题，每题2分，共30分）

IPv4地址中，以下合法的是（   ）

A.255.255.255.255 B.0.1.1.1 C.1.1. 1.0 D.1.0.0.0

八进制数7042转换为十六进制是（   ）

A.3521 B.F22 C.E22 D.111000100010

以下排序算法中，平均时间复杂度为

的是（   ）

A. 归并排序 B. 快速排序 C. 插入排序 D. 希尔排序

已知二叉树的前序遍历为HGBDAFEC，中序遍历为BGHFAEDC，其后序遍历是（   ）

A.ABDEFC B.DBEFAC C.DFEBCA D.ABCDEF

设栈初始为空，元素

依次入栈，若出栈顺序为

，则栈的最小容量为（   ）

A. 2 B. 3 C. 4 D. 5

以下关于C++字符串的说法，错误的是（   ）

A.string类型无需预定义长度 B. 字符数组可转化为string

C.char a[100]最多存储99字符 D.strlen(s)获取string s长度

在Linux系统中，可执行文件的默认扩展名是（   ）

A..exe B..chm C..dll D. 无默认扩展名

一个7个顶点的完全图至少删掉多少条边才能成为森林？（   ）

A. 16 B. 15 C. 21 D. 6

以下逻辑表达式中，当A、C为真，B、D为假时结果为假的是（   ）

A.

 B.

C.

 D.

Catalan数

的描述中，错误的是（   ）

A. 表示

个节点的二叉树形态数 B. 表示

对括号的合法序列数

C. 表示

元素出栈序列数 D. 表示

边凸多边形的三角剖分数

完全二叉树有 2023 个节点，则叶子节点数为（   ）

A. 1011 B. 1012 C. 1013 D. 1014

以下关于哈希表解决冲突的方法，错误的是（   ）

A. 开放定址法 B. 链地址法 C. 再哈希法 D. 二分查找法

快速排序在最坏情况下的时间复杂度是（   ）

A.

 B.

 C.

 D.

已知无向图有 6 个顶点和 8 条边，则该图至少有（   ）个连通分量

A. 1 B. 2 C. 3 D. 4

表达式a*(b+c)-d的后缀表达式是（   ）

A.abc+*d- B.abc*+d- C.abc+*d D.ab+c*d-

二、阅读程序（共3大题，40分）

程序一

题目：分糖果问题

#include <bits/stdc++.h>

using namespace std;

int main() {

int n, L, R;

cin >> n >> L >> R;

if (L % n + R - L >= n - 1)  cout << n - 1;

else  cout << L % n + R - L;

return 0;

}

问题：

若输入为7 16 23，输出是（   ）（3分）

A. 6 B. 7 C. 8 D. 9

该算法的时间复杂度为（   ）（3分）

A.

 B.

 C.

 D.

程序二

题目：字符串处理

#include <bits/stdc++.h>

using namespace std;

char s[1000005];

int main() {

string a;

cin >> a;

int t = 1;

for (char c : a) {

if (c == '4' || c == '7') continue;

if (c == '3' && s[t-1] == '1') t--;

else s[t++] = c;

}

cout << (t == 1 ? 0 : string(s+1, s+t));

}

问题：

输入1411733时，输出为（   ）（3分）

A.1 B.113 C.11133 D.0

当输入字符串全由'1'和'3'组成时，输出结果长度可能为（   ）（3分）

A. 0 B. 1 C. 原串长度 D. 原串长度减半

若将代码中c == '4' || c == '7'改为c >= '5' && c <= '9'，输入19527时输出是（   ）（4分）

A.15 B.12 C.9 D.1527

程序三

题目：图遍历与连通性判断

#include <bits/stdc++.h>

using namespace std;

vector<int> G[1005];

bool vis[1005];

void dfs(int u) {

  vis[u] = true;

  for (int v : G[u])

      if (!vis[v]) dfs(v);

}

int main() {

  int n, m, cnt = 0;

  cin >> n >> m;

  while (m--) {

      int u, v; cin >> u >> v;

      G[u].push_back(v);

      G[v].push_back(u);

  }

  for (int i=1; i<=n; i++)

      if (!vis[i]) { dfs(i); cnt++; }

  cout << cnt;

  return 0;

}

问题：

输入为：

5 3

1 2

3 4

4 5

输出为（   ）（3分）

A. 1 B. 2 C. 3 D. 5

三、完善程序（共2大题，30分）

题目一：动态规划求最大子矩阵和

#include <bits/stdc++.h>

using namespace std;

int a[1005][1005], dp[1005];

int main() {

int n, m;

cin >> n >> m;

for (int i=1; i<=n; i++)  for (int j=1; j<=m; j++)  cin >> a[i][j];

int max_sum = INT_MIN;

for (int i=1; i<=n; i++) {

memset(dp, 0, sizeof(dp));

for (int j=i; j<=n; j++) {

 for (int k=1; k<=m; k++)  dp[k] += a[j][k];

 int current = 0;

 for (int k=1; k<=m; k++) {

  current = max(dp[k], );

  max_sum = max(max_sum, );

 }

}

}

cout << max_sum;

return 0;

}

填空：

处应填（   ）（3分）

A.current + dp[k] B.dp[k] C.current D.0

题目二：DFS求全排列

#include <bits/stdc++.h>

using namespace std;

int n, a[10], vis[10];

void dfs(int step) {

  if (step > n) {

      for (int i=1; i<=n; i++) cout << a[i] << " ";

      cout << endl;

      return;

  }

  for (int i=1; i<=n; i++) {

      if () {

          vis[i] = 1;

          a[step] = i;

          dfs(step + 1);

          ;

      }

  }

}

int main() {

  cin >> n;

  dfs(1);

  return 0;

}

填空：

处应填（   ）（3分）

A.!vis[i] B.vis[i] == 0 C.vis[i] D.i > step

处应填（   ）（3分）

A.vis[i] = 0 B.a[step] = 0 C.step-- D.i++