5318：[GESP202506八级] 客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 一、单选题（每题 2 分，共 30 分）
**第 1 题** 一间的机房要安排 $6$ 名同学进行上机考试，座位共 $2$ 行 $3$ 列。考虑到在座位上很容易看到同一行的左右两侧的屏幕，安排中间一列的同学做 $A$ 卷，左右两列的同学做 $B$ 卷。请问共有多少种排座位的方案？()
- $720$
- $90$
- $48$
- $15$
**第 2 题** 又到了毕业季，学长学姐们都在开心地拍毕业照。现在有 $3$ 位学长、$3$ 位学姐希望排成一排拍照，要求男生不相邻、女生不相邻。请问共有多少种拍照方案？()
- $720$
- $72$
- $36$
- $2$
**第 3 题** 下列关于 `C++` 类和对象的说法，错误的是()
- 通过语句 `const int x = 5;` 定义了一个对象 $x$。
- 通过语句 `std::string t = "12345";` 定义了一个对象 $t$。
- 通过语句 `void (*fp)() = NULL;` 定义了一个对象 $fp$。
- 通过语句 `class MyClass;` 定义了一个类 $MyClass$。
**第 4 题** 关于生成树的说法，错误的是()
- 一个无向连通图，一定有生成树。
- $n$ 个顶点的无向图，其生成树要么不存在，要么一定包含 $n-1$ 条边。
- $n$ 个顶点、$n-1$ 条边的无向图，不可能有多颗生成树。
- $n$ 个顶点、$n-1$ 条边的无向图，它本身就是自己的生成树。
**第 5 题** 一对夫妻生男生女的概率相同。这对夫妻希望儿女双全。请问这对夫妻生下两个孩子时，实现儿女双全的概率是多少？()
- $\frac{2}{3}$
- $\frac{1}{3}$
- $\frac{1}{2}$
- $\frac{1}{4}$
**第 6 题** 已定义变量 `double a, b;`，下列哪个表达式可以用来判断一元二次方程 $x^2 + ax + b = 0$ 是否有实根?()
- `4 * b - a * a < 0`
- `4 * b <= a * a`
- `a * a - 4 * b`
- `b * 4 - a * a`
**第 7 题** $n$ 个结点的二叉树，执行广度优先搜索的平均时间复杂度是()
- $O(logn)$
- $O(nlogn)$
- $O(n)$
- $O(2^n)$
**第 8 题** 以下关于动态规划的说法中，错误的是()
- 动态规划方法通常能够列出递推公式。
- 动态规划方法的时间复杂度通常为状态的个数。
- 动态规划方法有递推和递归两种实现形式。
- 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。
**第 9 题** 下面的 `sum_digit` 函数试图求出从 $1$ 到 $n$ (包含 $1$ 和 $n$) 的数中，包含数字 $d$ 的个数。该函数的时间复杂度为()
```cpp
01 #include
02 int count_digit(int n, char d) {
03 int cnt = 0;
04 std::string s = std::to_string(n);
05 for (int i = 0; i < s.length(); i++)
06 if (s[i] == d)
07 cnt++;
08 return cnt;
09 }
10 int sum_digit(int n, char d) {
11 int sum = 0;
12 for (int i = 1; i <= n; i++)
13 sum += count_digit(i, d);
14 return sum;
15 }
```
- $O(nlogn)$
- $O(n)$
- $O(logn)$
- $O(n^2)$
**第 10 题** 下面程序的输出为()
```cpp
01 #include
02 const int N = 10;
03 int ch[N][N][N];
04 int main() {
05 for (int x = 0; x < N; x++)
06 for (int y = 0; y < N; y++)
07 for (int z = 0; z < N; z++)
08 if (x == 0 && y == 0 && z == 0)
09 ch[x][y][z] = 1;
10 else {
11 if (x > 0)
12 ch[x][y][z] += ch[x - 1][y][z];
13 if (y > 0)
14 ch[x][y][z] += ch[x][y - 1][z];
15 if (z > 0)
16 ch[x][y][z] += ch[x][y][z - 1];
17 }
18 std::cout << ch[1][2][3] << std::endl;
19 return 0;
20 }
```
- $60$
- $20$
- $15$
- $10$
**第 11 题** 下面 `count_triple` 函数的时间复杂度为()
```cpp
01 int gcd(int a, int b) {
02 if (a == 0)
03 return b;
04 return gcd(b % a, a);
05 }
06 int count_triple(int n) {
07 int cnt = 0;
08 for (int v = 1; v * v * 4 <= n; v++)
09 for (int u = v + 1; u * (u + v) * 2 <= n; u += 2)
10 if (gcd(u, v) == 1) {
11 int a = u * u - v * v;
12 int b = u * v * 2;
13 int c = u * u + v * v;
14 cnt += n / (a + b + c);
15 }
16 return cnt;
17 }
```
- $O(n)$
- $O(n^2)$
- $O(nlogn)$
- $O(n^2logn)$
**第 12 题** 下面 $quick_sort$ 函数试图实现快速排序算法，两处横线处分别应该填入的是()
```cpp
01 void swap(int & a, int & b) {
02 int temp = a; a = b; b = temp;
03 }
04 int partition(int a[], int l, int r) {
05 int pivot = a[l], i = l + 1, j = r;
06 while (i <= j) {
07 while (i <= j && a[j] >= pivot)
08 j--;
09 while (i <= j && a[i] <= pivot)
10 i++;
11 if (i < j)
12 swap(a[i], a[j]);
13 }
14 ________; // 在此处填入选项
15 return ________; // 在此处填入选项
16 }
17 void quick_sort(int a[], int l, int r) {
18 if (l < r) {
19 int pivot = partition(a, l, r);
20 quick_sort(a, l, pivot - 1);
21 quick_sort(a, pivot + 1, r);
22 }
23 }
```
- ```cpp
01 swap(a[l], a[i])
02 i
```
- ```cpp
01 swap(a[l], a[j])
02 i
```
- ```cpp
01 swap(a[l], a[i])
02 j
```
- ```cpp
01 swap(a[l], a[j])
02 j
```
**第 13 题** 下面 $LIS$ 函数试图求出最长上升子序列的长度，横线处应该填入的是()
```cpp
01 int max(int a, int b) {
02 return (a > b) ? a : b;
03 }
04 int LIS(vector & nums) {
05 int n = nums.size();
06 if (n == 0)
07 return 0;
08 vector dp(n, 1);
09 int maxLen = 1;
10 for (int i = 1; i < n; i++) {
11 for (int j = 0; j < i; j++)
12 if (nums[j] < nums[i])
13 ________; // 在此处填入选项
14 maxLen = max(maxLen, dp[i]);
15 }
16 return maxLen;
17 }
```
- `dp[j] = max(dp[j] + 1, dp[i])`
- `dp[j] = max(dp[j], dp[i] + 1)`
- `dp[i] = max(dp[i] + 1, dp[j])`
- `dp[i] = max(dp[i], dp[j] + 1)`
**第 14 题** 下面 $LIS$ 函数试图求出最长上升子序列的长度，其时间复杂度为()
```cpp
01 #define INT_MIN (-1000)
02 int LIS(vector & nums) {
03 int n = nums.size();
04 vector tail;
05 tail.push_back(INT_MIN);
06 for (int i = 0; i < n; i++) {
07 int x = nums[i], l = 0, r = tail.size();
08 while (l < r) {
09 int mid = (l + r) / 2;
10 if (tail[mid] < x)
11 l = mid + 1;
12 else
13 r = mid;
14 }
15 if (r == tail.size())
16 tail.push_back(x);
17 else
18 tail[r] = x;
19 }
20 return tail.size() - 1;
21 }
```
- $O(logn)$
- $O(n)$
- $O(nlogn)$
- $O(n^2)$
**第 15 题** 下面的程序使用邻接矩阵表达的带权无向图，则从顶点 $0$ 到顶点 $3$ 的最短距离为()
```cpp
01 int weight[4][4] = {
02 { 0, 5, 8, 10},
03 { 5, 0, 1, 7},
04 { 8, 1, 0, 3},
05 {10, 7, 3, 0}};
```
- $9$
- $10$
- $11$
- $12$
## 二、判断题（每题 2 分，共 20 分）
**第 1 题** `C++` 语言中，表达式 `9 | 12` 的结果类型为 `int`、值为 $13$。
- 正确
- 错误
**第 2 题** `C++` 语言中，访问数据发生下标越界时，总是会产生运行时错误，从而使程序异常退出。
- 正确
- 错误
**第 3 题** 对 $n$ 个元素的数组进行归并排序，最差情况的时间复杂度为 $O(nlogn)$。
- 正确
- 错误
**第 4 题** $5$ 个相同的红球和 $4$ 个相同的蓝球排成一排，要求每个蓝球的两侧都必须至少有一个红球，则一共有 $15$ 种排列方案。
- 正确
- 错误
**第 5 题** 使用 `math.h` 或 `cmath` 头文件中的函数，表达式 $log(8)$ 的结果类型为 `double`、值约为 $3$。
- 正确
- 错误
**第 6 题** `C++` 是一种面向对象编程语言，$C$ 则不是。继承是面向对象三大特性之一，因此，使用 $C$ 语言无法实现继承。()
- 正确
- 错误
**第 7 题** $n$ 个顶点的无向完全图，有 $n^{n-2}$ 棵生成树。
- 正确
- 错误
**第 8 题** 已知三个 $double$ 类型的变量 $a$、 $b$ 和 $theta$ 分别表示一个三角形的两条边长及二者的夹角 (弧度），则三角形的周长可以通过表达式 `sqrt(a * a + b * b - 2 * a * b * cos(theta))` 求得。
- 正确
- 错误
**第 9 题** 有 $V$ 个顶点、$E$ 条边的图的深度优先搜索遍历时间复杂度为 $O(V+E)$。
- 正确
- 错误
**第 10 题** 从 $32$ 名学生中选出 $4$ 人分别担任班长、副班长、学习委员和组织委员，老师要求班级综合成绩排名最后的 $4$ 名学生不得参选班长或学习委员 (仍可以参选副班长和组织委员），则共有 $P(30, 4)$ 种不同的选法。
- 正确
- 错误