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

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

第 1 题 在 $NOI\ Linux$ 的终端中，要列出当前目录下所有文件和文件夹的详细信息（包括权限、大小、修改时间等），应该使用命令（　　）。 {{ select(1) }}

• ls
• ls -l
• ls -a
• ls -s

第 2 题 在计算机网络中，$IP$ 地址 192.168.1.1 属于（　　）地址。 {{ select(2) }}

• $A$ 类
• $B$ 类
• $C$ 类
• $D$ 类

第 3 题 在 $C$++ 中，表达式 !(5 > 3) && (4 <= 4) || (2 != 2) 的结果是（　　）。 {{ select(3) }}

• $true$
• $false$
• $1$
• 编译错误

第 4 题 关于单向链表，以下描述中正确的是（　　）。 {{ select(4) }}

• 可以随机访问任意位置的元素
• 插入和删除元素的时间复杂度都是 $O(1)$
• 需要连续的存储空间
• 每个节点包含数据和指向下一个节点的指针

第 5 题 对于有 $n$ 个节点的二叉树，其最小高度是（　　）。 {{ select(5) }}

• $\lceil \log_2 n \rceil$
• $\lceil \log_2(n+1) \rceil - 1$
• $n-1$
• 1

第 6 题 将十进制小数 $100.25$ 转换为二进制数，结果是（　　）。 {{ select(6) }}

• $1010100.01$
• $1100100.11$
• $1100100.01$
• $1010100.11$

第 7 题 （考试成绩排序）场景：老师需要对全班 $50$ 名学生的成绩排序，要求相同分数的学生保持原来的相对顺序。下列排序算法中最合适的是（　　）。 {{ select(7) }}

• 快速排序
• 堆排序
• 归并排序
• 选择排序

第 8 题 突然断电后，数据不会丢失的存储设备是（　　）。 {{ select(8) }}

• 内存
• 缓存
• 固态硬盘
• 寄存器

第 9 题 使用深度优先搜索（$DFS$）遍历一个 $n$ 行 $m$ 列的矩阵。从左上角开始搜索，每次只能向右或向下移动一个位置。在搜索过程中，需要使用一个栈来维护当前搜索路径上的已访问位置。为了确保能够完成整个矩阵的遍历，栈的大小至少为（　　）。（注：本题不考虑栈空间的大小限制。） {{ select(9) }}

• $\max(n, m)$
• $m + n$
• $m + n - 1$
• $n \times m$

第 10 题 以下代码的时间复杂度是（　　）。

int n, i = 1;
cin >> n;
while (i < n) {
    i = i * 3;
}

{{ select(10) }}

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

第 11 题 某城市有 $8$ 个交通枢纽，如果要建设一个完全图式的道路网络，使得任意两个枢纽之间都有直达道路，需要建设（　　）条道路。 {{ select(11) }}

• $28$
• $64$
• $16$
• $7$

第 12 题 从 $5$ 个不同的红球和 $3$ 个不同的蓝球中，至少取 $1$ 个球，最多取 $4$ 个球，且红球和蓝球都必须至少取一个，不同的取法有（　　）种。 {{ select(12) }}

• $120$
• $125$
• $180$
• $210$

第 13 题 二叉树的节点按照先从上往下，后从左往右的顺序（对比"先行后列"的表达方式）进行编号，（　　）遍历方式可以按升序输出二叉搜索树的所有节点。 {{ select(13) }}

• 前序
• 中序
• 后序
• 层次

第 14 题 一个时间复杂度为 $O(n^3)$ 的算法，当 $n$ 从 $100$ 增大到 $200$ 时，运行时间大约变为原来的（　　）倍。 {{ select(14) }}

• $2$
• $4$
• $8$
• $16$

第 15 题 一段时长 $10$ 分钟的视频，分辨率为 $1080P$（$1920\times1080$），帧率为 $30$ 帧/秒，颜色深度为 $24$ 位。如果压缩比为 $50:1$，则压缩后的文件大小约为（　　）。 {{ select(15) }}

• $1.2GB$
• $2.1GB$
• $2.24GB$
• $104.3GB$

---

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

(1)

1  #include <iostream>
2  using namespace std;
3  int solve(int x, int y) {
4      if (y == 0) return x;
5      if (x < y) swap(x, y);
6      return solve(y, x - y);
7  }
8  int main() {
9      int a, b;
10     cin >> a >> b;
11     int k = solve(a, b);
12     cout << a/k << "/" << b/k << endl;
13     return 0;
14 }
15 // 输入的 a 和 b 是不大于 10000 的正整数

判断题

第 16 题 函数 solve(int x, int y) 计算 $x$ 和 $y$ 的最大公约数。　　（　　） {{ select(16) }}

• √
• ×

第 17 题 把第 $5$ 行代码去掉，程序会正常输出，但结果数值可能不对。　　（　　） {{ select(17) }}

• √
• ×

第 18 题 （$2$ 分）如果输入的值为 $160$ 和 $115$，则程序的输出结果为 $23/32$。　　（　　） {{ select(18) }}

• √
• ×

选择题

第 19 题 （$4$ 分）如果输入 $1817$ 和 $299$，则输出为（　　）。 {{ select(19) }}

• $1817/299$
• $97/13$
• $79/23$
• $79/13$

第 20 题 （$4$ 分）如果输入 $x, y$ 为 $1...10000$ 中随机生成的数，则程序的平均时间复杂度为（　　）。 {{ select(20) }}

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

(2)

1  #include <iostream>
2  using namespace std;
3  int main() {
4      int n, sum = 0;
5      cin >> n;
6      int arr[100];
7      for (int i = 0; i < n; i++) {
8          cin >> arr[i];
9      }
10     for (int i = 0; i < n; i++) {
11         int cnt = 0;
12         for (int j = 0; j < n; j++) {
13             if (arr[j] > arr[i]) {
14                 cnt++;
15             }
16         }
17         sum += (cnt == 1) * arr[i];
18     }
19     cout << sum << endl;
20     return 0;
21 }
22 // 输入的所有数为绝对值均不大于 1000 的整数

判断题

第 21 题 若输入数组为 $[5, 3, 8, 2]$，则程序输出为 $5$。　　（　　） {{ select(21) }}

• √
• ×

第 22 题 数组中可能存在多个元素满足条件，程序会将它们全部累加。　　（　　） {{ select(22) }}

• √
• ×

第 23 题 （$2$ 分）如果程序输出为 $0$，则数组中的所有元素一定都相等。　　（　　） {{ select(23) }}

• √
• ×

选择题

第 24 题 （$4$ 分）若输入数组为 $[9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2]$，则输出为（　　）。 {{ select(24) }}

• $-2$
• $-1$
• $8$
• $9$

第 25 题 （$4$ 分）该程序计算的是数组中（ ）。 {{ select(25) }}

• 第二大元素的值
• 所有比平均值大的元素之和
• 所有满足"恰好有一个元素比它大"的元素之和
• 最大元素和最小元素的和

(3)

1  #include <iostream>
2  #include <vector>
3  #include <algorithm>
4  using namespace std;
5
6  int n, k, ans = 0;
7  vector<int> nums;
8  vector<bool> used;
9
10 void dfs(int pos, int sum, int count) {
11     if (count == k) {
12         if (sum % 2 == 0) {
13             ans++;
14         }
15         return;
16     }
17     if (pos >= n) return;
18
19     if (!used[pos]) {
20         used[pos] = true;
21         dfs(pos + 1, sum + nums[pos], count + 1);
22         used[pos] = false;
23     }
24
25     dfs(pos + 1, sum, count);
26 }
27
28 int main() {
29     cin >> n >> k;
30     nums.resize(n);
31     used.resize(n, false);
32
33     for (int i = 0; i < n; i++) {
34         cin >> nums[i];
35     }
36
37     dfs(0, 0, 0);
38     cout << ans << endl;
39     return 0;
40 }

判断题

第 26 题 （$2$ 分）如果输入数据中存在重复数字，则重复数字的数量不会影响输出结果。　　（　　） {{ select(26) }}

• √
• ×

第 27 题 （$2$ 分）去掉 nums.resize(n); 和 used.resize(n, false); 这两行代码，不会影响程序的正常运行。　　（　　） {{ select(27) }}

• √
• ×

第 28 题 （$2$ 分）如果 $n=10$，$k=2$，$n$ 个数为 $1\sim10$ 的任意排列，则输出结果是 $2C_5^2$。　　（　　） {{ select(28) }}

• √
• ×

选择题

第 29 题 （$4$ 分）如果输入的 $k$ 为 $0$，则程序的输出结果为（ ）。 {{ select(29) }}

• $0$
• $1$
• 需要结合数组的数值，才能计算结果
• 以上都不对

第 30 题 （$4$ 分）程序的时间复杂度是（ ）。 {{ select(30) }}

• $O(n)$
• $O(n^2)$
• $O(2^n)$
• $O(n^k)$

---

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

(1)

归并排序算法通过递归地将数组不断地分割为更小的子数组，然后将这些子数组合并成有序数组，最终完成整个数组的排序。该排序为稳定排序，且时间复杂度较低。

1  #include <iostream>
2  #define N 100009
3  using namespace std;
4  int n;
5  int a[N],L[N],R[N];
6
7  void merge(int l, int m, int r) {
8      int n1 = m - l + 1;
9      int n2 = r - m;
10
11     for (int i = 0; i < n1; i++)
12         L[i] = a[l + i];
13     for (int j = 0; j < n2; j++)
14         R[j] = a[ ___①___ ];
15
16     int i = 0, j = 0, k = l;
17     while ( ___②___ ) {
18         if (L[i] <= R[j]) {
19             a[k] = L[i++];
20         } else {
21             a[k] = R[j++];
22         }
23         ++k;
24     }
25
26     while (i < n1) {
27         a[k++] = L[i++];
28     }
29
30     while (j < n2) {
31         a[k++] = R[j++];
32     }
33 }
34
35 void mSort(int left, int right) {
36     if (left < right) {
37         int mid = left + (right - left) / 2;
38         mSort(left, mid);
39         mSort(mid + 1, right);
40         merge( ___③___ );
41     }
42 }
43
44 int main() {
45     cin >> n;
46
47     for (int i = 0; i < n; i++) {
48         cin >> a[i];
49     }
50     mSort( ___④___ );
51     for (int i = 0; i < n-1; i++) {
52         cout << a[i] << " ";
53     }
54     cout << ___⑤___ << endl;
55     return 0;
56 }

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

• j
• j+1
• m+j
• m+1+j

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

• i < n && j < n
• i <= n && j <= n
• i < n1 && j < n2
• i <= n1 && j <= n2

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

• mid, left, right
• right, left, mid
• left, mid, right
• left, right, mid

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

• 0, n-1
• 0, n
• 1, n-1
• 1, n

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

• " " << a[n-1]
• a[n-1]
• " " << a[n]
• a[n]

(2)

波动序列指序列中的元素值交替上升和下降，最长波动子序列是已有的序列中满足这种波动性质的最长子序列。

1  #include <iostream>
2  #include <vector>
3  #include <algorithm>
4  #define N 1009
5  using namespace std;
6  int n;
7  int dp[N][2];
8  int main() {
9      cin >> n;
10     vector<int> nums(n);
11     for (int i = 0; i < n; i++) {
12         cin >> nums[i];
13     }
14
15     ___①___ ;
16
17     for (int i = 1; i < n; i++) {
18         for (int j = 0; ___②___ ; j++) {
19             if ( ___③___ ) {
20                 int tmp = dp[j][1] + 1;
21                 if (tmp > dp[i][0]) {
22                     dp[i][0] = tmp;
23                 }
24             }
25             else if (nums[i] < nums[j]) {
26                 int tmp = ___④___ ;
27                 if (tmp > dp[i][1]) {
28                     dp[i][1] = tmp;
29                 }
30             }
31         }
32     }
33
34     int max_Len = 1;
35     for (int i = 1; i < n; i++) {
36         max_Len = max(max_Len, ___⑤___ );
37     }
38
39     cout << max_Len << endl;
40
41     return 0;
42 }

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

• memset(dp, 1, sizeof(dp))
• memset(dp, 0x3f, sizeof(dp))
• fill(dp, dp + n * 2, 1)
• fill(dp[0], dp[0] + n * 2, 1)

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

• j < n
• j <= n
• j < i
• j <= i

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

• nums[i] > nums[j]
• nums[i] >= nums[j]
• nums[j] > nums[i]
• nums[j] >= nums[i]

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

• dp[i][0] + 1
• dp[i][1] + 1
• dp[j][0] + 1
• dp[j][1] + 1

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

• dp[i][0]
• dp[i][1]
• max(dp[i][0], dp[i][1])
• min(dp[i][0], dp[i][1])