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

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

A. 2
B. 3
C. 5
D. 6

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

A. void QuickSort(int a[][10], int n);
B. void QuickSort(int a[5][], int m);
C. void QuickSort(int a[][], int n, int m);
D. void QuickSort(int ** a, int n, int m);

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

A. 对象的生命周期开始时，会执行构造函数。
B. 对象的生命周期结束时，会执行析构函数。
C. 类的析构函数可以为虚函数。
D. 类的构造函数可以为虚函数。

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

A. n * (n + 1)
B. n * n
C. n * (n - 1)
D. n * (n - 1) / 2

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

A. 5
B. 24
C. 96
D. 120

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

A. n - 1
B. n
C. n + 1
D. 最小生成树可能不存在。

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

A. a * b * sin(theta) / 2
B. (a + b) * sin(theta) / 2
C. a * b * cos(theta) / 2
D. sqrt(a * a + b * b - 2 * a * b * cos(theta))

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

A. O(1)
B. O(log(n))
C. O(n)
D. O(n^2)

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

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

A. O(log(n))
B. O(n)
C. O(n * m)
D. O(m * 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;
}

A. O(n)
B. O(a^n)
C. O(log(n))
D. O(log(n) * a)

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

int record_choose[MAXN][MAXM];
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];
}

A. O(2^n)
B. O(2^m * (n - m))
C. O(C(n, m))
D. O(m * (n - m))

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

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

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

A. 12
B. 18
C. 36
D. 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;
}

A. 3
B. 6
C. 11
D. 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]; 
}

A. dis[i][j] = min(dis[i - 1][j] + v[i - 1][j], dis[i][j - 1] + h[i][j - 1]);
B. dis[i][j] = min(dis[i - 1][j] + h[i - 1][j], dis[i][j - 1] + v[i][j - 1]);
C. dis[i + 1][j + 1] = min(dis[i][j + 1] + v[i][j + 1], dis[i + 1][j] + h[i + 1][j]);
D. 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、C++语言非常强大，可以用来求解方程的解。例如，如果变量 x 为 double 类型的变量，则执行语句 x * 2 - 4 = 0; 后，变量 x 的值会变为 2.0 。

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

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

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

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

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

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

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

9、在 N个元素的二叉排序树中查找一个元素，最好情况的时间复杂度是O(logN) 。

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

编程题 (每题 25 分，共 50 分)

奖品分配

【问题描述】
班上有 N 名同学，学号从0 到N-1 。有M 种奖品要分给这些同学，其中，第 i 种奖品总共有ai 个（i = 0, 1, …, M - 1）。巧合的是，奖品的数量不多不少，每位同学都可以恰好分到一个奖品，且最后剩余的奖品不超过 1 个（即：N<= a0+a1+…+aM-1 <= N + 1 ）。
现在，请你求出每个班级礼物分配的方案数，所谓方案，指的是为每位同学都分配一个种类的奖品。只要有一位同学获得了不同种类的奖品，即视为不同的方案。方便起见，你只需要输出方案数对$10^9$ + 7 取模后的结果即可。
共有 T 个班级都面临着奖品分配的问题，你需要依次为他们解答。
【输入描述】
第一行一个整数 T ，表示班级数量。
接下来 T 行，每行若干用单个空格隔开的正整数。首先是两个正整数N, M ，接着是 M 个正整数a0, a1, …, aM-1 。保证N<= a0+a1+…+aM-1 <= N + 1 。
【输出描述】
输出 T 行，每行一个整数，表示该班级分配奖品的方案数对 $10^9$ + 7 取模的结果。
【特别提醒】
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
【样例输入 1】
3
3 2 1 2
3 2 1 3
5 3 3 1 1
【样例输出 1】
3
4
20
【样例解释 1】
对于第 1 个班级，学号为0,1,2 的同学可以依次分别获得奖品0,1,1 ，也可以依次分别获得奖品1,0,1 ，也可以依次分别获得奖品1,1,0 ，因此共有3 种方案。
对于第 2 个班级，学号为0,1,2 的同学可以依次分别获得奖品0,1,1 ，也可以依次分别获得奖品1,0,1 ，也可以依次分别获得奖品1,0,1 ，也可以依次分别获得奖品1,1,1 ，因此共有4 种方案。
对于第 3 个班级，可以把编号为1 的奖品分配给5 名同学中的任意一名，共有5 种方案；再把编号为 2的奖品分配给剩余4 名同学中的任意一名，共有4 种方案；最后给剩余3 名同学自然获得0 号奖品。因此，方案数为 5 * 4 = 20。
【样例输入 2】
5
100 1 100
100 1 101
20 2 12 8
123 4 80 20 21 3
999 5 101 234 499 66 99
【样例输出 2】
1
1
125970
895031741
307187590
【数据规模】
对于30%的测试点，保证 N <= 10 。
对于另外30%的测试点，保证M = 2 。
对于所有测试点，保证N <= 1,000 ；保证T <= 1,000 ；保证M <=1,001 。

大量的工作沟通

【问题描述】
某公司有 N 名员工，编号从0 至N - 1 。其中，除了 0 号员工是老板，其余每名员工都有一个直接领导。我们假设编号为i 的员工的直接领导是fi 。
该公司有严格的管理制度，每位员工只能受到本人或直接领导或间接领导的管理。具体来说，规定员工x 可以管理员工y ，当且仅当x = y ，或x = fy ，或x 可以管理fy 。特别地， 0号员工老板只能自我管理，无法由其他任何员工管理。
现在，有一些同事要开展合作，他们希望找到一位同事来主持这场合作，这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工，他们希望找到编号最大的员工。你能帮帮他们吗？

【输入描述】
第一行一个整数N ，表示员工的数量。
第二行N - 1 个用空格隔开的正整数，依次为f1, f2, …, fN-1 。
第三行一个整数Q ，表示共有 Q场合作需要安排。
接下来 Q行，每行描述一场合作：开头是一个整数m （2 <= m <= N ），表示参与本次合作的员工数量；接着是m个整数，依次表示参与本次合作的员工编号（保证编号合法且不重复）。
保证公司结构合法，即不存在任意一名员工，其本人是自己的直接或间接领导。
【输出描述】
输出 Q 行，每行一个整数，依次为每场合作的主持人选。
【特别提醒】
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
【样例输入 1】
5
0 0 2 2
3
2 3 4
3 2 3 4
2 1 4
【样例输出 1】
2
2
0
【样例解释 1】
对于第一场合作，员工3,4 有共同领导2 ，可以主持合作。
对于第二场合作，员工2 本人即可以管理所有参与者。
对于第三场合作，只有0 号老板才能管理所有员工。
【样例输入 2】
7
0 1 0 2 1 2
5
2 4 6
2 4 5
3 4 5 6
4 2 4 5 6
2 3 4
【样例输出 2】
2
1
1
1
0
【数据规模】
对于25%的测试点，保证 N <= 50。
对于50%的测试点，保证 N <= 300。
对于所有测试点，保证 3 <= N <= $10^5$；保证Q <= 100 ，保证 m <= $10^4$。

答案及解析

单选题

1、【答案】C
【解析】本题可抽象为分类计数问题，应使用加法原理，而不是乘法原理。答案为 ACB 的方案数 2 加上 ADB 的方案数 3=5，选 C。

2、【答案】A
【解析】C++在函数中把数组作为参数进行传递时，只会传递数组的首地址，函数中如果想要通过首地址计算数组中任意一位元素所处的地址时，就需要知道第二维数组的长度，比如第二维数组长度为 10 时，a[1][3]的地址就是a[0][0]的地址+13，本题的选项中只有选项 A 给出了数组第二维长度，所以本题选A。

3、【答案】D
【解析】对象的声明周期开始和结束时会分别执行构造函数和析构函数，选项A、B 正确。对于选项 C、D，虚函数是指被 virtual 关键字修饰的成员函数，定义虚函数是为了允许用基类的指针来调用派生类的该函数。允许将析构函数定义为虚函数，是因为有使用“delete 基类指针”来销毁对象的需求，选项C正确。但对象构造时必须指定准确的类，不能使用基类名构造派生类的对象，没有将构造函数定义为虚函数的需要，选项 D 错误。

4、【答案】B
【解析】邻接矩阵的行列均为[0~n-1],所以矩阵的大小为n*n，本题选B。

5、【答案】C
【解析】按照第 1,2,3,4,5 位的顺序依次安排同学，某位同学不能在第一位，所以第 1 位有 4 种安排方法，第二位可以从剩余的 4 名同学中选一位，有4种方法，依次类推，第 3,4,5 各有 3,2,1 种，总方案数为 44321=96，选C。

6、【答案】D
【解析】n 个顶点组成的树包含 n-1 条边，但是题目没有保证图连通，所以可能不存在最小生成树，选 D。

7、【答案】A
【解析】若△ABC 中,已知两边 a.b 和它们的夹角 theta ,作边a 上的高h. 则S=(1/2)ah,而 h/b=sin(theta),即 h=b*sin(theta)
∴S=(1/2)absin(theta)选 A。

8、【答案】C
【解析】树的遍历过程需要对每个元素访问一次，因此时间复杂度为O(n)，选择 C。

9、【答案】A
【解析】本题代码为辗转相除法，复杂度为 O(logn)。最差情况，输入为斐波那契数列的相邻两项时，循环次数为输入在数列中的位置。选A。

10、【答案】C
【解析】本题代码为快速幂，复杂度为 O(logn)。通过观察可得该函数的时间复杂度只与 n 相关，假设为 T(n)，则 T(n)=T(n / 2) + 常数，求解可得上述时间复杂度。选 C。

11、【答案】D
【解析】本题代码是在计算 C[n][m],使用了递归的写法并加上了记忆化搜索，可以通过画图来看所有被访问到的二维数组个数，以 n=6，m=2 为例， 可以发现访问的元素个数为 nm-mm，本题选 D。

12、【答案】B
【解析】结构体 edge 里的 next 指向的是下一条边，Node 里的first 指向的是每个点的第一条边，所以 0 号点指向 1 号点，1 号点指向2,3 号点，2 号点指向3号点，3 号点指向 0 号点，选 B。

13、【答案】B
【解析】代码中 a,b,h 的取值范围均为[1,10]，要(a+b)*h=20,那么可能的h有1,2,4,5,10，h 为 1 时，(a+b)=20,有 1 种方法，h 为 2 时，(a+b)=10,有9 种方案，依次计算出 h 为 4,5,10 时，(a+b)的方案数依次为 4,3,1，总方案数为1+9+4+3+1=18,选 B。

14、【答案】A
【解析】代码中要求 a，b，c 都是正整数，满足 a+b+c<=30 且,符合要求的a,b,c有 3 4 5；5 12 13；6 8 10 共 3 种，选 A。

15、【答案】C
【解析】观察到 11 行的输出为 dis[y][x],而我们枚举的范围是<y 与<x，所以第10 行计算的肯定是 dis[i+1][j+1]，排除 AB，接着看 C 选项第一个转移，dis[i][j+1]，说明这里是从第一维转移过来，而第 5 行也是从第一维转移过来的，使用的是v数组，选项 C 正确，排除 D 选项，本题选 C。

判断题

1、【答案】错误
【解析】错误。x*2-4=0;既不是判断语句，也不是赋值语句。它不是合法的C++语句，不能通过编译。

2、【答案】正确
【解析】正确，可能出现红红红，蓝红红，红蓝红，红红蓝，蓝蓝红，红蓝蓝，蓝红蓝。

3、【答案】正确
【解析】正确，杨辉三角，是二项式系数在三角形中的一种几何排列，在中国南宋数学家杨辉所著的《详解九章算法》中出现。

4、【答案】错误
【解析】错误。有向完全图，(x,y)和(y,x)不算同一条边，所以有N*(N-1)条边。

5、【答案】正确
【解析】正确。极端情况，可以先将待查找元素放进哈希表中，再根据位置构造一个由 if-else 判断组成的哈希函数：当查找元素与某一项待查找相同时，返回对应的位置。虽然这样构造的哈希函数的时间复杂度较高，但满足不会产生冲突。

6、【答案】正确
【解析】正确，动态规划的时间复杂度⼀般为状态数*转移复杂度。

7、【答案】错误
【解析】错误，梯形面积可能带有小数，不能直接/2。

8、【答案】错误
【解析】错误,还可以使用深度优先搜索算法。

9、【答案】错误
【解析】错误，最好情况的时间复杂度为 O(1)，即二叉排序树的根即为查找的元素。

10、【答案】正确
【解析】正确，函数 y= $x^2$在值域[0，+∞]上具有单调性。

编程题1

1、

编程题2

2、【解题思路】容易想到，能够管理员工a1 ,a2,…,am的人为lca(a1 ,a2,…,am)以及该lca的祖先节点，题目还要求编号最大，也就是从根到该lca路径上所有点的编号最大值，这个可以提前预处理，设mxID[u]表示从根到u路径上所有节点编号的最大值，对于每组询问，首先求出所有参与的员工的lca，接着输出mxID[lca]即可，求lca比较常用的有倍增法或树链剖分等。