一、单项选择题

1. 在 NOI Linux 系统中，使用 g++ 编译 C++ 程序时，如果要生成可调试的可执行文件，应该使用选项（普通选择题）

{{ select(1) }}

• -O2
• -g
• -static
• -Wall

2. 执行 int x = 0xAB; cout << (x >> 4 | (x & 0x0F) << 4);，输出为（普通选择题）

{{ select(2) }}

• 186
• 171
• 180
• 176

3. 连接 n 个字符串，每个字符串的长度不大于 m，选择不同的实现方法会导致时间复杂度不一样。最坏情况下，该操作的时间复杂度是（普通选择题）

{{ select(3) }}

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

4. 已知某完全二叉树的层次遍历序列为 ACBGFED，则其中序遍历序列是（普通选择题）

{{ select(4) }}

• DBEAFCG
• ABDCEFG
• GCFAEBD
• GCFAEDB

5. 用两个栈模拟队列，如果 push 操作总是入栈 $S_1$，那么 pop 操作是（普通选择题）

{{ select(5) }}

• 直接弹出 $S_1$ 栈顶
• 直接弹出 $S_2$ 栈顶
• 将 $S_2$ 全部弹出并压入 $S_1$，然后弹出 $S_1$ 栈顶
• 如果 $S_2$ 为空，将 $S_1$ 全部弹出并压入 $S_2$，然后弹出 $S_2$ 栈顶

6. 关于树的重心，下列说法中不正确的是（普通选择题）

{{ select(6) }}

• 树至少有一个重心
• 树最多有两个重心，且这两个重心一定相邻
• 树最多有两个重心，且这两个重心可以不相邻
• 重心到其他点的距离之和最小

7. 给定数字 0、1、5、6、7、9，每个数字最多用一次，可能组成多少个正偶数（普通选择题）

{{ select(7) }}

• 216
• 480
• 586
• 589

8. 最长公共子序列（LCS）的应用不包括（普通选择题）

{{ select(8) }}

• 文件差异比较
• DNA 序列比对
• 拼写检查
• 数据加密

9. 给一个无向图着色，相邻节点不能同色，如果至少需要 3 种颜色，则该图（普通选择题）

{{ select(9) }}

• 一定是二分图
• 一定包含奇环
• 一定是完全图
• 一定是连通图

10. 同余方程组 $x \equiv 1 \pmod 3$，$x \equiv 2 \pmod 5$ 的解为（普通选择题）

{{ select(10) }}

• $x \equiv 7 \pmod {15}$
• $x \equiv 8 \pmod {15}$
• $x \equiv 11 \pmod {15}$
• $x \equiv 13 \pmod {15}$

11. 下列几种排序算法中，在平均情况下，哪一种的时间复杂度与其他三种不同（普通选择题）

{{ select(11) }}

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

12. 假设有 5 名同学，i 号同学的座位为 i 号课桌。考试时为了防止作弊，每个同学不能坐在自己的位置上，则考试时 5 名同学共有多少种坐法（普通选择题）

{{ select(12) }}

• 36
• 44
• 48
• 120

13. 哈希表长度为 13，哈希函数 $H(key)=key\bmod 13$，采用线性探查法解决问题。已依次插入关键码 {26,39,52,65,78,91,104,117}。现要查找关键码 91，需要探查的桶的下标依次是（包括第一次计算哈希地址）（普通选择题）

{{ select(13) }}

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

14. 以下代码执行后，输出的结果是（普通选择题）

int a = 0, b = 1;
for (int i = 1; i <= 6; i++) {
    if (i % 2 == 1) {
        a = a + b;
    } else {
        b = a + b;
    }
}
cout << a << " " << b << endl;

{{ select(14) }}

• 5 8
• 8 13
• 13 21
• 21 34

15. 抛掷一枚均匀骰子，直到出现 2 次 6 为止，期望的抛掷次数是（普通选择题）

{{ select(15) }}

• 6
• 12
• 24
• 48

二、阅读程序

阅读下列程序，回答第 16 到 20 题。

#include <iostream>
using namespace std;

int main() {
    int n, p;
    cin >> n >> p; // 保证 n 为正整数，p 为素数，cur 不会溢出 long long 类型
    int ans = 0;
    long long cur = p;
    while (cur <= n) {
        ans += n / cur;
        cur *= p;
    }
    cout << ans << endl;
    return 0;
}

16. 输入 10 2 时，程序输出为 8（判断题）

{{ select(16) }}

• 正确
• 错误

17. 输出一定是正整数（判断题）

{{ select(17) }}

• 正确
• 错误

18. 程序的时间复杂度为 $O(\log_p n)$（判断题）

{{ select(18) }}

• 正确
• 错误

19. 如果希望从低位到高位依次输出 n 在 p 进制下的各位，ans += n / cur; 这句应该改为（阅读程序题）

{{ select(19) }}

• cout << n / cur << endl;
• cout << n % cur << endl;
• cout << n / cur % p << endl;
• cout << n * p / cur % p << endl;

20. 输入 n=100, p=5 时，程序输出为（阅读程序题）

{{ select(20) }}

• 20
• 24
• 25
• 100

阅读下列程序，回答第 21 到 25 题。

#include <iostream>
using namespace std;

const int N = 100009;
int prime[N], tot, sd[N], sp[N];
bool vis[N];

void init() {
    sd[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!vis[i]) {
            prime[++tot] = i;
            sd[i] = i + 1;
            sp[i] = i + 1;
        }
        for (int j = 1; j <= tot && i * prime[j] < N; j++) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                sp[i * prime[j]] = sp[i] * prime[j] + 1;
                sd[i * prime[j]] = sd[i] / sp[i] * sp[i * prime[j]];
                break;
            } else {
                sp[i * prime[j]] = prime[j] + 1;
                sd[i * prime[j]] = sd[i] * sd[prime[j]];
            }
        }
    }
}

int main() {
    init();
    int n;
    cin >> n;
    cout << sd[n] << endl;
    return 0;
}

21. 输入 7，则输出是 8（判断题）

{{ select(21) }}

• 正确
• 错误

22. init() 函数使用线性筛法标记素数，vis[i] 为 1 时，表示 i 是素数（判断题）

{{ select(22) }}

• 正确
• 错误

23. init() 函数预计算区间 [1,N-1] 内每一个整数的所有素因数之和，并用数组 sd 记录（判断题）

{{ select(23) }}

• 正确
• 错误

24. 输入 2026 时，输出为（阅读程序题）

{{ select(24) }}

• 1016
• 2026
• 3041
• 3042

25. init() 函数的时间复杂度是（阅读程序题）

{{ select(25) }}

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

阅读下列程序，回答第 26 到 30 题。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T, a, m, ans;

ll quickpow(ll a, ll b) {
    if (b < 0) return 0;
    ll ret = 1;
    a %= m;
    while (b) {
        if (b & 1) ret = (ret * a) % m;
        b >>= 1;
        a = (a * a) % m;
    }
    return ret;
}

ll inverse(ll a, ll m) {
    return quickpow(a, m - 2);
}

int main() {
    cin >> a >> m;
    ans = inverse(a, m);
    cout << ans << " ";
    return 0;
}

26. 输入 a=3, m=7，输出是 5（判断题）

{{ select(26) }}

• 正确
• 错误

27. 输入 a=4, m=6，输出是 4（判断题）

{{ select(27) }}

• 正确
• 错误

28. 输入 m=2，无论 a 为何值，输出都是 1（判断题）

{{ select(28) }}

• 正确
• 错误

29. 输入的两个数分别为 a 和 m，则程序的时间复杂度是（阅读程序题）

{{ select(29) }}

• $O(a)$
• $O(m)$
• $O(\log a)$
• $O(\log m)$

30. 如果 inverse() 函数是求 a 模 m 的逆元，下列说法中正确的是（阅读程序题）

{{ select(30) }}

• 它使用扩展欧几里得算法求逆元
• 它要求 a 和 m 必须互素，否则程序会异常退出
• 它使用费马小定理，要求 m 必须是素数
• 它适用于任意正整数 m

三、完善程序

阅读下列程序，回答第 31 到 35 题。

#include <bits/stdc++.h>
using namespace std;
const int N = 1009;
vector<int> to[N];
int n, timer, euler[①];

void dfs(int u, int fa) {
    ++timer;
    ②
    for (int i = 0; i < to[u].size(); ++i)
        if (to[u][i] != fa) dfs(to[u][i], u);
    ③
}

int main() {
    cin >> n; // 保证输入的 1 <= u,v <= n <= 1000，且无环
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        to[u].push_back(v);
        to[v].push_back(u);
    }

    for (int u = 1; u <= n; ++u)
        ④

    dfs(1, 0);
    for (int i = 1; ⑤; ++i) cout << euler[i] << " ";
    cout << euler[2 * n - 1] << endl;
    return 0;
}

31. ① 处应填（完善程序题）

{{ select(31) }}

• N - 1
• N
• N + 1
• N + N

32. ② 处应填（完善程序题）

{{ select(32) }}

• euler[timer] = u;
• euler[timer++] = u;
• euler[++timer] = u;
• euler[timer] = fa;

33. ③ 处应填（完善程序题）

{{ select(33) }}

• euler[timer] = u;
• euler[timer] = fa;
• euler[++timer] = fa;
• euler[++timer] = u;

34. ④ 处应填（完善程序题）

{{ select(34) }}

• sort(to, to + n);
• sort(to[u], to[u] + n);
• sort(to[u].begin(), to[u].begin() + to[u].size() - 1);
• sort(to[u].begin(), to[u].end());

35. ⑤ 处应填（完善程序题）

{{ select(35) }}

• i < n - 1
• i <= n - 1
• i < 2 * n - 1
• i <= 2 * n - 1

阅读下列程序，回答第 36 到 40 题。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > dst(n + 1, vector<int>(n + 1, INT_MAX));
    vector<int> deg(n + 1, 0);
    ll total = 0;
    for (int i = 1; i <= n; ++i) dst[i][i] = 0;

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        if (①) {
            dst[u][v] = w;
            dst[v][u] = w;
        }
        deg[u]++;
        deg[v]++;
        total += w;
    }

    // Floyd-Warshall 算法：计算所有顶点对的最短路径
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            if (dst[i][k] == INT_MAX) continue;
            for (int j = 1; j <= n; ++j) {
                if (dst[k][j] == INT_MAX) continue;
                if (②)
                    dst[i][j] = dst[i][k] + dst[k][j];
            }
        }
    }

    vector<int> odd;
    for (int i = 1; i <= n; ++i)
        if (deg[i] % 2 == 1) odd.push_back(i);
    if (③) {
        cout << total << endl;
        return 0;
    }

    int k = odd.size();
    vector<long long> dp(1 << k, LLONG_MAX); // dp 数组用于状态压缩 DP，大小为 2^k，初始化为极大值
    dp[0] = 0;

    // 枚举所有匹配状态（用二进制位表示顶点是否已匹配）
    for (int mask = 0; mask < (1 << k); ++mask) {
        if (dp[mask] == LLONG_MAX) continue;

        // 找到第一个未匹配的顶点（二进制位中 0 表示未匹配）
        int i = 0;
        while (④) i++;
        if (i >= k) continue;

        // 尝试将顶点 i 与另一个未匹配的顶点 j 配对
        for (int j = i + 1; j < k; ++j) {
            if (mask & (1 << j)) continue;
            if (dst[odd[i]][odd[j]] == INT_MAX) continue;

            // 新状态：将 i 和 j 标记为已匹配
            int new_mask = ⑤;
            ll new_val = dp[mask] + dst[odd[i]][odd[j]];
            if (new_val < dp[new_mask]) dp[new_mask] = new_val;
        }
    }

    ll ans = total + dp[(1 << k) - 1];
    cout << ans << endl;
    return 0;
}

36. ① 处应填（完善程序题）

{{ select(36) }}

• w < dst[u][v]
• w <= dst[u][v]
• w > dst[u][v]
• w >= dst[u][v]

37. ② 处应填（完善程序题）

{{ select(37) }}

• dst[i][j] < dst[i][k] + dst[k][j]
• dst[i][j] <= dst[i][k] + dst[k][j]
• dst[i][j] > dst[i][k] + dst[k][j]
• dst[i][j] >= dst[i][k] + dst[k][j]

38. ③ 处应填（完善程序题）

{{ select(38) }}

• odd.empty()
• !odd.empty()
• odd.size()%2==0
• odd.size()%2==1

39. ④ 处应填（完善程序题）

{{ select(39) }}

• i < k && (mask | (1 << i))
• i <= k && (mask | (1 << i))
• i < k && (mask & (1 << i))
• i <= k && (mask & (1 << i))

40. ⑤ 处应填（完善程序题）

{{ select(40) }}

• (1 << i) | (1 << j)
• mask | (1 << i)
• mask | (1 << j)
• mask | (1 << i) | (1 << j)