一、单选题（每题 2 分，共 30 分）

第 1 题 用数字0、1、2、3、4、5 组成没有重复数字的三位数，且该三位数能被 3 整除，共有（）个。

{{ select(1) }}

• 36
• 40
• 44
• 48

第 2 题 $6$ 个人围成一圈就座，座位没有区分，但区分时针方向，且甲、乙两人必须相邻，则共有（）种不同坐法。

{{ select(2) }}

• 24
• 36
• 48
• 120

第 3 题 有 $4$ 堆石子，数量分别为 1、2、3、4。每次可以合并相邻两堆，合并代价为两堆石子数之和。将所有石子合并成一堆的最小总代价为（）。

{{ select(3) }}

• 17
• 19
• 20
• 23

第 4 题 某二叉树的先序遍历序列为 A B D E C F G，中序遍历序列为 D B E A F C G，则其后序遍历序列为()。

{{ select(4) }}

• D E B F G C A
• D B E F G C A
• D E B G F C A
• D E B F C G A

第 5 题 关于快速幂算法，下列说法正确的是（）。

{{ select(5) }}

• 快速幂可以处理任意负指数的情况
• 快速幂将指数按二进制拆分，能够把乘法次数从朴素乘幂时的 $O(b)$ 优化为 $O(logb)$
• 快速幂只能在模数为质数时使用
• 快速幂的空间复杂度通常为 $O(b)$

第 6 题 杨辉三角中，第$7$行第$3$个数（行、列均从$0$开始计数）是（）。

{{ select(6) }}

• 21
• 35
• 42
• 56

第 7 题 一个长方形的长是宽的 $3$ 倍，周长为 $48$，则该长方形的面积为（）。

{{ select(7) }}

• 72
• 96
• 108
• 144

第 8 题 若 $x+y=7, x-y=1$，则 $x \times y$ 的值为（）。

{{ select(8) }}

• 7
• 8
• 10
• 12

第 9 题 关于最小生成树（MST）算法，下列说法正确的是（）。

{{ select(9) }}

• Prim 算法适用于稠密图，Kruskal 算法适用于稀疏图
• Prim 算法和 Kruskal 算法得到的最小生成树边集一定完全相同
• Kruskal 算法必须使用邻接矩阵存储图
• Prim 算法只能处理有向图

第 10 题 某连通带权无向简单图的边集合为 ${(1,2,5),(1,3,1),(2,3,3),(2,4,4),(3,4,2),(3,5,6),(4,5,7)}$，其中，每条边的三元组 $(u,v,w)$ 表示结点 $u$ 和结点 $v$ 之间有一条权值为 $w$ 的无向边。使用 Kruskal 算法按边权从小到大扫描，第 $3$ 条被选入最小生成树的边是()。

{{ select(10) }}

• (1,2,5)
• (2,3,3)
• (3,4,2)
• (4,5,7)

第 11 题 在使用小根堆（优先队列）优化的 Dijkstra 算法中，堆中每个元素通常存储的是（）。

{{ select(11) }}

• 顶点编号和该顶点当前的最短距离
• 边的权值和边的终点
• 顶点的入度
• 父结点编号和边权

第 12 题 在 Floyd 算法的经典三重循环 for (k) for (i) for (j) 中，最外层变量 $k$ 表示（）。

{{ select(12) }}

• 当前允许作为中间顶点的最大编号（即只允许编号不超过 $k$ 的顶点作为中间点）
• 当前起点
• 当前终点
• 当前最短路径的长度

第 13 题 下列常见复杂度量级，按渐近增长速度从慢到快排列，正确的是（）。

{{ select(13) }}

• $O(n^2)、O(nlogn)、O(n)、O(logn)$
• $O(logn)、O(n)、O(n^2)、O(nlogn)$
• $O(logn)、O(n)、O(nlogn)、O(n^2)$
• $O(nlogn)、O(logn)、O(n)、O(n^2)$

第 14 题 对长度为$n$ 的数组使用差分数组支持 $m$ 次区间加操作，最后通过一次前缀和还原每个位置的最终值，整个过程的渐进时间复杂度为（）。

{{ select(14) }}

• $O(mn)$
• $O((n+m)logn)$
• $O(nlogm)$
• $O(n+m)$

第 15 题 下列程序的输出结果为（）。

#include <iostream>
using namespace std;
class A {
public:
	A () {
		cout << "A";
	}
	~A () {
		cout << "~A";
	}
};
class B : public A {
public:
	B () {
		cout << "B";
	}
	~B () {
		cout << "~B";
	}
};
int main() {
	B b;
	return 0;
}

{{ select(15) }}

• BA~A~B
• BA~B~A
• AB~A~B
• AB~B~A

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

第 16 题 从 $4$ 本不同的书中选出 $3$ 本，分别分给甲、乙、丙 $3$ 人，每人至多 $1$ 本，共有 $P(4,3)=24$ 种不同分法。

{{ select(16) }}

• 正确
• 错误

第 17 题 对任意正整数 $n$，二项式 $(a+b)^n$ 的展开式中，按项序从第 $0$ 项起计数，奇数项系数之和等于偶数项系数之和。

{{ select(17) }}

• 正确
• 错误

第 18 题 若一个连通无向图的最小生成树中存在权值相同的边，则最小生成树一定不唯一。

{{ select(18) }}

• 正确
• 错误

第 19 题 使用邻接表存储图时，Dijkstra 算法的朴素实现（不使用堆优化）的时间复杂度为 $O(V^2)$，其中 $V$ 为结点数。

{{ select(19) }}

• 正确
• 错误

第 20 题 堆排序是一种稳定的排序算法。

{{ select(20) }}

• 正确
• 错误

第 21 题 每个大于 $1$ 的整数都可以唯一地分解为若干个质因数的乘积（不考虑因子顺序）。

{{ select(21) }}

• 正确
• 错误

第 22 题 循环队列通过牺牲一个存储单元，可以区分队空和队满两种状态。

{{ select(22) }}

• 正确
• 错误

第 23 题 在C++语言的私有继承中，基类的 public 成员在派生类中仍为 public 成员。

{{ select(23) }}

• 正确
• 错误

第 24 题 使用滚动数组优化动态规划时，通常只能降低空间复杂度，不能降低时间复杂度。

{{ select(24) }}

• 正确
• 错误

第 25 题 一个三角形的三条边的边长分别为 $5、12、13$, 则它的面积为 $30$。

{{ select(25) }}

• 正确
• 错误