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

1. 在现代游戏开发中，常使用带 Alpha 通道的 32 位 RGBA 颜色模式。一幅分辨率为 1920 x 1080 的此类未经压缩的位图图像，若按 1 MiB = 1024^2 Byte 计算，大约需要占用（ ）的存储空间。{{ select(1) }}

• $2\,\mathrm{MiB}$
• $7.9\,\mathrm{MiB}$
• $15.8\,\mathrm{MiB}$
• $63\,\mathrm{MiB}$

2. 将十六进制数 $(3A)_{16}$ 与二进制数 $(10110)_2$ 相加，其结果用八进制表示为（ ）{{ select(2) }}

• $(112)_8$
• $(120)_8$
• $(140)_8$
• $(150)_8$

3. 一个 8 位无符号计数器的值始终按模 256 保存。初值为 250，依次执行"加 20""减 17""乘 3"，且每一步的结果都会重新存入该计数器。最终计数器的值是（ ）{{ select(3) }}

• $-9$
• $223$
• $251$
• $247$

4. 一个无向无权图有 8 个顶点，边集为 1-2, 1-3, 2-4, 2-5, 3-5, 4-6, 5-6, 5-7, 6-8, 7-8。从顶点 1 到顶点 8 至少需要经过（ ）条边。{{ select(4) }}

• $2$
• $3$
• $4$
• $5$

5. 将 1, 2, 3, 4, 5, 6, 7, 8 依次入栈，下列哪个出栈序列是不可能得到的？（ ）{{ select(5) }}

• 4, 6, 5, 3, 8, 7, 2, 1
• 2, 1, 5, 4, 7, 8, 6, 3
• 3, 5, 4, 2, 1, 8, 6, 7
• 1, 4, 3, 2, 7, 6, 8, 5

6. 运行以下代码片段。若 n = 2^k，其中 k 为非负整数，则该代码片段的时间复杂度最接近（ ）。

   int cnt = 0;
   for (int i = 1; i <= n; i *= 2) {
       for (int j = 1; j <= i; j++) {
           for (int t = n; t > 0; t /= 2) {
               cnt++;
           }
       }
   }
   ```{{ select(6) }}
   

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

7. 某循环队列使用长度为 8 的数组，数组下标为 0..7，并浪费一个单元来区分队空和队满。front 指向队首元素位置，rear 指向下一次入队的位置。初始时 front = rear = 0。依次执行：入队 1, 2, 3；出队一次；入队 4, 5, 6, 7；出队一次；入队 8, 9。执行结束后，队列状态为（ ）。{{ select(7) }}

• front = 2, rear = 1，从队首到队尾依次为 3 4 5 6 7 8 9
• front = 2, rear = 0，从队首到队尾依次为 3 4 5 6 7 8
• front = 1, rear = 1，从队首到队尾依次为 2 3 4 5 6 7 8 9
• front = 2, rear = 7，从队首到队尾依次为 3 4 5 6 7

8. 无向图有 6 个顶点，边集为 $1-2, 1-3, 2-4, 2-5, 3-5, 4-6, 5-6$。从顶点 1 开始进行递归深度优先遍历，且每次按顶点编号从小到大的顺序访问尚未访问的邻接点，则访问序列为（ ）。{{ select(8) }}

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

9. 下面的数组元素由 (关键字, 标号) 组成：

   (2, a), (1, b), (2, c), (1, d)
   

   若使用简单选择排序按关键字从小到大排序，且每一轮在未排序部分中选择"关键字最小且下标最大"的元素与当前位置交换，则最终标号顺序为（ ）。{{ select(9) }}

• b d a c
• d b c a
• b d c a
• d b a c

10. 运行以下代码片段，输出结果是（ ）。

    int a[8] = {1, 2, 2, 2, 4, 4, 7, 9};
    int l = 0, r = 8;
    while (l < r) {
        int mid = (l + r) / 2;
        if (a[mid] <= 4) l = mid + 1;
        else r = mid;
    }
    cout << l << " " << a[l - 1];
    ```{{ select(10) }}
    

• 6 4
• 4 4
• 6 7
• 5 4

11. 在一个 $6 \times 6$ 的网格中（从 $(0,0)$ 到 $(5,5)$），每次只能向右或向上移动一个单位。由于施工，点 $(2,2)$ 和点 $(3,4)$ 无法通行。从 $(0,0)$ 走到 $(5,5)$ 共有（ ）种不同的走法。{{ select(11) }}

• $27$
• $132$
• $81$
• $252$

12. 关于 ASCII 编码，下列说法正确的是（ ）。{{ select(12) }}

• 数字字符 '0' 到 '9' 的编码连续，因此 '9' 比 '0' 大 9；大写字母 'A' 到 'Z' 的编码连续，因此 'Z' 比 'A' 大 25。
• 字符 '9' 的编码值等于整数 9。
• 小写字母 'a' 的编码值小于大写字母 'Z' 的编码值。
• 数字字符和大写字母在 ASCII 表中交替连续排列。

13. 使用栈计算后缀表达式 5 1 2 + 4 * + 3 - 的值，结果为（ ）。{{ select(13) }}

• $9$
• $14$
• $17$
• $20$

14. 关于 C++ 函数参数传递，下列说法正确的是（ ）。{{ select(14) }}

• 形参写作 int x 时，在函数内修改 x 会直接修改调用者传入的变量。
• 形参写作 int& x 时，函数会得到实参的一份副本，因此不能修改原变量。
• 形参写作 int* p 时，只要在函数内执行 p = nullptr，调用者的指针变量也一定变为 nullptr。
• 形参写作 int& x 可直接修改实参；形参写作 int* p 时可通过 *p 修改所指对象，但给 p 重新赋值不会改变调用者的指针变量。

15. 运行以下 C++ 代码片段，输出结果是（ ）。

    int mask = 0;
    for (int i = 1; i <= 5; i++) {
        if (i % 2 == 1) {
            mask |= (1 << (i - 1));
        } else {
            mask ^= (1 << (i / 2 - 1));
        }
    }
    cout << mask;
    ```{{ select(15) }}
    

• $10$
• $18$
• $22$
• $31$

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

(1)

#include <bits/stdc++.h>
using namespace std;

int n, limit;
vector<int> a;
long long calls = 0;

int dfs(int idx, int sum) {
    calls++;

    if (sum > limit) return -1;
    if (idx == n) return sum;

    int take = dfs(idx + 1, sum + a[idx]);
    int skip = dfs(idx + 1, sum);

    return max(take, skip);
}

int main() {
    cin >> n >> limit;
    a.resize(n);

    for (int i = 0; i < n; i++) cin >> a[i];

    cout << dfs(0, 0) << " " << calls << endl;

    return 0;
}

16. 变量 calls 统计了 dfs 被调用的次数，包括因为 sum > limit 而立即返回的调用。（）{{ select(16) }}

• 对
• 错

17. 在本题输入均为正整数的条件下，若某次调用中 sum > limit，则继续向后选择更多数也不可能得到合法答案。（）{{ select(17) }}

• 对
• 错

18. 若输入为：

    5 10
    2 3 5 6 7
    

    程序输出为（）{{ select(18) }}

• 10 53
• 10 31
• 9 53
• 12 53

19. 若输入为：

    4 11
    4 8 5 3
    

    程序输出为（）{{ select(19) }}

• 10 23
• 11 15
• 11 23
• 12 23

20. 若将 dfs 中的两次递归调用顺序改为先计算 skip，再计算 take，其余代码不变，下列说法正确的是（）{{ select(20) }}

• 返回的最优值和 calls 都不变
• 返回的最优值不变，但 calls 一定减少
• calls 不变，但返回的最优值可能改变
• 返回的最优值和 calls 都可能改变

21. 设输入的数有 n 个，该程序最坏情况下的时间复杂度和递归栈空间复杂度分别为（）{{ select(21) }}

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

(2)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    priority_queue<long long, vector<long long>, greater<long long>> pq;

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        pq.push(x);
    }

    long long cost = 0;

    while (pq.size() > 1) {
        long long a = pq.top();
        pq.pop();
        long long b = pq.top();
        pq.pop();

        long long s = a + b;
        cost += s;
        pq.push(s);
    }

    cout << cost << " " << pq.top() << endl;

    return 0;
}

22. 由于使用了 greater<long long>，该程序的优先队列堆顶始终是当前队列中的最小值。（）{{ select(22) }}

• 对
• 错

23. 每执行一次 while 循环，优先队列中的元素个数都会减少 1。（）{{ select(23) }}

• 对
• 错

24. 若每次任意取出两个数合并，而不是每次取出最小的两个数，则最终得到的 cost 一定不变。（）{{ select(24) }}

• 对
• 错

25. 若输入为：

    5
    2 3 7 9 18
    

    程序输出为（）{{ select(25) }}

• 77 39
• 82 39
• 77 18
• 39 77

26. 若输入为：

    6
    1 1 2 3 5 8
    

    程序输出为（）{{ select(26) }}

• 42 20
• 45 20
• 45 19
• 50 20

27. 设输入的数有 n 个，该程序的时间复杂度和空间复杂度最接近（）{{ select(27) }}

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

(3)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, V;
    cin >> n >> V;

    vector<int> w(n + 1), c(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> c[i];
    }

    vector<int> dp(V + 1, 0);

    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
        }
    }

    for (int j = 0; j <= V; j++) {
        if (j) cout << " ";
        cout << dp[j];
    }
    cout << endl;

    cout << dp[V] << endl;

    return 0;
}

28. 在程序运行结束后，dp[j] 表示容量不超过 j 时可以获得的最大价值。（）{{ select(28) }}

• 对
• 错

29. 内层循环 for (int j = V; j >= w[i]; j--) 从大到小枚举，是为了保证每个物品最多被选择一次。（）{{ select(29) }}

• 对
• 错

30. 若将内层循环改为从小到大枚举，则程序仍然计算的是每个物品最多选一次的 0/1 背包。（）{{ select(30) }}

• 对
• 错

31. 若输入为：

    4 7
    3 4
    4 5
    2 3
    3 6
    

    程序第一行输出为（）{{ select(31) }}

• 0 0 3 6 6 9 10 11
• 0 0 3 4 5 7 8 9
• 0 0 3 6 6 9 9 11
• 0 0 0 6 6 9 10 11

32. 若将程序中的内层循环改为

    for (int j = w[i]; j <= V; j++) {
        dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
    }
    

    并仍使用第 31 题的输入，则程序第二行输出为（）{{ select(32) }}

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

33. 设背包容量为 V，物品数量为 n，该程序的时间复杂度和空间复杂度分别为（）{{ select(33) }}

• $O(nV)$，$O(V)$
• $O(nV)$，$O(nV)$
• $O(n + V)$，$O(V)$
• $O(2^n)$，$O(nV)$

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

(1)（最短达标子数组）

给定一个长度为 n 的正整数数组 a 和一个正整数 S，要求找出和至少为 S 的最短连续子数组长度。若不存在这样的子数组，输出 -1。

试补全程序。

#include <bits/stdc++.h>
using namespace std;

int minLen(const vector<int>& a, int S) {
    int n = (int)a.size();
    int ans = n + 1;
    int sum = 0, l = 0;

    for (int r = 0; r < n; r++) {
        __(34)__;

        while (__(35)__) {
            __(36)__;
            __(37)__;
            l++;
        }
    }

    if (__(38)__) return -1;
    return ans;
}

int main() {
    int n, S;
    cin >> n >> S;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << minLen(a, S) << endl;
    return 0;
}

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

• sum = a[r]
• sum += a[l]
• sum += a[r]
• r++

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

• sum > S
• sum + a[r] >= S
• l < r
• sum >= S

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

• ans = max(ans, r - l + 1)
• ans = min(ans, r - l + 1)
• ans = r + 1
• ans = min(ans, r - l)

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

• sum -= a[l]
• sum -= a[r]
• l--
• sum = 0

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

• ans == 0
• ans < n + 1
• ans == n + 1
• sum < S

(2)（最小最大差配对）

给定 n 个整数和一个正整数 m，保证 2 * m <= n。现在要从这 n 个数中选出 m 对数，每个数最多使用一次。每一对的代价为两个数之差的绝对值，所有配对方案的总代价定义为这 m 对代价中的最大值。请输出所有配对方案中，总代价的最小可能值。

试补全程序。

#include <bits/stdc++.h>
using namespace std;

bool canMake(const vector<int>& a, int m, int limit) {
    int cnt = 0;

    for (int i = 1; i < (int)a.size(); ) {
        if (__(39)__) {
            cnt++;
            __(40)__;
        } else {
            i++;
        }
    }

    return __(41)__;
}

int solve(vector<int>& a, int m) {
    sort(a.begin(), a.end());

    int l = 0, r = a.back() - a.front(), ans = r;

    while (l <= r) {
        int mid = (l + r) / 2;

        if (__(42)__) {
            ans = mid;
            __(43)__;
        } else {
            l = mid + 1;
        }
    }

    return ans;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << solve(a, m) << endl;
    return 0;
}

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

• a[i] - a[i - 1] < limit
• a[i] - a[i - 1] <= limit
• a[i - 1] - a[i] <= limit
• a[i] + a[i - 1] <= limit

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

• i++
• cnt++
• i = 1
• i += 2

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

• cnt == m
• cnt < m
• cnt >= m
• cnt > (int)a.size()

42. (42) 处应填（）{{ select(42) }}

• canMake(a, m, mid)
• canMake(a, mid, m)
• canMake(a, m, ans)
• canMake(a, m, l)

43. (43) 处应填（）{{ select(43) }}

• l = mid + 1
• r = mid - 1
• r = mid + 1
• l = mid - 1