一.单选题(每题2分，共30分)

1. 下⾯关于C++类和对象的说法， 错误的是

{{ select(1) }}

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

2. 对于⼀个具有n个顶点的⽆向图， 若采⽤邻接矩阵表⽰， 则该矩阵的⼤⼩为

{{ 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) }}

• swap(a[begin + 1], a[i]);
  pailie(begin + 1, end, a);
  swap(a[i], a[begin]);
  

• swap(a[begin], a[i]);
  pailie(begin, end, a);
  swap(a[i], a[begin]);
  

• swap(a[begin], a[i]);
  pailie(begin + 1, end, a);
  swap(a[i], a[begin]);
  

• swap(a[begin] + 1, a[i]);
  pailie(begin + 1, end, a);
  swap(a[i], a[begin + 1]);
  

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算法中， 横线处应该填⼊的是

```cpp
#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(\empty^n)$，$\empty=\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. 现有 个完全相同的元素， 要将其分为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) }}

• 正确

• 错误