首页 › 试卷 › GESP编程能力等级认证 › GESP-C++八级 › 2024年9月CCF-GESP编程能力等级认证C++编程八级真题

2024年9月CCF-GESP编程能力等级认证C++编程八级真题 VIP

GESP-C++八级 共 27 题 2024 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

下面关于C++类和对象的说法,错误的是( )。

  • A 类的析构函数可以为虚函数。
  • B 类的构造函数不可以为虚函数。
  • C class中成员的默认访问权限为private。
  • D struct中成员的默认访问权限为private。
查看答案与解析
答案:D
解析:

在C++中,struct默认的访问权限是public,而class的默认访问权限是private。如果你想改变这一默认行为,可以在struct中显式地声明成员为private。

2. 单选题

在一个单位圆上,随机分布 n 个点,求这 n 个点能被一个单位半圆周全部覆盖的概率( )。

  • A
  • B
  • C
  • D
查看答案与解析
答案:A
这道题暂未补解析。
3. 单选题

对于一个具有 n 个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小为( )。

  • A
  • B n×n
  • C (n−1)×(n−1)
  • D (n+1)×(n+1)
查看答案与解析
答案:B
解析:

n个顶点对的无向图,需要n行n列的矩阵(对称),可以用数组下标0~n-1对应,选B。

4. 单选题

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

  • A 5
  • B 120
  • C 20
  • D 60
查看答案与解析
答案:C
解析:

先从5个球中选择2个球放到对应的盒子中,有种,剩余的3个球不能和盒子编号相同,因此第3个球有2种盒子可以选择,第4个球和第5个球只有1种选择。

共10*2=20种,选C。

5. 单选题

从甲地到乙地,可以乘高铁,也可以乘汽车,还可以乘轮船。一天中,高铁有10班,汽车有5班,轮船有2班。那么一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法?( )。

  • A 100
  • B 60
  • C 30
  • D

    17

查看答案与解析
答案:D
解析:

由加法原理,ans=10+5+2=17种。

6. 单选题

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

  • A O(n)
  • B O(nlogn)
  • C O(logn)
  • D O(2n)
查看答案与解析
答案:A
解析:

对二叉树执行DFS,在回溯阶段依次释放每个节点,复杂度O(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++) {
		__________ // 在此处填入选项
	}
}
  • 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选项。

8. 单选题

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

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。

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;
}
  • 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
这道题暂未补解析。
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;
		}
	}
}
  • 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。

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

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];
				}
			}
		}
	}
}
  • 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。

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

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);
}
  • A O(nlogn)
  • B O(n2)
  • C O(2n)
  • D O(logn)
查看答案与解析
答案:A
解析:

归并排序基于分治

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

15. 单选题

下面 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
这道题暂未补解析。

二、判断题

16. 判断题

表达式 ‘3’ & 1 的结果为 ‘1’ 。

  • A对
  • B错
查看答案与解析
答案:错
解析:

ASCII码’3’为51,是奇数,&1操作是取51的最低位2进制。结果为1,而非字符’1’。

17. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
解析:

变量可以为全局变量。

18. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
解析:

基于比较的排序中不稳定的有四个:希尔,选择,快速,堆,其余都稳定。

19. 判断题

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

  • A对
  • B错
查看答案与解析
答案:对
解析:

二叉排序树查找的时间复杂度为树的高度。

20. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
解析:

cos函数接受的角度参数是以弧度为单位的。因此,如果要用角度(如60度)作为参数,需要先将其转换为弧度。在C或C++中,可以使用M_PI(在math.h或cmath中定义)来表示π,从而将60度转换为弧度,即60 * M_PI / 180。

21. 判断题

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

  • A对
  • B错
查看答案与解析
答案:对
解析:

7+5+5+5+5=27共5枚,且没有更优方案。

22. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
解析:

插板法:首先,我们有n个球排成一列,然后在这n个球之间以及两端共n+1个空位中选择k-1个位置插入隔板。这样,隔板将球分成了k组,每组中的球数即为该组的元素数(包括0个)。

组合计算:从n+1个空位中选择k-1个位置插入隔板,即组合数C(n+1, k-1)。但注意到,由于我们实际上是在n个球和k-1个板之间做选择,且板的数量是固定的k-1,所以更准确的组合应该是从n+k-1个“位置”(n个球和k-1个“潜在隔板位置”的总和)中选择k个“实体”(k-1个实际隔板和1个“虚拟”的起始或结束位置,用于确定组的边界),即C(n+k-1, k)。

23. 判断题

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

  • A对
  • B错
查看答案与解析
答案:对
解析:

a/2.0会自动隐式转换为double,从而保证结果的正确性。

24. 判断题

已知等差数列的通项公式an=a1+(n−1)⋅d,则前 n nn 项和的求和公式为Sn=n⋅(a1+an)/2。使用这一公式计算Sn的时间复杂度是O(1)。

  • A对
  • B错
查看答案与解析
答案:对
解析:

公式计算一步到位,和规模无关,复杂度O(1).

25. 判断题

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

  • A对
  • B错
查看答案与解析
答案:对
解析:

说谎的人回答的是去诚实国的路,诚实的人回答的是去诚实国的路,故而分辨出来。

三、简答题

26. 简答题

手套配对

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有 n 对不同的手套,每对手套由左右各一只组成。

小杨想知道从中取出 m 只手套,m 只手套恰好包含 k 对手套的情况有多少种。

小杨认为两种取出的情况不同,当且仅当两种情况取出的手套中存在不同的手套(同一对手套的左右手也视为不同的手套)。

输入格式

第一行包含一个正整数 t ,代表测试用例组数。

接下来是 t 组测试用例。对于每组测试用例,一共一行。

第一行包含三个正整数n,m,k,代表手套数量,取出的手套数和目标对数。

输出格式

对于每组测试数据,输出一个整数,代表可能的情况数量对109+7 取模的结果。

输入样例

2
5 6 2
5 1 5

输出样例

120
0

对于全部数据,保证有1≤t≤105,1≤n≤1000,1≤m≤2×n,1≤k≤n。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 2e3+10; const int p = 1e9+7; #define ll long long ll c[N][N]; ll pw[N]; int n,m,k; void init(){ pw[0]=1; for(int i=0;i&lt;N;i++){ if(i)pw[i]=pw[i-1]*2%p; for(int j=0;j&lt;=i;j++){ if(j==0)c[i][j]=1; else c[i][j]=(c[i-1][j]+c[i-1][j-1])%p; } } } int main(){ init(); int t; cin&gt;&gt;t; while(t--){ cin&gt;&gt;n&gt;&gt;m&gt;&gt;k; if(m&lt;2*k||m-2*k&gt;n-k){ cout&lt;&lt;"0\n"; continue; } ll ans=c[n][k]*c[n-k][m-2*k]%p; ans=ans*pw[m-2*k]%p; cout&lt;&lt;ans&lt;&lt;"\n"; } }</pre>
这道题暂未补解析。
27. 简答题

试题名称:美丽路径

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含 n 个节点的树,节点从 1 到 n 编号,并且每个节点要么是白色,要么是黑色。

对于树上的一条简单路径(不经过重复节点的路径),小杨认为它是美丽的当且仅当路径上相邻节点的颜色均不相同。例如下图,其中节点 1 和节点 4 是黑色,其余节点是白色,路径2−1−3−4 是美丽路径,而 路径2−1−3−5 不是美丽路径(相邻节点 3 和 5 颜色相同)。

对于树上的一条简单路径,小杨认为它的长度是路径包含节点的数量。小杨想知道最长的美丽路径的长度是多少。

输入格式

第一行包含一个正整数 n ,代表节点数量。

第二行包含 n 个整数c1,c2,...,cn,代表每个节点的颜色,如果 ci=0,代表节点 i 为白色,如果ci=1,代表节点 i 为黑色。

之后 n−1 行,每行包含两个正整数ui,vi,代表存在一条连接节点ui和节点vi的边。

输出格式

输出一个整数,代表最长美丽路径的长度。

输入样例1

5
1 0 0 1 0
1 2
3 5
4 3
1 3

输出样例1

4

输入样例2

5
0 0 0 0 0
1 2
2 3
3 4
4 5

输出样例

1

对于全部数据,保证有1≤n≤105,0≤ci≤1,同时保证给出的数据构成一棵树。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 1e5+10; vector&lt;int&gt; g[N]; int dep[N],vis[N],c[N]; int n,ans; int dfs(int x,int fa){ vis[x]=1; dep[x]=dep[fa]+1; int mx = dep[x]; vector&lt;int&gt; tmp; tmp.push_back(mx); for(auto i:g[x]){ if(i==fa||c[i]==c[x])continue; int d = dfs(i,x); tmp.push_back(d); mx = max(d,mx); } sort(tmp.begin(),tmp.end()); int m = tmp.size(),res=1; if(m&gt;1){ res = tmp[m - 1] + tmp[m - 2] - 2 * dep[x] + 1; } ans=max(ans,res); return mx; } int main(){ cin&gt;&gt;n; for(int i=1;i&lt;=n;i++){ cin&gt;&gt;c[i]; } for(int i=1;i&lt;n;i++){ int u,v; cin&gt;&gt;u&gt;&gt;v; g[u].push_back(v); g[v].push_back(u); } for(int i=1;i&lt;=n;i++){ if(!vis[i]){ dfs(i,0); } } cout&lt;&lt;ans&lt;&lt;"\n"; }</pre>
解析:

1.定义DP[x][0/1]:x以x为根的,x颜色为(0白1黑)的最长链路节点数量

初始化:DP[x][A[x]]=1 ,DP[x][1-A[x]]=0;

2.定义Fx:穿过x的满足题目要求的最长节点数量,则Fx由以x为端点的最长链和次长链组成。

状态转移方程:

对(父亲x->孩子y A[x]为x的节点颜色)

①若A[x]=0:DP[x][0]=max(DP[x][0],DP[y][1]+1);

②若A[x]=1:DP[x][1]=max(DP[x][1],DP[y][0]+1);

在此基础上,Fx因为由最长和次长组成,因此需要在DP[x]更新前完成更新,因此:

①若A[x]=0

Fx=max(Fx,DP[x][0]+DP[y][1]);

DP[x][0]=max(DP[x][0],DP[y][1]+1);

②若A[x]=1;

Fx=max(Fx,DP[x][1]+DP[y][0]);

DP[x][1]=max(DP[x][1],DP[y][0]+1);

目标状态:Fx