信息学奥赛 CSP-J 2026 初赛模拟卷 5

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

第 1 题 以下关于存储器的说法中，错误的是（ ）。 {{ select(1) }}

• $RAM$ 中的信息在断电后会丢失
• $CPU$ 可以直接从硬盘中读取指令并执行
• 内存的访问速度通常比外存快
• $ROM$ 是一种只读存储器

第 2 题 对于变量 a = 7,b = 4，表达式 (a ^ b) & ((~a) | b) 的结果是（ ）。 {{ select(2) }}

• $3$
• $4$
• $7$
• $0$

第 3 题 一个 $8$ 位有符号整数采用二进制补码表示，其可以表示的最小十进制数是（ ）。 {{ select(3) }}

• $-127$
• $-128$
• $-255$
• $-256$

第 4 题 在 $NOI\ Linux$ 终端中，要创建一个名为 test 的新目录，应该使用（ ）命令。 {{ select(4) }}

• new test
• create test
• mkdir test
• md test

第 5 题 $x$ 是正整数且在 $int$ 范围内，则表达式 (x & (x-1)) == 0 可以用来判断一个无符号整数 $x$（ ）。 {{ select(5) }}

• 是偶数
• 是 $2$ 的幂次
• 是 $0$
• 是奇数

第 6 题 在平均情况下，（ ）算法的时间复杂度最低。 {{ select(6) }}

• 冒泡排序
• 插入排序
• 快速排序
• 选择排序

第 7 题 以下代码的空间复杂度是（ ）。

int sum = 0;
for (int i = 0; i < n; i++) {
  int temp = i * 2;
  sum += temp;
}

{{ select(7) }}

• $O(1)$
• $O(n)$
• $O(n^2)$
• $O(\log n)$

第 8 题 一个项目团队有 $12$ 名成员，团队内部任意两人都有过合作经历。这样的合作关系对应（ ）。 {{ select(8) }}

• 连通图
• 完全图
• 二分图
• 稀疏图

第 9 题 一个栈的入栈序列为 $1,2,3,4,5,6$。出栈序列中，$3$ 是第二个出栈的元素。出栈序列（ ）是不可能的。 {{ select(9) }}

• $1,3,2,4,5,6$
• $2,3,4,6,1,5$
• $4,3,2,1,5,6$
• $2,3,4,1,5,6$

第 10 题 $5$ 个男生和 $3$ 个女生站成一排，要求女生不相邻，且第一个和最后一个位置必须是男生，不同的排法有（ ）种。 {{ select(10) }}

• $1440$
• $2160$
• $2880$
• $4320$

第 11 题 已知二叉树的中序遍历序列为 $DBEAC$，后序遍历序列为 $DEBCA$，则前序遍历序列为（ ）。 {{ select(11) }}

• $ABCDE$
• $ABDEC$
• $ABEDC$
• $ABECD$

第 12 题 用数组存储完全二叉树，按从上到下、从左到右的顺序编号（从 $1$ 开始），则节点 $i$ 的左子节点是（ ）。 {{ select(12) }}

• $2i$
• $2i+1$
• $i/2$
• $(i+1)/2$

第 13 题 以下关于 $CPU$（中央处理器）的描述中，正确的是（ ）。 {{ select(13) }}

• $CPU$ 主要由存储器和控制器组成
• $CPU$ 的性能仅由主频决定
• 多核 $CPU$ 是指一个 $CPU$ 中有多个运算器
• $CPU$ 是计算机的"大脑"，负责所有的运算和控制

第 14 题 学校有 $n$ 门课程，部分课程有先修关系（必须先修 $A$ 才能修 $B$）。现要判断课程安排是否合理，有没有循环依赖。这对应图论中的（ ）问题。 {{ select(14) }}

• 最短路径
• 拓扑排序
• 最小生成树
• 负环

第 15 题 某哈夫曼树有 $8$ 个叶节点，该树总共有（ ）个节点。 {{ select(15) }}

• $8$
• $15$
• $16$
• $17$

---

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

(1)

1  #include <iostream>
2  using namespace std;
3
4  int process(int n) {
5      if (n == 0) return 0;
6      return n % 2 + process(n / 2) * 10;
7  }
8
9  int main() {
10     int num;
11     cin >> num;
12     int result = process(num);
13     cout << result << endl;
14     return 0;
15 }

判断题

第 16 题 输入 10 时，输出为 1010。　　（　　） {{ select(16) }}

• √
• ×

第 17 题 输入 1024 时，输出为 10000000000。　　（　　） {{ select(17) }}

• √
• ×

第 18 题 对于任意正整数 $n$，process(n) 的输出总是一个由 0 和 1 组成的数。　（　　） {{ select(18) }}

• √
• ×

选择题

第 19 题 （$2$ 分）若输入 2025，则函数 process 被递归调用（　　）次（包括第一次调用）。 {{ select(19) }}

• $10$
• $11$
• $12$
• $13$

第 20 题 （$2$ 分）函数 process 的时间复杂度是（　　）。 {{ select(20) }}

• $O(1)$
• $O(n)$
• $O(\log n)$
• $O(2^n)$

第 21 题 程序能正常处理的最大输入值为（　　）。 {{ select(21) }}

• $1023$
• $1024$
• $1000000000$
• $2^{31}-1$

(2)

1  #include <iostream>
2  #include <cmath>
3  #define MAX 100
4  using namespace std;
5  int digits[MAX+9];
6  void solve(int a, int b, int precision) {
7      if (b == 0) {
8          cout << "Error: Division by zero!" << endl;
9          return;
10     }
11     if (precision > MAX) precision = MAX;
12     if (precision < 0) precision = 0;
13
14     bool negative = (a < 0 && b > 0) || (a > 0 && b < 0);
15     a = abs(a);
16     b = abs(b);
17     digits[0]=a / b;
18     int remainder = a % b;
19
20     for (int i = 1; i <= precision+1; i++) {
21         remainder *= 10;
22         digits[i] = remainder / b;
23         remainder %= b;
24     }
25
26     if (digits[precision+1] >= 5) {
27         digits[precision]++;
28         for (int i = precision; i >= 1; i--) {
29             if (digits[i] >= 10) {
30                 digits[i] -= 10;
31                 digits[i - 1]++;
32             } else {
33                 break;
34             }
35         }
36     }
37
38     if (negative) cout << "-";
39     cout << digits[0] << cout << '.';
40     for (int i = 1; i <= precision; i++) {
41         cout << digits[i];
42     }
43     cout<<endl;
44 }
45
46 int main() {
47     int a, b, prec;
48     cin >> a >> b >> prec;
49     solve(a, b, prec);
50     return 0;
51 }
52 // 所有输入数据的绝对值均小于 1000

判断题

第 22 题 程序输出结果保留指定的小数位数，同时实现四舍五入，小数位的数量等于输入变量 prec 的值。　　（　　） {{ select(22) }}

• √
• ×

第 23 题 若输入 2025 25 0，程序会输出 81。　　（　　） {{ select(23) }}

• √
• ×

第 24 题 若将程序中的 solve(a, b, prec); 替换成 cout << fixed << setprecision(prec) << (1.0*a/b) << endl;，其他部分不变，则当 prec 的输入值在 $[0,15]$ 区间时，输出结果是一样的。　　（　　） {{ select(24) }}

• √
• ×

选择题

第 25 题 如果输入 2026 26 4，则输出的结果是（　　）。 {{ select(25) }}

• $77.923$
• $77.9230$
• $77.9231$
• $77.9232$

第 26 题 如果输入的数据为 2026 0 -6，下列说法中正确的是（　　）。 {{ select(26) }}

• 程序会因为执行除以 $0$ 的操作而出错，不能正常输出数据
• 程序不会报错，但不会输出具体数值，而是输出自定义的出错提示语
• 程序不会报错，可以正常输出结果，输出结果为 $2026$
• 程序不会报错，可以正常输出结果，输出结果为 $2026$

(3)

1  #include <iostream>
2  #include <vector>
3  using namespace std;
4
5  int bSearch(vector<int>& a, int target) {
6      int left = 0, right = a.size() - 1;
7
8      while (left <= right) {
9          int mid = left + (right - left) / 2;
10         if (a[mid] == target) {
11             return mid;
12         } else if (a[mid] > target) {
13             left = mid + 1;
14         } else {
15             right = mid - 1;
16         }
17     }
18     return -1;
19 }
20
21 int main() {
22     int n, x;
23     cin >> n >> x;
24
25     vector<int> a(n);
26     for (int i = 0; i < n; i++) cin >> a[i];
27     int ans = bSearch(a, x);
28     cout << (ans!=-1 ? ans : -1) << endl;
29     return 0;
30 }

判断题

第 27 题 如果输入 6 3 10 9 8 6 5 4，程序会输出 -1。　　（　　） {{ select(27) }}

• √
• ×

第 28 题 该程序使用二分法，在单调不升数组中查找某个数在整个数组中排在第几个位置。　（　　） {{ select(28) }}

• √
• ×

第 29 题 要保证正常查找功能，输入必须从大到小排列，并且数值要连续。　　（　　） {{ select(29) }}

• √
• ×

选择题

第 30 题 如果输入 10 4 20 17 15 11 10 9 8 6 5 3，程序会输出（　　）。 {{ select(30) }}

• $11$
• $10$
• $8$
• $-1$

第 31 题 如果输入单调不升数组，被查找的数值出现过多次，则程序输出是（　　）。 {{ select(31) }}

• 匹配的最小的下标
• 匹配的最大的下标
• 任意一个匹配的下标都有可能
• $-1$

第 32 题 如果输入 4 4 4 4 4 4，程序会输出（　　）。 {{ select(32) }}

• $0$
• $1$
• $2$
• $3$

---

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

(1)

给定一个整数数组和一个整数 $k$，程序找出数组中 $k$ 个不相邻元素（即任意两个被选元素在数组中不相邻）的最大和。

1  #include <iostream>
2  #include <vector>
3  #include <algorithm>
4  using namespace std;
5
6  int solve(vector<int>& nums, int k) {
7      int n = ___①___ ;
8      vector<vector<int>> dp( ___②___ );
9
10     for (int i = 1; i <= n; i++) {
11         for (int j = 1; j <= k; j++) {
12             if (j == 1) {
13                 dp[i][j] = max( ___③___ );
14             } else {
15                 dp[i][j] = max(dp[i-1][j], ___④___ );
16             }
17         }
18     }
19     return ___⑤___ ;
20 }
21
22 int main() {
23     int n, k;
24     cin >> n >> k;
25     vector<int> nums(n);
26     for (int i = 0; i < n; i++) cin >> nums[i];
27     cout << solve(nums, k) << endl;
28     return 0;
29 }

第 33 题 ① 处应填（　　）。 {{ select(33) }}

• nums.size()-1
• nums.size()
• nums.length()-1
• nums.length()

第 34 题 ② 处应填（　　）。 {{ select(34) }}

• n, vector<int>(k, 0)
• n, vector<int>(k+1, 0)
• n+1, vector<int>(k, 0)
• n+1, vector<int>(k+1, 0)

第 35 题 ③ 处应填（　　）。 {{ select(35) }}

• dp[i-1][j], nums[i-1]
• dp[i][j], nums[i-1]
• dp[i-1][j-1] + nums[i-1]
• dp[i][j] + nums[i-1]

第 36 题 ④ 处应填（　　）。 {{ select(36) }}

• dp[i-1][j], nums[i-1]
• dp[i][j], nums[i-1]
• dp[i-2][j-1] + nums[i-1]
• dp[i][j] + nums[i-1]

第 37 题 ⑤ 处应填（　　）。 {{ select(37) }}

• dp[n-1][k-1]
• dp[n][k-1]
• dp[n-1][k]
• dp[n][k]

(2)

给定一条长度为 $L$ 的线段（$L$ 为整数），以及 $n$ 个整数区间，每个区间有整数起始位置和结束位置。程序的目标是选择最少数量的区间，使得这些区间完全连续覆盖整个线段 $[0,L]$。如果无法完全覆盖，则输出 $-1$。

1  #include <iostream>
2  #include <algorithm>
3  using namespace std;
4  const int N = 100005;
5
6  struct Interval { int s, e; } ivl[N];
7  bool cmp(Interval a, Interval b) {
8      return a.s < b.s || ( ___①___ );
9  }
10
11 int main() {
12     int L, n;
13     cin >> L >> n;
14
15     for (int i = 0; i < n; i++) {
16         cin >> ivl[i].s >> ivl[i].e;
17     }
18     ___②___ ;
19
20     int curr = 0;
21     int cnt = 0;
22     int i = 0;
23
24     while (curr < L) {
25         int mx_reach = curr;
26
27         while ( ___③___ ) {
28             if (ivl[i].e > mx_reach) {
29                 mx_reach = ivl[i].e;
30             }
31             i++;
32         }
33
34         if ( ___④___ ) {
35             cout << -1 << endl;
36             return 0;
37         }
38         cnt++;
39         ___⑤___ ;
40     }
41
42     cout << cnt << endl;
43     return 0;
44 }

第 38 题 ① 处应填（　　）。 {{ select(38) }}

• a.s == b.s && a.e < b.e
• a.s == b.s && a.e <= b.e
• a.s == b.s && a.e != b.e
• a.s == b.s && a.e >= b.e

第 39 题 ② 处应填（　　）。 {{ select(39) }}

• sort(ivl, ivl + n)
• sort(ivl, ivl + n, cmp)
• sort(ivl + 1, ivl + 1 + n)
• sort(ivl + 1, ivl + 1 + n, cmp)

第 40 题 ③ 处应填（　　）。 {{ select(40) }}

• i < n && ivl[i].s > curr
• i < n && ivl[i].s >= curr
• i < n && ivl[i].s <= curr
• i < n && ivl[i].s < curr

第 41 题 ④ 处应填（　　）。 {{ select(41) }}

• i < n
• i > n
• mx_reach < curr
• mx_reach == curr

第 42 题 ⑤ 处应填（　　）。 {{ select(42) }}

• curr = mx_reach;
• curr += mx_reach;
• curr = intervals[i].e;
• curr += intervals[i].e - intervals[i].s + 1;