GESP 客观题评测系统

2024-03-Level-8

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

单选题

第 1 题（单选题，2 分）

为丰富食堂菜谱，炒菜部进行头脑风暴。肉类有鸡肉、牛肉、羊肉、猪肉4种，切法有肉排、肉块、肉末3种，配菜有圆白菜、油菜、豆腐3种，辣度有麻辣、微辣、不辣3种。不考虑口感的情况下，选1种肉、1种切法、1种配菜、1种辣度产生一道菜（例如：麻辣牛肉片炒豆腐），这样能产生多少道菜？（）。

108

正确答案D

解析详情

【答案】D

【考点】乘法原理

【解析】 4种肉、3种切法、3种配菜、3种辣度彼此独立，总数为 4×3×3×3=108。因此应选 D。

【易错点】这类题用乘法原理，不要把四个维度相加。

第 2 题（单选题，2 分）

已知袋中有2个相同的红球、3个相同的绿球、5个相同的黄球。每次取出一个不放回，全部取出。可能产生多少种序列？（）。

1440

2520

3628800

正确答案C

解析详情

【答案】C

【考点】多重集排列

【解析】共有 10 个位置，其中红球相同有 2 个、绿球相同有 3 个、黄球相同有 5 个。不同序列数为 10!/(2!×3!×5!)=2520，所以选 C。

【易错点】相同颜色的小球不可区分，不能直接按 10! 计算。

第 3 题（单选题，2 分）

以下二维数组的初始化，哪个是符合语法的？（）。

int a[][] = {{1, 2}, {3, 4}};

int a[][2] = {}；

int a[2][2] = {{1, 2, 3}, {4, 5, 6}};

int a[2][] = {{1, 2, 3}, {4, 5, 6}};

正确答案B

解析详情

【答案】B

【考点】二维数组初始化

【解析】二维数组初始化时可以省略第一维，但必须给出最后一维大小，所以 `a[][2]` 的写法合法。 A 和 D 都缺少最后一维，C 的每行初值个数又超过了 `[2][2]` 的边界，因此只有 B 对。

【易错点】数组声明中能省略的是最前面的维度，不是最后面的维度。

第 4 题（单选题，2 分）

下面有关C++拷贝构造函数的说法，错误的是（）。

必须实现拷贝构造函数，否则一定会出现编译错误。

对象作为函数参数、以值传递方式传入函数时，会自动调用拷贝构造函数。

对象作为函数返回值、以值传递方式从函数返回时，会自动调用拷贝构造函数。

使用一个对象初始化另一个对象时，会自动调用拷贝构造函数。

正确答案A

解析详情

【答案】A

【考点】拷贝构造函数

【解析】拷贝构造函数在未手写时，编译器通常会生成默认版本，所以并不是必须自己实现，否则一定编译错误这句话是错的。值传参、值返回、用一个对象初始化另一个对象都会触发拷贝构造，因此 B、C、D 都是常见场景。

【易错点】不要把需要自定义拷贝构造和必须手写拷贝构造混为一谈。

第 5 题（单选题，2 分）

使用邻接表表达一个无向简单图，图中包含 v 个顶点、e 条边，则该表中边节点的个数为（）。

v \times (v - 1)

v \times v

2 \times e

正确答案C

解析详情

【答案】C

【考点】邻接表存储

【解析】无向图的一条边会分别出现在两个端点的邻接表中各一次。因此 e 条边对应 2e 个边结点，选 C。

【易错点】有向图和无向图的邻接表边结点数不同，别把 e 和 2e 混用。

第 6 题（单选题，2 分）

关于生成树的说法，错误的是（）。

一个无向连通图可以有多个生成树。

一个无向图，只要连通，就一定有生成树。

n 个顶点的无向完全图，有

n^{n-2}

棵生成树。

n 个顶点的无向图，生成树包含 n-1 条边。

正确答案D

解析详情

【答案】D

【考点】生成树性质

【解析】 A、B、C 都成立：连通无向图可以有多个生成树，连通无向图一定存在生成树，完全图的生成树数为 n^{n-2}。 D 少了连通这个前提，任意无向图未必存在生成树，所以把它说成普遍结论是错的。

【易错点】生成树的性质只对连通图成立，图不连通时谈不上整图的生成树。

第 7 题（单选题，2 分）

已知三个 double 类型的变量 a、b 和 theta 分别表示一个三角形的两条边长及二者的夹角（弧度），则下列哪个表达式可以计算这个三角形的周长？（）。

a * b * sin(theta) / 2

a + b + (a + b) * sin(theta) / 2

a * b * cos(theta) / 2

a + b + sqrt(a * a + b * b - 2 * a * b * cos(theta))

正确答案D

解析详情

【答案】D

【考点】余弦定理

【解析】第三边长度由余弦定理得 `c = sqrt(a*a + b*b - 2*a*b*cos(theta))`。三角形周长就是 `a + b + c`，对应选项 D；A 和 C 是面积相关式子，不是周长。

【易错点】见到两边和夹角时先求第三边，再算周长或面积。

第 8 题（单选题，2 分）

在有 n 个元素的二叉排序树中进行查找，其最好、最差时间复杂度分别为（）。

O(1)

、

O(n)

O(1)

、

O(\log n)

O(\log n)

、

O(\log n)

O(\log n)

、

O(n)

正确答案A

解析详情

【答案】A

【考点】二叉排序树查找复杂度

【解析】最好情况是一开始就在根结点找到目标，只比较一次，时间复杂度为 O(1)。最差情况树退化成链，查找到最深处要走 n 个结点，复杂度为 O(n)，所以选 A。

【易错点】平均或较平衡情况下常见 O(log n)，但题目问的是最好和最差。

第 9 题（单选题，2 分）

如下图所示，半径为 r 、圆心角为 t （弧度）的扇形，下面哪个表达式能够求出顶部阴影部分的面积？（）。

r * r * sin(t) / 2

r * r * t / 2

r * r * (t - sin(t))

r * r * (t - sin(t)) / 2

正确答案D

解析详情

【答案】D

【考点】扇形与三角形面积

【解析】阴影部分可看作扇形面积减去两条半径夹成的三角形面积。前者是 `r*r*t/2`，后者是 `r*r*sin(t)/2`，相减得 `r*r*(t-sin(t))/2`，对应 D。

【易错点】 `r*r*(t-sin(t))` 少了整体的 `/2`，这是最容易漏掉的系数。

第 10 题（单选题，2 分）

下面程序的时间复杂度为（）。

int fib(int n) {
    if (n <= 1)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

O(2^{n})

O(\phi^{n})

, 其中

\phi = \frac{\sqrt{5} + 1}{2}

O(n)

O(1)

正确答案B

解析详情

【答案】B

【考点】递归时间复杂度

【解析】该函数满足递推式 `T(n)=T(n-1)+T(n-2)+O(1)`，递归树规模与斐波那契数同阶。斐波那契数增长率为 `phi^n`，所以复杂度写成 `O(phi^n)` 更准确，对应 B。

【易错点】虽然递归分成两支，但精确量级不是随手写成 O(2^n) 就结束。

第 11 题（单选题，2 分）

下面程序的时间复杂度为（）。

int choose(int n, int m) {
    if (m == 0 || m == n)
        return 1;
    return choose(n - 1, m - 1) + choose(n - 1, m);
}

O(2^{n})

O(2^{m} \times (n - m))

O(C(n, m))

O(m \times (n - m))

正确答案C

解析详情

【答案】C

【考点】递归计数

【解析】 `choose(n,m)` 的递归会展开成杨辉三角中的一棵递归树，直到 `m=0` 或 `m=n` 才停止。递归调用总数与组合数 `C(n,m)` 同阶，因此时间复杂度为 `O(C(n,m))`，选 C。

【易错点】这里 m 不是简单的循环层数，不能机械套成多项式复杂度。

第 12 题（单选题，2 分）

下面程序的时间复杂度为（）。

int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve() {
    for (int n = 2; n <= MAXN; n++) {
        if (!isPrime[n])
            primes[num++] = n;
        for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
            isPrime[n * primes[i]] = true;
            if (n % primes[i] == 0)
                break;
        }
    }
}

O(n)

O(n \times \log n)

O(n \times \log \log n)

O(n^{2})

正确答案A

解析详情

【答案】A

【考点】线性筛

【解析】这段程序是欧拉筛，每个合数只会被它的最小质因子筛掉一次。因此内层循环的总执行次数与 n 同阶，整体时间复杂度为 O(n)，选 A。

【易错点】不要把它和埃氏筛混淆，欧拉筛的关键特征就是每个合数只标记一次。

第 13 题（单选题，2 分）

下面程序的输出为（）。

#include <iostream>
using namespace std;

int a[10][10];
int main() {
    int m = 5, n = 4;
    for (int x = 0; x <= m; x++)
        a[x][0] = 1;
    for (int y = 1; y <= n; y++)
        a[0][y] = 1;
    for (int x = 1; x <= m; x++)
        for (int y = 1; y <= n; y++)
            a[x][y] = a[x - 1][y] + a[x][y - 1];
    cout << a[m][n] << endl;
    return 0;
}

126

3024

正确答案C

解析详情

【答案】C

【考点】动态规划计数

【解析】 `a[x][y]=a[x-1][y]+a[x][y-1]` 表示从左边和上边转移，边界都初始化为 1。所以 `a[5][4]` 等于从 `(0,0)` 走到 `(5,4)` 的路径数，即组合数 `C(9,4)=126`，输出 126。

【易错点】看到这种左上递推时，优先把它识别成路径计数而不是直接硬算整张表。

第 14 题（单选题，2 分）

下面程序的输出为（）。

#include <iostream>
using namespace std;

int main() {
    int cnt = 0;
    for (int x = 0; x <= 10; x++)
        for (int y = 0; y <= 10; y++)
            for (int z = 0; z <= 10; z++)
                if (x + y + z == 15)
                    cnt++;
        cout << cnt << endl;
        return 0;
}

100

正确答案B

解析详情

【答案】B

【考点】三重循环计数

【解析】程序统计的是 `0<=x,y,z<=10` 且 `x+y+z=15` 的整数解个数。无限制时有 `C(17,2)=136` 个；减去某一变量至少为 11 的情况，三种各有 `C(6,2)=15` 个，得 `136-45=91`，所以输出 91。

【易错点】这题不是简单枚举感知，限制 `<=10` 需要用容斥扣掉超界情况。

第 15 题（单选题，2 分）

下面的程序使用邻接矩阵表达的带权无向图，则从顶点0到顶点3的最短距离为（）。

int weight[4][4] = {
    { 0, 1, 7, 100 },
    { 1, 0, 5, 15 },
    { 7, 5, 0, 6 },
    { 100, 15, 6, 0 }
};

100

正确答案C

解析详情

【答案】C

【考点】最短路径

【解析】从 0 到 3 的几条明显路径中，直接走是 100，走 `0→1→3` 是 1+15=16，走 `0→2→3` 是 7+6=13。最短的是 `0→1→2→3`，长度 `1+5+6=12`，对应当前 JSON 的 C。

【易错点】带权图最短路不能只看边数，必须比较路径权值和。

判断题

第 1 题（判断题，2 分）

已知 int 类型的变量 a 和 b，则执行语句 a, b = b, a; 后，变量 a 和 b 的值会互换。

正确答案错误

解析详情

【答案】错误

【考点】逗号运算符与赋值

【解析】 `a, b = b, a;` 并不是交换语句，真正发生赋值的是中间的 `b = b`，`a` 不会因此得到原来的 `b`。所以执行后 a 和 b 不会完成互换。

【易错点】 C++ 里没有 Python 那样的多重赋值交换写法，不能照搬。

第 2 题（判断题，2 分）

一个袋子中有3个完全相同的红色小球、2个完全相同的蓝色小球。每次从中取出1个，再放回袋子，这样进行3次后，可能的颜色顺序有7种。

正确答案错误

解析详情

【答案】错误

【考点】乘法原理

【解析】每次放回后下一次仍可取红或蓝，两种颜色每次都有 2 种选择。进行 3 次共有 `2^3=8` 种颜色序列，不是 7 种。

【易错点】放回意味着每次选择数不变，不能按不放回去数。

第 3 题（判断题，2 分）

孙子定理是求解一次同余方程组的方法，最早见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》。又称中国余数定理，是中国数学史上的一项伟大成就。

正确答案正确

解析详情

【答案】正确

【考点】中国余数定理

【解析】题干对孙子定理的内容、别名和历史出处描述是符合常识的。它确实是求解一次同余方程组的重要方法，也常被称为中国余数定理。

【易错点】不要把孙子定理和欧几里得算法、费马小定理混成同一类结论。

第 4 题（判断题，2 分）

N个顶点的无向完全图有 $N \times (N - 1)$ 条边。

正确答案错误

解析详情

【答案】错误

【考点】完全图边数

【解析】无向完全图中每一对不同顶点之间恰有一条边，所以边数是组合数 `C(N,2)=N(N-1)/2`。题干写成 `N(N-1)` 多算了一倍，因此错误。

【易错点】无向边没有方向，不能把 `(u,v)` 和 `(v,u)` 当成两条不同的边。

第 5 题（判断题，2 分）

为解决哈希函数冲突，在哈希表项内设置链表存储该项内的所有冲突元素，则该哈希表内查找元素的最差时间复杂度为 $O(1)$ 。

正确答案错误

解析详情

【答案】错误

【考点】哈希冲突与最坏复杂度

【解析】链地址法只能改善平均情况，最坏时所有元素都落到同一个桶里。这时查找要顺着整条链表扫描，复杂度是 O(n)，不是 O(1)。

【易错点】哈希表常说的 O(1) 一般指平均复杂度，不是最坏复杂度。

第 6 题（判断题，2 分）

求一个包含 v 个顶点、 e 条边的带权连通无向图的最小生成树，Prim算法的时间复杂度为O(v × e)。

正确答案错误

解析详情

【答案】错误

【考点】Prim 算法复杂度

【解析】 Prim 算法常见实现复杂度是邻接矩阵版 O(v^2)，或配合堆优化时为 O(e log v)。题干写成 O(v×e) 不是 Prim 的标准复杂度表达，因此错误。

【易错点】图算法复杂度要看具体实现，不能只记一个模糊公式。

第 7 题（判断题，2 分）

已知 int 类型的变量 a、b 和 c 中分别存储着一个三角形的三条边长，则这个三角形的面积可以通过表达式 $\sqrt{(a + b + c) \times (b + c - a) \times (a + c - b) \times (a + b - c)}$ / 4 求得。

正确答案正确

解析详情

【答案】正确

【考点】海伦公式

【解析】三角形面积可写为 `sqrt(p(p-a)(p-b)(p-c))`，其中 `p=(a+b+c)/2`。把 1/2 提到根号内化简后，正好得到题中的 `sqrt((a+b+c)(b+c-a)(a+c-b)(a+b-c))/4`，所以结论正确。

【易错点】海伦公式里的半周长是 `p=(a+b+c)/2`，不要误写成周长本身。

第 8 题（判断题，2 分）

可以使用深度优先搜索算法判断图的连通性。

正确答案正确

解析详情

【答案】正确

【考点】图的遍历

【解析】从任一点出发做一次 DFS，若最终能访问到图中所有顶点，则图连通；否则不连通。因此 DFS 完全可以用于判断连通性。

【易错点】 DFS 和 BFS 都能做连通性判断，区别主要在遍历顺序。

第 9 题（判断题，2 分）

在N个元素的二叉排序树中查找一个元素，平均情况的时间复杂度是 $O(\log N)$ 。

正确答案正确

解析详情

【答案】正确

【考点】二叉排序树平均复杂度

【解析】二叉排序树在平均情况下高度约为 O(log N)，查找沿着一条根到叶的路径进行。因此平均查找复杂度是 O(log N)，题干说法正确。

【易错点】平均复杂度和最坏复杂度不同，最坏退化成链时会变成 O(N)。

第 10 题（判断题，2 分）

给定 double 类型的变量 x，且其值大于等于 1，我们可以通过二分法求出 $\log x$ 的近似值。

正确答案正确

解析详情

【答案】正确

【考点】二分求函数近似解

【解析】当 `x>=1` 时，`y=log x` 满足 `e^y=x`，而指数函数单调递增。在合适区间内对 y 做二分，比较 `e^y` 与 x 的大小，就能逼近 `log x` 的值，所以说法正确。

【易错点】二分法要求目标函数在区间内单调，先确认单调性再套用。