一、 单项选择题（共 15 题，每题 2 分，共计 30 分）

1. [2 分] 执行下列代码片段，cnt 的值是（ ）。

int x = 2026, cnt = 0;
while (x) {
    x &= x - 1;
    cnt++;
}

（ {{ select(1) }} ）

• 6
• 7
• 11
• 8

2. [2 分] 用权值 $\{1, 2, 3, 4, 5, 6, 7, 8\}$ 构造哈夫曼树，其带权路径长度为（ ）。 （ {{ select(2) }} ）

• 108
• 96
• 99
• 102

3. [2 分] 写出 1 到 1000 的所有整数时，数字“1”共出现的次数为（ ）。 （ {{ select(3) }} ）

• 300
• 271
• 301
• 320

4. [2 分] 将 5 封信随机装入 5 个写好地址的信封（每封一个），恰好有 2 封装对的方案数是（ ）。 （ {{ select(4) }} ）

• 44
• 24
• 10
• 20

5. [2 分] $3^{2026} \bmod 100$ 的值是（ ）。 （ {{ select(5) }} ）

• 29
• 9
• 43
• 81

6. [2 分] 有 5 堆石子排成一行，重量依次为 4、1、3、2、5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（ ）。 （ {{ select(6) }} ）

• 36
• 35
• 34
• 33

7. [2 分] 树状数组维护长度 n=16 的序列，查询前缀和 sum(11) 与单点修改 add(3, x) 分别需要访问树状数组中多少个下标（ ）。 （ {{ select(7) }} ）

• 3 和 4
• 4 和 4
• 3 和 5
• 4 和 3

9. [2 分] 有向无环图 G 顶点集为 {1,2,3,4}，边集为 {(1,2),(1,3)}，顶点 4 与任何顶点均不相邻。该图不同的拓扑序共有多少种（ ）。 （ {{ select(8) }} ）

• 12
• 8
• 4
• 6

9. [2 分] 递归式 $T(n) = T(n/3) + T(2n/3) +O(n)$，$T(1) = O(1)$，则 $T(n) =$（ ）。 （ {{ select(9) }} ）

• $O(n \log n)$
• $O(n^2)$
• $O(n^{1.5})$
• $O(n)$

10. [2 分] 无根树含 9 个结点（编号为 1—9），边集为 {(1,2),(1,3),(2,4),(2,5),(3,6),(6,7),(7,8),(5,9)}。该树的直径（以边数计）与重心分别是（ ）。 （ {{ select(10) }} ）

• 直径 6，重心为结点 3
• 直径 7，重心为结点 2
• 直径 8，重心为结点 1
• 直径 7，重心为结点 1

11. [2 分] 一张有向图缩点后得到的有向无环图含 6 个顶点，其中入度为 0 的顶点有 3 个，出度为 0 的顶点有 4 个。为使原图变成强连通图，至少需要添加多少条有向边（ ）。 （ {{ select(11) }} ）

• 7
• 6
• 4
• 3

12. [2 分] 含 6 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（ ）。 （ {{ select(12) }} ）

• 42
• 429
• 132
• 720

13. [2 分] 字符串 S = "ababaabab"，其所有既是真前缀又是真后缀的子串（非空）的长度之和是（ ）。 （ {{ select(13) }} ）

• 4
• 6
• 7
• 5

14. [2 分] 用归并排序统计逆序对，合并部分的核心代码为：

// 分并 a[l..mid] 与 a[mid+1..r]，同时累加逆序对
if (a[i] <= a[j]) {
    tmp[k++] = a[i++]; // 取左半段元素
} else {
    tmp[k++] = a[j++]; // 取右半段元素
    ans += mid - i + 1;
}

若把判断条件中的 a[i] <= a[j] 改成 a[i] < a[j]，则 ans 统计出的结果（ ）。 （ {{ select(14) }} ）

• 完全不变
• 变为原来的两倍
• 变为满足 $i<j$ 且 a[i]≥a[j] 的数对个数
• 变为原来的一半

15. [2 分] 执行 power(2, 100, 1000) 调用下列函数，返回值是（ ）。

long long power(long long a, long long b, long long p) {
    long long r = 1 % p;
    while (b) {
        if (b & 1)
            r = r * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return r;
}

（ {{ select(15) }} ）

• 576
• 376
• 976
• 176

---

二、 阅读程序（判断题正确填 $\checkmark$，错误填 $\times$；判断题 1.5 分，选择题 3 分，共计 40 分）

（1）

#include <iostream>
#include <string>
using namespace std;
int a[100];
string s;
int gen[13] = {1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};
int main() {
    cin >> s;
    for (int i = 0; i < 32; ++i) {
        a[i] = s[i] - '0';
    }
    for (int i = 32; i < 44; ++i) {
        a[i] = 0;
    }
    for (int i = 0; i < 32; ++i) {
        if (a[i] == 0) continue;
        for (int j = 0; j < 13; ++j) {
            a[i + j] ^= gen[j];
        }
    }
    for (int i = 32; i < 44; ++i) {
        cout << a[i];
    }
    cout << endl;
    return 0;
}

说明：输入保证为一个长度恰为 32 的 '0'/'1' 字符串。

判断题

16. [1 分] 当输入为 32 个 '0' 时，程序输出 12 个 0。（ {{ select(16) }} ）

• $\checkmark$
• $\times$

17. [1.5 分] 程序运行结束后，数组 a 中下标从 0 到 31 的元素一定全为 0。（ {{ select(17) }} ）

• $\checkmark$
• $\times$

18. [1.5 分] 若将第 12—14 行（为 a[32] 到 a[43] 补 0 的循环）删除，会改变程序输出的结果。（ ）（ {{ select(18) }} ）

• $\checkmark$
• $\times$

单选题

19. [3 分] 关于第 6 行定义的数组 gen，下列说法正确的是（ ）。 （ {{ select(19) }} ）

• gen 共有 12 个元素，表示一个 12 位的除数
• gen 共有 13 个元素，表示一个 13 位的被除数
• gen 共有 13 个元素，其中 gen[0] 是除数的最高位
• gen 共有 13 个元素，其中 gen[12] 是除数的最高位

21. [3 分] 该程序实现的功能，最准确的说法是（ ）。 （ {{ select(20) }} ）

• 将输入的 32 位串看成二进制数 M，输出 M 与 13 位二进制数 1100000001111 按位异或的结果
• 将输入串视为 32 位二进制数 M，在其后补 12 个 0（即计算 M×2 12 ），再对它做模 2 除法求余数，并输出 12 位余数
• 对输入的 32 位串逐位取反并输出结果
• 统计输入串中 1 的个数，并把该个数用 12 位二进制表示后输出

21. [3 分] 若把第 16 行 if (a[i] == 0) continue; 删除，说法正确的是（ ）。 （ {{ select(21) }} ）

• 程序输出的结果不会改变
• 可能造成程序运行错误
• 程序能够正常输出一个 12 位 '0' / '1' 串，但是输出结果与输入的 s 无关
• 程序运行结束后，a[0] 的值一定为 0

（2）

#include <iostream>
using namespace std;
int n, m, a[100007], L, R, lg[100007], i, j, t, dp[100007][25], pw[25];
int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
}
int main() {
    cin >> n >> m;
    for (i = 1; i <= n; i++) cin >> a[i];
    t = 0;
    pw[0] = 1;
    for (i = 1; i <= 24; i++) pw[i] = pw[i - 1] * 2;
    for (i = 1; i <= 100000; i++)
        if (pw[t + 1] >= i) lg[i] = t;
        else { t++; lg[i] = t; }
    for (i = 1; i <= n; i++) {
        dp[i][0] = a[i];
    }
    for (j = 1; j <= lg[n]; j++) {
        for (i = 1; i + pw[j] - 1 <= n; i++) {
            dp[i][j] = gcd(dp[i][j - 1], dp[i + pw[j - 1]][j - 1]);
        }
    }
    for (i = 1; i <= m; i++) {
        cin >> L >> R;
        cout << gcd(dp[L][lg[R - L + 1]], dp[R - pw[lg[R - L + 1]] + 1][lg[R - L + 1]]) << endl;
    }
    return 0;
}

说明：保证 $1 \le n \le 100000$，每次查询满足 $1 \le L \le R \le n$，且数组 $a$ 的元素均为正整数。

判断题

22. [1.5 分] 当 $n=5, a=\{4, 2, 6, 3, 3\}$，且只有一次查询 $L=2, R=5$ 时，输出为 1。（ {{ select(22) }} ）

• $\checkmark$
• $\times$

23. [1.5 分] 当某次查询的区间长度为 1（即 $L=R$）时，程序查询的输出一定等于 $a[L]$。（ {{ select(23) }} ）

• $\checkmark$
• $\times$

24. [1.5 分] 任意一次查询的输出结果一定不小于该查询区间内的最小值。（ ）（ {{ select(24) }} ）

• $\checkmark$
• $\times$

单选题

25. [3 分] 对于 $j \ge 1$，数组 dp[i][j] 保存的是（ ）。 （ {{ select(25) }} ）

• 从 $a[i]$ 开始连续 $j$ 个数的最大公约数
• 从 $a[i]$ 开始连续 $2^j$ 个数的最大公约数
• $a[i]$ 与 $a[j]$ 的最大公约数
• $a[1]$ 到 $a[i]$ 的最大公约数

26. [3 分] 若把一次查询次数的运算视为 $O(1)$，则第 17-22 行建表过程的时间复杂度为（ ）。 （ {{ select(26) }} ）

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

27. [3 分] 设 $x$ 为一次查询的区间长度（即 $x = R - L + 1$），则使得 lg[x] = 5 的 $x$ 的取值范围是（ ）。 （ {{ select(27) }} ）

• $[16, 31]$
• $[17, 32]$
• $[32, 63]$
• $[33, 64]$

（3）

#include <iostream>
using namespace std;
int n, fa[100007], f[100007], ans;
int main() {
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        cin >> fa[i];
    }
    for (int i = n; i >= 2; --i) {
        if (f[fa[i]] + f[i] + 1 > ans) {
            ans = f[fa[i]] + f[i] + 1;
        }
        if (f[i] + 1 > f[fa[i]]) {
            f[fa[i]] = f[i] + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

说明：输入第一行为结点个数 $n$，第二行为 $n-1$ 个整数，依次表示结点 $2 \sim n$ 的父结点编号，满足 $2 \le n \le 10000$ 且 $1 \le fa[i] < i$，根结点为 1。

判断题

28. [1.5 分] 当 $n=5, fa[2] \sim fa[5] = \{1, 2, 3, 4\}$ 时，程序输出 4。（ {{ select(28) }} ）

• $\checkmark$
• $\times$

29. [1.5 分] 程序输出前，f[1] 的值一定等于 ans 的值。（ {{ select(29) }} ）

• $\checkmark$
• $\times$

30. [1.5 分] 将第 10-12 行与第 13-15 行两个 if 语句的顺序交换后，程序输出结果不受影响。（ {{ select(30) }} ）

• $\checkmark$
• $\times$

单选题

31. [3 分] 程序输出的 ans 表示的是（ ）。 （ {{ select(31) }} ）

• 树中距离最远的两个结点之间路径所经过的边数
• 根结点 1 到最远叶子结点之间路径所经过的边数
• 树中叶子结点的个数
• 所有结点的父结点编号之和

32. [3 分] 当 $n=7, fa[2] \sim fa[7] = \{1, 1, 2, 2, 3, 3\}$ 时，输出为（ ）。 （ {{ select(32) }} ）

• 2
• 3
• 4
• 5

33. [3 分] 当 $n=10$，满足输出为 9 的合法输入种类数为（ ）。 （ {{ select(33) }} ）

• 0
• 9
• 256
• 512

---

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

（1）平衡路径

给定一张有 $n$ 个顶点、$m$ 条边的无向图，每条边带有符号 '+' 或 '-'。对于一条从顶点 $s$ 到顶点 $t$ 的路径，允许重复经过顶点和边。定义一条路径的权值如下：记 $n^+, n^-$ 分别为经过的 '+' 边数和 '-' 边数，则该路径的权值为 $|n^+ - n^-|$。

请计算从 $s$ 到 $t$ 的路径的最小权值。若不存在从 $s$ 到 $t$ 的路径，则输出 -1。

输入第一行为四个整数 $n, m, s, t$。接下来 $m$ 行，每行给出两个整数 $a, b$ 和一个字符 '+' 或 '-'，描述一条连接 $a$ 与 $b$ 的无向边及其符号。

数据满足 $2 \le n \le 2 \times 10^5, 1 \le m \le 4 \times 10^5, 1 \le s, t \le n$ 且 $s \ne t, 1 \le a, b \le n$，可能出现重边。

以下程序通过 BFS 求出最小权值。请补全程序。

#include <iostream>
constexpr int N = 200005;
constexpr int M = 400005;
int n, m, s, t;
int h[N], e[M << 1], ne[M << 1], w[M << 1], idx;
int q[N], d[N], c[N];
void add(int a, int b, int z) {
    e[idx] = b;
    w[idx] = z;
    ne[idx] = h[a];
    h[a] = idx++;
}
int main() {
    std::cin >> n >> m >> s >> t;
    for (int i = 1; i <= n; i++)
        h[i] = d[i] = c[i] = -1;
    for (int i = 0; i < m; i++) {
        int a, b;
        char op[2];
        std::cin >> a >> b >> op;
        int z = /* ① */;
        add(a, b, z);
        add(b, a, z);
    }
    int hh = 0, tt = 0;
    int p = 0, ng = 0, ok = 1;
    q[tt++] = s;
    d[s] = c[s] = 0;
    while (/* ② */) {
        int x = q[hh++];
        for (int i = h[x]; i != -1; i = ne[i]) {
            int y = e[i];
            if (w[i] > 0) p = 1;
            if (w[i] < 0) ng = 1;
            if (d[y] == -1) {
                d[y] = /* ③ */;
                c[y] = c[x] ^ 1;
                q[tt++] = y;
            } else if (/* ④ */)
                ok = 0;
        }
    }
    if (d[t] == -1) {
        std::cout << -1;
        return 0;
    }
    if (!p || !ng) {
        std::cout << d[t];
        return 0;
    }
    if (/* ⑤ */) std::cout << 0;
    else std::cout << 1;
    return 0;
}

34. [3 分] ① 处应填（ {{ select(34) }} ）

• op[0] == '+' ? 0 : 1
• op[0] == '+'
• op[0] == '+' ? 1 : -1
• op[0] == '-' ? 1 : 0

35. [3 分] ② 处应填（ {{ select(35) }} ）

• hh < n
• tt < n
• hh <= tt
• hh < tt

36. [3 分] ③ 处应填（ {{ select(36) }} ）

• d[y] + 1
• d[x] + 1　
• d[x]
• d[x] - 1

38. [3 分] ④ 处应填（ {{ select(37) }} ）

• c[y] == c[x]
• w[i] == 1
• c[y] != c[x]
• d[y] + 1 != d[x]

38. [3 分] ⑤ 处应填（ {{ select(38) }} ）

• ok && c[s] == c[t]
• ok && c[s] != c[t]
• !ok || c[s] == c[t]
• !ok && c[s] != c[t]

（2）标准答案

给定 $n$ 名学生参加一场考试，考试共有 $m$ 道选择题，每题只有 A、B 两个选项。

第 $i$ 名学生的作答为一个长度为 $m$ 的字符串。若最终公布的标准答案与该学生在某道题上的作答相同，则该学生在这道题上得 1 分，否则得 0 分。记第 $i$ 名学生最终得到的总分为 $r_i$。

每名学生还有一个预期得分 $x_i$。现在需要构造一份标准答案，使 $\sum_{i=1}^n |r_i - x_i|$ 尽可能大。 数据满足 $1 \le n \le 18, 1 \le m \le 300, 0 \le x_i \le m$。

提示：可以把一个角度处理 $\sum |r_i - x_i|$，把它写成更易优化的形式；对正整数 x，__builtin_ctzll(x) 返回 x 的二进制表示末尾连续 0 的个数；__builtin_popcountll(x) 返回 x 的二进制表示中 1 的个数。

以下程序构造出一组满足要求的标准答案。请补全程序。

#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> x(n), c(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
        c[i] = /* ① */;
    }
    vector<string> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<int> s(n, -1);
    vector<ll> q(m, 0);
    ll C = 0, S = 0;
    for (int i = 0; i < n; i++) {
        C -= c[i];
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'A') q[j]--;
            else q[j]++;
        }
    }
    for (int j = 0; j < m; j++) S += abs(q[j]);
    ll ans = C + S;
    ull best = 0, lst = 0;
    for (ull mask = 1; mask < (1ULL << n); mask++) {
        ull g = /* ② */;
        ull d = g ^ lst;
        int k = /* ③ */;
        C -= /* ④ */;
        for (int j = 0; j < m; j++) {
            ll old = q[j];
            int v = (a[k][j] == 'A' ? 1 : -1);
            q[j] -= 2ll * s[k] * v;
            S += abs(q[j]) - abs(old);
        }
        s[k] = -s[k];
        if (C + S > ans) {
            ans = C + S;
            best = g;
        }
        lst = g;
    }
    for (int i = 0; i < n; i++) {
        if ((best >> i) & 1) s[i] = 1;
        else s[i] = -1;
    }
    string res(m, 'A');
    for (int j = 0; j < m; j++) {
        ll v = 0;
        for (int i = 0; i < n; i++) {
            if (a[i][j] == 'A') v += s[i];
            else v -= s[i];
        }
        if (/* ⑤ */) res[j] = 'A';
        else res[j] = 'B';
    }
    cout << res << endl;
    return 0;
}

39. [3 分] ① 处应填（ {{ select(39) }} ）

• 2 * x[i] - m
• -m + 2 * x[i] + 1
• m - 2 * x[i]
• m + 2 * x[i]

40. [3 分] ② 处应填（ {{ select(40) }} ）

• mask | (mask >> 1)
• mask ^ (mask >> 1)
• mask & (mask >> 1)
• mask ^ ((mask >> 1) + 1)

41. [3 分] ③ 处应填（ {{ select(41) }} ）

• __builtin_ctzll(d) + 1
• __builtin_popcountll(d)
• __builtin_ctzll(g)
• __builtin_ctzll(d)

42. [3 分] ④ 处应填（ {{ select(42) }} ）

• 2ll * s[k] * c[k]
• s[k] * c[k]
• 2ll * (s[k] - c[k])
• 2ll * c[k]

43. [3 分] ⑤ 处应填（ {{ select(43) }} ）

• v >= (n & 1)
• v > (n & 1)
• v + (n & 1) >= 0
• v * (n & 1) >= 0

---