5623：[GESP202609八级] 客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 一、单选题（每题 2 分，共 30 分）
**第 1 题** 用数字 $0$、$1$、$2$、$3$、$4$、$5$ 组成没有重复数字的三位数，且该三位数能被 $3$ 整除，共有（ ）个
- $36$
- $40$
- $44$
- $48$
**第 2 题** $6$ 个人围成一圈就座，座位没有区分，但区分时针方向，且甲、乙两人必须相邻，则共有（ ）种不同坐法。
- $24$
- $36$
- $48$
- $120$
**第 3 题** 有 $4$ 堆石子，数量分别为 $1$、$2$、$3$、$4$。每次可以合并相邻两堆，合并代价为两堆石子数之和。将所有石子合并成一堆的最小总代价为（ ）。
- $17$
- $19$
- $20$
- $23$
**第 4 题** 某二叉树的先序遍历序列为 `A B D E C F G`，中序遍历序列为 `D B E A F C G`，则其后序遍历序列为（ ）
- `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 题** 关于快速幂算法，下列说法正确的是（ ）
- 快速幂可以处理任意负指数的情况
- 快速幂将指数按二进制拆分，能够把乘法次数从朴素乘幂时的 $O(b)$ 优化为 $O(\log b)$
- 快速幂只能在模数为质数时使用
- 快速幂的空间复杂度通常为 $O(b)$
**第 6 题** 杨辉三角中，第 $7$ 行第 $3$ 个数（行、列均从 $0$ 开始计数）是（ ）
- $21$
- $35$
- $42$
- $56$
**第 7 题** 一个长方形的长是宽的 $3$ 倍，周长为 $48$，则该长方形的面积为（ ）
- $72$
- $96$
- $108$
- $144$
**第 8 题** 若 $x + y = 7$，$x - y = 1$，则 $x \times y$ 的值为（ ）
- $7$
- $8$
- $10$
- $12$
**第 9 题** 关于最小生成树（`MST`）算法，下列说法正确的是（ ）
- `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$ 条被选入最小生成树的边是（ ）
- $(1,2,5)$
- $(2,3,3)$
- $(3,4,2)$
- $(4,5,7)$
**第 11 题** 在使用小根堆（优先队列）优化的 `Dijkstra` 算法中，堆中每个元素通常存储的是（ ）
- 顶点编号和该顶点当前的最短距离
- 边的权值和边的终点
- 顶点的入度
- 父结点编号和边权
**第 12 题** 在 `Floyd` 算法的经典三重循环 `for (k) for (i) for (j)` 中，最外层变量 `k` 表示（ ）
- 当前允许作为中间顶点的最大编号（即只允许编号不超过 $k$ 的顶点作为中间点）
- 当前起点
- 当前终点
- 当前最短路径的长度
**第 13 题** 下列常见复杂度量级，按渐近增长速度从慢到快排列，正确的是（ ）
- $O(n^2)$、$O(n\log n)$、$O(n)$、$O(\log n)$
- $O(\log n)$、$O(n)$、$O(n^2)$、$O(n\log n)$
- $O(\log n)$、$O(n)$、$O(n\log n)$、$O(n^2)$
- $O(n\log n)$、$O(\log n)$、$O(n)$、$O(n^2)$
**第 14 题** 对长度为 $n$ 的数组使用差分数组支持 $m$ 次区间加操作，最后通过一次前缀和还原每个位置的最终值，整个过程的渐进时间复杂度为（ ）
- $O(mn)$
- $O((n+m)\log n)$
- $O(n\log m)$
- $O(n+m)$
**第 15 题** 下列程序的输出结果为（ ）
```cpp
01 #include
02 using namespace std;
03 class A {
04 public:
05 A() {
06 cout << "A";
07 }
08 ~A() {
09 cout << "~A";
10 }
11 };
12 class B : public A {
13 public:
14 B() {
15 cout << "B";
16 }
17 ~B() {
18 cout << "~B";
19 }
20 };
21 int main() {
22 B b;
23 return 0;
24 }
```
- `BA~A~B`
- `BA~B~A`
- `AB~A~B`
- `AB~B~A`
## 二、判断题（每题 2 分，共 20 分）
**第 1 题** 从 $4$ 本不同的书中选出 $3$ 本，分别分给甲、乙、丙 $3$ 人，每人至多 $1$ 本，共有 $P(4,3) = 24$ 种不同分法。
- 正确
- 错误
**第 2 题** 对任意正整数 $n$，二项式 $(a+b)^n$ 的展开式中，按项序从第 $0$ 项起计数，奇数项系数之和等于偶数项系数之和。
- 正确
- 错误
**第 3 题** 若一个连通无向图的最小生成树中存在权值相同的边，则最小生成树一定不唯一。
- 正确
- 错误
**第 4 题** 使用邻接表存储图时，`Dijkstra` 算法的朴素实现（不使用堆优化）的时间复杂度为 $O(V^2)$，其中 $V$ 为结点数。
- 正确
- 错误
**第 5 题** 堆排序是一种稳定的排序算法。
- 正确
- 错误
**第 6 题** 每个大于 $1$ 的整数都可以唯一地分解为若干个质因数的乘积（不考虑因子顺序）。
- 正确
- 错误
**第 7 题** 循环队列通过牺牲一个存储单元，可以区分队空和队满两种状态。
- 正确
- 错误
**第 8 题** 在 `C++` 语言的私有继承中，基类的 `public` 成员在派生类中仍为 `public` 成员。
- 正确
- 错误
**第 9 题** 使用滚动数组优化动态规划时，通常只能降低空间复杂度，不能降低时间复杂度。
- 正确
- 错误
**第 10 题** 一个三角形的三条边的边长分别为 $5$、$12$、$13$，则它的面积为 $30$。
- 正确
- 错误