CSP-J 模拟卷2

    客观题

CSP-J 模拟卷2

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

1. CPU 主要由（ ）组成。
{{ select(1) }}

  • 运算器与控制器
  • 存储器与运算器
  • 控制器与输入设备
  • 输出设备与存储器

2. 八进制数 173 对应的十进制数是（ ）。
{{ select(2) }}

  • 119
  • 123
  • 125
  • 173

3. 在 C++ 中，表达式 (5 & 3) | 4 的值是（ ）。
{{ select(3) }}

  • 1
  • 4
  • 5
  • 7

4. 执行 int a[5] = {1,2,3,4,5}; 后，表达式 *(a + 2) 的值是（ ）。
{{ select(4) }}

  • 1
  • 2
  • 3
  • 4

5. 一棵二叉树第 5 层（根结点为第 1 层）最多有（ ）个结点。
{{ select(5) }}

  • 8
  • 15
  • 16
  • 31

6. 下列数据结构中，适合实现“先进先出”的是（ ）。
{{ select(6) }}

  • 栈
  • 队列
  • 二叉树
  • 哈希表

7. 将 5 个不同元素进行全排列，共有（ ）种不同的排列。
{{ select(7) }}

  • 60
  • 100
  • 120
  • 240

8. 归并排序的空间复杂度为（ ）。
{{ select(8) }}

  • O(1)
  • O(n)
  • O(log n)
  • O(n²)

9. 在 C++ 中，char 类型变量占（ ）个字节。
{{ select(9) }}

  • 1
  • 2
  • 4
  • 8

10. HTTP 协议默认使用的端口号是（ ）。
{{ select(10) }}

  • 21
  • 80
  • 443
  • 8080

11. 一棵完全二叉树共有 15 个结点，则它的深度为（ ）（根结点深度记为 1）。
{{ select(11) }}

  • 2
  • 3
  • 4
  • 5

12. 有 6 个结点的无向完全图共有（ ）条边。
{{ select(12) }}

  • 12
  • 14
  • 15
  • 16

13. 在 n 个有序元素中使用二分查找查找一个元素，时间复杂度为（ ）。
{{ select(13) }}

  • O(log n)
  • O(n)
  • O(n log n)
  • O(1)

14. 关于 C++ 中的引用（&），下列说法正确的是（ ）。
{{ select(14) }}

  • 引用形参是实参的拷贝，修改形参不影响实参
  • 引用形参是实参的别名，修改形参会直接影响实参
  • 引用必须指向动态分配的内存
  • 引用可以重新绑定到其他变量

15. 若 x = 7，y = 3，则表达式 x % y 与 x / y 的值分别是（ ）。
{{ select(15) }}

  • 1 和 2
  • 2 和 1
  • 1 和 1
  • 2 和 2

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

阅读程序（一）

  1 #include <iostream>
  2 using namespace std;
  3 const int MAXN = 1005;
  4 int a[MAXN];
  5 int main() {
  6     int n, x;
  7     cin >> n >> x;
  8     for (int i = 1; i <= n; i++) cin >> a[i];
  9     int l = 1, r = n, ans = 0;
 10     while (l <= r) {
 11         int mid = (l + r) / 2;
 12         if (a[mid] <= x) {
 13             ans = mid;
 14             l = mid + 1;
 15         } else {
 16             r = mid - 1;
 17         }
 18     }
 19     cout << ans << endl;
 20     return 0;
 21 }

16. 输入 n = 5，x = 3，a = {1, 2, 2, 4, 5}，程序输出 3。（ ）
{{ select(16) }}

  • 正确
  • 错误

17. 若 x 大于数组中的所有元素，程序输出 0。（ ）
{{ select(17) }}

  • 正确
  • 错误

18. 若输入数组 a 不是升序排列，程序的输出结果可能不正确。（ ）
{{ select(18) }}

  • 正确
  • 错误

19. 输入 n = 5，x = 4，a = {1, 3, 5, 7, 9}，程序输出（ ）。
{{ select(19) }}

  • 1
  • 2
  • 3
  • 4

20. 该程序的时间复杂度为（ ）。
{{ select(20) }}

  • O(n)
  • O(log n)
  • O(n log n)
  • O(n²)

阅读程序（二）

  1 #include <iostream>
  2 using namespace std;
  3 const int MAXN = 105;
  4 int a[MAXN][MAXN];
  5 bool vis[MAXN][MAXN];
  6 int n, m;
  7 int dx[4] = {1, -1, 0, 0};
  8 int dy[4] = {0, 0, 1, -1};
  9 
 10 void dfs(int x, int y) {
 11     vis[x][y] = true;
 12     for (int i = 0; i < 4; i++) {
 13         int nx = x + dx[i];
 14         int ny = y + dy[i];
 15         if (nx >= 1 && nx <= n && ny >= 1 && ny <= m
 16             && !vis[nx][ny] && a[nx][ny] == 1)
 17             dfs(nx, ny);
 18     }
 19 }
 20 
 21 int main() {
 22     cin >> n >> m;
 23     for (int i = 1; i <= n; i++)
 24         for (int j = 1; j <= m; j++)
 25             cin >> a[i][j];
 26     int cnt = 0;
 27     for (int i = 1; i <= n; i++)
 28         for (int j = 1; j <= m; j++)
 29             if (a[i][j] == 1 && !vis[i][j]) {
 30                 cnt++;
 31                 dfs(i, j);
 32             }
 33     cout << cnt << endl;
 34     return 0;
 35 }

21. 输入 2×2 矩阵 {{1,1},{1,1}}，程序输出 1。（ ）
{{ select(21) }}

  • 正确
  • 错误

22. 若将方向数组 dx、dy 改为只包含上下两个方向（其他不变），程序输出的值一定不会变小。（ ）
{{ select(22) }}

  • 正确
  • 错误

23. 程序中同一格子可能被调用多次 dfs。（ ）
{{ select(23) }}

  • 正确
  • 错误

24. 输入 3×3 矩阵：主对角线位置为 1，其余位置为 0，程序输出（ ）。
{{ select(24) }}

  • 1
  • 2
  • 3
  • 4

25. 若将递归的 dfs 改为非递归实现，最适合使用的数据结构是（ ）。
{{ select(25) }}

  • 队列
  • 栈
  • 优先队列
  • 哈希表

阅读程序（三）

  1 #include <iostream>
  2 using namespace std;
  3 const int MAXN = 305;
  4 int a[MAXN], sum[MAXN], dp[MAXN][MAXN];
  5 
  6 int main() {
  7     int n;
  8     cin >> n;
  9     for (int i = 1; i <= n; i++) {
 10         cin >> a[i];
 11         sum[i] = sum[i - 1] + a[i];
 12     }
 13     for (int len = 2; len <= n; len++) {
 14         for (int l = 1; l + len - 1 <= n; l++) {
 15             int r = l + len - 1;
 16             dp[l][r] = 1e9;
 17             for (int k = l; k < r; k++)
 18                 dp[l][r] = min(dp[l][r],
 19                     dp[l][k] + dp[k + 1][r] + sum[r] - sum[l - 1]);
 20         }
 21     }
 22     cout << dp[1][n] << endl;
 23     return 0;
 24 }

26. 输入 n = 3，a = {1, 2, 3}，程序输出 9。（ ）
{{ select(26) }}

  • 正确
  • 错误

27. dp[l][r] 表示合并第 l 堆到第 r 堆石子所需的最小代价。（ ）
{{ select(27) }}

  • 正确
  • 错误

28. 输入 n = 4，a = {4, 1, 3, 2}，程序输出 19。（ ）
{{ select(28) }}

  • 正确
  • 错误

29. 输入 n = 4，a = {3, 5, 2, 1}，程序输出（ ）。
{{ select(29) }}

  • 18
  • 19
  • 20
  • 22

30. 该程序的时间复杂度为（ ）。
{{ select(30) }}

  • O(n log n)
  • O(n²)
  • O(n³)
  • O(2ⁿ)

31. 若将分割点 k 的枚举方向改为从 r-1 向下枚举到 l（其他不变），程序输出（ ）。
{{ select(31) }}

  • 0
  • 变小
  • 变大
  • 与原来相同

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

完善程序（一）· 约瑟夫问题

【题面】n 个人围成一圈，从第 1 个人开始按顺时针方向依次报数，报到 m 的人出圈，然后从下一个人重新开始报数，直到所有人都出圈为止。请按出圈顺序输出每个人的编号。 【输入格式】一行，两个整数 n、m（1 ≤ n ≤ 100，1 ≤ m ≤ 10）。 【输出格式】一行，n 个整数，表示出圈顺序，相邻两数之间用空格隔开。 【程序功能】用数组模拟报数过程：a[i] = 0 表示第 i 个人已出圈，cnt 记录当前报数，pos 指向当前报数的人，out 记录已出圈人数。

  1 #include <iostream>
  2 using namespace std;
  3 const int MAXN = 105;
  4 int a[MAXN];
  5 
  6 int main() {
  7     int n, m;
  8     cin >> n >> m;
  9     for (int i = 1; i <= n; i++)
 10         a[i] = ____①____;
 11     int cnt = 0, pos = 1, out = 0;
 12     while (____②____ < n) {
 13         if (a[pos] != 0) {
 14             cnt++;
 15             if (cnt == m) {
 16                 cout << a[pos] << " ";
 17                 a[pos] = ____③____;
 18                 cnt = ____④____;
 19                 out++;
 20             }
 21         }
 22         pos++;
 23         if (pos > n) pos = ____⑤____;
 24     }
 25     return 0;
 26 }

32. ① 处应填（ ）。
{{ select(32) }}

  • 0
  • i
  • n
  • m

33. ② 处应填（ ）。
{{ select(33) }}

  • out
  • cnt
  • pos
  • m

34. ③ 处应填（ ）。
{{ select(34) }}

  • -1
  • 0
  • m
  • cnt

35. ④ 处应填（ ）。
{{ select(35) }}

  • m
  • 1
  • 0
  • pos

36. ⑤ 处应填（ ）。
{{ select(36) }}

  • 1
  • 0
  • n
  • pos - n

完善程序（二）· 公交换乘（NOIP 2019 普及组改编）

【题面】某城市的公共交通系统包含地铁和公交两种方式。乘地铁须付现金，同时获得一张优惠券；乘公交时，若存在可用优惠券（距获得时间不超过 45 分钟，且优惠券价格不低于本次公交车费），则使用获得时间最早的优惠券，否则付现金。给定 n 次出行记录，求总花费。 【输入格式】第一行一个整数 n；接下来 n 行，每行三个整数 type、price、time，type = 0 表示地铁，type = 1 表示公交。 【输出格式】一个整数，表示总花费。 【程序功能】用数组模拟优惠券队列：q 保存优惠券价格，t 保存获得时间，used 标记是否已使用；每次乘公交时先移除过期的优惠券，再寻找最早获得且价格足够的优惠券。

  1 #include <iostream>
  2 using namespace std;
  3 const int MAXN = 100005;
  4 int q[MAXN], t[MAXN];
  5 bool used[MAXN];
  6 
  7 int main() {
  8     int n, sum = 0;
  9     cin >> n;
 10     int head = 0, tail = 0;
 11     for (int i = 1; i <= n; i++) {
 12         int type, p, time;
 13         cin >> type >> p >> time;
 14         if (type == 0) {
 15             sum += p;
 16             q[tail] = p;
 17             t[tail] = time;
 18             tail++;
 19         } else {
 20             while (head < tail && time - t[head] > ____①____)
 21                 head++;
 22             bool ok = false;
 23             for (int j = head; j < tail; j++) {
 24                 if (!used[j] && q[j] ____②____ p) {
 25                     used[j] = ____③____;
 26                     ok = true;
 27                     break;
 28                 }
 29             }
 30             if (!ok) sum ____④____ p;
 31         }
 32     }
 33     cout << ____⑤____ << endl;
 34     return 0;
 35 }

37. ① 处应填（ ）。
{{ select(37) }}

  • 30
  • 45
  • 60
  • 90

38. ② 处应填（ ）。
{{ select(38) }}

  • <
  • <=
  • >
  • >=

39. ③ 处应填（ ）。
{{ select(39) }}

  • false
  • true
  • 0
  • -1

40. ④ 处应填（ ）。
{{ select(40) }}

  • +=
  • -=
  • =
  • *=

41. ⑤ 处应填（ ）。
{{ select(41) }}

  • sum
  • p
  • n
  • head

CSP-J普及组第二轮模拟卷

未参加
状态
已结束
规则
OI
题目
1
开始于
2026-9-12 19:00
结束于
2026-9-12 20:30
持续时间
1.5 小时
主持人
参赛人数
16
  1. Language
  2. 兼容模式
  3. 主题
  2. Company Logo

  6. © 2025-2025 bigcodeforce.cn 沪ICP备2025138606号
  7. Worker 0, 16ms
  8. Powered by Hydro v5.0.4 Community