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

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

1、如果下面代码输入整数为10，输出是1，则横线处填写？（ ）

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

int main() {
	int x;
	cin >> x;
	cout << ________ << endl;
	return 0;
}

A. log10(x)
B. sin(x)
C. exp(x)
D. pow(x,10)

2、下面定义的函数用来求斐波那契数列的F(n)，其中 ，描述正确的是（ ）。

int fab(int n){
	int f[n + 1];
	f[0] = 0, f[1] = 1;
	for (int i = 2; i <= n; i++)
		f[i] = f[i - 1] + f[i - 2];
	return f[n];
}

A. f[0]和f[1]是递归终止条件
B. 数组f保存算法执行过程的状态
C. 使用倍增法来求解
D. 算法不能正常结束

3、下列关于C++语言中函数的叙述，正确的是（ ）。

A. 函数定义前必须声明
B. 函数调用前必须定义
C. 函数调用时必须提供足够的实际参数
D. 函数声明只能写在函数调用前

4、4个结点的简单有向图，最多可以有多少条边（ ）。

A. 4
B. 6
C. 8
D. 12

5、哈希表上可以执行的操作不包括（ ）

A. 插入
B. 排序
C. 查找
D. 删除

6、将关键码集合{100，300，500，700，800，900}逐一保存在一个长度为100的哈希表中，选取哈希函数为Hash(key)=key/100，则800保存在表中的位置应该是（ ）。

A. 5
B. 6
C. 7
D. 8

7、定义double型常量pi=3.14和变量x，x代表等边三角形边长，则该三角形的面积是（ ）。

A. x*x*sin(pi/3)
B. x*x*sin(pi/3)/2
C. x*x*cos(pi/3)
D. x*x*cos(pi/3)/2

8、动态规划将一个问题分解为一系列子问题后来求解。下面关于子问题的描述正确的是（ ）。

A. 具有重叠子问题的性质
B. 和分治法的子问题类似
C. 不具有最优子结构的性质
D. 问题的最优解可以由部分子问题的非最优解推导出来

9、阅读以下代码，visited起到的作用是（ ）。

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

int visited[100], k = 0;
void dfs(int graph[][100], int start, int int vexnum){
	visited[start] = ++k;
	cout << start << " ";
	for (int i = 0; i < vexnum; i++){
		if ((start != i) && !visited[i]){
			dfs(graph, i, vexnum);
		}
	}
}

A. 实现遍历过程
B. 以广度优先的方式记录图中的顶点
C. 存储深搜时节点的访问顺序
D. 能够记录最短路径

10、下面函数尝试使用动态规划方法求出如下递推公式的函数，则横线处填写下列哪段代码可以完成预期功能?（ ）
$C(n,m)=\{\begin{array}{ll}1& \text{当n?=?0?或?m?=?0}\\ C(n?1,m?1)+C(n?1,m)& \text{当?n?>?0?且?m?>?0}\end{array}$

int rec_C[MAXN][MAXN];
int C(int n, int m){
	for (int i = 0; i <= n; i++)
		rec_C[i][0] = 1;
	for (int j = 0; i <= m; j++)
		rec_C[0][j] = 1;
	________ //在此处填写 代码
		rec_C[i][j] = rec_C[i - 1][j - 1] + rec_C[i - 1][j];
	return rec_C[n][m]; 
}

A. for (int i = n; i >= 1; i--) for (int j = 1; j <= m; j++)
B. for (int i = 1; i <= n; i++) for (int j = m; j >= 1; j--)
C. for (int j = 1; j <= m; j++) for (int i = 1; i <= n; i++)
D. for (int j = 1; j <= m; j++) for (int i = n; i >= 1; i--)

11、深度为4的完全二叉树，结点总数最少有多少个？（ ）

A. 5
B. 6
C. 7
D. 8

12、下面有向图中的数字表示顶点序号，则从1号顶点出发的BFS遍历的输出顶点序列可能是（ ）。

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

13、一个简单有向图有20个结点，假设图中已经存在300条边，请问增加多少条边可以成为完全图。（ ）

A. 77
B. 78
C. 79
D. 80

14、在下面的有向图中，强连通分量有多少个？（ ）

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

15、下?有关格雷码的说法，错误的是（ ）。

A. 在格雷码中，任意两个相邻的代码只有一位二进制数不同
B. 格雷码是一种唯一性编码
C. 在格雷码中，最大数和最小数只有一位二进制数不同
D. 格雷码是一种可靠性编码

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

1、定义变量double x=exp(-1)，则x<0为真。( )

2、 假设x和y都是double型正数，如果说x比y大一个数量级，log(x/y)等于10。( )

3、如果double型变量x代表锐角对应的弧度角，则可以编程来确定sin(x)>cos(x)的近似区间。( )

4、pow(1,2)返回的结果是浮点数。( )

5、如果哈希表足够大，哈希函数确定后，不会产生冲突。( )

6、动态规划最终要推导出状态转移方程才能求解。( )

7、简单有向图的深搜结果和广搜结果一样。( )

8、判断图是否连通可以用深搜实现。( )

9、在C++中，可以使?二分法查找链表中的元素。( )

10、有些算法或数据结构在C/C++语?中使?指针实现，?个典型的例?就是链表。因此，链表这?数据结构在C/C++语?中只能使?指针来实现。( )

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

迷宫统计

【问题描述】
在神秘的幻想大陆中，存在着n个古老而神奇的迷宫，迷宫编号从1到n。有的迷宫之间可以直接往返，有的可以走到别的迷宫，但是不能走回来。玩家小杨想挑战一下不同的迷宫，他决定从m号迷宫出发。现在，他需要你帮助他统计：有多少迷宫可以直接到达m号迷宫，m号迷宫可以直接到达其他的迷宫有多少，并求出他们的和。
需要注意的是，对于i (1 <= i <= n ) 号迷宫，它总可以直接到达自身。
【输入描述】
第一行两个整数n和m，分别表示结点迷宫总数n，指定出发迷宫的编号m 。
下面n行，每行n个整数，表示迷宫之间的关系。对于第i行第j列的整数，1表示能从i号迷宫直接到达j号迷宫，0表示不能直接到达。
【输出描述】
一行输出空格分隔的三个整数，分别表示迷宫m可以直接到达其他的迷宫有多少个，有多少迷宫可以直接到达m号
迷宫，这些迷宫的总和。
【样例输入 1】
6 4
1 1 0 1 0 0
0 1 1 0 0 0
1 0 1 0 0 1
0 0 1 1 0 1
0 0 0 1 1 0
1 0 0 0 1 1
【样例输出 1】
3 3 6
【样例解释 1】
4号迷宫能直接到达的迷宫有3,4,6 号迷宫，共3个。
能直接到达4号迷宫的迷宫有1,4,5号迷宫，共3个。
总和为6。
【子任务】
对于全部数据，保证有4 <= n <= 1000 ，1 <= m <= n 。

最长不下降子序列

【问题描述】
小杨有一个包含n个节点m条边的有向无环图，其中节点的编号为 1到n。
对于编号为i的节点Ai，其权值为 。对于图中的一条路径，根据路径上的经过节点的先后顺序可以得到一个节点权
值的序列，小杨想知道图中所有可能序列中最长不下降子序列的最大长度。
注：给定一个序列S ，其最长不下降子序列S’ 是原序列中的如下子序列：整个子序列S’ 单调不降，并且是序列中最长的单调不降子序列。例如，给定序列S = [11,12,13,9,8,17,19] ，其最长不下降子序列为S’=[11,12,13,17,19]，长度为5 。
【输入描述】
第一行包含两个正整数n,m ，表示节点数和边数。第二行包含n个正整数A1,A2,…,An ，表示节点1到n的点权。之后m行每行包含两个正整数ui,vi ，表示第i条边连接节点ui和vi ，方向为从ui到vi。
【输出描述】
输出一个正整数，表示该图中所有可能序列中最长不下降子序列的最大长度。
【样例输入 1】
5 4
2 10 6 3 1
5 2
2 3
3 1
1 4
【样例输出 1】
3
【样例输入 2】
6 11
1 1 2 1 1 2
3 2
3 1
5 3
4 2
2 6
3 6
1 6
4 6
1 2
5 1
5 4
【样例输出 2】
4
【样例输入 3】
6 11
5 9 10 5 1 6
5 4
5 2
4 2
3 1
5 3
6 1
4 1
4 3
5 1
2 3
2 1
【样例输出 3】
4
【子任务】
对于全部数据，保证有1 <= n <= 10⁵ ，1 <= m <= 10⁵ ，1 <= Ai <= 10 。

参考答案

单选题

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

判断题

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

编程题1

#include<cstdio>
#define M 101
int g[M][M];
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&g[i][j]);
		}
	}
	int ans1 = 0,ans2 = 0;
	for(int i=1;i<=n;i++){
		ans1+=g[i][m];
		ans2+=g[m][i];
	}
	printf("%d %d %d",ans2,ans1,ans1+ans2);
	return 0;
}

编程题2

#include "bits/stdc++.h"

using namespace std;
const int N = 100010;
vector<int> g[N];
int n,m;
int a[N];
int d[N],dp[N][15];

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		d[v]++;
	}
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(!d[i]){
			q.push(i);
			dp[i][a[i]]=1;
	}
	}
	while(!q.empty()){
		int now = q.front();
		q.pop();
		for(auto i:g[now]){
			for(int j=1;j<=10;j++){
				dp[i][j]=max(dp[i][j],dp[now][j]);
			}
			d[i]--;
			if(!d[i]){
				for(int k=a[i];k>=1;k--){
					dp[i][a[i]]=max(dp[i][a[i]],dp[i][k]+1);
				}
				q.push(i);
			}
		}
	}
	int mx=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=10;j++){
			mx=max(mx,dp[i][j]);
		}
	}
	cout<<mx<<"\n";
}