GESP 客观题评测系统

2026-06-Level-8

试卷解析总览，可直接查看每题答案与解析。

单选题

第 1 题（单选题，2 分）

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

420

455

465

495

正确答案B

解析详情

【答案】B

【考点】组合计数与容斥

【解析】不加限制选 4 本有 `C(12,4)=495` 种。减去全选算法书的 `C(7,4)=35` 种和全选数学书的 `C(5,4)=5` 种，得到 `495-35-5=455`。

【易错点】 “两类都至少一本”可用容斥，不能只固定成 2 本加 2 本。

第 2 题（单选题，2 分）

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

240

480

600

720

正确答案B

解析详情

【答案】B

【考点】排列与捆绑法

【解析】 6 人任意排列有 `6!=720` 种。甲乙相邻时把二人视为一块，块内有 2 种顺序，共 `2×5!=240` 种，因此不相邻为 `720-240=480`。

【易错点】相邻情形中甲乙内部的两种次序不能漏算。

第 3 题（单选题，2 分）

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

正确答案C

解析详情

【答案】C

【考点】二项式展开

【解析】取 k 个 `-1/x` 时，x 的指数为 `2(6-k)-k=12-3k`。常数项要求指数为 0，得 k=4；系数为 `C(6,4)(-1)^4=15`。

【易错点】既要令指数为 0，也要计入负号的 k 次幂。

第 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] = __________;
}

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

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

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

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

正确答案A

解析详情

【答案】A

【考点】杨辉三角递推

【解析】组合数满足帕斯卡恒等式 `C(i,j)=C(i-1,j-1)+C(i-1,j)`，边界 `C(i,0)=C(i,i)=1`，所以横线应填选项 A。

【易错点】两个来源都在上一行，不能混入本行尚未完成的状态。

第 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;
}

正确答案C

解析详情

【答案】C

【考点】快速幂与模运算

【解析】模 17 下 `3^4=81≡13`，`3^8≡13^2≡16`，`3^16≡16^2≡1`，故 `3^20≡3^16·3^4≡13`。程序输出 13。

【易错点】每次乘法和平方后都要取模，不能先计算完整的巨大幂。

第 6 题（单选题，2 分）

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

O(n)

O(n^2)

O(\log n)

O(n \log n)

正确答案D

解析详情

【答案】D

【考点】归并排序复杂度

【解析】归并排序满足递推 `T(n)=2T(n/2)+O(n)`：递归树有 `O(log n)` 层，每层合并总工作量为 `O(n)`，所以总复杂度为 `O(n log n)`。

【易错点】分治层数是对数级，但每层并非只做常数工作。

第 7 题（单选题，2 分）

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

正确答案A

解析详情

【答案】A

【考点】坐标几何与叉积

【解析】向量 `AB=(4,1)`，`AC=(2,5)`，叉积绝对值为 `|4×5-1×2|=18`。三角形面积为叉积绝对值的一半，即 9。

【易错点】叉积得到的是平行四边形面积，三角形还需除以 2。

第 8 题（单选题，2 分）

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

x * x + y * y <= 25

abs(x) + abs(y) <= 5

x * x - y * y <= 25

x + y <= 5

正确答案A

解析详情

【答案】A

【考点】点与圆的位置关系

【解析】点到原点距离平方为 `x²+y²`。在半径 5 的圆内或圆上等价于距离不超过 5，即 `x²+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) 。该图最小生成树的总权值为（）。

正确答案D

解析详情

【答案】D

【考点】最小生成树

【解析】按 Kruskal 选边：先选权 1 的 (2,3)，再选权 2 的 (1,3) 和 (4,5)；权 4 的 (1,2) 会成环而跳过，最后选权 5 的 (2,4)。总权为 `1+2+2+5=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 号顶点的最短距离为（）。

正确答案A

解析详情

【答案】A

【考点】Dijkstra 最短路

【解析】从 1 出发，先得 `d2=3,d3=10`；由 2 松弛得 `d3=5,d4=7`；再由 3 松弛得 `d4=6`。因此到 4 的最短距离为 6。

【易错点】不能只比较题目中直接列出的两段路径，还要允许经 2、3 连续松弛。

第 11 题（单选题，2 分）

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

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

O(n)

O(n \log n)

O(n \sqrt{n})

O(n^2)

正确答案C

解析详情

【答案】C

【考点】循环复杂度

【解析】外层循环执行 n 次；内层条件 `j*j≤n`，所以 j 最大约为 `√n`，每次外层执行 `O(√n)` 次。总复杂度为 `O(n√n)`。

【易错点】看到两层循环不能直接判为 `O(n²)`，要根据内层终止条件计算次数。

第 12 题（单选题，2 分）

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

O(nM)

O(n log M)

O(M log n)

O(n + M)

正确答案B

解析详情

【答案】B

【考点】二分答案复杂度

【解析】答案区间 `[1,M]` 每次二分缩小一半，需要 `O(log M)` 次判定；每次 `check` 为 `O(n)`，故总复杂度为 `O(n log M)`。

【易错点】二分的对数取决于答案值域 M，不是数据规模 n。

第 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;  // 这条语句的目的是？
    }
}

保证递归深度不超过

O(\log n)

。

保证每个合数只被它的最小质因子筛去一次。

保证每个素数都被标记为合数。

把筛法时间复杂度提高到

O(n\log n)

。

正确答案B

解析详情

【答案】B

【考点】线性筛

【解析】当 `p` 是 i 的最小质因子且 `i%p==0` 后继续枚举更大质数，会让同一合数被重复标记。此处 `break` 保证每个合数只由其最小质因子对应的组合筛去一次，从而达到线性复杂度。

【易错点】 `break` 不是为了漏掉后续合数，而是消除重复标记。

第 14 题（单选题，2 分）

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

派生类可以直接访问基类的 private 成员。

基类的 protected 成员在私有继承后会变成派生类的 public 成员。

创建派生类对象时，会先调用基类构造函数，再调用派生类构造函数。

销毁派生类对象时，会先调用基类析构函数，再调用派生类析构函数。

正确答案C

解析详情

【答案】C

【考点】继承的构造与析构顺序

【解析】创建派生类对象时必须先把基类部分构造完成，因此先调用基类构造函数，再调用派生类构造函数。销毁时顺序相反，先派生类析构，再基类析构。

【易错点】派生类不能直接访问基类 `private` 成员；继承方式也不会把 `protected` 提升为 `public`。

第 15 题（单选题，2 分）

将4个元素按1,2,3,4的顺序入栈，在该过程中可随时插入出栈操作。下列序列中不可能作为出栈序列的是（）。

1, 2, 3, 4

2, 1, 4, 3

3, 2, 1, 4

3, 1, 2, 4

正确答案D

解析详情

【答案】D

【考点】栈的合法出栈序列

【解析】要先弹出 3，必须先把 1、2、3 依次入栈，此时栈顶向下为 3、2、1。弹出 3 后，下一个只能是 2，不可能直接弹出 1，因此 `3,1,2,4` 不合法。

【易错点】栈遵循后进先出；被压在 2 下方的 1 不能越过 2 出栈。

判断题

第 1 题（判断题，2 分）

若一项任务可从两种互斥的方案中选择一种完成，其中，方案A有m种做法，方案B有n种做法，则总做法数为 m+n 。

正确答案正确

解析详情

【答案】正确

【考点】加法原理

【解析】两种方案互斥，完成任务时只能选择其中一种。方案 A 的 m 种做法与方案 B 的 n 种做法没有重叠，因此总数为 `m+n`。

【易错点】只有互斥分类才能直接相加；若方案有重叠需扣除重复部分。

第 2 题（判断题，2 分）

将 n 个不同元素围成一圈，若只把旋转视为同一种排法、翻转仍视为不同排法，则方案数为 (n-1)! 。

正确答案正确

解析详情

【答案】正确

【考点】圆排列

【解析】 n 个不同元素的线排列有 `n!` 种。圆排列中同一排列的 n 次旋转视为相同，故除以 n 得 `(n-1)!`；题目不把翻转视为相同，所以无需再除以 2。

【易错点】是否把镜像翻转视为同一种排列会影响是否需要再除以 2。

第 3 题（判断题，2 分）

从 n 个不同元素中可重复地选取 k 个且不考虑顺序，方案数为 C(n+k,k) 。

正确答案错误

解析详情

【答案】错误

【考点】可重复组合

【解析】从 n 种元素中可重复选 k 个且不计顺序，用隔板法得到 `C(n+k-1,k)`。题目写成 `C(n+k,k)`，上参数多了 1。

【易错点】可重复组合公式与从 n+k 个元素直接选 k 个不同元素的组合不同。

第 4 题（判断题，2 分）

杨辉三角中的组合数满足 C(n,k)=C(n-1,k)+C(n-2,k) 。

正确答案错误

解析详情

【答案】错误

【考点】帕斯卡恒等式

【解析】正确递推是 `C(n,k)=C(n-1,k-1)+C(n-1,k)`，表示按某个特定元素是否被选分类。题目第二项错误地写成了 `C(n-2,k)`。

【易错点】两个递推项的上参数都应是 n-1，下参数分别为 k-1 和 k。

第 5 题（判断题，2 分）

快速幂通过二进制拆分指数，可以在 $O(\log b)$ 时间内计算 $a^b \bmod m$ 。

正确答案正确

解析详情

【答案】正确

【考点】快速幂

【解析】快速幂把指数 b 按二进制位处理，每轮令 b 右移一位并把底数平方。循环轮数等于 b 的二进制位数，为 `O(log b)`。

【易错点】复杂度按乘法次数计算；大整数乘法本身的成本另需视数据范围而定。

第 6 题（判断题，2 分）

只要图中不存在负权环，Dijkstra 算法就一定能正确处理带负权边的图。

正确答案错误

解析详情

【答案】错误

【考点】Dijkstra 适用条件

【解析】 Dijkstra 在确定当前最短顶点后不会重新推翻该结果，依赖所有边权非负。即使没有负权环，只要存在负边，也可能在顶点确定后出现更短路径，应使用 Bellman-Ford 等算法。

【易错点】 “没有负环”保证最短路有定义，但不等于 Dijkstra 可以正确求解。

第 7 题（判断题，2 分）

若一张连通无向图所有边权两两不同，则它的最小生成树一定唯一。

正确答案正确

解析详情

【答案】正确

【考点】最小生成树唯一性

【解析】若所有边权互不相同，对任意割，跨越该割的最轻边都是唯一的，按割性质它必须属于最小生成树。因此各步选择被唯一确定，最小生成树唯一。

【易错点】边权存在相同值时仍可能唯一，但不能再仅凭“两两不同”的充分条件反推。

第 8 题（判断题，2 分）

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

正确答案正确

解析详情

【答案】正确

【考点】点与圆的判定

【解析】点到原点的距离为 `√(x²+y²)`。由于两边均非负，比较距离与 r 等价于比较平方，即判断 `x²+y²≤r²`，可避免开平方。

【易错点】使用平方比较时要选择足够宽的数值类型，防止 `x*x` 或 `r*r` 溢出。

第 9 题（判断题，2 分）

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

正确答案错误

解析详情

【答案】错误

【考点】二分答案的单调性

【解析】二分答案要求可行性随 x 呈单调变化，例如从某个位置起全部可行。若 `check(x)` 真、假交替，舍弃一半区间时可能把最优解一起丢掉，不能保证正确。

【易错点】能写判定函数只是第一步，还必须证明判定结果在答案域上单调。

第 10 题（判断题，2 分）

归并排序是一种稳定排序算法，常见实现的时间复杂度为 $O(n\log n)$ 。

正确答案正确

解析详情

【答案】正确

【考点】归并排序

【解析】归并时若相等元素优先取左半部分，就能保持其原相对顺序，因此归并排序稳定。递归有 `O(log n)` 层，每层合并 `O(n)`，总时间为 `O(n log n)`。

【易错点】稳定性取决于合并时相等元素的处理顺序，不能在相等时随意优先取右侧。