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

1. 小杨要从 $\tt A$ 城到 $\tt B$ 城，又想顺路游览一番。他有两个选项：$1$、坐高铁路到 $\tt C$ 城游览，再坐高铁或飞机到 $\tt B$ 城；$2$、坐船到 $\tt D$ 城游览，再坐船、高铁或飞机到 $\tt B$ 城。请问小杨从 $\tt A$ 城到 $\tt B$ 城共有几种交通方案可以选择？（ ）

{{ select(1) }}

• $2$
• $3$
• $5$
• $6$

2. 以下哪个函数声明是符合语法的，且在调用时可以将二维数组的名字作为实际参数传递给形式参数 $a$？（ ）

{{ select(2) }}

• void QuickSort(int a[][10], int n);
• void QuickSort(int a[5][], int m);
• void QuickSort(int a[][], int n, int m);
• void QuickSort(int ** a, int n, int m);

3. 下面有关 $\tt C$++ 类和对象的说法，错误的是（ ）。

{{ select(3) }}

• 对象的生命周期开始时，会执行构造函数
• 对象的生命周期结束时，会执行析构函数
• 类的析构函数可以为虚函数
• 类的构造函数可以为虚函数

4. 使用邻接矩阵表达 $n$ 个顶点的有向图，则该矩阵的大小为（ ）。

{{ select(4) }}

• $n \times (n+1)$
• $n \times n$
• $n \times (n-1)$
• $n \times (n-1)/2$

5. $5$ 位同学排队，其中一位同学不能排在第一，则共有多少种可能的排队方式？（ ）

{{ select(5) }}

• $5$
• $24$
• $96$
• $120$

6. 一个无向图包含 $n$ 个顶点，则其最小生成树包含多少条边？（ ）

{{ select(6) }}

• $n-1$
• $n$
• $n+1$
• 最小生成树可能不存在

7. 已知三个 $\tt double$ 类型的变量 $a$、$b$ 和 $\tt theta$ 分别表示一个三角形的两条边长及二者的夹角（弧度），则下列哪个表达式可以计算这个三角形的面积？（ ）

{{ select(7) }}

• a * b * sin(theta) / 2
• (a + b) * sin(theta) / 2
• a * b * cos(theta) / 2
• sqrt(a * a + b * b - 2 * a * b * cos(theta))

8. 对有 $n$ 个元素的二叉排序树进行中序遍历，其时间复杂度是（ ）。

{{ select(8) }}

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

9. 假设输入参数 $m$ 和 $n$ 满足，则下面程序的最差情况的时间复杂度为（ ）。

   int gcd(int m, int n) {
   	while (m > 0) {
   		int t = m;
   		m = n % m;
   		n = t;
   	}
   
   	return n;
   }
   

{{ select(9) }}

• $O(\log n)$
• $O(n)$
• $O(n \times m)$
• $O(m \times \log n)$

10. 下面程序的时间复杂度为（ ）。

    long long power_mod(long long a, long long n, long long mod) {
    	if (n == 0)
    		return 1;
    	
    	a = a % mod;
    	if (n == 1)
    		return a;
    
    	long long pw = power_mod(a, n / 2, mod);
    	long long pw2 = pw * pw % mod;
    	if (n % 2 == 0)
    		return pw2;
    
    	return pw2 * a % mod;
    }
    

{{ select(10) }}

• $O(n)$
• $O(a^n)$
• $O(\log n)$
• $O(a \times \log n)$

11. 下面程序的时间复杂度为（ ）。

    int record_choose[MAXN][MAXN];
    int choose(int n, int m) {
    	if (m == 0 || m == n)
    		return 1;
    
    	if (record_choose[n][m] == 0)
    		record_choose[n][m] = choose(n - 1, m - 1) + choose(n - 1, m);
    
    	return record_choose[n][m];
    }
    

{{ select(11) }}

• $O(2^n)$
• $O(2^m \times (n-m))$
• $O(C(n, m))$
• $O(m \times (n-m))$

12. 下面的程序使用出边的邻接表表达有向图，则下列选项中哪个是它表达的图？（ ）

    #include <iostream>
    
    struct Edge {
    	int e;
    	Edge * next;
    };
    
    struct Node {
    	Edge * first;
    };
    
    int main() {
    	Edge e[5] = {{1, nullptr}, {2, &e[2]},
    				 {3, nullptr}, {3, nullptr}, {0, nullptr}};
    	Node n[4] = {&e[0], &e[1], &e[3], &e[4]};
    	;	// 其它处理
    
    	return 0;
    }
    

{{ select(12) }}

• 
• 
• 
• 

13. 下面程序的输出为（ ）。

    #include <iostream>
    
    using namespace std;
    
    int main() {
    	int cnt = 0;
    	for (int a = 1; a <= 10; a++)
    		for (int b = 1; b <= 10; b++)
    			for (int h = 1; h <= 10; h++)
    				if ((a + b) * h == 20)
    					cnt++;
    	
    	cout << cnt << endl;
    
    	return 0;
    }
    

{{ select(13) }}

• $12$
• $18$
• $36$
• $42$

14. 下面程序的输出为（ ）。

    #include <iostream>
    
    using namespace std;
    
    int main() {
    	const int N = 30;
    	int cnt = 0;
    	for (int a = 1; a <= N; a++)
    		for (int b = a; a + b <= N; b++)
    			for (int c = b; a + b + c <= N; c++)
    				if (a * a + b * b == c * c)
    					cnt++;
    
    	cout << cnt << endl;
    
    	return 0;
    }
    

{{ select(14) }}

• $3$
• $6$
• $11$
• $22$

15. 下面的程序中，二维数组 $h$ 和 $v$ 分别代表如下图所示的网格中的水平边的时间消耗和垂直边的时间消耗。程序使用动态规划计算从左下角到右上角的最小时间消耗，则横线处应该填写下列哪个选项的代码？（ ）

    

    int dis[MAXY][MAXX];
    int shortest_path(int x, int y) {
    	dis[0][0] = 0;
    	for (int i = 0; i < y; i++)
    		dis[i + 1][0] = dis[i][0] + v[i][0];
    	for (int j = 0; j < x; j++)
    		dis[0][j + 1] = dis[0][j] + h[0][j];
    	for (int i = 0; i < y; i++)
    		for (int j = 0; j < x; j++)
    			__________; // 在此处填写代码
    
    	return dis[y][x];
    }
    

{{ select(15) }}

• dis[i][j] = min(dis[i - 1][j] + v[i - 1][j], dis[i][j - 1] + h[i][j - 1]);
• dis[i][j] = min(dis[i - 1][j] + h[i - 1][j], dis[i][j - 1] + v[i][j - 1]);
• dis[i + 1][j + 1] = min(dis[i][j + 1] + v[i][j + 1], dis[i + 1][j] + h[i + 1][j]);
• dis[i + 1][j + 1] = min(dis[i][j + 1] + h[i][j + 1], dis[i + 1][j] + v[i + 1][j]);

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

1. $\tt C$++ 语言非常强大，可以用来求解方程的解。例如，如果变量 $x$ 为 $\tt double$ 类型的变量，则执行语句 x * 2 - 4 = 0; 后，变量 $x$ 的值会变为 $2.0$。（ ）

{{ select(16) }}

• 正确
• 错误

2. 一个袋子中有 $3$ 个完全相同的红色小球、$2$ 个完全相同的蓝色小球。每次从中取出 $1$ 个，且不放回袋子，这样进行 $3$ 次后，将取出的小球依次排列，则可能的颜色顺序有 $7$ 种。（ ）

{{ select(17) }}

• 正确
• 错误

3. 杨辉三角，是二项式系数的一种三角形排列，在中国南宋数学家杨辉 $1261$ 年所著的《详解九章算法》一书中出现，是中国数学史上的一项伟大成就。（ ）

{{ select(18) }}

• 正确
• 错误

4. $N$ 个顶点的有向完全图（不带自环）有 $N \times (N-1)/2$ 条边。（ ）

{{ select(19) }}

• 正确
• 错误

5. 如果待查找的元素确定，只要哈希表的大小不小于查找元素的个数，就一定存在不会产生冲突的哈希函数。（ ）

{{ select(20) }}

• 正确
• 错误

6. 动态规划算法的时间复杂度一般为：必要状态的数量，乘以计算一次状态转移方程的时间复杂度。（ ）

{{ select(21) }}

• 正确
• 错误

7. 已知 $\tt int$ 类型的变量 $a$、$b$ 和 $h$ 中分别存储着一个梯形的顶边长、底边长和高，则这个梯形的面积可以通过表达式 (a + b) * h / 2 求得。（ ）

{{ select(22) }}

• 正确
• 错误

8. 判断图是否连通只能用广度优先搜索算法实现。（ ）

{{ select(23) }}

• 正确
• 错误

9. 在 $N$ 个元素的二叉排序树中查找一个元素，最好情况的时间复杂度是 $O(\log N)$。（ ）

{{ select(24) }}

• 正确
• 错误

10. 给定 $\tt double$ 类型的变量 $x$，且其值大于等于 $0$，我们可以通过二分法求出 $\sqrt{x}$ 的近似值。（ ）

{{ select(25) }}

• 正确
• 错误