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

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

A. 720
B. 90
C. 48
D. 15

正确答案：A

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

A. 720
B. 72
C. 36
D. 2

正确答案：B

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

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

正确答案：D

4、关于生成树的说法，错误的是（ ）。

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

正确答案：D

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

A.$\frac{2}{3}$
B.$\frac{1}{3}$
C.$\frac{1}{2}$
D.$\frac{1}{4}$

正确答案：C

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

A. 4 * b - a * a < 0
B. 4 * b <= a * a
C. a * a - 4 * b
D. b * 4 - a * a

正确答案：B

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

A.$O(logn)$
B.$O(nlogn)$
C.$O(n)$
D.$O(2^n)$

正确答案：C

8、以下关于动态规划的说法中，错误的是（ ）。

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

正确答案：B

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

#include <string>
int count_digit(int n, char d) {int cnt = 0;std::string s = std::to_string(n);for (int i = 0; i < s.length(); i++)if (s[i] == d)cnt++;return cnt;
}
int sum_digit(int n, char d) {int sum = 0;for (int i = 1; i <= n; i++)sum += count_digit(i, d);return sum;
}

A.$O(nlogn)$
B.$O(n)$
C.$O(logn)$
D.$O(n^2)$

正确答案：A

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

#include <iostream>
const int N = 10;
int ch[N][N][N];
int main() {for (int x = 0; x < N; x++)for (int y = 0; y < N; y++)for (int z = 0; z < N; z++)if (x == 0 && y == 0 && z == 0)ch[x][y][z] = 1;else {if (x > 0)ch[x][y][z] += ch[x - 1][y][z];if (y > 0)ch[x][y][z] += ch[x][y - 1][z];if (z > 0)ch[x][y][z] += ch[x][y][z - 1];}std::cout << ch[1][2][3] << std::endl;return 0;
}

A. 60
B. 20
C. 15
D. 10

正确答案：A

11、下面 count_triple 函数的时间复杂度为( )。

int gcd(int a, int b) {if (a == 0)return b;return gcd(b % a, a);
}
int count_triple(int n) {int cnt = 0;for (int v = 1; v * v * 4 <= n; v++)for (int u = v + 1; u * (u + v) * 2 <= n; u += 2)if (gcd(u, v) == 1) {int a = u * u - v * v;int b = u * v * 2;int c = u * u + v * v;cnt += n / (a + b + c);}return cnt;
}

A.$O(n)$
B.$O(n^2)$
C.$O(nlogn)$
D.$O(n^{2}logn)$

正确答案：C

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

void swap(int & a, int & b) {int temp = a; a = b; b = temp;
}
int partition(int a[], int l, int r) {int pivot = a[l], i = l + 1, j = r;while (i <= j) {while (i <= j && a[j] >= pivot)j--;while (i <= j && a[i] <= pivot)i++;if (i < j)swap(a[i], a[j]);}________; // 在此处填入选项return ________; // 在此处填入选项
}
void quick_sort(int a[], int l, int r) {if (l < r) {int pivot = partition(a, l, r);quick_sort(a, l, pivot - 1);quick_sort(a, pivot + 1, r);}
}

A. swap(a[l], a[i])		i
B. swap(a[l], a[j])		i
C. swap(a[l], a[i])		j
D. swap(a[l], a[j])		j

正确答案：D

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

int max(int a, int b) {return (a > b) ? a : b;
}
int LIS(vector<int> & nums) {int n = nums.size();if (n == 0)return 0;vector<int> dp(n, 1);int maxLen = 1;for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++)if (nums[j] < nums[i])________; // 在此处填入选项maxLen = max(maxLen, dp[i]);}return maxLen;
}

A. dp[j] = max(dp[j] + 1, dp[i])
B. dp[j] = max(dp[j], dp[i] + 1)
C. dp[i] = max(dp[i] + 1, dp[j])
D. dp[i] = max(dp[i], dp[j] + 1)

正确答案：D

14、下面 LIS 函数试图求出最长上升子序列的长度，其时间复杂度为（ ）。

#define INT_MIN (-1000)
int LIS(vector<int> & nums) {int n = nums.size();vector<int> tail;tail.push_back(INT_MIN);for (int i = 0; i < n; i++) {int x = nums[i], l = 0, r = tail.size();while (l < r) {int mid = (l + r) / 2;if (tail[mid] < x)l = mid + 1;elser = mid;}if (r == tail.size())tail.push_back(x);elsetail[r] = x;}return tail.size() - 1;
}

A.$O(logn)$
B.$O(n)$
C.$O(nlogn)$
D.$O(n^2)$

正确答案：C

15、下面的程序使用邻接矩阵表达的带权无向图，则从顶点0到顶点3的最短距离为（ ）。

int weight[4][4] = {{ 0, 5, 8, 10},{ 5, 0, 1, 7},{ 8, 1, 0, 3},{10, 7, 3, 0}};

A. 9
B. 10
C. 11
D. 12

正确答案：A

判断题（每题 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)种不同的选法。

正确答案：正确

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

树上旅行

【问题描述】
给定一棵有n个结点的有根树，结点依次以1,2,…,n编号，其中根结点的编号为1。
小A计划在这棵有根树上进行q次旅行。在第i次旅行中，小A首先会选定结点$s_i$作为起点，并移动若干次。移动分为以下两种：
1.移动至当前结点的父结点。特殊地，如果当前位于根结点，则不进行移动。
2.移动至当前结点的所有子结点中编号最小的结点。特殊地，如果当前位于叶子结点，则不进行移动。
由于移动次数可能很大，对于第i次旅行，旅行中的移动将以$k_i$个不为零的整数构成的序列$a_{i,1},a_{i,2},...,a_{i,k_i}$表示。对于$a_{i,j}$,若$a_{i,j}$>0则代表进行$a_{i,j}$次第一种移动；若$a_{i,j}$<0则代表进行$-a_{i,j}$次第二种移动。根据给出的序列从左至右完成所有移动后，小A所在的结点即是旅行的终点。
给定每次旅行的起点与移动序列，请你求出旅行终点的结点编号。

【输入格式】
第一行，两个正整数n,q,分别表示有根树的结点数量，以及旅行次数。

第二行，n-1个整数$p_2,p_3,\dots ,p_n$,其中$p_i$表示结点i的父结点编号。

接下来2q行中的第2i-1行$(1\le i\le q)$包含两个正整数$s_i,k_i$,分别表示第i次旅行的起点编号，以及移动序列的长度。第2i行包含k;个整数$a_{i,1},a_{i,2},...,a_{i,k_i}$,表示移动序列。

【输出格式】
输出共q行，第i行包含一个整数，表示第i次旅行终点的结点编号。

【样例输入 1】
5 4
1 1 2 2
3 3
1 -1 1
2 5
1 -1 1 -1 1
5 8
1 1 1 -1 -1 -1 -1 -1
5 3
-1 -1 1
【样例输出 1】
4
1
4
2
【样例输入 2】
8 3
5 4 2 1 3 6 6
8 1
8
8 2
8 -8
8 3
8 -8 8
【样例输出 2】
1
7
1
【数据范围】

子任务编号	测试点占比	n	q	$\sum k_i$	特殊性质
1	20%	$\le 100$	$\le 100$	\leq 100$	保证$a_{i,j}$为1或-1
2	20%	$\le 10^4$	$\le 10^4$	$\le 4\ast 10^4$	仅包含第一种移动
3	20%	$\le 10^4$	$\le 10^4$	$\le 4\ast 10^4$	仅包含第二种移动
4	40%	$\le 10^5$	$\le 2\ast 10^4$	$\le 10^5$

对于所有测试点，保证$1\le n\le 10^5,1\le q\le 2\times 10^4,1\le p_i\le n,1\le s_i\le n,k_i\ge 1且\sum k_i\le 10^5,1\le |a_{i,j}|\le n$

遍历计数

【问题描述】
给定一棵有n个结点的树T,结点依次以1,2,…,n标号。树T的深度优先遍历序可由以下过程得到：
1.选定深度优先遍历的起点$s(1\le s\le n)$,当前所在结点即是起点。
2.若当前结点存在未被遍历的相邻结点u则遍历u,也即令当前所在结点为u并重复这一步；否则回溯。
3.按照遍历结点的顺序依次写下结点编号，即可得到一组深度优先遍历序。
第一步中起点的选择是任意的，并且第二步中遍历相邻结点的顺序是任意的，因此对于同一棵树T可能有多组不同的深度优先遍历序。请你求出树T有多少组不同的深度优先遍历序。由于答案可能很大，你只需要求出答案对$10^9$取模之后的结果。

【输入格式】
第一行，一个整数n,表示树T的结点数。

接下来n-1行，每行两个正整数$u_i,v_i$,表示树T中的一条连接结点$u_i,v_i$的边。

【输出格式】
输出一行，一个整数，表示树T的不同的深度优先遍历序数量对$10^9$取模的结果。

【样例输入 1】
4
1 2
2 3
3 4
【样例输出 1】
6
【样例输入 2】
8
1 2
1 3
1 4
2 5
2 6
3 7
3 8
【样例输出 2】
112
【数据范围】
对于40%的测试点，保证$1\le n\le 8$。
对于另外20%的测试点，保证给定的树是一条链。
对于所有测试点，保证$1\le n\le 10^5$。