5293：[GESP202509八级] 客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：4
解决：0
题目描述
## 一、单选题（每题 2 分，共 30 分）
**第 1 题** 小杨想点一杯奶茶外卖，但还差 $5$ 元起送。于是，小杨决定点一些小料。可选的小料包括：珍珠 $1$ 元、椰果 $2$ 元、奶冻 $3$ 元、奶盖 $4$ 元。每种小料最多点 $1$ 份。请问共有多少种满足起送条件的点小料方案？
- $16$
- $10$
- $9$
- $7$
**第 2 题** 小杨和小刘是好朋友，她们在逛商场时发现新设置的大头贴自拍机，于是决定一起拍一组照片。一组照片包括 $4$ 张，这 $4$ 张照片没有顺序区分。拍每张照片时，可以选择有相框或无相框、两人可以分别选择有头饰或无头饰、还可以从 $2$ 种位置 (小杨在左，或小刘在左) 中选出一种。她们不希望一组照片中出现完全相同的相框、头饰、位置的组合。请问一组照片共有多少种不同的方案？
- $1820$
- $70$
- $24$
- $16$
**第 3 题** 下列关于 `C++` 类的说法，错误的是 ( )
- 派生类对象占用的内存总是不小于基类对象。
- 派生类可以不实现基类的虚函数。
- 如果一个类包含纯虚函数，则它不能包含成员变量。
- 如果一个类包含纯虚函数，则不能用它定义对象。
**第 4 题** 下列关于树和图的说法，错误的是 ( )
- 每个连通图都存在生成树。
- 每个存在生成树的有向图，都一定是强连通的。
- 保留树的所有节点，并把树的每个节点指向其父节点，则可以将树转换为一个有向弱连通图。
- 保留树的所有节点，并把树的每个节点指向其子节点，则可以将树转换为一个有向无环图。
**第 5 题** 一对夫妻生男生女的概率相同。这对夫妻希望儿女双全。请问这对夫妻生下三个孩子时，实现儿女双全的概率是多少？( )
- $\frac{1}{4}$
- $\frac{1}{2}$
- $\frac{1}{4}$
- $\frac{7}{8}$
**第 6 题** 二项式 $(x+y)^6$ 的展开式中 $x^2y^4$ 项的系数是 ( )
- $720$
- $120$
- $20$
- $15$
**第 7 题** 对一个包含 $V$ 个顶点、$E$ 条边的图，执行广度优先搜索，其最优时间复杂度是( )
- $O(V)$
- $O(V+E)$
- $O(V^2)$
- $O(E)$
**第 8 题** 以下关于贪心法和动态规划的说法中，错误的是 ( )
- 动态规划能解决大部分多阶段决策问题。
- 对特定的问题，贪心法不一定适用。
- 当特定的问题适用贪心法时，通常比动态规划的时间复杂度更低。
- 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。
**第 9 题** 下面程序的输出为 ( )
```cpp
01 #include
02 using namespace std;
03 int main() {
04 int N = 15, cnt = 0;
05 for (int x = 1; x + x + x <= N; x++)
06 for (int y = x; x + y + y <= N; y++)
07 for (int z = y; x + y + z <= N; z++)
08 cnt++;
09 cout << cnt << endl;
10 return 0;
11 }
```
- $45$
- $102$
- $174$
- $3375$
**第 10 题** 下面程序的时间复杂度为 ( )
```cpp
01 int primes[MAXP], num = 0;
02 bool isPrime[MAXN] = {false};
03 void sieve() {
04 for (int n = 2; n <= MAXN; n++) {
05 if (!isPrime[n])
06 primes[num++] = n;
07 for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
08 isPrime[n * primes[i]] = true;
09 if (n % primes[i] == 0)
10 break;
11 }
12 }
13 }
```
- $O(nlogn)$
- $O(nloglogn)$
- $O(n)$
- $O(log n)$
**第 11 题** 下列 `Dijkstra` 算法，假设图 `graph` 中顶点数 `v`、边数 `e`，则程序的时间复杂度为 ( )
```cpp
01 typedef struct Edge {
02 int in, out; // 从下标in顶点到下标out顶点的边
03 int len; // 边长度
04 struct Edge * next;
05 } Edge;
06 // v：顶点个数，graph：出边邻接表，start：起点下标，dis：输出每个顶点的最短距离
07 void dijkstra(int v, Edge * graph[], int start, int * dis) {
08 const int MAX_DIS = 0x7fffff;
09 for (int i = 0; i < v; i++)
10 dis[i] = MAX_DIS;
11 dis[start] = 0;
12 int * visited = new int[v];
13 for (int i = 0; i < v; i++)
14 visited[i] = 0;
15 visited[start] = 1;
16 for (int t = 0; ; t++) {
17 int min = MAX_DIS, minv = -1;
18 for (int i = 0; i < v; i++) {
19 if (visited[i] == 0 && min > dis[i]) {
20 min = dis[i];
21 minv = i;
22 }
23 }
24 if (minv < 0)
25 break;
26 visited[minv] = 1;
27 for (Edge * e = graph[minv]; e != NULL; e = e->next)
28 if (dis[e->out] > e->len)
29 dis[e->out] = e->len;
30 }
31 delete[] visited;
32 }
```
- $O(v^2)$
- $O(vlogv + e)$
- $O((v + e)logv)$
- $O(v+e)$
**第 12 题** 下面 `count_triple` 函数的时间复杂度为 ( )。
```cpp
01 int gcd(int m, int n) {
02 if (m == 0) return n;
03 return gcd(n % m, m);
04 }
05 int count_triple(int n) {
06 int cnt = 0;
07 for (int v = 1; v * v * 4 <= n; v++)
08 for (int u = v + 1; u * (u + v) * 2 <= n; u += 2)
09 if (gcd(u, v) == 1) {
10 int a = u * u – v * v;
11 int b = u * v * 2;
12 int c = u * u + v * v;
13 cnt += n / (a + b + c);
14 }
15 return cnt;
16 }
```
- $O(n^2)$
- $O(n^2logn)$
- $O(n)$
- $O(nlogn)$
**第 13 题** 下面 `merge_sort` 函数试图实现归并排序算法，横线处应该填入的是 ( )
```cpp
01 #include
02 using namespace std;
03 void merge_sort(vector & arr, int left, int right) {
04 if (right – left <= 1)
05 return;
06
07 int mid = (left + right) / 2;
08 merge_sort(________); // 在此处填入选项
09 merge_sort(________); // 在此处填入选项
10
11 vector temp(right – left);
12 int i = left, j = mid, k = 0;
13 while (i < mid && j < right)
14 if (arr[i] <= arr[j])
15 temp[k++] = arr[i++];
16 else
17 temp[k++] = arr[j++];
18 while (i < mid)
19 temp[k++] = arr[i++];
20 while (j < right)
21 temp[k++] = arr[j++];
22 for (i = left, k = 0; i < right; ++i, ++k)
23 arr[i] = temp[k];
24 }
```
- ```cpp
01 arr, left, mid
02 arr, mid, right
```
- ```cpp
01 arr, left, mid + 1
02 arr, mid + 1, right
```
- ```cpp
01 arr, left, mid
02 arr, mid + 1, right
```
- ```cpp
01 arr, left, mid + 1
02 arr, mid + 1, right + 1
```
**第 14 题** 下面 `Prim` 算法程序中，横线处应该填入的是 ( )
```cpp
01 #include
02 #include
03 #include
04 using namespace std;
05 int prim(vector> & graph, int n) {
06 vector key(n, INT_MAX);
07 vector parent(n, -1);
08 key[0] = 0;
09 for (int i = 0; i < n; i++) {
10 int u = min_element(key.begin(), key.end()) - key.begin();
11 if (key[u] == INT_MAX)
12 break;
13 for (int v = 0; v < n; v++) {
14 if (__________) { // 在此处填入选项
15 key[v] = graph[u][v];
16 parent[v] = u;
17 }
18 }
19 }
20 int sum = 0;
21 for (int i = 0; i < n; i++) {
22 if (parent[i] != -1) {
23 cout << "Edge: " << parent[i] << " - " << i << " Weight: " << key[i] << endl;
24 sum += key[i];
25 }
26 }
27 return sum;
28 }
29 int main() {
30 int n, m;
31 cin >> n >> m;
32 vector> graph(n, vector(n, 0));
33 for (int i = 0; i < m; i++) {
34 int u, v, w;
35 cin >> u >> v >> w;
36 graph[u][v] = w;
37 graph[v][u] = w;
38 }
39 int result = prim(graph, n);
40 cout << "Total weight of the minimum spanning tree: " << result << endl;
41 return 0;
42 }
```
- ```cpp
01 graph[u][v] >= 0 && key[v] > graph[u][v]
```
- ```cpp
01 graph[u][v] <= 0 && key[v] > graph[u][v]
```
- ```cpp
01 graph[u][v] == 0 && key[v] > graph[u][v]
```
- ```cpp
01 graph[u][v] != 0 && key[v] > graph[u][v]
```
**第 15 题** 下面的程序使用出边邻接表表达的带权无向图，则从顶点 $0$ 到顶点 $3$ 的最短距离为 ( )
```cpp
01 #include
02 using namespace std;
03 class Edge {
04 public:
05 int dest;
06 int weight;
07 Edge(int d, int w) : dest(d), weight(w) {}
08 };
09 class Graph {
10 private:
11 int num_vertex;
12 vector> vve;
13 public:
14 Graph(int v) : num_vertex(v), vve(v) {}
15 void addEdge(int s, int d, int w) {
16 vve[s].emplace_back(d, w);
17 vve[d].emplace_back(s, w)
18 }
19 };
20 int main() {
21 Graph g(4);
22 g.addEdge(0, 1, 8);
23 g.addEdge(0, 2, 5);
24 g.addEdge(1, 2, 1);
25 g.addEdge(1, 3, 3);
26 g.addEdge(2, 3, 7);
27 return 0;
28 }
```
- $12$
- $11$
- $10$
- $9$
## 二、判断题（每题 2 分，共 20 分）
**第 1 题** `C++` 语言中，表达式 `'9' ^ 3` 的结果值为 `'999'`。
- 正确
- 错误
**第 2 题** 下列 `C++` 语言代码，能够安全地输出 `arr[5]` 的值。
```cpp
01 int n = 5;
02 int arr[n] = {1, 2, 3};
03 std::cout << arr[5];
```
- 正确
- 错误
**第 3 题** 对 $n$ 个元素的数组进行排序，最差情况的时间复杂度为 $O(n^2)$。
- 正确
- 错误
**第 4 题** 有 $4$ 个红球、$3$ 个蓝球和 $2$ 个绿球排成一排 (相同色球视为完全相同)，则不同的排列方案数为 $1260$ 种。
- 正确
- 错误
**第 5 题** 使用 `math.h` 或 `cmath` 头文件中的函数，对于 `int` 类型的变量 `x`，表达式 `fabs(x)` 和 `sqrt(x * x)` 的结果总是近似相等的。
- 正确
- 错误
**第 6 题** 运算符重载是 `C++` 语言静态多态的一种典型体现，而使用 `C` 语言则无法实现运算符重载。
- 正确
- 错误
**第 7 题** 存在一个简单无向图满足：顶点数为 $6$，边数为 $8，6$ 个顶点的度数分别为`3、3、3、3、2、2`。
- 正确
- 错误
**第 8 题** 已知两个 `double` 类型的变量 $r$ 和 $theta$ 分别表示一个扇形的圆半径及圆心角 (弧度)，则扇形的周长可以通过表达式 `(2 + theta) * r` 求得。
- 正确
- 错误
**第 9 题** `Dijkstra` 算法的时间复杂度为 $O(V^2)$，其中 $V$ 为图中顶点的数量。
- 正确
- 错误
**第 10 题** 从 $32$ 名学生中选出 $2$ 人分别担任男生班长和女生班长 (男生班长必须是男生，女生班长必须是女生)，则共有 `C(32, 2)/3` 种不同的选法。
- 正确
- 错误