CCF编程能力等级认证GESP—C++8级—样题1

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

1、从A城到C城需要经过B城，其中A到B可选高铁和飞机，B到C可以自驾或打的，请问A到C有几种交通选择（）。

A. 2
B. 4
C. 8
D. 不知道

2、下面程序输出的n的值是（ ）。

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int main(){
	int a, b, c, d, n = 0;
	for (a = 1; a < 5; a++)
		for (b = 1; b < 5; b++)
			for (c = 1; c < 5; c++)
				for (d = 1; d < 5; d++)
					if (a != b && a != c && a != d && b != c && b != d && c != d)
						if (a != 4){
							cout << a * 1000 + b * 100 + c * 10 + d << " ";
							n++; 
						}	
	cout << endl << n << endl;
	return 0;

A. 4
B. 12
C. 18
D. 24

3、对$(a+b{)}^5$ ,想求出$a^3{b}^2$ 的系数可以使用（ ）

A. 杨氏三角
B. 祖冲之角
C. 勾股三角
D. 杨辉三角

4、对于 4 个结点的简单有向图，最少（ ）条边可以形成一条覆盖所有顶点的环。

A. 5
B. 4
C. 3
D. 2

5、对正整数a和n（n 为2的正整数次幂），下面求aⁿ值的方法是（ ）

int fan(int a, int n){
	if (n == 0) return 1;
	if (n == 1) return a;
	long long s = fan(a, n / 2);
	return s * s;
}

A. 折半
B. 二分
C. 倍增
D. 迭代

6、平面内，通过一点可以作( )条平行于给定直线的直线？

A. 0
B. 1
C. 2
D. 无限多

7、定义常量const double pi=3.14159。如果一个等边三角形的边长为4，下列（ ）表达式可以求其面积 。

A. 16*sin(pi/3)
B. 16*cos(pi/3)
C. 8*sin(pi/3)
D. 8*cos(pi/3)

8、下面程序使用BFS遍历一个有n个顶点、边权都为1的无向图G，下面说法正确的是（ ）。

#include <vector> 
using namespace std;

#define N 2023
int n, m;
vector<int> G[N];
int q[N], hd, tl;
int dis[N]; 
void BFS(int st){
	hd = 1, tl = 0;
	for (int i = 1; i <= n; i++)
		dis[i] = -1;
	q[++tl] = st, dis[st] = 0;
	while (hd <= tl){
		int u = q[hd++];
		for (int i = 0; i < G[u].size(); i++){
			int v = G[u][i];
			if (dis[v] != -1)
				continue;
			dis[v] = dis[u] + 1;
			q[++tl] = v;
		}
	}
}

A. tl记录遍历的结点数
B. dis按照贪心法变化
C. dis存储st到其他顶点的距离
D. 算法复杂度是O(n^2)

9、下面的冒泡排序中尝试提前结束比较过程，横线处应该填写的代码是（ ）。

void BubbleSort(int R[], int n){
	int i, j, lastExchangeIndex;
	i = n;
	while (i > 1){
		lastExchangeIndex = 1;
		for (j = 1; j < i; j++)
			if (R[j + 1] < R[j]){
				int t;
				t = R[j], R[j] = R[j + 1], R[j + 1] = t;
				lastExchangeIndex = j;
			}
		________;
	} // while
} // BubbleSort

A. i = lastExchangeIndex + 1
B. i = lastExchangeIndex -1
C. i = lastExchangeIndex
D. i = lastExchangeIndex - j

10、对数列3、4、7、12、19、28、39求和，除简单累加外，还可以用下面（ ）来直接计算。

A. 等差数列求和
B. 等比数列求和
C. 斐波拉契数列
D. 其他某种有规律序列

11、约定杨辉三角形第0行只有1个元素是1，第1行有2个元素都是1，第四行的所有元素之和是（ ）？

A. 8
B. 16
C. 24
D. 32

12、下列程序的输出是 ( ) 。

int main(){
	int sum = 0, x;
	for (x = -10; x <= 10; x++)
		if ((3*x+5 >= -11) && (3*x+5 <= 11))
			sum += x;
	cout << sum;
	cout << endl;
	return 0;
}

A. -12
B. 0
C. 55
D. -55

13、对于具有n个元素的二叉排序树（又名二分查找树）进行前序遍历，其时间复杂度是( )？

A. O(1)
B. O(log n)
C. O(n)
D. O(n^2)

14、 Dijkstra的算法在实现时一般可以选用（ ）来提高效率？

A. 数组
B. 链表
C. 堆
D. 栈

15、有关下?代码的说法正确的是（ ）。

#include <iostream>

class Node{
public:
	int Value;
	Node* Next;
	
	Node(int Val, Node* Nxt = nullptr){
		Value = Val;
		Next = Nxt;
	}
};
int main(){
	Node* firstNode = new Node(10);
	firstNode->Next = new Node(100);
	firstNode->Next->Next = new Node(111, firstNode);
	return 0;
}

A. 上述代码构成单向链表。
B. 上述代码构成双向链表。
C. 上述代码构成循环链表。
D. 上述代码构成指针链表。

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

1、学校组织班际排球赛，每个班级可以派男女各一个参赛队伍，每队5人。班级A的每位同学都可以报名，那可
以用加法原理来计算A班有多少支候选队伍。( )

2、若a,x,b都是double类型，则对方程a*x+b=0求解的程序中可以直接用x=-b/a来求解。( )

3、从15本不同的书中选3本，总共有455种方法。 ( )

4、连通图G有n个顶点m条边，须删除m-n+1条边后才能变成一棵生成树。( )

5、 在C++语言中，所有int类型的值，经过若干次左移操作（<<）后，它们的值总会变为0。( )

6、如果一个四边形的对角线互相平分，并且两条对角线的长度都为8，那么这个四边形的面积一定是32。( )

7、 最小生成树的权值是指生成树所有边的权值之和最小。( )

8、如果一个图中所有边的权重都为正数，则Floyd算法可以求出该图中任意两个顶点间的最短路径。 ( )

9、下面是图的深度遍历的代码，则横线处可以填入：if(vis[x]) return。（ ）

void dfs(int x){
	________; //补充代码
	vis[x] = 1;
	cout << x << endl; //访问当前节点
	for (int i = vFirst[x]; i != -1; i = e[i].next){
		dfs(e[i].v);
	} 
}

10、下图中A到E的Dijkstra单源最短路可以在第2次探索中找到。（ )

编程题 (每题 25 分，共 50 分)

区间

【问题描述】
小杨有一个长度为n的正整数序列A。
小杨有q次询问。第i次（1 <= i <= q）询问时，小杨会给出$l_i,r_i,x_i$ ，请你求出$x_i$在$A_{l_i},A_{l_{i+1},...,A_{r_i}}$中出现的次数。
【输入描述】
第一行包含一个正整数T，表示数据组数。
对于每组数据：第一行包含一个正整数n，表示序列A的长度。第二行包含n个正整数$A_1,A_2,...,A_n$ ，表示序列A。第三行包含一个正整数q，表示询问次数。接下来q行，每行三个正整数$l_i,r_i,x_i$，表示一组询问。
【输出描述】
对于每组数据，输出q行。第i行（1 <= i <= q）输出一个非负整数，表示第i次询问的答案。
【样例输入 1】
2
5
7 4 6 1 1
2
1 2 3
1 5 1
5
1 2 3 4 5
2
5 5 3
1 4 3
【样例输出 1】
0
2
0
1
【子任务】
对于全部数据，保证有1 <= T <= 5 ，1 <= n <= 10⁵ ，1 <= q <= 10⁵ ，1 <= Ai <= 10⁹ 。

小杨的旅游

【问题描述】
小杨准备前往 B 国旅游。
B 国有n座城市，这n座城市依次以1至n编号。城市之间由n-1条双向道路连接，任意两座城市之间均可达（即任意两座城市之间存在可达的路径）。
小杨可以通过双向道路在城市之间移动，通过一条双向道路需要1 单位时间。
B 国城市中有k座城市设有传送门。设有传送门的城市的编号依次为$b_1,b_2,...,b_k$ 。小杨可以从任意一座设有传送门
的城市花费0单位时间前往另一座设有传送门的城市。
注：如果两座设有传送门的城市之间存在双向道路，那么小杨可以选择通过双向道路移动，也可以选择通过传送门传送。
小杨计划在 B 国旅游q次。第i次旅游（ 1 <= i <= q），小杨计划从编号为ui的城市前往编号为vi的城市，小杨希望
你能求出所需要的最短时间。
【输入描述】
第一行包含三个正整数n,k,q ，分别表示 B 国的城市数量，设有传送门的城市数量，以及小杨计划在 B 国旅游的次数。
接下来n - 1行，每行包含两个正整数xi, yi ，表示一条双向道路连接的两座城市的编号。
第n + 1行包含k个正整数$b_1,b_2,...,b_k$ ，表示设有传送门的城市的编号。
接下来q行，每行包含两个正整数ui,vi ，表示小杨第i次旅游行程的起点城市编号与终点城市编号。
【输出描述】
输出共q行。第i行（1 <= i <= q ）输出一个非负整数，表示小杨计划第i次旅游从编号为ui的城市前往编号为vi的城市所需要的最短时间。
【样例输入 1】
7 2 1
5 7
3 6
2 3
1 5
5 4
1 2
7 4
3 7
【样例输出 1】
4
【样例输入 2】
5 0 3
2 3
5 1
5 2
1 4
4 5
1 4
4 3
【样例输出 2】
2
1
4
【子任务】
对于全部数据，保证有1 <= k <= n <= 2 * 10⁵ ，1 <= q <= 2 * 10⁵ ，1 <= xi,yi <= n ，1 <= ui,vi <= n 。对于所有1 <= i <= n - 1，有 $x_i\ne y_i$。

参考答案

单选题

题号	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
答案	B	C	D	B	C	B	C	C	C	D	B	A	C	C	C

判断题

题号	1	2	3	4	5	6	7	8	9	10
答案	√	×	√	√	√	×	√	√	√	×

编程题1

#include <bits/stdc++.h>

const int maxn=100086;
using namespace std;
int t, n, q;
map<int,vector<int> >mp;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n;
		mp.clear();
		for(int i = 1;i <= n;i++){
			int x;
			cin>>x;
			mp[x].push_back(i);
		}
		cin>>q;
		while(q--){
			int l, r, x;
			cin>>l>>r>>x;
			cout<<upper_bound(mp[x].begin(), mp[x].end(), r) -
lower_bound(mp[x].begin(), mp[x].end(), l)<<endl;
		}
	}
}

编程题2

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define Getchar() p1==p2 and (p2=(p1=Inf)+fread(Inf,1,1<<21,stdin),p1==p2)?EOF:*p1++
#define Putchar(c) p3==p4 and (fwrite(Ouf,1,1<<21,stdout),p3=Ouf),*p3++=c

char Inf[1<<21],Ouf[1<<21],*p1,*p2,*p3=Ouf,*p4=Ouf+(1<<21);
inline void read(int &x,char c=Getchar()){
	bool f=c!='-';
	x=0;
	while(c<48 or c>57) c=Getchar(),f&=c!='-';
	while(c>=48 and c<=57) x=(x<<3)+(x<<1)+(c^48),c=Getchar();
	x=f?x:-x;
}
inline void write(int x){
	if(x<0) Putchar('-'),x=-x;
	if(x>=10) write(x/10),x%=10;
	Putchar(x^48);
}
int n,k,q,head[200010],mini[200010],dep[200010],siz[200010],hvson[200010],fa[200010],start[200010],pos;
struct edge{
	int to, next;
};
edge e[400010];
inline void add(const int &x,const int &y){
	static int cnt=0;
	e[++cnt].to=y,e[cnt].next=head[x],head[x]=cnt;
}
inline void dfs1(int pos,int fath,int de,int maxi=-0x3f3f3f3f){
	fa[pos]=fath,dep[pos]=de,siz[pos]=1;
	for(int i=head[pos];i;i=e[i].next)
		if(e[i].to!=fath){
			dfs1(e[i].to,pos,de+1),siz[pos]+=siz[e[i].to];
			if(siz[e[i].to]>maxi) hvson[pos]=e[i].to,maxi=siz[e[i].to];
	}
}
inline void dfs2(int pos,int Start){
	start[pos]=Start;
	if(hvson[pos]){
		dfs2(hvson[pos],Start);
		for(int i=head[pos];i;i=e[i].next) if(e[i].to!=fa[pos] && e[i].to!=hvson[pos]) dfs2(e[i].to,e[i].to);
	}
}
inline int lca(int x,int y){
	while(start[x]!=start[y])
		if(dep[start[x]]>=dep[start[y]]) x=fa[start[x]];
		else y=fa[start[y]];
	if(dep[x]>=dep[y]) return y;
	return x;
}
queue<int> qu;
inline void bfs(){
	while(!qu.empty()){
		pos=qu.front(),qu.pop();
		for(int i=head[pos];i;i=e[i].next) 
			if(mini[e[i].to]>mini[pos]+1)
				mini[e[i].to]=mini[pos]+1,qu.push(e[i].to);
	}
}
signed main(){
	read(n),read(k),read(q),memset(mini,0x3f,sizeof(mini));
	for(int i=1,x,y;i<n;i++) read(x),read(y),add(x,y),add(y,x);
	dfs1(1,0,1),dfs2(1,1);
	for(int i=1,x;i<=k;i++) read(x),mini[x]=0,qu.push(x);
	bfs();
	for(int i=1,x,y;i<=q;i++){
		read(x),read(y);
		write(min(dep[x]+dep[y]-dep[lca(x,y)]*2,mini[x]+mini[y])),Putchar('\n');
	}
	fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
	return 0;
}