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

$1、$ 一间的机房要安排6名同学进行上机考试，座位共2行3列。考虑到在座位上很容易看到同一行的左右两侧的屏幕，安排中间一列的同学做A卷，左右两列的同学做B卷。请问共有多少种排座位的方案？（） {{ select(1) }}

• 720
• 90
• 48
• 15

$2、$ 又到了毕业季，学长学姐们都在开心地拍毕业照。现在有3位学长、3位学姐希望排成一排拍照，要求男生不相邻、女生不相邻。请问共有多少种拍照方案？（） {{ select(2) }}

• 720
• 72
• 36
• 2

$3、$ 下列关于 C++ 类和对象的说法，错误的是（）。 {{ select(3) }}

• 通过语句 const int x = 5; 定义了一个对象 x。
• 通过语句 std::string t = "12345"; 定义了一个对象 t。
• 通过语句 void (*fp)() = NULL; 定义了一个对象 fp。
• 通过语句 class MyClass; 定义了一个类 MyClass。

$4、$ 关于生成树的说法，错误的是（）。 {{ select(4) }}

• 一个无向连通图，一定有生成树。
• n个顶点的无向图，其生成树要么不存在，要么一定包含 n-1 条边。
• n个顶点、n-1 条边的无向图，不可能有多颗生成树。
• n个顶点、n-1 条边的无向图，它本身就是自己的生成树。

$5、$ 一对夫妻生男生女的概率相同。这对夫妻希望儿女双全。请问这对夫妻生下两个孩子时，实现儿女双全的概率是多少？（） {{ select(5) }}

• $\frac23$
• $\frac13$
• $\frac12$
• $\frac14$

$6、$ 已定义变量 double a, b;，下列哪个表达式可以用来判断一元二次方程 $x^2 + a x + b$ = 0 是否有实根？（） {{ select(6) }}

• $4*b - a*a < 0$
• $4*b <= a*a$
• $a*a - 4*b$
• $b*4 - a*a$

$7、$ n个结点的二叉树，执行广度优先搜索的平均时间复杂度是（）。 {{ select(7) }}

• $O(log n)$
• $O(n log n)$
• $O(n)$
• $O(2^n)$

$8、$ 以下关于动态规划的说法中，错误的是（）。 {{ select(8) }}

• 动态规划方法通常能够列出递推公式
• 动态规划方法的时间复杂度通常为状态的个数
• 动态规划方法有递推和递归两种实现形式
• 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当

$9、$ 下列的 sum_digit 函数试图求出从 1 到 n（包含 1 和 n）的数中，包含数字 d 的个数。该函数的时间复杂度为（）。

01 #include <string>
02 
03 int count_digit(int n, char d) {
04     int cnt = 0;
05     std::string s = std::to_string(n);
06     for (int i = 0; i < s.length(); i++)
07         if (s[i] == d)
08             cnt++;
09     return cnt;
10 }
11 
12 int sum_digit(int n, char d) {
13     int sum = 0;
14     for (int i = 1; i <= n; i++)
15         sum += count_digit(i, d);
16     return sum;
17 }

{{ select(9) }}

• $O(n log n)$
• $O(n)$
• $O(log n)$
• $O(n^2)$

$10、$ 下列程序的输出为（）。

01 #include <iostream>
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 }

{{ select(10) }}

• 60
• 20
• 15
• 10

$11、$ 下列 count_triple 函数的时间复杂度为（）。

01 int gcd(int a, int b) {
02     if (a == 0) return b;
03     return gcd(b % a, a);
04 }
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 }

{{ select(11) }}

• $O(n)$
• $O(n^2)$
• $O(n log n)$
• $O(n^2 log n)$

$12、$ 下列 quick_sort 函数试图实现快速排序算法，两处横线处分别应该填入的是（）。

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 }

{{ select(12) }}

• swap(a[l], a[i]); i;
• swap(a[l], a[j]); i;
• swap(a[l], a[i]); j;
• swap(a[l], a[j]); j;

$13、$ 下列 LIS 函数试图求出最长上升子序列的长度，横线处应该填入的是（）。

01 int max(int a, int b) {
02     return (a > b) ? a : b;
03 }
04 int LIS(vector<int> & nums) {
05     int n = nums.size();
06     if (n == 0)
07         return 0;
08     vector<int> 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                 dp[i] = max(dp[i], dp[j] + 1); // 在此处填入选项
14         maxLen = max(maxLen, dp[i]);
15     }
16     return maxLen;
17 }

{{ select(13) }}

• 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 函数试图求出最长上升子序列的长度，其时间复杂度为（）。

01 #define INT_MIN (-1000)
02 int LIS(vector<int> &nums) {
03     int n = nums.size();
04     vector<int> 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 }

{{ select(14) }}

• $O(log n)$
• $O(n)$
• $O(n log n)$
• $O(n^2)$

$15、$ 下列选项中，哪个不可能是下图的广度优先遍历序列（）。

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}
06 };

{{ select(15) }}

• 9
• 10
• 11
• 12

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

$16、$ C++ 语言中，表达式 9 & 12 的结果类型为 int、值为 13。
{{ select(16) }}

• 正确
• 错误

$17、$ C++ 语言中，访问数据发生下标越界时，总是会产生运行时错误，从而使程序异常退出。
{{ select(17) }}

• 正确
• 错误

$18、$ 对 n 个元素的数组进行快速排序，最差情况的时间复杂度为 $O(n log n)$。
{{ select(18) }}

• 正确
• 错误

$19、$ 5个相同的红球和4个相同的蓝球排成一排，要求每个蓝球的两侧都必须至少有一个红球，则一共有15种排列方案。 {{ select(19) }}

• 正确
• 错误

$20、$ 使用 math.h 或 cmath 头文件中的函数，表达式 log(8) 的结果类型为 double 、值约为 3 。

{{ select(20) }}

• 正确
• 错误

$21、$ C++是一种面向对象编程语言，C则不是。继承是面向对象三大特性之一，因此，使用C语言无法实现继承。 {{ select(21) }}

• 正确
• 错误

$22、$ 题 $n$个顶点的无向完全图，有 $n^{n-2}$棵生成树。

{{ select(22) }}

• 正确
• 错误

$23、$ 已知三个 double 类型的变量 a 、 b 和 theta 分别表示一个三角形的两条边长及二者的夹角（弧度），则三角形的周长可以通过表达式 sqrt(a * a + b * b - 2 * a * b * cos(theta)) 求得。
{{ select(23) }}

• 正确
• 错误

$24、$ 有 $V$个顶点、 条边的图的深度优先搜索遍历时间复杂度为 $O(V+E)$。 {{ select(24) }}

• 正确
• 错误

$25、$ 从32名学生中选出4人分别担任班长、副班长、学习委员和组织委员，老师要求班级综合成绩排名最后的4名学生不得参选班长或学习委员（仍可以参选副班长和组织委员），则共有 $P(30,4)$种不同的选法。 {{ select(25) }}

• 正确
• 错误