GESP认证
万卷网> GESP认证 >C++ > 2024年12月CCF—GESP（C++七级）编程能力等级认证试卷

2024年12月CCF—GESP（C++七级）编程能力等级认证试卷
七级 2024 2025-06-03 14:39:58 81次

一、单选题

1．

下列关于二叉树的说法，错误的是（ ）。

A．

二叉排序树的中序遍历顺序与元素排序的顺序是相同的。

 B．

n 个元素的二叉排序树，其高一定为 [log2n]。
C．

自平衡二叉查找树（AVL树）是一种二叉排序树。


 D．

任意的森林，都可以映射为一颗二叉树进行表达和存储。
答案 详情
2．

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

int sieve[MAX_N];
void init_sieve(int n) {
	for (int i = 1; i <= n; i++)
		sieve[i] = i;
	for (int i = 2; i <= n; i++)
		for (int j = i; j <= n; j += i)
			sieve[j]--;
}
A．

O(n)

 B．

O(nlogn)
C．

O(n2)

 D．

无法正常结束。
答案 详情
3．

一棵二叉树的每个结点均满足：结点的左子树和右子树，要么同时存在，要么同时不存在。该树有197个结点，则其叶结点有多少个？( )

A．

98

 B．

99
C．

不存在这样的树。

 D．

无法确定叶结点数量。
答案 详情
4．

已知小写字母 b 的ASCII码为98，下列C++代码的输出结果是（ ）。

#include <iostream>
using namespace std;
int main() {
	char a = 'b';
	cout << a + 1;
	return 0;
}
A．

b

 B．

c
C．

98

 D．

99
答案 详情
5．

下列关于有向图的说法，错误的是( )。

A．

n 个顶点的弱连通有向图，最少有 n−1 条边。

 B．

n 个顶点的强连通有向图，最少有 n 条边。
C．

n 个顶点的有向图，最多有 n×(n−1) 条边。

 D．

n 个顶点的有向完全图，有 n×(n−1) 条边。
答案 详情
6．

下面程序的输出为（ ）。

#include <iostream>
#define N 10
using namespace std;
int h[N];
int main() {
	h[0] = h[1] = 1;
	for (int n = 2; n < N; n++)
		for (int j = 0; j < n; j++)
			h[n] += h[j] * h[n - j - 1];
	cout << h[6] << endl;
	return 0;
}
A．

132

 B．

1430
C．

16796

 D．

结果是随机的。
答案 详情
7．

以下关于动态规划的说法中，错误的是（ ）。

A．

动态规划方法将原问题分解为一个或多个相似的子问题。

 B．

动态规划方法通常能够列出递推公式。
C．

动态规划方法有递推和递归两种实现形式。

 D．

递推实现动态规划方法的时间复杂度总是不低于递归实现。
答案 详情
8．

一个哈希表，包括n个位置（分别编号0~(n-1)），每个位置最多仅能存储一个元素。该哈希表只有插入元素和查询两种操作，没有删除或修改元素的操作。以下说法错误的是（ ）。

A．

如果哈希函数取值范围为0 ~ (n-1)，且当发生哈希函数碰撞时循环向后寻找空位，则查询操作的最差时间复杂度为 O(n)。（“循环向后”指：0向后一位为1，1向后一位为2，……，(n-2)向后一位为(n-1)，(n-1)向后一位为0）

 B．

如果哈希函数取值范围为0 ~ (n-1)，且当发生哈希函数碰撞时仅循环向后一个位置寻找空位，则查询操作的最差时间复杂度为 O(1)。
C．

如果哈希函数取值范围为0 ~ (m-1)（m < n），且当发生哈希函数碰撞时仅在m ~ (n-1)的范围内寻找空位，则查询操作的最差时间复杂度为 O(n−m)。

 D．

查询操作时，如果发现查询元素经哈希函数对应的位置为空位，该查询元素仍可能出现在哈希表内。
答案 详情
9．

下列选项中，哪个不可能是下图的深度优先遍历序列（ ）。

A．

1, 2, 3, 5, 7, 8, 6, 9, 4

 B．

1, 4, 7, 8, 9, 5, 2, 3, 6
C．

1, 5, 7, 8, 9, 4, 2, 3, 6

 D．

1, 2, 3, 6, 9, 8, 5, 7, 4
答案 详情
10．

下列关于C++类的说法，错误的是( )。

A．

构造函数不能声明为虚函数，但析构函数可以。

 B．

函数参数如声明为类的引用类型，调用时不会调用该类的复制构造函数。
C．

静态方法属于类、不属于对象，因此不能使用 对象.方法(…) 的形式调用静态方法。

 D．

析构派生类的对象时，一定会调用基类的析构函数。
答案 详情
11．

下面程序的输出为（ ）。

#include <iostream>
#include <cmath>
using namespace std;
int main() {
	cout << (int)exp(2) << endl;
	return 0;
}
A．

4

 B．

7
C．

100

 D．

无法通过编译。
答案 详情
12．

一个简单无向图有10个结点、6条边。在最差情况，至少增加多少条边可以使其连通？（ ）

A．

3

 B．

4
C．

6

 D．

9
答案 详情
13．

上题中程序的时间复杂度为（ ）。

A．

O(N)

 B．

O(NlogN)
C．

O(N3/2)

 D．

O(N2)
答案 详情
14．

已知数组 a 的定义 int a[10] = {0}; ，下列说法不正确的是（ ）。

A．

语句 a[-1] = 0; 会产生编译错误。

 B．

数组 a 的所有元素均被初始化为 0 。
C．

数组 a 至少占用 10 个 int 大小的内存，一般为 40 个字节。

 D．

语句 a[13] = 0; 不会产生编译错误，但会导致难以预测的运行结果。
答案 详情
15．

已知 a 为 int 类型变量， p 为 int * 类型变量，下列赋值语句不符合语法的是（ ）。

A．

+a = *p;

 B．

*p = +a;
C．

a = *(p + a);

 D．

*(p + a) = a;
答案 详情

二、判断题

1．

使用 math.h 或 cmath 头文件中的函数，表达式 log2(32) 的结果为 5 、类型为 int 。

A．正确 B．错误
答案 详情
2．

在 n 个元素中进行二分查找，平均时间复杂度是 O(logn)，但须要事先进行排序。

A．正确 B．错误
答案 详情
3．

MD5是一种常见的哈希函数，可以由任意长度的数据生成128位的哈希值，曾广泛应用于数据完整性校验。

中国科学家的系列工作首次发现了可实用的MD5破解方法。之后，MD5逐渐被其他哈希函数所取代。

A．正确 B．错误
答案 详情
4．

C++是一种面向对象编程语言，C则不是。继承是面向对象三大特性之一。因此，使用C语言无法实现继承。

A．正确 B．错误
答案 详情
5．

一个图中，每个顶点表达一个城市，连接两个顶点的边表达从一个城市到达另一个城市的一种交通方式。这个图可以用来表达交通网络，且是简单有向图。

A．正确 B．错误
答案 详情
6．

在C++语言中，函数定义和函数调用可以不在同一个文件内。

A．正确 B．错误
答案 详情
7．

unsigned long long 类型是C++语言中表达范围最大的非负整数类型之一，其表达范围是 [0,264−1]。超出该范围的非负整数运算，将无法使用C++语言进行计算。

A．正确 B．错误
答案 详情
8．

递归调用在运行时会由于层数过多导致程序崩溃，可以通过循环配合栈缓解这一问题。

A．正确 B．错误
答案 详情
9．

表达式 5 ^ 3 的结果为 125 。

A．正确 B．错误
答案 详情
10．

邻接表和邻接矩阵都是图的存储形式。邻接表在遍历单个顶点的所有边时，时间复杂度更低；邻接矩阵在判断两个顶点之间是否有边时，时间复杂度更低。

A．正确 B．错误
答案 详情

三、编程题

1．

燃烧

时间限制：1.0 s

内存限制：512.0 MB

题面描述

小杨有一棵包含 n 个节点的树，其中节点的编号从 1 到 n 。节点 i 的权值为 ai。

小杨可以选择一个初始节点引燃，每个燃烧的节点会将其相邻节点中权值严格小于自身权值的节点也引燃，火焰会在节点间扩散直到不会有新的节点被引燃。

小杨想知道在合理选择初始节点的情况下，最多可以燃烧多少个节点。

输入格式

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

第二行包含 n 个正整数 a1,a2,...,an，代表节点权值。

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

输出格式

输出一个正整数，代表最多燃烧的节点个数。


输入样例

5
6 2 3 4 5
1 2
2 3
2 5
1 4

输出样例

3

对于全部数据，保证有 1≤n≤105,1≤ai≤106。

答案 详情
2．

武器购买

时间限制：1.0 s

内存限制：512.0 MB

题面描述

商店里有 n 个武器，第 i 个武器的强度为 pi，花费为 ci。

小杨想要购买一些武器，满足这些武器的总强度不小于 P ，总花费不超过 Q ，小杨想知道是否存在满足条件的购买方案，如果有，最少花费又是多少。

输入格式

第一行包含一个正整数 t ，代表测试数据组数。

对于每组测试数据，第一行包含三个正整数 n,P,Q，含义如题面所示。

之后 n 行，每行包含两个正整数 pi,ci，代表武器的强度和花费。

输出格式

对于每组测试数据，如果存在满足条件的购买方案，输出最少花费，否则输出 -1。


输入样例

3
3 2 3
1 2
1 2
2 3
3 3 4
1 2
1 2
2 3
3 1000 1000
1 2
1 2
2 3

输出样例

3
-1
-1

对于全部数据，保证有 1≤t≤10,1≤n≤100,1≤pi,ci,P,Q≤5×104。

答案 详情
万卷网 版权所有 蒙ICP备2025029916号-1

蒙公网安备15040202200102号
由于万卷网是一个信息共享平台，不保证部分用户上传资料的来源及知识产权归属。如您发现相关资料侵犯您的合法权益，请联系万卷网，我们核实后将及时进行处理。
公众号
客服 反馈
顶部