5302：[GESP202603八级] 客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 一、单选题（每题 2 分，共 30 分）
**第 1 题** 某班级有 $8$ 名男生和 $6$ 名女生，现要选出 $3$ 人组成学习小组，要求小组中至少有 $1$ 名男生和$1$ 名女生，则不同的选法共有 ( ) 种。
- $112$
- $168$
- $224$
- $288$
**第 2 题** 在杨辉三角中，从第 $0$ 行开始计数，第 $10$ 行的所有数之和为 ( )。
- $512$
- $1024$
- $2048$
- $4096$
**第 3 题** 下列代码实现了快速幂算法，其时间复杂度为 ( )。
```cpp
01 long long fastPow(long long b, long long e, long long mod) {
02 long long result = 1;
03 while (e > 0) {
04 if (e & 1)
05 result = result * b % mod;
06 b = b * b % mod;
07 e >>= 1;
08 }
09 return result;
10 }
```
- $O(logb)$
- $O(loge)$
- $O(logmod)$
- $O(e)$
**第 4 题** 从 $5$ 本不同的数学书和$4$ 本不同的物理书中选取 $3$ 本书，要求至少包含 $1$ 本数学书，则不同的选法有 ( ) 种。
- $60$
- $74$
- $80$
- $84$
**第 5 题** 在二叉搜索树($BST$)中，若中序遍历的序列为 `{1,2,3,4，5}`，且先序遍历的第一个序列元素为 $3$，则下列说法正确的是 ( )。
- 该树一定是一棵完全二叉树
- 元素 $4$ 和 $5$ 不可能是兄弟节点
- 元素 $1$ 所在节点的深度可能大于$3$(根节点深度为 $1$)
- 元素 $2$ 一定是元素 $1$ 的父节点
**第 6 题** 在一个有向带权图中，使用 `Dijkstra` 算法求单源最短路时，若使用优先队列(小根堆)优化，其时间复杂度为 ( )
- $O(V^2)$
- $O(V \cdot E)$
- $O((V+E)logV)$
- $O(V^2logV)$
**第 7 题** 对于含 $n$ 个顶点 ($n≥2$) 的连通加权有向图，若图中不存在负权环，则任意两点之间的最短路径(简单路径) 最多包含 ( ) 条边。
- $n$
- $n-1$
- $n+1$
- 无法确定，取决于图的具体边数
**第 8 题** 在使用 $Floyd$ 算法求任意两点间最短路径时，时间复杂度为$O(V^3)$。若在某次算法执行前，已经用 $Dijkstra$ 算法正确求出了所有点对的最短路并存入了 $dist$ 数组。如果此时继续对该 $dist$ 数组执行一次完整的 $Floyd$ 算法过程(无任何提前终止)，执行完毕后 $dist$ 数组内的值( )
- 会发生改变，因为 $Floyd$ 又做了一次松弛
- 不会发生改变
- 可能变大，因为未针对已有最短路优化
- 可能在某些负权图中陷入死循环
**第 9 题** 关于图论中的最短路径算法，下列说法中严格正确的是 ( )。
- $Dijkstra$ 算法能够高效处理包含负权边的有向图。
- $Floyd$ 算法可以求出任意两点间的最短路径，且允许图中存在负权边(但不能有负权环)
- 单源最短路径算法无法用于无向图，无向图只能通过 $BFS$ 求解。
- $Djkstra$ 算法的每一步必定从当前未访问的节点中，选取距离起始点最远的节点进行松弛操作。
**第 10 题** 有 $6$ 个人排成一排照相，其中甲、乙两人必须相邻，且丙不能站在排头的不同排法有 ( ) 种。
- $120$
- $144$
- $192$
- $240$
**第 11 题** 下列代码试图实现 $Floyd$ 算法求所有点对之间的最短路径，横线处应填入 ( )
```cpp
01 void floyd(int n, int dist[][MAXN]) {
02 for (int k = 0; k < n; k++)
03 for (int i = 0; i < n; i++)
04 for (int j = 0; j < n; j++)
05 if (__________) // 在此处填入选项
06 dist[i][j] = dist[i][k] + dist[k][j];
07 }
```
- `dist[i][k] + dist[k][j] < dist[i][j]`
- `dist[i][k] != INF && dist[k][j] != INF`
- `dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]`
- `dist[i][j] == INF`
**第 12 题** 用数字 $0$、$1$、$2$、$3$、$4$ 组成无重复数字的五位偶数，共有( )个。
- $48$
- $60$
- $72$
- $96$
**第 13 题** 在一个无向带权图中，若使用 $Prim$ 算法从顶点 $0$ 开始构造最小生成树(边权均为正整数，且`graph[u][v]==0` 表示无边)，下列代码中横线处应填入 ( )
```cpp
01 int prim(vector>& graph, int n) {
02 vector inMST(n, false);
03 vector minEdge(n, INT_MAX);
04 minEdge[0] = 0;
05 int result = 0;
06 for (int i = 0; i < n; i++) {
07 int u = -1;
08 for (int j = 0; j < n; j++)
09 if (!inMST[j] && (u == -1 || minEdge[j] < minEdge[u]))
10 u = j;
11 inMST[u] = true;
12 result += minEdge[u];
13 for (int v = 0; v < n; v++)
14 if (__________) // 在此处填入选项
15 minEdge[v] = graph[u][v];
16 }
17 return result;
18 }
```
- `graph[u][v] && !inMST[v] && graph[u][v] < minEdge[v]`
- `!inMST[v] && graph[u][v] < minEdge[v]`
- `graph[u][v] > 0 && !inMST[v]`
- `!inMST[v] && minEdge[v] > 0`
**第 14 题** 已知三个点$A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)$ 在平面直角坐标系中的坐标。下列 $C++$ 表达式中，在精度误差范围 1e-8 内 能正确计算判断这三个点是三点共线的表达式是 ( )。
- `(x2-x1)/(y2-y1) == (x3-x1)/(y3-y1)`
- `(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1) == 0`
- `fabs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)) < 1e-8`
- `fabs((x2-x1)/(y2-y1)-(x3-x1)/(y3-y1)) < 1e-8`
**第 15 题** 在 $64$ 位操作系统下($LP64/LLP64$ 模型)，下面代码的输出结果是 ( )
```cpp
01 #include
02 using namespace std;
03
04 int main() {
05 int a[4] = {1, 2, 3, 4};
06 int (*p)[4] = &a;
07 int *q = a;
08
09 cout << sizeof(a) << " ";
10 cout << sizeof(p) << " ";
11 cout << sizeof(p + 1) << " ";
12 cout << sizeof(q + 1) << " ";
13 cout << (p + 1) - p << " ";
14 cout << (q + 1) - q << endl;
15 }
```
- `16 8 8 8 1 1`
- `16 8 16 8 1 1`
- `16 8 8 4 4 1`
- `16 8 8 8 4 1`
## 二、判断题（每题 2 分，共 20 分）
**第 1 题** 在 `C++` 中，若结构体中包含一个 `static` 成员变量，则该变量的存储空间属于结构体对象的一部分。
- 正确
- 错误
**第 2 题** 对于任意正整数 $n$，二项式 $(a+6)^n$ 展开式中各项的二项式系数之和等于 $2^n$。
- 正确
- 错误
**第 3 题** 在 `C++` 中，若函数参数类型为 `const int&`，则该参数既可以绑定左值，也可以绑定右值。
- 正确
- 错误
**第 4 题** 若一个无向图的最小生成树唯一，则图中所有边权必定各不相同。
- 正确
- 错误
**第 5 题** 使用快速排序对$n$ 个元素进行排序时，无论最好、最坏还是平均情况，时间复杂度均为$O(nlogn)$。
- 正确
- 错误
**第 6 题** 若一个图中所有顶点的度数为偶数，则一定存在欧拉回路。
- 正确
- 错误
**第 7 题** 使用倍增法预处理区间最值问题时，预处理的时间复杂度为O(nlogn)，查询的时间复杂度为 $O(1)$。
- 正确
- 错误
**第 8 题** 如果将一个连通无向图 $G_1$ 中所有边的权值都统一增加同一个正整数常数 $C$，形成图 $G_2$。则$G_1$ 的最小生成树中每条边在 $G_2$ 中对应的边组成的树，一定是 $G_2$ 的最小生成树。
- 正确
- 错误
**第 9 题** 在图论算法中，$Kruskal$ 算法和 $Prim$ 算法都可以用来求解最小生成树，且这两者的贪心策略无论在任何连通无向图上求得的最小生成树总边权和必定相同。
- 正确
- 错误
**第 10 题** 在动态规划问题中，“状态转移方程+递推”和“递归+记忆化搜索”通常是解决同一问题的两种不同实现方式，它们的时间复杂度总是相同的。
- 正确
- 错误