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

1. 十进制整数 $-18$ 的 $8$ 位二进制补码为（ ）。 {{ select(1) }}

• 10010010
• 11101101
• 11101110
• 11101111

2. 用数字 $0,1,2,3,4$ 组成无重复的三位正整数，要求百位为偶数（即 $2$ 或 $4$）且个位不为 $0$，这样的三位数共有（ ）个。 {{ select(2) }}

• $18$
• $20$
• $22$
• $24$

3. 中缀表达式 a * (b + c) - d / e 对应的前缀表达式为（ ）。 {{ select(3) }}

• - * a + b c / d e
• * - a + b c / d e
• - a * + b c / d e
• - * a b + c / d e

4. 执行下列递归函数 g(4) 时，返回值为（ ）。

int g(int n) {
    if (n <= 1) return 1;
    return g(n - 1) + g(n - 2);
}

{{ select(4) }}

• $3$
• $5$
• $8$
• $13$

5. 下列表达式中，可以判断非负整数 $x$ 是否为奇数的是（ ）。 {{ select(5) }}

• (x | 1) == 1
• (x & 1) == 1
• (x ^ 1) == 1
• (x >> 1) == 1

6. 定义 long long a[2026];，该数组占用的内存最接近（ ）。 {{ select(6) }}

• $2$ KiB
• $8$ KiB
• $16$ KiB
• $32$ KiB

7. 在单链表中插入一个新结点 p，并使 p 成为链表的第一个结点（即新的链表头）。已知 head 指向原链表头，正确的操作顺序是（ ）。 {{ select(7) }}

• head = p; p->next = head;
• p->next = head; head = p;
• p = head; head->next = p;
• head->next = p; p->next = head;

8. 对一个已排序的数组进行二分查找，最坏情况下需要比较 $8$ 次。该数组的元素个数 $n$ 最大为（ ）。 {{ select(8) }}

• $128$
• $255$
• $256$
• $512$

9. 执行下列代码后，x 和 y 的值分别为（ ）。

int x = 7, y = 12;
int &r = x;
int *p = &y;
r = *p;
*p = 20;

{{ select(9) }}

• x=7, y=12
• x=12, y=12
• x=12, y=20
• x=20, y=12

10. 有 $n$ 级台阶，每次可以走 $1$ 级或 $2$ 级，要求不能连续两次走 $1$ 级。若 $f(n)$ 表示到达第 $n$ 级的方案数，则从最后一步分类可得（ ）。 {{ select(10) }}

• $f(n)=f(n-1)+f(n-2)$
• $f(n)=f(n-1)+f(n-2)+f(n-3)$
• $f(n)=f(n-2)+f(n-3)$
• $f(n)=f(n-1)+f(n-3)$

11. 已知某二叉树的前序遍历为 ACBDEFG，中序遍历为 CBADFEG，则后序遍历为（ ）。 {{ select(11) }}

• BCFGEDA
• CBDFGEA
• BCDFGEA
• CBGFEDA

12. 有向无环图中有边 $1\to2$、$1\to3$、$2\to4$、$3\to4$、$3\to5$、$4\to6$、$5\to6$。下列序列中，不可能是其拓扑序的是（ ）。 {{ select(12) }}

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

13. 从 $7$ 名男生和 $5$ 名女生中选出 $4$ 人，要求至少有 $2$ 名女生，则共有（ ）种选法。 {{ select(13) }}

• $245$
• $265$
• $285$
• $295$

14. 有若干活动的开始和结束时间如下，每个活动在时间段 [开始时间, 结束时间) 内进行（结束时刻不再占用），同一时刻只能参加一个活动。最多能参加多少个互不冲突的活动？（ ）

A: (1,4)    B: (3,5)    C: (0,6)
D: (5,7)    E: (3,9)    F: (5,9)
G: (6,10)   H: (8,11)   I: (8,12)
J: (2,14)   K: (12,16)

{{ select(14) }}

• $3$
• $4$
• $5$
• $6$

15. 以下哪个不是操作系统？（ ） {{ select(15) }}

• Windows
• HarmonyOS
• macOS
• Microsoft Office

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

第 1 题

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

char x[105], y[105];
int m;

bool same(char a, char b) {
    if (a == b) return true;
    for (int i = 0; i < m; i++)
        if ((x[i] == a && y[i] == b) || (x[i] == b && y[i] == a))
            return true;
    return false;
}

bool check(string s) {
    int l = 0, r = (int)s.size() - 1;
    while (l <= r) {
        if (!same(s[l], s[r])) return false;
        l++;
        r--;
    }
    return true;
}

int main() {
    string s;
    cin >> s >> m;
    for (int i = 0; i < m; i++) cin >> x[i] >> y[i];
    cout << (check(s) ? "Yes" : "No") << endl;
    return 0;
}

16. 长度为 $1$ 的字符串一定满足 check。（ ） {{ select(16) }}

• 正确
• 错误

17. 若输入关系包含 a b 和 b c，程序一定认为 a 与 c 可以匹配。（ ） {{ select(17) }}

• 正确
• 错误

18. 将 while (l <= r) 改为 while (l < r) 后，对于所有输入，输出结果都不变。（ ） {{ select(18) }}

• 正确
• 错误

19. 若 s = "abca"，关系只有 b c，则程序输出为（ ）。 {{ select(19) }}

• Yes
• No
• true
• false

20. （4 分）若字符串长度为 $3$、字符只取 a,b,c，关系为 a b、b c，则能输出 Yes 的字符串共有（ ）个。 {{ select(20) }}

• $15$
• $18$
• $21$
• $27$

第 2 题

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

int n, a[100005], b[100005];
ll cnt;

void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            b[k++] = a[i++];
        } else {
            b[k++] = a[j++];
            cnt += mid - i + 1;
        }
    }
    while (i <= mid) b[k++] = a[i++];
    while (j <= r) b[k++] = a[j++];
    for (int t = 0; t < k; t++) a[l + t] = b[t];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    merge_sort(0, n - 1);
    cout << cnt << endl;
    return 0;
}

21. 程序最终输出的是原数组逆序对的数量。（ ） {{ select(21) }}

• 正确
• 错误

22. 执行 cnt += mid - i + 1 时，说明 a[i..mid] 中的每个元素都大于 a[j]。（ ） {{ select(22) }}

• 正确
• 错误

23. 程序结束后，数组 a 已经按从小到大排好序。（ ） {{ select(23) }}

• 正确
• 错误

24. 输入为 4 和 3 1 4 2 时，程序输出为（ ）。 {{ select(24) }}

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

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

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

第 3 题

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

int n, a[55][2], best;

void dfs(int len, int sum) {
    if (len == 1) {
        best = max(best, sum);
        return;
    }
    for (int i = 1; i < len; i++) {
        int x = a[i - 1][0], y = a[i - 1][1];
        int p = a[i][0], q = a[i][1];
        a[i - 1][0] = x + p;
        a[i - 1][1] = y + q;
        for (int j = i; j < len - 1; j++) {
            a[j][0] = a[j + 1][0];
            a[j][1] = a[j + 1][1];
        }
        dfs(len - 1, sum + x + p + abs(y - q));
        for (int j = len - 1; j > i; j--) {
            a[j][0] = a[j - 1][0];
            a[j][1] = a[j - 1][1];
        }
        a[i - 1][0] = x; a[i - 1][1] = y;
        a[i][0] = p; a[i][1] = q;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i][0];
    for (int i = 0; i < n; i++) cin >> a[i][1];
    best = 0;
    dfs(n, 0);
    cout << best << endl;
    return 0;
}

26. 当 len == 1 时，程序不会再递归调用 dfs。（ ） {{ select(26) }}

• 正确
• 错误

27. 每次递归调用都会把相邻的两个数对合并成一个数对。（ ） {{ select(27) }}

• 正确
• 错误

28. （3 分）若初始只有两个数对 (1,2)、(3,5)（即 a[0][0]=1, a[0][1]=2, a[1][0]=3, a[1][1]=5），最终 best 为 $10$。（ ） {{ select(28) }}

• 正确
• 错误

29. 当初始有 $3$ 个数对时，第一次可以选择的合并位置有（ ）个。 {{ select(29) }}

• $1$
• $2$
• $3$
• $4$

30. （4 分）设初始有 $n$ 个数对，不考虑复制数组的常数，递归分支数量的最坏数量级接近（ ）。 {{ select(30) }}

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

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

（1）二进制掩码统计

给定一个只包含小写字母的字符串，统计其中“每个字母都出现偶数次”的非空连续子串的数量。用二进制数 mask 的第 $i$ 位（从 $0$ 开始）表示字母 'a'+i 出现次数的奇偶性，$1$ 表示出现奇数次，$0$ 表示出现偶数次。试补全程序。

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

string s;
ll cnt[1 << 26];

int main() {
    cin >> s;
    ll ans = 0;
    int mask = ①;
    cnt[0] = 1;
    for (int i = 0; i < (int)s.size(); i++) {
        mask ^= ②;
        ans += cnt[③];
        cnt[④]++;
    }
    cout << ⑤ << endl;
    return 0;
}

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

• 0
• 1
• -1
• (int)s.size()

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

• 1 << (s[i] - 'a')
• 1 << s[i]
• s[i] - 'a'
• mask << 1

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

• mask
• 0
• s[i] - 'a'
• cnt[mask]

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

• mask
• cnt[mask]
• s[i]
• i

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

• ans
• mask
• cnt[0]
• s

（2）最大平均值

给定一个长度为 $n$ 的整数序列 $a_1\sim a_n$，求长度至少为 $m$ 的连续子段的平均值的最大值，结果四舍五入保留两位小数输出。保证 $1\le m\le n\le 10^5$，$0\le a_i\le 2000$。试补全程序。

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

int n, m;
double a[100005], b[100005];

bool check(double mid) {
    for (int i = 1; i <= n; i++)
        b[i] = b[i - 1] + ①;
    double minb = 1e18;
    for (int i = m; i <= n; i++) {
        minb = min(minb, ②);
        if (③) return true;
    }
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    double l = -1e9, r = 1e9;
    while (r - l > ④) {
        double mid = ⑤;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << fixed << setprecision(2) << l << endl;
    return 0;
}

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

• a[i] - mid
• a[i] + mid
• a[i] * mid
• a[i] / mid

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

• b[i - m]
• b[i]
• b[i - 1]
• b[m]

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

• b[i] >= minb
• b[i] <= minb
• b[i] > a[i]
• minb >= b[i]

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

• 1e-4
• 1e4
• 0
• 1

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

• (l + r) / 2
• (l - r) / 2
• l * r
• (l + r) * 2