GESP 202606 C++ 八级

一、 单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. [2 分] 从 7 本不同的算法书和 5 本不同的数学书中选出 4 本，要求两类书都至少选 1 本，共有（ ）种不同选法。 （ {{ select(1) }} ）

• 420
• 455
• 465
• 495

2. [2 分] 6 个人排成一排照相，其中甲、乙两人不能相邻，共有（ ）种不同排法。 （ {{ select(2) }} ）

• 240
• 480
• 600
• 720

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

• 6
• 12
• 15
• 20

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

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) }} ）

• c[i - 1][j - 1] + c[i - 1][j]
• c[i][j - 1] + c[i][j + 1]
• c[i - 1][j] + c[i][j + 1]
• c[i][j - 1] * c[i - 1][j]

5. [2 分] 下列程序输出的值为（ ）。

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

• 1
• 4
• 13
• 16

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

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

7. [2 分] 在平面直角坐标系中，三角形三个顶点为 $(1, 1)$、$(5, 2)$、$(3, 6)$，该三角形面积为（ ）。 （ {{ select(7) }} ）

• 9
• 10
• 12
• 18

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

• x * x + y * y <= 25
• abs(x) + abs(y) <= 5
• x * x - y * y <= 25
• x + y <= 5

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

• 7
• 8
• 9
• 10

10. [2 分] 有向非负权图边为 $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) }} ）

• 6
• 7
• 8
• 11

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

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

（ {{ select(11) }} ）

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

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

• $O(nM)$
• $O(n \log M)$
• $O(M \log n)$
• $O(n + M)$

13. [2 分] 下列线性筛的代码片段中，当枚举到质数 $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) }} ）

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

14. [2 分] 在 C++ 中，关于类的继承和构造、析构顺序，下列说法正确的是（ ）。 （ {{ select(14) }} ）

• 派生类可以直接访问基类的 private 成员。
• 基类的 protected 成员在私有继承后会变成派生类的 public 成员。
• 创建派生类对象时，会先调用基类构造函数，再调用派生类构造函数。
• 销毁派生类对象时，会先调用基类析构函数，再调用派生类析构函数。

15. [2 分] 将 4 个元素按 1, 2, 3, 4 的顺序入栈，在该过程中可随时插入出栈操作。下列序列中不可能作为出栈序列的是（ ）。 （ {{ select(15) }} ）

• 1, 2, 3, 4
• 2, 1, 4, 3
• 3, 2, 1, 4
• 3, 1, 2, 4

---

二、 判断题（每题 2 分，共 20 分）

16. [2 分] 若一项任务可从两种互斥的方案中选择一种完成，其中，方案 A 有 $m$ 种做法，方案 B 有 $n$ 种做法，则总做法数为 $m+n$。 （ {{ select(16) }} ）

• 正确
• 错误

17. [2 分] 将 $n$ 个不同元素围成一圈，若只把旋转视为同一种排法、翻转仍视为不同排法，则方案数为 $(n-1)!$。 （ {{ select(17) }} ）

• 正确
• 错误

18. [2 分] 从 $n$ 个不同元素中可重复地选取 $k$ 个且不考虑顺序，方案数为 $C(n+k, k)$。 （ {{ select(18) }} ）

• 正确
• 错误

19. [2 分] 杨辉三角中的组合数满足 $C(n, k) = C(n-1, k) + C(n-2, k)$。 （ {{ select(19) }} ）

• 正确
• 错误

20. [2 分] 快速幂通过二进制拆分指数，可以在 $O(\log b)$ 时间内计算 $a^b \mod m$。 （ {{ select(20) }} ）

• 正确
• 错误

21. [2 分] 只要图中不存在负权环，Dijkstra 算法就一定能正确处理带负权边的图。 （ {{ select(21) }} ）

• 正确
• 错误

22. [2 分] 若一张连通无向图所有边权两两不同，则它的最小生成树一定唯一。 （ {{ select(22) }} ）

• 正确
• 错误

23. [2 分] 判断点 $(x, y)$ 是否在以原点为圆心、半径为 $r$ 的圆内或圆上时，可以比较 $x^2 + y^2$ 与 $r^2$，不必先开平方。 （ {{ select(23) }} ）

• 正确
• 错误

24. [2 分] 若能写出判定函数 check(x)，表示“答案为 x 时是否可行”，即使 check(x) 不满足单调性，也一定可以使用二分答案求最优解。 （ {{ select(24) }} ）

• 正确
• 错误

25. [2 分] 归并排序是一种稳定排序算法，常见实现的时间复杂度为 $O(n \log n)$。 （ {{ select(25) }} ）

• 正确
• 错误