1. 从7本不同的算法书和5本不同的数学书中选出4本，要求两类书都至少选1本，共有（ ）种不同选法。

{{ select(1) }}

• A. 420
• B. 455
• C. 465
• D. 495

2. 6个人排成一排照相，其中甲、乙两人不能相邻，共有（ ）种不同排法。

{{ select(2) }}

• A. 240
• B. 480
• C. 600
• D. 720

3. 展开式 $(x^2 - \frac{1}{x})^6$ 中，常数项的系数为（ ）。

{{ select(3) }}

• A. 6
• B. 12
• C. 15
• D. 20

4. 下面代码用于预处理组合数，横线处应填入的是（ ）。

for (int i = 0; i <= n; i++) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j < i; j++)
        c[i][j] = __________;
}

{{ select(4) }}

• A. c[i - 1][j - 1] + c[i - 1][j]
• B. c[i][j - 1] + c[i - 1][j - 1]
• C. c[i - 1][j] + c[i][j + 1]
• D. c[i][j - 1] * c[i - 1][j]

5. 下列程序输出的值为（ ）。

#include <iostream>
using namespace std;
long long qpow(long long a, long long b, long long mod) {
    long long ans = 1 % mod;
    while (b) {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main() {
    cout << qpow(3, 20, 17) << endl;
    return 0;
}

{{ select(5) }}

• A. 1
• B. 4
• C. 13
• D. 16

6. 归并排序每次把长度为 $n$ 的序列分成两个规模约为 $n/2$ 的子序列，递归排序后再用线性时间合并。该算法的时间复杂度通常为（ ）。

{{ select(6) }}

• A. $O(n)$
• B. $O(n^2)$
• C. $O(\log n)$
• D. $O(n \log n)$

7. 在平面直角坐标系中，三角形三个顶点为 $A(1,1)$、$B(5,2)$、$C(3,6)$，该三角形面积为（ ）。

{{ select(7) }}

• A. 9
• B. 10
• C. 12
• D. 18

8. 某程序需要判断点 $P(x, y)$ 是否在以原点为圆心、半径为5的圆内或圆上。下列判断条件正确的是（ ）。

{{ select(8) }}

• A. x * x + y * y <= 25
• B. abs(x) + abs(y) <= 5
• C. x * x - y * y <= 25
• D. x + y <= 5

9. 某无向带权图有边 $(1,2,4)$、$(1,3,2)$、$(2,3,1)$、$(2,4,5)$、$(3,4,8)$、$(3,5,10)$、$(4,5,2)$。该图最小生成树的总权值为（ ）。

{{ select(9) }}

• A. 7
• B. 8
• C. 9
• D. 10

10. 有向非负权图边为 $1 \to 2(3)$，$2 \to 4(4)$，$1 \to 3(10)$，$3 \to 4(1)$，$2 \to 3(2)$，使用 Dijkstra 算法从 1 号顶点出发到 4 号顶点的最短距离为（ ）。

{{ select(10) }}

• A. 6
• B. 7
• C. 8
• D. 11

11. 下列代码片段的时间复杂度为（ ）。

long long s = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j * j <= n; j++) {
        s += i + j;
    }
}

{{ select(11) }}

• A. $O(n)$
• B. $O(n \log n)$
• C. $O(n\sqrt{n})$
• D. $O(n^2)$

12. 某优化问题的答案是 $[1, M]$ 内的整数，存在单调判定函数 check(x)，且每次判定的时间复杂度为 $O(n)$。使用二分答案求最小可行值，整体时间复杂度通常为（ ）。

{{ select(12) }}

• A. $O(nM)$
• B. $O(n \log M)$
• C. $O(M \log n)$
• D. $O(n + M)$

13. 下列线性筛的代码片段中，当找到质数 p 且 i % p == 0 时，使用 break; 语句停止继续枚举。这样做的主要目的是（ ）。

for (int i = 2; i <= n; ++i) {
    if (!is_composite[i])
        primes.push_back(i);
    for (int p : primes) {
        if (i * p > n)
            break;
        is_composite[i * p] = true;
        if (i % p == 0)
            break;            // 这条语句的目的是?
    }
}

{{ select(13) }}

• A. 保证递归深度不超过 $O(\log n)$。
• B. 保证每个合数只被它的最小质因子筛去一次。
• C. 保证每个素数都被标记为合数。
• D. 把筛法时间复杂度提高到 $O(n \log n)$。

14. 在 C++ 中，关于类的继承和构造、析构顺序，下列说法正确的是（ ）。

{{ select(14) }}

• A. 派生类可以直接访问基类的 private 成员。
• B. 基类的 protected 成员，在公有继承后仍为 public 成员。
• C. 派生类可以直接访问基类继承而来的 public 成员。
• D. 构造派生类对象时，会先调用派生类构造函数，再调用基类构造函数。

15. 将 4 个元素 1, 2, 3, 4 依次入栈，只允许在出栈后立即输出。下列哪个不可能是合法的出栈序列（ ）。

{{ select(15) }}

• A. 1, 2, 3, 4
• B. 2, 1, 4, 3
• C. 3, 1, 2, 4
• D. 4, 3, 2, 1