---

1. 在NOI Linux中，使用 $\mathrm{g++}$ 编译 $\mathrm{C++}$ 程序时，如果要开启所有警告信息，应该使用选项（）。 {{ select(1) }}

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

---

2. 如果 $x$ 是正整数，则表达式 $(x \& (x-1)) == 0$ 成立当且仅当（）。 {{ select(2) }}

• x是偶数
• x是2的幂次
• x的二进制表示中没有相邻的1
• x等于1

---

3. 操作系统的主要功能不包括（）。 {{ select(3) }}

• 进程管理
• 内存管理
• 数据库管理
• 文件管理

---

4. 以下问题中，贪心算法不能得到最优解的是（）。 {{ select(4) }}

• 哈夫曼编码
• Dijkstra算法
• 0-1背包
• Prim算法

---

5. 采用长度为7的哈希表，哈希函数 $h(k) = k \% 7$，采用线性探查法解决冲突。依次插入关键字19，26，35，48，55，最后55存放在位置（）。 {{ select(5) }}

• 0
• 1
• 2
• 3

---

6. 以下关于欧拉图的叙述中，正确的是（）。 {{ select(6) }}

• 欧拉图必须包含欧拉回路
• 欧拉图一定不包含哈密顿回路
• 所有顶点度数为偶数的无向图一定是欧拉图
• 有且仅有两个奇度数顶点的连通无向图是欧拉图

---

7. 以下给定代码段的时间复杂度为（）。

for (int i = 1; i <= n; i *= 2) {
    for (int j = 1; j <= i; j++) {
        // O(1) 操作
    }
}

{{ select(7) }}

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

---

8. 定义函数 $f(n) = f(n-1) + 2f(n-2)$，其中 $f(0) = 1$，$f(1) = 3$，则 $f(4)$ 的值为（）。 {{ select(8) }}

• 11
• 17
• 21
• 25

---

9. 对长度为 $n$ 的有序数组进行二分查找，（ ）不是必须满足的条件。 {{ select(9) }}

• 数组元素必须连续存储
• 数组必须按关键字有序
• 必须能够随机访问元素
• 数组元素必须从小到大排好序

---

10. 在模 11 运算中，7 的乘法逆元是（ ）。 {{ select(10) }}

• 3
• 4
• 5
• 8

---

11. 在 $4 \times 5$ 的网格中，起点为左上角的格子，终点为右下角的格子，每次可以移动到右方、下方、右下方的格子，则总共有（ ）种不同的路径。 {{ select(11) }}

• 20
• 35
• 126
• 129

---

12. 一个无向图至少需要 3 种颜色对顶点着色（才能保证任何一条边的两端不同色），当且仅当该图（ ）。 {{ select(12) }}

• 是二分图
• 包含奇环
• 是完全图
• 顶点数至少为3

---

13. 在以下排序算法中，最坏情况下时间复杂度为 $O(n \log n)$ 且是稳定排序的是（ ）。 {{ select(13) }}

• 快速排序
• 堆排序
• 归并排序
• 希尔排序

---

14. 要交换两个整数 $a$ 和 $b$ 的值，不使用临时变量，最安全稳妥的办法是（ ）。 {{ select(14) }}

• $a = b - a; b = b - a; a = a + b;$
• $a = a \sim b; b = b \sim a; a = a \sim b;$
• $a = a * b; b = a / b; a = a / b;$
• $a = a + b; b = a - b; a = a - b;$

---

15. 已知哈夫曼树有5个叶节点，其权值分别为 1,3,5,7,9，该树的带权路径长度为（ ）。 {{ select(15) }}

• 50
• 54
• 60
• 65

---

阅读程序（1）：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i]; // 保证输入的都是正整数

    vector<vector<bool>> dp(k + 1, vector<bool>(m + 1, false));
    dp[0][0] = true;
    for (int idx = 0; idx < n; idx++) {
        int num = nums[idx];
        for (int i = k; i >= 1; i--) {
            for (int j = m; j >= num; j--) {
                if (dp[i - 1][j - num]) {
                    dp[i][j] = true;
                }
            }
        }
    }

    if (dp[k][m]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

16. 输入 5 10 3 1 2 3 4 5 时，输出结果为 Yes。 {{ select(16) }}

• 正确
• 错误

---

17. 如果 $m < k$，最终输出肯定是 No。 {{ select(17) }}

• 正确
• 错误

---

18. 将 for (int i = k; i >= 1; i--) 改为正序遍历，程序结果不变。 {{ select(18) }}

• 正确
• 错误

---

19. dp[i][j] 的状态定义正确的是（ ）。 {{ select(19) }}

• 使用前 i 个数，能否组成 j
• 使用不超过 i 个数，能否组成 j
• 使用恰好 i 个数，能否组成 j
• 使用最少 i 个数，能否组成 j

---

20. （4分）当 $n > 0$、$k = 0$ 且 $m = 0$ 时，下列说法中正确的是（ ）。 {{ select(20) }}

• 程序输出 Yes
• 程序输出 No
• 程序运行过程中会报错
• 程序无输出

---

阅读程序（2）：

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

ll fPow(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    ll n, p;
    cin >> n >> p;
    if (n >= p) {
        cout << 0 << endl;
        return 0;
    }
    ll res = p - 1;
    for (ll i = n + 1; i < p; i++)
        res = (res * fPow(i, p - 2, p)) % p;

    cout << res << endl;
    return 0;
}

21. 输入 $n = 1$，$p = 5$ 时，输出结果为 4。 {{ select(21) }}

• 正确
• 错误

---

22. 当 $p$ 是合数时，程序仍然能正常运行。 {{ select(22) }}

• 正确
• 错误

---

23. fPow(2, 10, 1000) 的返回值是 24。 {{ select(23) }}

• 正确
• 错误

---

24. 如果输入 $n = 0$，$p = 7$，程序的输出结果是（ ）。 {{ select(24) }}

• 0
• 1
• 6
• 7

---

25. （4分）如果 $p$ 是素数，程序的时间复杂度是（ ）。 {{ select(25) }}

• $O(p)$
• $O(p \log p)$
• $O(p^2)$
• $O(1)$

---

阅读程序（3）：

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if ((n & 1) == 0) return false;
    for (int i = 3; i * i <= n; i += 2)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int l, r;
    cin >> l >> r;
    int cnt = 0;

    for (int i = 1; i <= r; i++) {
        if (isPrime(i)) {
            int power2 = 1;
            while (power2 < i) power2 <<= 1;
            if ((power2 - i) <= 2 || (i - (power2 >> 1)) <= 2)
                cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

26. 对于任意大于2的素数，isPrime函数中的循环次数严格小于 $\lfloor \sqrt{n} / 2 \rfloor$。 {{ select(26) }}

• 正确
• 错误

---

27. 如果区间 $[l, r]$ 内没有素数，程序输出0。 {{ select(27) }}

• 正确
• 错误

---

28. 若输入 5 7，则程序输出0。 {{ select(28) }}

• 正确
• 错误

---

29. （4分）输入 5 31 时，程序的输出结果为（ ）。 {{ select(29) }}

• 2
• 3
• 4
• 5

---

30. （4分）该程序在最坏情况下的时间复杂度是（ ）。 {{ select(30) }}

• $O(r)$
• $O(r \sqrt{r})$
• $O(r^2)$
• $O(2^r)$

---

完善程序（1）：

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

ll exgcd(①) {
    if (②) {
        x = 1;
        y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, y, x);
    y = y - a / b * x;
    return g;
}

ll mod(ll a, ll b) {
    return (a % b + b) % b;
}

ll crt(vector<ll> &a, vector<ll> &m) {
    int n = a.size();
    ll a1 = a[0], m1 = m[0];

    for (int i = 1; i < n; i++) {
        ll a2 = a[i], m2 = m[i];
        ll x, y;
        ll g = exgcd(m1, m2, x, y);
        if (③) return -1;

        ll p, q;
        exgcd(m1 / g, m2 / g, p, q);

        ④;

        ll x_val = (a1 + m1 * (a2 - a1) / g * p) % lcm;
        a1 = mod(x_val, lcm);
        m1 = lcm;
    }
    return ⑤;
}

int main() {
    int n;
    cin >> n;
    vector<ll> a(n), m(n);
    for (int i = 0; i < n; i++) // 表示一个方程 x = a (mod m)
        cin >> a[i] >> m[i];
    ll res = crt(a, m);
    if (res == -1) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}

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

• int a, int b, int x, int y
• int a, int b, int &x, int &y
• ll a, ll b, ll x, ll y
• ll a, ll b, ll &x, ll &y

---

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

• a == 0
• b == 0
• x == 0
• y == 0

---

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

• a1 % g != 0
• a2 % g != 0
• a1 % g == a2 % g
• (a2 - a1) % g != 0

---

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

• ll lcm = m1 * m2;
• ll lcm = m1 / g * m2;
• ll lcm = g / m1 * m2;
• ll lcm = m1 * g / m2;

---

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

• a1
• m1
• -1
• lcm

---

完善程序（2）：

#include <bits/stdc++.h>
using namespace std;
const int N = 200009;

vector<int> to[N];
int L, n, q, p[N][20];
int tI[N], tO[N], timer;

void dfs(int u, int fa) {
    tI[u] = ++timer;
    p[u][0] = fa;
    for (int i = 1; i <= L; ++i) p[u][i] = ①;
    for (int i = 0; i < to[u].size(); ++i)
        if (to[u][i] != fa) dfs(to[u][i], u);
    tO[u] = ++timer;
}

bool up(int u, int v) {
    return ②;
}

int lca(int u, int v) {
    if (up(u, v)) return u;
    if (up(v, u)) return v;
    for (int i = L; i >= 0; --i)
        if (③) u = p[u][i];
    return ④;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        to[u].push_back(v);
        to[v].push_back(u);
    }
    L = 1;
    while (⑤) ++L;
    dfs(1, 0);

    cin >> q;
    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }
    return 0;
}

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

• p[p[u][i]][i-1]
• p[p[u][i-1]][i-1]
• p[p[fa][i]][i-1]
• p[p[fa][i-1]][i-1]

---

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

• u && tI[u] <= tI[v] && tO[v] <= tO[u]
• u || tI[u] <= tI[v] && tO[v] <= tO[u]
• u && tI[u] <= tI[v] && tO[v] <= tO[u]
• u || tI[u] <= tI[v] && tO[v] <= tO[u]

---

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

• up(p[u][i], v)
• up(p[u][i], v)
• up(u, p[v][i])
• up(u, p[v][i])

---

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

• u
• v
• p[u][0]
• p[v][0]

---

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

• (1 << L) <= n
• L <= n
• (1 << L) < n
• L < n

---