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

$1、$​​ 下面关于C++类和对象的说法，错误的是（ ）。

{{ select(1) }}

• 类的析构函数可以为虚函数。
• 类的构造函数不可以为虚函数。
• class中成员的默认访问权限为private。
• struct中成员的默认访问权限为private。

$2、$ 对于一个具有 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。

{{ select(2) }}

• $n*\frac{n}{2}$
• $n*n$
• $(n-1)*(n-1)$
• $(n+1)*(n+1)$

$3、$ 设有编号为A、B、C、D、E的5个球和编号为A、B、C、D、E的5个盒子。现将这5个球投入5个盒子，要求每个盒子放一个球，并且恰好有两个球的编号与盒子编号相同，问有多少种不同的方法？（ ）。

{{ select(3) }}

• 5
• 120
• 20
• 60

$4、$ 从甲地到乙地，可以乘高铁，也可以乘汽车，还可以乘轮船。一天中，高铁有10班，汽车有5班，轮船有2班。那么一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法？（ ）。

{{ select(4) }}

• 100
• 60
• 30
• 17

$5、$ n个结点的二叉树，执行释放全部结点操作的时间复杂度是（ ）。

{{ select(5) }}

• $O(n)$
• $O(nlogn)$
• $O(logn)$
• $O(2^n)$

$6、$ 在一个单位圆上，随机分布 个点，求这 个点能被一个单位半圆周全部覆盖的概率（ ）。

{{ select(6) }}

• $\frac{n}{2^{n-1}}$
• $\frac{1}{n^{2}}$
• $\frac{1}{n}$
• $\frac{1}{2^{n}}$

$7、$ 下面 pailie 函数是一个实现排列的程序，横线处可以填入的是（ ）。

#include <iostream>
using namespace std;
int sum = 0;
void swap(int & a, int & b) {
	int temp = a;
	a = b;
	b = temp;
}
void pailie(int begin, int end, int a[]) {
	if (begin == end) {
		for (int i = 0; i < end; i++)
			cout << a[i];
		cout << endl;
	}
	for (int i = begin; i < end; i++) {
		__________ // 在此处填入选项
	}
}

{{ select(7) }}

• 
• 
• 
• 

$8、$ 上一题中，如果主函数为如下的程序，则最后的排列数是多少个？（ ）。

int main() {
	int a[5] = {1, 2, 3, 4, 5};
	pailie(0, 5, a);
	return 0;
}

{{ select(8) }}

• 120
• 60
• 240
• 180

$9、$ 下列程序实现了输出杨辉三角形，代码中横线部分应该填入的是（ ）。

#include <iostream>
using namespace std;
#define N 35
int a[N][N];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++) {
			if (j == 1 || j == i)
				a[i][j] = 1;
			else
				__________ // 在此处填入选项
		}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++)
			cout << a[i][j];
		cout<<endl;
	}
	return 0;
}

{{ select(9) }}

• a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
• a[i][j] = a[i][j - 1] + a[i - 1][j];
• a[i][j] = a[i - 1][j] + a[i - 1][j];
• a[i][j] = a[i - 1][j - 1] + a[i][j];

$10、$ 下面最小生成树的Kruskal算法程序中，横线处应该填入的是（ ）。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
	int u, v, weight;
	bool operator <(const Edge & other) const {
		return weight < other.weight;
	}
};
int findParent(int vertex, vector<int> & parent) {
	if (parent[vertex] == -1)
		return vertex;
	return parent[vertex] = findParent(parent[vertex], parent);
}
int main() {
	int n, m;
	cin >> n >> m; // n: 顶点数, m: 边数
	vector<Edge> edges(m);
	vector<int> parent(n, -1);
	int totalWeight = 0;
	for (int i = 0; i < m; i++)
		cin >> edges[i].u >> edges[i].v >> edges[i].weight;
	sort(edges.begin(), edges.end());
	for (const auto & edge : edges) {
		int uParent = findParent(edge.u, parent);
		int vParent = findParent(edge.v, parent);
		if (__________) { // 在此处填入选项
			parent[uParent] = vParent;
			totalWeight += edge.weight;
		}
	}
}

{{ select(10) }}

• uParent == vParent
• uParent >= vParent
• uParent != vParent
• uParent <= vParent

$11、$ 下面Prim算法程序中，横线处应该填入的是（ ）。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int prim(vector<vector<int>> & graph, int n) {
	vector<int> key(n, INT_MAX);
	vector<int> parent(n, -1);
	key[0] = 0;
	for (int i = 0; i < n; i++) {
		int u = min_element(key.begin(), key.end()) - key.begin();
		if (key[u] == INT_MAX)
			break;
		for (int v = 0; v < n; v++) {
			if (__________) { // 在此处填入选项
				key[v] = graph[u][v];
				parent[v] = u;
			}
		}
	}
	int sum = 0;
	for (int i = 0; i < n; i++) {
		if (parent[i] != -1) {
			cout << "Edge: " << parent[i] << " - " << i << " Weight: " << key[i] <<
			endl;
			sum += key[i];
		}
	}
	return sum;
}
int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> graph(n, vector<int>(n, 0));
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		graph[u][v] = w;
		graph[v][u] = w;
	}
	int result = prim(graph, n);
	cout << "Total weight of the minimum spanning tree: " << result << endl;
	return 0;
}

{{ select(11) }}

• graph[u][v] >= 0 && key[v] > graph[u][v]
• graph[u][v] <= 0 && key[v] > graph[u][v]
• graph[u][v] == 0 && key[v] > graph[u][v]
• graph[u][v] != 0 && key[v] > graph[u][v]

$12、$ 下列Dijkstra算法中，横线处应该填入的是（ ）。

#include <iostream>
using namespace std;
#define N 100
int n, e, s;
const int inf = 0x7fffff;
int dis[N + 1];
int cheak[N + 1];
int graph[N + 1][N + 1];
int main() {
	for (int i = 1; i <= N; i++)
		dis[i] = inf;
	cin >> n >> e;
	for (int i = 1; i <= e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a][b] = c;
	}
	cin >> s;
	dis[s] = 0;
	for (int i = 1; i <= n; i++) {
		int minn = inf, minx;
		for (int j = 1; j <= n; j++) {
			if (__________) { // 在此处填入选项
				minn = dis[j];
				minx = j;
			}
		}
		cheak[minx] = 1;
		for (int j = 1; j <= n; j++) {
			if (graph[minx][j] > 0) {
				if (minn + graph[minx][j] < dis[j]) {
					dis[j] = minn + graph[minx][j];
				}
			}
		}
	}
}

{{ select(12) }}

• dis[j] > minn && cheak[j] == 0
• dis[j] < minn && cheak[j] == 0
• dis[j] >= minn && cheak[j] == 0
• dis[j] < minn && cheak[j] != 0

$13、$ 下面Floyd算法中，横线处应该填入的是（ ）。

#include <iostream>
using namespace std;
#define N 21
#define INF 99999999
int map[N][N];
int main() {
	int n, m, t1, t2, t3;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				map[i][j] = 0;
			else
				map[i][j] = INF;
		}
		}
	for (int i = 1; i <= m; i++) {
		cin >> t1 >> t2 >> t3;
		map[t1][t2] = t3;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (__________) // 在此处填入选项
					map[i][j] = map[i][k] + map[k][j];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout.width(4);
			cout << map[i][j];
		}
		cout << endl;
	}
}

{{ select(13) }}

• map[i][j] < map[i][k] + map[k][j]
• map[i][j] > map[i][k] + map[k][j]
• map[i][j] > map[i][k] - map[k][j]
• map[i][j] < map[i][k] - map[k][j]

$14、$ 下面程序的 Merge_Sort 函数时间复杂度为（ ）。

void Merge(int a[], int left, int mid, int right) {
	int temp[right - left + 1];
	int i = left;
	int j = mid + 1;
	int k = 0;
	while (i <= mid && j <= right) {
		if (a[i] < a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}
	while (i <= mid)
		temp[k++] = a[i++];
	while (j <= right)
		temp[k++] = a[j++];
	for (int m = left, n = 0; m <= right; m++, n++)
		a[m] = temp[n];
}
void Merge_Sort(int a[], int left, int right) {
	if (left == right)
		return;
	int mid = (left + right) / 2;
	Merge_Sort(a, left, mid);
	Merge_Sort(a, mid + 1, right);
	Merge(a, left, mid, right);
}

{{ select(14) }}

• $O(nlogn)$
• $O(n^2)$
• $O(2^n)$
• $O(logn)$

$15、$ 下面 fibonacci 函数的时间复杂度为（ ）。

int fibonacci(int n) {
	if (n <= 1)
		return n;
	else
		return fibonacci(n - 1) + fibonacci(n - 2);
}

{{ select(15) }}

• $O(1)$
• $O(\phi^n),\phi=\frac{\sqrt{5}-1}{2}$
• $O(n)$
• $O(nlogn)$

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

$16、$ 表达式 '3' & 1 的结果为 '1' 。

{{ select(16) }}

• 正确
• 错误

$17、$ 在C++语言中，变量定义必须在某一个函数定义之内。

{{ select(17) }}

• 正确
• 错误

$18、$ 冒泡排序一般是不稳定的。

{{ select(18) }}

• 正确
• 错误

$19、$ 二叉排序树的查找操作的平均时间复杂度，正比于树的高度。

{{ select(19) }}

• 正确
• 错误

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

{{ select(20) }}

• 正确
• 错误

$21、$ 你有三种硬币，分别面值2元、5元和7元，每种硬币都有足够多。买一本书需要27元，则最少可以用5个硬币组合起来正好付清，且不需要对方找钱。

{{ select(21) }}

• 正确
• 错误

$22、$ 现有 n个完全相同的元素，要将其分为 k组，允许每组可以有0 个元素，则一共有 C(n-1,k-1)种分组方案

{{ select(22) }}

• 正确
• 错误

$23、$ 题 已知 int 类型的变量 a 和 b 中分别存储着一个直角三角形的两条直角边的长度，则该三角形的面积可以通 过表达式 a / 2.0 * b 求得。

{{ select(23) }}

• 正确
• 错误

$24、$ 已知等差数列的通项公式 $a_n=a_1+(n-1)d$，则前 n项和的求和公式为 $S_n=n(a_1+a_n)/2$。使用这一公 式计算$S_n$ 的时间复杂度是 $O(1)$。

{{ select(24) }}

• 正确
• 错误

$25、$ 诚实国公民只说实话，说谎国公民只说谎话。你来到一处分岔口，一条通往诚实国，一条通往说谎国，但不知是哪一条通往哪里。正在为难之际，走来两位路人，他们都自称是诚实国公民，都说对方是说谎国公民。你想去说谎国，可以这样问其中一位路人：“我要去说谎国，如果我去问另一个路人，他会指向哪一条路？”。

{{ select(25) }}

• 正确
• 错误