首页 › 题库 › GESP编程能力等级认证 › GESP-C++八级

GESP-C++八级 题库

共 270 道题 ,第 5 / 14 页 · 按题型筛选,点「查看答案」核对解析
81 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

n个结点的二叉树,执行释放全部结点操作的时间复杂度是( )。

A
O(n)
B
O(nlogn)
C
O(logn)
D
O(2n)
答案与解析
正确答案:A

对二叉树执行DFS,在回溯阶段依次释放每个节点,复杂度O(n)。

题目详情
82 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 2.1 排列

下面 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++) {
		__________ // 在此处填入选项
	}
}
A
swap(a[begin + 1], a[i]);
pailie(begin + 1, end, a);
swap(a[i], a[begin]);
B
swap(a[begin], a[i]);
pailie(begin, end, a);
swap(a[i], a[begin]);
C
swap(a[begin], a[i]);
pailie(begin + 1, end, a);
swap(a[i], a[begin]);
D
swap(a[begin] + 1, a[i]);
pailie(begin + 1, end, a);
swap(a[i], a[begin + 1]);
答案与解析
正确答案:C

函数作用:在0n-1的区间,对A[0n-1]的元素进行全排列。

全排列可以这么理解,每个元素都有尝试在开头的机会,之后其他的元素在这个前提之下,继续在该元素后方继续尝试。当然在尝试完成后,还需要将排列还原,方便后续尝试,符合该要求的只有C选项。

题目详情
83 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 2.1 排列

上一题中,如果主函数为如下的程序,则最后的排列数是多少个?( )。

int main() {
	int a[5] = {1, 2, 3, 4, 5};
	pailie(0, 5, a);
	return 0;
}
A
120
B
60
C
240
D
180
答案与解析
正确答案:A

5的全排列5!=120。

题目详情
84 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 3.1 杨辉三角定义

下列程序实现了输出杨辉三角形,代码中横线部分应该填入的是( )。

#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;
}
A
a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
B
a[i][j] = a[i][j - 1] + a[i - 1][j];
C
a[i][j] = a[i - 1][j] + a[i - 1][j];
D
a[i][j] = a[i - 1][j - 1] + a[i][j];
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
85 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下面最小生成树的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;
		}
	}
}
A
uParent == vParent
B
uParent >= vParent
C
uParent != vParent
D
uParent <= vParent
答案与解析
正确答案:C

Kruskal基于避圈法和贪心思想,先按照边权升序,依次考虑每条边(x,y,z),如果x和y已经处于同一个生成树中,则过滤掉当前的边,否则将x和y的生成树通过z边连接,同时用并查集维护x和y(联接x和y的集合),组成更大的生成树。

横线处为判断x和y是否处于同一个集合,不是则链接,并更新最小生成树的边权和。答案选C。

题目详情
86 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下面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;
}
A
graph[u][v] >= 0 && key[v] > graph[u][v]
B
graph[u][v] <= 0 && key[v] > graph[u][v]
C
graph[u][v] == 0 && key[v] > graph[u][v]
D
graph[u][v] != 0 && key[v] > graph[u][v]
答案与解析
正确答案:D

最小生成树的Prim算法思想:选择圈内的一个点x(一开始随便选一个点作为x),遍历x的所有出边y,从中选取一个边权z最小的y,该(x,y,z)一定是最小生成树的生成边(因为最小生成树的点之间相互连通),程序中key数组就是用来记录过程中每个节点距离圈的距离的最小值,parent数组是记录节点和边权依次加入圈的具体路径(最终形成一棵生成树),横线处是比较圈外距离u最小的边权v,因此答案选D。

题目详情
87 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.2 最短路径

下列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];
				}
			}
		}
	}
}
A
dis[j] > minn && cheak[j] == 0
B
dis[j] < minn && cheak[j] == 0
C
dis[j] >= minn && cheak[j] == 0
D
dis[j] < minn && cheak[j] != 0
答案与解析
正确答案:B

朴素dijkstra算法,在非负权图中,用cheak[]标记已经求得最短路的点(因为已经求得,所以后续不会再更新),每次选择距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx,由非负权图的原因,该节点minxj将加入已经求得最短路的点的集合,同时用minx尝试是否能更新S到其他待球节点的最短路。横线处就是求解距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx的,因此选B。

题目详情
88 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.2 最短路径

下面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;
	}
}
A
map[i][j] < map[i][k] + map[k][j]
B
map[i][j] > map[i][k] + map[k][j]
C
map[i][j] > map[i][k] - map[k][j]
D
map[i][j] < map[i][k] - map[k][j]
答案与解析
正确答案:B

Floyd算法本质是个DP,或者可以理解为松弛操作:

i和j的最短路如果可以通过中间节点k做更新:

则需要map[i][j]>map[i][k]+map[k][j];选B。

题目详情
89 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面程序的 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);
}
A
O(nlogn)
B
O(n2)
C
O(2n)
D
O(logn)
答案与解析
正确答案:A

归并排序基于分治

时间复杂度为O(nlogn)。空间复杂度O(n);

题目详情
90 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面 fibonacci 函数的时间复杂度为( )。

int fibonacci(int n) {
	if (n <= 1)
		return n;
	else
		return fibonacci(n - 1) + fibonacci(n - 2);
}
A
O(1)
B
C
O(n)
D
O(nlogn)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
91 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

GESP活动期间,举办方从获胜者ABCDE五个人中选出三个人排成一队升国旗,其中A不能排在队首,请问有多少种排法?

A
24
B
48
C
32
D
12
答案与解析
正确答案:B

排列组合问题。A不能排队首,因此第一位有4种选法;第二位不能与第一位相同,因此有4种选法;第三位不能与前两位相同,有3种选法;共计4*4*3=48种。

题目详情
92 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

7进制数235转换成3进制数是( )。

A
11121
B
11122
C
11211
D
11112
答案与解析
正确答案:A

先将235转换成十进制124,然后再转换成3进制即可。

题目详情
93 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

0,1,2,3,4,5这些数字组成一个三位数,请问没有重复数字的情况下,有多少种组法( )。

A
180
B
120
C
80
D
100
答案与解析
正确答案:D

一共6个数字,百位不能为0,因此有5种可能;然后再选2个数字排列,就是P(5,2),答案是5*P(5,2)=100

题目详情
94 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

有V个顶点、E条边的图的深度优先搜索遍历时间复杂度为( )。

A
O(V)
B
O(E)
C
O(V+E)
D
O(log(V+E))
答案与解析
正确答案:C

每个顶点每条边都会被访问一次,所有时间复杂度是C。

题目详情
95 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

一对夫妻生男生女的概率相同。已知这对夫妻有两个孩子,其中一个是女孩,另一个是男孩的概率是多少?

A
B
C
D
答案与解析
正确答案:C

概率知识。每次男孩和女孩的概率都是1/2。

题目详情
96 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

从1到2024这2024个数中,共有( )个包含数字6的数。

A
544
B
546
C
564
D
602
答案与解析
正确答案:A

1位数字,只有1个6。

2位数字,有6的情况是6*,*表示0到9,共10种;*6,*表示1-9(除掉6),共8种,所以两位数有6的共18种。

3位数字,有6的情况,1位数字6,十位补0,*06,*表示1-9(除掉6),有8种;两位数前面加数字1-9(除掉6),(含6),818=144,百位是6的有600-699,共100个数字,总计100+144+8=252种。

同理1000-1999,1位数补成4位数,1006;2位数补成10(含6),3位数前面加1,有1+18+252=271种。

2000-2024有2个含数字6的数字,总数是1+18+252+271+2=544.

题目详情
97 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

二进制数 100.001 转换成十进制数是( )。

A
4.25
B
4.125
C
4.5
D
4.75
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
98 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

以下函数声明,哪个是符合C++语法的?( )。

A
void BubbleSort(char a[][], int n);
B
void BubbleSort(char a[][20], int n);
C
void BubbleSort(char a[10][], int n);
D
void BubbleSort(char[,] a, int n);
答案与解析
正确答案:B

考察的是二维数组定义的知识。二维数组第二维长度必须确定。

题目详情
99 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

下面有关C++重载的说法,错误的是( )。

A
两个参数个数不同的函数可以重名。
B
两个参数类型不同的函数可以重名。
C
两个类的方法可以重名。
D
所有C++运算符均可以重载。
答案与解析
正确答案:D

不能重载的运算符还是挺多的。“::”、“.”、“?:”等。

题目详情
100 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

小于或等于给定正整数n的数中,与n互质的数的个数,我们称为欧拉函数,记作。下面说法错误的是( )。

A
如果n是质数,那么。
B
两个质数一定是互质数。
C
两个相邻的数一定是互质数。
D
相邻的两个质数不一定是互质数。
答案与解析
正确答案:D

两个不同的质数是互质数。

题目详情