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

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

• A. ls
• B. ls -l
• C. ls -a
• D. ls -s

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

• A. A 类
• B. B 类
• C. C 类
• D. D 类

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

• A. true
• B. false
• C. 1
• D. 编译错误

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

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

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

• A. $\lfloor \log_2 n \rfloor$
• B. $\lceil \log_2(n+1) \rceil - 1$
• C. $n - 1$
• D. $1$

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

• A. $1010100.01$
• B. $1100100.11$
• C. $1100100.01$
• D. $1010100.11$

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

• A. 快速排序
• B. 堆排序
• C. 归并排序
• D. 选择排序

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

• A. 内存
• B. 缓存
• C. 固态硬盘
• D. 寄存器

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

• A. $\max(n, m)$
• B. $m + n$
• C. $m + n - 1$
• D. $n \times m$

10. 以下代码的时间复杂度是（ ）。 {{ select(10) }}

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

• A. $O(1)$
• B. $O(n)$
• C. $O(\log n)$
• D. $O(n \log n)$

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

• A. $28$
• B. $64$
• C. $16$
• D. $7$

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

• A. $120$
• B. $125$
• C. $180$
• D. $210$

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

• A. 前序
• B. 中序
• C. 后序
• D. 层次

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

• A. $2$
• B. $4$
• C. $8$
• D. $16$

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

• A. $1.2\text{GB}$
• B. $2.1\text{GB}$
• C. $2.24\text{GB}$
• D. $104.3\text{GB}$

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 ✓，错误填 ✗；除特殊说明外，判断题每题 2 分，选择题每题 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) }}

• A. 正确
• B. 错误

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

• A. 正确
• B. 错误

18. 如果输入的值为 160 和 115，则程序的输出结果为 23/32。 {{ select(18) }}

• A. 正确
• B. 错误

选择题

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

• A. $1817/299$
• B. $97/13$
• C. $79/23$
• D. $79/13$

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

• A. $O(1)$
• B. $O(\log n)$
• C. $O(n)$
• D. $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) }}

• A. 正确
• B. 错误

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

• A. 正确
• B. 错误

23. 如果程序输出为 0，则数组中的所有元素一定都相等。 {{ select(23) }}

• A. 正确
• B. 错误

选择题

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

• A. $-2$
• B. $-1$
• C. $8$
• D. $9$

25. 该程序计算的是数组中（ ）。 {{ select(25) }}

• A. 第二大元素的值
• B. 所有比平均值大的元素之和
• C. 所有满足“恰好有一个元素比它大”的元素之和
• D. 最大元素和最小元素的和

(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. 如果输入数据中存在重复数字，则重复数字的数量不会影响输出结果。 {{ select(26) }}

• A. 正确
• B. 错误

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

• A. 正确
• B. 错误

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

• A. 正确
• B. 错误

选择题

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

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

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

• A. $O(n)$
• B. $O(n^2)$
• C. $O(2^n)$
• D. $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
51   mSort(④);
52
53   for (int i = 0; i < n-1; i++) {
54     cout << a[i] << " ";
55   }
56   cout << ⑤ << endl;
57
58   return 0;
59 }

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

• A. j
• B. j + 1
• C. m + j
• D. m + 1 + j

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

• A. i < n && j < n
• B. i <= n && j <= n
• C. i < n1 && j < n2
• D. i <= n1 && j <= n2

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

• A. mid, left, right
• B. right, left, mid
• C. left, mid, right
• D. left, right, mid

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

• A. 0, n - 1
• B. 0, n
• C. 1, n - 1
• D. 1, n

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

• A. " " << a[n - 1]
• B. a[n - 1]
• C. " " << a[n]
• D. 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) }}

• A. memset(dp, 1, sizeof(dp));
• B. memset(dp, 0x3f, sizeof(dp));
• C. fill(dp, dp + n * 2, 1);
• D. fill(dp[0], dp[0] + n * 2, 1);

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

• A. j < n
• B. j <= n
• C. j < i
• D. j <= i

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

• A. nums[i] > nums[j]
• B. nums[i] >= nums[j]
• C. nums[j] > nums[i]
• D. nums[j] >= nums[i]

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

• A. dp[i][0] + 1
• B. dp[i][1] + 1
• C. dp[j][0] + 1
• D. dp[j][1] + 1

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

• A. dp[i][0]
• B. dp[i][1]
• C. max(dp[i][0], dp[i][1])
• D. min(dp[i][0], dp[i][1])