试卷解析 · 理解每一步

2023-12-Level-8

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

单选题

第 1 题（单选题，2 分）

小杨要从A城到B城，又想顺路游览一番。他有两个选项：1、坐高铁路到C城游览，再坐高铁或飞机到B城；2、坐船到D城游览，再坐船、高铁或飞机到B城。请问小杨从A城到B城共有几种交通方案可以选择？（）。

正确答案C

解析详情

答案 C分类加法与分步乘法

思路与推导

经 C 城时，第一段只有高铁，第二段可选高铁或飞机，共 $1×2=2$ 种。
经 D 城时，第一段只有轮船，第二段有 3 种选择，共 $1×3=3$ 种。两类路线互不重合，所以共有 $2+3=5$ 种，选 C。

第 2 题（单选题，2 分）

以下哪个函数声明是符合语法的，且在调用时可以将二维数组的名字作为实际参数传递给形式参数 a？（）。

void QuickSort(int a[][10], int n);

void QuickSort(int a[5][], int m);

void QuickSort(int a[][], int n, int m);

void QuickSort(int ** a, int n, int m);

正确答案A

解析详情

答案 A二维数组形参

思路与推导

二维数组按行连续存储，编译器必须知道每行有多少个元素，才能计算 a[i][j] 的地址。
int a[][10] 在形参中调整为指向含 10 个 int 的数组的指针，可以接收第二维长度为 10 的二维数组名。第一维可以省略，第二维不能省略，因此选 A。
int ** 是二级指针，和指向一整行数组的指针不是同一种类型。

第 3 题（单选题，2 分）

下面有关C++类和对象的说法，错误的是（）。

对象的生命周期开始时，会执行构造函数。

对象的生命周期结束时，会执行析构函数。

类的析构函数可以为虚函数。

类的构造函数可以为虚函数。

正确答案D

解析详情

答案 D构造函数与虚函数

思路与推导

构造函数负责初始化正在创建的对象，C++ 不允许把构造函数声明为 virtual，因此 D 错误。
析构函数可以是虚函数；通过基类指针删除派生类对象时，虚析构函数能让派生类部分也得到正确析构。普通对象在构造和销毁时分别执行相应构造、析构过程。

第 4 题（单选题，2 分）

使用邻接矩阵表达 n 个顶点的有向图，则该矩阵的大小为（）。

n \times (n+1)

n \times n

n \times (n-1)

n \times (n-1)/2

正确答案B

解析详情

答案 B邻接矩阵

思路与推导

给顶点编号为 0 到 n−1，用矩阵 a[i][j] 表示从顶点 i 到顶点 j 的边。
起点有 n 种取值，终点也有 n 种取值，因此需要 $n×n$ 个位置，选 B。即使没有自环，对角线位置仍然存在。

第 5 题（单选题，2 分）

5 位同学排队，其中一位同学不能排在第一，则共有多少种可能的排队方式？（）。

120

正确答案C

解析详情

答案 C限制排列与补集

思路与推导

先安排第一位：不能选那位受限制的同学，故有 4 种选择。剩下 4 位同学可任意排列，有 $4!=24$ 种。
总方案数为 $4×24=96$ ，选 C。也可用全部 $5!=120$ 种减去受限同学排第一的 $4!=24$ 种。

第 6 题（单选题，2 分）

一个无向图包含 n 个顶点，则其最小生成树包含多少条边？（）。

n - 1

n + 1

最小生成树可能不存在。

正确答案D

解析详情

答案 D生成树的存在条件

思路与推导

生成树必须覆盖原图所有顶点，并且连通、无环。
题目只说是无向图，没有保证连通；若图分成两个互不相通的部分，就不能选出覆盖所有顶点的生成树，所以选 D。
只有在生成树确实存在时，其边数才一定为 $n-1$ 。

第 7 题（单选题，2 分）

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

a * b * sin(theta) / 2

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

a * b * cos(theta) / 2

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

正确答案A

解析详情

答案 A三角形面积

思路与推导

以长度为 a 的边作为底，另一条边 b 在垂直于底边方向上的高度为 $b\sin\theta$ 。
面积等于底乘高的一半，即 $S=\frac{ab\sin\theta}{2}$ ，对应 A。C++ 的 sin 接收弧度，符合题设。
D 是余弦定理计算第三边的式子，并不是面积。

第 8 题（单选题，2 分）

对有 n 个元素的二叉排序树进行中序遍历，其时间复杂度是（）。

O(1)

O(\log(n))

O(n)

O(n^2)

正确答案C

解析详情

答案 C树的遍历复杂度

思路与推导

中序遍历依次访问左子树、当前结点、右子树。无论二叉排序树是否平衡，每个结点都恰好被访问一次。
n 个结点的访问工作总量与 n 成正比，因此时间复杂度为 $O(n)$ ，选 C。

第 9 题（单选题，2 分）

假设输入参数 m 和 n 满足 $m \leq n$ ，则下面程序的最差情况的时间复杂度为（）。

int gcd(int m, int n) {
    while (m > 0) {
        int t = m;
        m = n % m;
        n = t;
    }
    return n;
}

O(\log(n))

O(n)

O(n \times m)

O(m \times \log(n))

正确答案A

解析详情

答案 A欧几里得算法

思路与推导

每轮把数对 (m,n) 更新为 (n%m,m)，最大公约数保持不变，直到余数为 0。
余数严格小于除数，而且至多经过两轮，较小的正数就至少缩小一半，因此迭代次数为对数级。
在把整数取模视为常数时间的通常分析中，复杂度可写为 $O(\log n)$ ，选 A；更精细地可用较小输入 m 表示。

第 10 题（单选题，2 分）

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

long long power_mod (long long a, long long n, long long mod) {
    if (n == 0)
        return 1;
    a = a % mod;
    if (n == 1)
        return a;
    long long pw = power_mod(a, n / 2, mod);
    long long pw2 = pw * pw % mod;
    if (n % 2 == 0)
        return pw2;
    return pw2 * a % mod;
}

O(n)

O(a^n)

O(\log n)

O(\log n \times a)

正确答案C

解析详情

答案 C递归快速幂

思路与推导

每次只递归调用一次 power_mod(a,n/2,mod)，得到 pw 后再平方；奇数指数额外乘一次 a。
递推关系为 $T(n)=T(\lfloor n/2\rfloor)+O(1)$ 。指数依次约为 n、n/2、n/4，直到 0 或 1，共对数层，故选 C。

第 11 题（单选题，2 分）

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

int record_choose[MAXN][MAXM];
int choose(int n, int m) {
    if (m == 0 || m == n)
        return 1;
    if (record_choose[n][m] == 0)
        record_choose[n][m] = choose(n - 1, m - 1) + choose(n - 1, m);
    return record_choose[n][m];
}

O(2^n)

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

O(C(n,m))

O(m \times (n - m))

正确答案D

解析详情

答案 D记忆化组合数

思路与推导

用剩余需选个数 m 和不选个数 n−m 来理解状态：两种递归分支分别让其中一个数减少 1。到某一个数为 0 时直接返回。
非边界状态至多形成 $m×(n-m)$ 的网格，每个状态第一次计算后存入 record_choose，后续访问直接返回。每次状态计算只做常数次操作，因此通常非边界情形复杂度为 $O(m(n-m))$ ，选 D。
m=0 或 m=n 时立即返回，耗时为常数。

第 12 题（单选题，2 分）

下面的程序使用出边的邻接表表达有向图，则下列选项中哪个是它表达的图？（）。

#include <iostream>

struct Edge {
    int e;
    Edge * next;
};

struct Node {
    Edge * first;
};

int main() {
    Edge e[5] = {{1, nullptr}, {2, &e[2]}, 
                 {3, nullptr}, {3, nullptr}, {0, nullptr}};
    Node n[4] = {{&e[0]}, {&e[1]}, {&e[3]}, {&e[4]}};
    ;//其他处理
    return 0;
}

正确答案B

解析详情

答案 B出边邻接表

思路与推导

n[0] 指向 e[0]，得到边 0→1。n[1] 指向 e[1]，再沿 next 到 e[2]，得到 1→2 和 1→3。
n[2] 指向 e[3]，得到 2→3；n[3] 指向 e[4]，得到 3→0。
共五条有向边，核对图中箭头方向后，与选项 B 一致。

图解 · 看懂这一步沿 next 读出每个顶点的出边

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

顶点	边结点链	对应有向边
0	e[0]	0 → 1
1	e[1] → e[2]	1 → 2；1 → 3
2	e[3]	2 → 3
3	e[4]	3 → 0

先确定 n[i].first，再沿 next 读到空指针；箭头表示有向边。

第 13 题（单选题，2 分）

下面程序的输出为（）。

#include <iostream>
using namespace std;

int main() {
    int cnt = 0;
    for (int a = 1; a <= 10; a++)
        for (int b = 1; b <= 10; b++)
            for (int h = 1; h <= 10; h++)
                if ((a + b) * h == 20)
                    cnt++;
    cout << cnt << endl;
    return 0;
}

正确答案B

解析详情

答案 B枚举计数与约数

思路与推导

条件是 $(a+b)h=20$ ，且 a、b、h 都在 1 到 10。按 h 分类，只需考虑 20 的约数 1、2、4、5、10。
相应 a+b 为 20、10、5、4、2；满足范围的有序数对分别有 1、9、4、3、1 个。
总数为 $1+9+4+3+1=18$ ，选 B。例如和为 10 时，(1,9) 到 (9,1) 共 9 个。

图解 · 看懂这一步按高度 h 分类计数

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

h	a+b	有序数对数
1	20	1
2	10	9
4	5	4
5	4	3
10	2	1
合计	—	18

a、b 有顺序且都在 1 到 10；每行计数互不重叠。

第 14 题（单选题，2 分）

下面程序的输出为（）。

#include <iostream>
using namespace std;

int main() {
    const int N = 30;
    int cnt = 0;
    for (int a = 1; a <= N; a++)
        for (int b = a; a + b <= N; b++)
            for (int c = b; a + b + c <= N; c++)
                if (a * a + b * b == c * c)
                    cnt++;
    cout << cnt << endl;
    return 0;
}

正确答案A

解析详情

答案 A勾股数枚举

思路与推导

循环限制了 $1≤a≤b≤c$ ，同时要求周长 $a+b+c≤30$ ；if 再筛出满足勾股关系的三元组。
符合条件的只有 (3,4,5)、(6,8,10)、(5,12,13)，周长分别是 12、24、30。
因此 cnt 为 3，选 A。a≤b 的限制避免把两条直角边交换后重复计数。

第 15 题（单选题，2 分）

下面的程序中，二维数组 h 和 v 分别代表如下图所示的网格中的水平边的时间消耗和垂直边的时间消耗。程序使用动态规划计算从左下角到右上角的最小时间消耗，则横线处应该填写下列哪个选项的代码？（）。

int dis[MAXY][MAXX];
int shortest_path(int x, int y) {
    dis[0][0] = 0;
    for (int i = 0; i < y; i++)
        dis[i + 1][0] = dis[i][0] + v[i][0];
    for (int j = 0; j < x; j++)
        dis[0][j + 1] = dis[0][j] + h[0][j];
    for (int i = 0; i < y; i++)
        for (int j = 0; j < x; j++)
            // 在此处填写代码
    return dis[y][x];
}

dis[i][j] = min(dis[i - 1][j] + v[i - 1][j], dis[i][j - 1] + h[i][j - 1]);

dis[i][j] = min(dis[i - 1][j] + h[i - 1][j], dis[i][j - 1] + v[i][j - 1]);

dis[i + 1][j + 1] = min(dis[i][j + 1] + v[i][j + 1], dis[i + 1][j] + h[i + 1][j]);

dis[i + 1][j + 1] = min(dis[i][j + 1] + h[i][j + 1], dis[i + 1][j] + v[i + 1][j]);

正确答案C

解析详情

答案 C网格动态规划

思路与推导

dis[i][j] 表示从左下角到第 i 行第 j 列结点的最小代价，图中 h 是水平边、v 是竖直边。边界已先初始化。
当前循环应计算 dis[i+1][j+1]。从下方 dis[i][j+1] 来，经过 v[i][j+1]；从左方 dis[i+1][j] 来，经过 h[i+1][j]。
取两种代价的较小值，即选 C。循环从 0 开始，直接使用 i−1、j−1 会越界。

判断题

第 1 题（判断题，2 分）

C++语言非常强大，可以用来求解方程的解。例如，如果变量 x 为 double 类型的变量，则执行语句 x * 2 - 4 = 0；后，变量 x 的值会变为 2.0。

正确答案错误

解析详情

答案错误赋值表达式

思路与推导

C++ 中 = 表示赋值，左边必须是可修改的对象。x*2−4 是计算出的临时数值，不能作为赋值目标，因此这条语句不合法。
若要求方程 $2x-4=0$ 的解，需要先推导 $x=2$ ，再写 x=2.0；计算机不会把赋值号自动解释成求解方程。

第 2 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确有上限的颜色序列

思路与推导

不考虑球数时，3 个位置各选红或蓝，共 $2^3=8$ 个颜色序列。
袋中有 3 个红球，所以红球数不会超限；只有 2 个蓝球，唯一不合法的序列是“蓝蓝蓝”。因此合法序列有 $8-1=7$ 种。

第 3 题（判断题，2 分）

杨辉三角，是二项式系数的一种三角形排列，在中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现，是中国数学史上的一项伟大成就。

正确答案正确

解析详情

答案正确杨辉三角

思路与推导

杨辉三角的边界均为 1，内部每个数等于左上方与右上方两数之和；第 n 行对应 $(a+b)^n$ 的二项式系数。
题目所述杨辉在 1261 年《详解九章算法》中记载这一排列，符合该数学史知识点，所以判断正确。

第 4 题（判断题，2 分）

N 个顶点的有向完全图（不带自环）有 $N \times (N - 1)/2$ 条边。

正确答案错误

解析详情

答案错误有向完全图边数

思路与推导

每个顶点都向其余 N−1 个顶点连出一条边，所以总边数为 $N(N-1)$ 。
例如 N=2 时，既有 1→2，也有 2→1，共 2 条边；题中公式只给出 1 条，因此错误。

第 5 题（判断题，2 分）

如果待查找的元素确定，只要哈希表的大小不小于查找元素的个数，就一定存在不会产生冲突的哈希函数。

正确答案正确

解析详情

答案正确完美哈希的存在性

思路与推导

对预先确定的 k 个不同关键字，只要表至少有 k 个位置，就可以为这 k 个关键字分别指定不同的位置，构造出在该集合上无冲突的映射。
题目说的是“存在这样的函数”，并没有说任意哈希函数都不会冲突，因此判断正确。

第 6 题（判断题，2 分）

动态规划算法的时间复杂度一般为：必要状态的数量，乘以计算一次状态转移方程的时间复杂度。

正确答案正确

解析详情

答案正确动态规划复杂度

思路与推导

动态规划通常把重复子问题合并成状态，每个必要状态计算一次。
若有 S 个状态，每个状态枚举转移需 T 时间，总工作量通常为 $O(S×T)$ ；例如 n 个位置、每个枚举 k 个前驱，就是 $O(nk)$ 。各状态代价不同时应将它们求和，并考虑初始化等额外开销。

第 7 题（判断题，2 分）

已知 int 类型的变量 a、b 和 h 中分别存储着一个梯形的顶边长、底边长和高，则这个梯形的面积可以通过表达式 $(a + b) * h / 2$ 求得。

正确答案错误

解析详情

答案错误整数除法与面积

思路与推导

当 a、b、h 都是 int 时，乘法和除法按整数运算执行，最后的 /2 会舍弃小数部分。
例如 a=1、b=2、h=1，真实面积为 1.5，而表达式算出 3/2=1，所以不能保证正确。可在范围允许时使用 (a+b)*h/2.0。

第 8 题（判断题，2 分）

判断图是否连通只能用广度优先搜索算法实现。

正确答案错误

解析详情

答案错误图的连通性判定

思路与推导

对于无向图，从任意顶点出发，检查能否访问所有顶点即可判断连通性。广度优先搜索和深度优先搜索都能完成这件事。
也可以用并查集处理所有边后检查是否只剩一个连通块，因此“只能用 BFS”错误。

第 9 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误二叉排序树查找

思路与推导

若要查找的元素恰好位于根结点，只比较一次就成功，最好时间复杂度为 $O(1)$ 。
平衡树的查找最坏可为 $O(\log N)$ ，普通二叉排序树若退化为链，最坏还可能达到 $O(N)$ 。因此题目把最好情况说成对数级不准确。

第 10 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确二分求平方根

思路与推导

在非负区间上，函数 $f(t)=t^2$ 单调递增。可令左端为 0、右端为 max(1,x)，保证平方根位于区间内。
取中点 mid：若 $mid^2<x$ 就提高左端，否则降低右端。经过足够轮数或区间足够小后，中点就是近似平方根。
x=0 时可以直接返回 0。