2024年06月CCF-GESP编程能力等级认证C++编程八级真题解析

本文收录于专栏《C++等级认证CCF-GESP真题解析》，专栏总目录：点这里。订阅后可阅读专栏内所有文章。

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

第 1 题

GESP活动期间，举办方从获胜者ABCDE五个人中选出三个人排成一队升国旗，其中A不能排在队首，请问有多少种排法？
A. 24
B. 48
C. 32
D. 12

答案：B

第 2 题

7进制数235转换成3进制数是（）。
A. 11121
B. 11122
C. 11211
D. 11112

答案：A

第 3 题

0,1,2,3,4,5这些数字组成一个三位数，请问没有重复数字的情况下，有多少种组法（）。
A. 180
B. 120
C. 80
D. 100

答案：D

第 4 题

有V个顶点、E条边的图的深度优先搜索遍历时间复杂度为（）。
A. $O (V)$
B. $O (E)$
C. $O (V + E)$
D. $O (l o g (V + E))$

答案：C

第 5 题

一对夫妻生男生女的概率相同。已知这对夫妻有两个孩子，其中一个是女孩，另一个是男孩的概率是多少？
A. $\frac{2}{3}$
B. $\frac{1}{4}$
C. $\frac{1}{2}$
D. $\frac{1}{3}$

答案：C

第 6 题

从1到2024这2024个数中，共有（）个包含数字6的数。
A. 544
B. 546
C. 564
D. 602

答案：A

第 7 题

二进制数 100.001 转换成十进制数是（）。
A. 4.25
B. 4.125
C. 4.5
D. 4.75

答案：B

第 8 题

以下函数声明，哪个是符合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

第 9 题

下面有关C++重载的说法，错误的是（）。
A. 两个参数个数不同的函数可以重名。
B. 两个参数类型不同的函数可以重名。
C. 两个类的方法可以重名。
D. 所有C++运算符均可以重载。

答案：D

第 10 题

小于或等于给定正整数n的数中，与n互质的数的个数，我们称为欧拉函数，记作 $\phi(n)$ 。下面说法错误的是（）。
A. 如果n是质数，那么 $\phi(n)=n-1$ 。
B. 两个质数一定是互质数。
C. 两个相邻的数一定是互质数。
D. 相邻的两个质数不一定是互质数。

答案：D

第 11 题

已知一棵二叉树有10个节点，则其中至多有（）个节点有2个子节点。
A. 4
B. 5
C. 6
D. 3

答案：A

第 12 题

二项展开式 $(x+y)^n=x^n+n\dot{x}^{n-1}y+\frac{n(n-1)}{2}\dot{x}^{n-2}y^2+...+y^n$ 的系数，正好满足杨辉三角的规律。当时，二项式展开式中 $xy^9$ 项的系数是（）。
A. 5
B. 9
C. 10
D. 8

答案：C

第 13 题

下面程序的时间复杂度为（）。

bool notPrime[N] = {false};
void sieve() {
	for (int n = 2; n * n < N; n++)
		if (!notPrime[n])
			for (int i = n * n; i < N; i += n)
				notPrime[i] = true;
}

A. $O (N)$
B. $O (N \times l o g N)$
C. $O (N \times l o g l o g N)$
D. $O(N^2)$

答案：C

第 14 题

下面程序的最差时间复杂度为（）。

int gcd(int m, int n) {
	if (m == 0)
		return n;
	return gcd(n % m, m);
}

A. $O(\sqrt{n})$
B. $O (l o g (n))$
C. $O (n)$
D. $O (1)$

答案：B

第 15 题

下面程序的输出为（）。

#include <iostream>
using namespace std;
int main() {
	int cnt = 0;
	for (int x = 0; x <= 10; x++)
		for (int y = 0; y <= 10; y++)
			for (int z = 0; z <= 10; z++)
				if (x + y + z <= 15)
					cnt++;
	cout << cnt << endl;
	return 0;
}

A. 90
B. 91
C. 710
D. 711

答案：D

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

第 16 题

ABCDE五个小朋友，排成一队跑步，其中AB两人必须排在一起，一共有48种排法。

答案：正确

第 17 题

已知 double 类型的变量 a 和 b ，则执行语句 a = a + b; b = a - b; a = a - b; 后，变量 a 和 b 的值会互换。

答案：错误

第 18 题

一个袋子中有3个完全相同的红色小球、2个完全相同的蓝色小球。每次从中取出1个，再放回袋子，这样进行3次后，可能的颜色顺序有8种。

答案：正确

第 19 题

已知 int 类型的变量 a 和 b 中分别存储着一个直角三角形的两条直角边的长度，则斜边的长度可以通过表达式 sqrt(a * a + b * b) 求得。

答案：正确

第 20 题

在一个包含 v 个顶点、 e 条边的带权连通简单有向图上使用Dijkstra算法求最短路径，时间复杂度为 $O(v^2)$ ，可进一步优化至 $O (e + v l o g (v))$ 。

答案：正确

第 21 题

在 $N$ 个元素的二叉排序树中查找一个元素，最差情况的时间复杂度是 $O (l o g N)$ 。

答案：错误

第 22 题

C++语言中，可以为同一个类定义多个析构函数。

答案：错误

第 23 题

使用单链表和使用双向链表，查找元素的时间复杂度相同。

答案：正确

第 24 题

为解决哈希函数冲突，可以使用不同的哈希函数为每个表项各建立一个子哈希表，用来管理该表项的所有冲突元素。这些子哈希表一定不会发生冲突。

答案：错误

第 25 题

要判断无向图的连通性，在深度优先搜索和广度优先搜索中选择，深度优先的平均时间复杂度更低。

答案：错误

三、编程题（每题 25 分，共 50 分）

第 26 题

试题名称：最远点对
时间限制：1.0 s
内存限制：512.0 MB
题面描述
小杨有一棵包含 $n$ 个节点的树，这棵树上的任意一个节点要么是白色，要么是黑色。
小杨想知道相距最远的一对不同颜色节点的距离是多少。
输入格式
第一行包含一个正整数 $n$ ，代表树的节点数。
第二行包含 $n$ 个非负整数 $a_1,a_2,...,a_n$ （对于所有的 $1 \leq i \leq n$ ，均有 $a_i$ 等于 0 或 1），其中如果 $a_i=0$ ，则节点 $i$ 的颜色为白色；如果 $a_i=1$ ，则节点 $i$ 的颜色为黑色。
之后 $n - 1$ 行，每行包含两个正整数 $x_i,y_i$ ，代表存在一条连接节点 $x_i$ 和 $y_i$ 的边。
保证输入的树中存在不同颜色的点。
输出格式
输出一个整数，代表相距最远的一对不同颜色节点的距离。
样例1

样例解释
相距最远的不同颜色的一对节点为节点 2 和 5。
数据范围
在这里插入图片描述

对于全部数据，保证有 $1≤n≤10^5,0≤a_i≤1$ 。

参考程序

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<int> g[N];
int col[N];
int n;
int dep[N],far[N][2];
int ans;
void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	far[x][col[x]]=dep[x];
	for(int i:g[x]){
		if(i!=fa){
			dfs(i,x);
			for(int j=0;j<2;j++){
				if(far[x][j]!=-1&&far[i][j^1]!=-1){
					ans = max(ans,far[x][j]-dep[x]+far[i][j^1]-dep[x]);
				}
			}
			for(int j=0;j<2;j++){
				far[x][j]=max(far[x][j],far[i][j]);
			}
		}
	}
	ans = max(ans,far[x][col[x]^1]-dep[x]);
}
int main(){
	int n;
	cin>>n;
	memset(far,-1,sizeof far);
	for(int i=1;i<=n;i++){
		cin>>col[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	cout<<ans<<"\n";
}

第 27 题

试题名称：空间跳跃
时间限制：1.0 s
内存限制：512.0 MB

题面描述
小杨在二维空间中有 $n$ 个水平挡板，并且挡板之间彼此不重叠，其中第 $i$ 个挡板处于水平高度 $h_i$ ，左右端点分别位于 $l_i$ 与 $r_i$ 。
小杨可以在挡板上左右移动，当小杨移动到右端点时，如果再向右移动会竖直掉落，从而落到下方第一个挡板上，移动到左端点时同理。小杨在挡板上每移动 $1$ 个单位长度会耗费 $1$ 个单位时间，掉落时每掉落 $1$ 个单位高度也会耗费 $1$ 个单位时间。
小杨想知道，从第 $s$ 个挡板上的左端点出发到第 $t$ 个挡板需要耗费的最少时间是多少？
注意：可能无法从第 $s$ 个挡板到达到第 $t$ 个挡板。
输入格式
第一行包含一个正整数 $n$ ，代表挡板数量。
第二行包含两个正整数 $s, t$ ，含义如题面所示。
之后 $n$ 行，每行包含三个正整数 $l_i,r_i,h_i$ ，代表第 $i$ 个挡板的左右端点位置与高度。
输出格式
输出一个整数代表需要耗费的最少时间，如果无法到达则输出 $- 1$ 。
样例1

样例范围
耗费时间最少的移动方案为，从第 3 个挡板左端点移动到右端点，耗费 3 个单位时间，然后向右移动掉落到第 2 个挡板上，耗费 $100000 - 6 = 99994$ 个单位时间，之后再向右移动 1 个单位长度，耗费 1 个单位时间，最后向右移动掉落到第 1 个挡板上，耗费 3 个单位时间。共耗费 $3 + 99994 + 1 + 3 = 100001$ 个单位时间。
数据范围
在这里插入图片描述

对于全部数据，保证有 $1≤n≤1000,1≤l_i≤r_i≤10^5,1≤h_i≤10^5$ 。
参考程序

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e4+10;

struct edge {
	int v, w;
	edge() {
	}
	edge(int vv,int ww) {
		v=vv;
		w=ww;
	}
};

struct node {
	int dis, u;
	node () {
	}
	node (int diss,int uu) {
		dis=diss;
		u=uu;
	}
	bool operator>(const node& a) const {
		return dis > a.dis;
	}
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q;
int cnt;
void dijkstra(int s) {
	for (int i=1;i<=cnt;i++)dis[i]=INT_MAX;
	dis[s] = 0;
	q.push(node(0, s));
	while (!q.empty()) {
		int u = q.top().u;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto ed : e[u]) {
			int v = ed.v, w = ed.w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				q.push(node(dis[v], v));
			}
		}
	}
}

map<pair<int,int>,int> mp;
vector<int> es[2010];
int l[maxn],r[maxn],h[maxn];
int main() {
	int n;
	cin>>n;
	int s,t;
	cin>>s>>t;
	for (int i=1;i<=n;i++) {
		cin>>l[i]>>r[i]>>h[i];
		mp[make_pair(l[i],h[i])]=i;
		mp[make_pair(r[i],h[i])]=n+i;
		es[i].push_back(i);
		es[i].push_back(n+i);
		e[i].push_back(edge(n+i,r[i]-l[i]));
		e[n+i].push_back(edge(i,r[i]-l[i]));
	}
	cnt=2*n+1;
	for (int i=1;i<=n;i++) {
		int hh = -1,idx = i;
		for (int j=1;j<=n;j++) {
			if(i==j)continue;
			if(l[j]<=l[i]&&l[i]<=r[j]&&h[j]<=h[i]) {
				if(h[j]>hh) {
					hh=h[j];
					idx=j;
				}
			}
		}
		if(hh!=-1) {
			if(!mp[make_pair(l[i],hh)]) {
				mp[make_pair(l[i],hh)]=cnt++;
			}
			int v = mp[make_pair(l[i],hh)];
			e[i].push_back(edge(v,h[i]-hh));
			e[idx].push_back(edge(v,abs(l[i]-l[idx])));
			e[n+idx].push_back(edge(v,abs(l[i]-r[idx])));
			e[v].push_back(edge(idx,abs(l[i]-l[idx])));
			e[v].push_back(edge(n+idx,abs(l[i]-r[idx])));
			es[idx].push_back(v);
		}
		hh = -1,idx = i;
		for (int j=1;j<=n;j++) {
			if(i==j)continue;
			if(l[j]<=r[i]&&r[i]<=r[j]&&h[j]<=h[i]) {
				if(h[j]>hh) {
					hh=h[j];
					idx=j;
				}
			}
		}
		if(hh!=-1) {
			if(!mp[make_pair(r[i],hh)]) {
				mp[make_pair(r[i],hh)]=cnt++;
			}
			int v = mp[make_pair(r[i],hh)];
			e[n+i].push_back(edge(v,h[i]-hh));
			e[idx].push_back(edge(v,abs(r[i]-l[idx])));
			e[n+idx].push_back(edge(v,abs(r[i]-r[idx])));
			e[v].push_back(edge(idx,abs(r[i]-l[idx])));
			e[v].push_back(edge(n+idx,abs(r[i]-r[idx])));
			es[idx].push_back(v);
		}
	}
	dijkstra(s);
	int ans = INT_MAX;
	for (auto i:es[t]) {
		ans=min(ans,dis[i]);
	}
	if(ans!=INT_MAX)cout<<ans<<"\n"; else cout<<"-1\n";
}