---

1. 在NOI Linux系统中，使用 $g++$ 编译 $\mathrm{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^2 m)$
• $O(nm^2)$
• $O(\log n)$

---

4. 已知某完全二叉树的层次遍历序列为 ACBGED，则其中序遍历序列是（）。 {{ 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(\mathrm{mod}3)$ ， $x \equiv 2(\mathrm{mod}5)$ 的解为（）。 {{ select(10) }}

• $x \equiv 7(\mathrm{mod}15)$
• $x \equiv 8(\mathrm{mod}15)$
• $x \equiv 11(\mathrm{mod}15)$
• $x \equiv 13(\mathrm{mod}15)$

---

11. 下列几种排序算法中, 在平均情况下, ( ) 的时间复杂度与其他三种不同。 {{ select(11) }}

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

---

12. 假设有 5 名同学, $i$ 号同学的座位为 $i$ 号课桌。考试时为了防止作弊, 每个同学不能坐在自己的位置上, 则考试时 5 名同学共有 ( ) 种坐法。 {{ select(12) }}

• 36
• 44
• 48
• 120

---

13. 哈希表长度为 13, 哈希函数 $H(key) = key\% 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

---

阅读程序（1）：

#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

---

阅读程序（2）：

#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. （4分）输入2026时，输出为（）。 {{ select(24) }}

• 1016
• 2026
• 3041
• 3042

---

25. （4分）init()函数的时间复杂度是（）。 {{ select(25) }}

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

---

阅读程序（3）：

#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. （4分）输入的两个数分别为a和m,则程序的时间复杂度是( )。 {{ select(29) }}

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

---

30. （4分）如果 inverse() 函数是求a模m的逆元,下列说法中正确的是( )。 {{ select(30) }}

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

---

完善程序（1）：

#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] = u;
• euler[++timer] = fa;

---

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

---

完善程序（2）：

#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)

---