试卷解析 · 理解每一步

2024-03-Level-8

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

单选题

第 1 题（单选题，2 分）

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

108

正确答案D

解析详情

答案 D乘法原理

思路与推导

一道菜要依次确定肉类、切法、配菜和辣度，四步选择互不限制。
每种肉都有 $3×3×3=27$ 种搭配，4 种肉共 $4×27=108$ 道菜，选 D。

第 2 题（单选题，2 分）

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

1440

2520

3628800

正确答案C

解析详情

答案 C重复元素排列

思路与推导

共有 10 个位置，先从中选 2 个放红球，再从剩余 8 个选 3 个放绿球，最后 5 个自动放黄球。
方案数为 $\binom{10}{2}\binom{8}{3}=45×56=2520$ ，选 C。也可写成 $10!/(2!3!5!)$ 。

第 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拷贝构造函数

思路与推导

没有手写拷贝构造函数，不等于一定无法拷贝。编译器会按规则隐式声明拷贝构造函数，在成员允许拷贝等条件满足时可直接使用，因此 A 的“一定编译错误”不成立。
用已有对象初始化新对象、按值传入对象，是理解拷贝构造的典型场景。实际 C++ 中返回对象还可能发生移动或拷贝消除，不能把每次按值返回都理解为必然执行一次拷贝。

第 5 题（单选题，2 分）

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

v \times (v - 1)

v \times v

2 \times e

正确答案C

解析详情

答案 C无向图邻接表

思路与推导

一条无向边 {u,v} 需要同时出现在 u 的邻接表和 v 的邻接表中：一项记录 u→v，另一项记录 v→u。
因此 e 条边对应 $2e$ 个边结点，选 C。这里统计的是边结点，不包括 v 个表头。

第 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余弦定理与周长

思路与推导

周长需要三条边相加，已知 a、b 后，先用夹角求第三边 c。
由余弦定理， $c^2=a^2+b^2-2ab\cos\theta$ ，故周长为 $a+b+\sqrt{a^2+b^2-2ab\cos\theta}$ ，对应 D。

第 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 的链，最坏要比较 n 次，即 $O(n)$ 。两者对应 A。

第 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弓形面积

思路与推导

图中阴影是圆弧和弦之间的区域，可用扇形面积减去两条半径与弦组成的三角形面积。
圆心角 t 使用弧度，扇形面积为 $r^2t/2$ ，三角形面积为 $r^2\sin t/2$ 。
相减得到 $r^2(t-\sin t)/2$ ，对应 D。

第 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斐波那契递归复杂度

思路与推导

每次调用分成 fib(n−1) 和 fib(n−2)，且没有记忆化，因此同一参数会被反复计算。
调用数满足 $T(n)=T(n-1)+T(n-2)+O(1)$ ，增长率与斐波那契数列相同，其紧确指数级为 $\Theta(\phi^n)$ ，其中 $\phi=(1+\sqrt5)/2$ ，选 B。
$O(2^n)$ 也是较宽松的上界，但没有 B 精确。

第 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组合数递归复杂度

思路与推导

遇到 m=0 或 m=n 时返回 1；其他调用恰好有两个子调用。由于每个叶子返回 1，最终返回的 $\binom{n}{m}$ 也等于叶子数。
一棵每个内部结点都有两个孩子的递归树，若有 L 个叶子，就有 2L−1 个结点，因此总调用数为 $2\binom{n}{m}-1$ 。
每次调用做常数工作，复杂度为 $\Theta(\binom{n}{m})$ ，选 C。

第 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][0] 和 a[0][y] 都设为 1，表示沿一条边界到达某点只有一种走法。
内部位置的最后一步只能来自左边或下边，故 a[x][y]=a[x−1][y]+a[x][y−1]。到 (5,4) 共走 9 步，其中选 4 步沿 y 方向即可。
因此结果为 $\binom{9}{4}=126$ ，选 C。

图解 · 看懂这一步逐格相加的路径数

左右滑动表格，可查看完整内容。

x\y	0	1	2	3	4
0	1	1	1	1	1
1	1	2	3	4	5
2	1	3	6	10	15
3	1	4	10	20	35
4	1	5	15	35	70
5	1	6	21	56	126

第一行、第一列为 1，其余格等于上方与左方之和；表的 x 方向向下。

第 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有限制的整数解计数

思路与推导

先忽略每个变量不超过 10 的上界，非负整数解 $x+y+z=15$ 有 $\binom{17}{2}=136$ 个。
若 x≥11，令 x'=x−11，则 x'+y+z=4，有 $\binom{6}{2}=15$ 个解。y 或 z 超限也各有 15 个。
两个变量同时≥11 会使总和至少为 22，不可能发生，所以不需加回交集。合法方案为 $136-3×15=91$ ，选 B。

第 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；经过顶点 1 为 1+15=16，经过顶点 2 为 7+6=13。
先走 0→1→2 再到 3，代价为 $1+5+6=12$ 。另一种三段简单路径 0→2→1→3 为 27，更长。
所有边权为正，无需重复绕圈，最短距离为 12，选 C。

判断题

第 1 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误逗号运算符与赋值

思路与推导

赋值运算符的优先级高于逗号运算符，所以 a,b=b,a 等价于依次计算 a、执行 b=b、再计算 a。
唯一赋值是 b=b，a 和 b 均未交换。例如原来 a=1、b=2，执行后仍是 1、2。应使用临时变量或 swap(a,b)。

第 2 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误有放回取球

思路与推导

每取一个球都会放回，因此每次仍可出现红或蓝，两种颜色都不会用完。
3 次取球共有 $2×2×2=8$ 种颜色顺序，包含“蓝蓝蓝”。题目说 7 种错误。

第 3 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确中国余数定理

思路与推导

孙子定理用于处理一组同余条件，例如一个数除以 3 余 2、除以 5 余 3、除以 7 余 2，23 就满足这些条件。
在模数两两互质时，可确定模其乘积意义下的唯一解。题目对名称、用途及《孙子算经》来源的描述正确。

第 4 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误无向完全图

思路与推导

每个顶点与其他 N−1 个顶点相连，按顶点累加得到 N(N−1)，但每条无向边被两个端点各数了一次。
因此边数应为 $N(N-1)/2$ 。例如 3 个顶点的完全图只有 3 条边，而题中公式得到 6，故错误。

第 5 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误链地址法最坏复杂度

思路与推导

链地址法把哈希到同一位置的元素放入链表。最坏情况下，n 个元素全部落入同一个位置。
查找链尾元素或不存在的元素，需要沿链比较最多 n 次，最坏为 $O(n)$ ，不是 $O(1)$ 。

第 6 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误Prim 算法复杂度

思路与推导

朴素 Prim 每轮扫描所有未加入顶点，选最小连接代价，再更新候选，共 v 轮，典型时间复杂度为 $O(v^2)$ 。
采用邻接表和优先队列时，常见实现可达到 $O((v+e)\log v)$ 。题目给出的 $O(ve)$ 不是通常所指的 Prim 标准复杂度，按考试口径判错误。

第 7 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确海伦公式

思路与推导

令半周长 $s=(a+b+c)/2$ ，海伦公式是 $S=\sqrt{s(s-a)(s-b)(s-c)}$ 。
四个因子分别提出 1/2，乘积中形成 1/16，开平方后为 1/4，所以得到题中根式再除以 4 的形式，数学上成立。
若直接用 C++ 的 int 计算乘积，还要防止中间结果溢出，可先转换为足够宽的数值类型。

第 8 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确深度优先搜索与连通性

思路与推导

对无向图选一个起点进行 DFS，沿边不断访问未访问顶点。若最终所有顶点都被访问，图连通；否则未访问部分与起点不连通。
对有向图则要先区分弱连通和强连通，DFS 也可作为相应判定算法的基础，因此可以使用 DFS 判断连通性。

第 9 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确二叉排序树平均查找

思路与推导

在常见的随机插入顺序分析下，二叉排序树结点的平均深度为对数级，查找所需比较次数因而平均为 $O(\log N)$ ，按题目默认口径判断正确。
但特定插入顺序可能构造出链状树，此时平均查找也可能达到线性级；题目的平均结论依赖随机模型。

第 10 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确二分求对数

思路与推导

以自然对数为例，把问题改写为寻找满足 $e^y=x$ 的 y。指数函数在实数上严格递增，因此可按 $e^{mid}$ 与 x 的大小缩小区间。
当 x≥1 时，可从 y∈[0,x] 开始；若 $e^{mid}<x$ ，向右找，否则向左找，直到误差足够小。其他合法底数的对数也可通过相应单调函数求近似值。