选择题 共15道

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

判断题 共10道

16 17 18 19 20 21 22 23 24 25

编程题 共2道

26 27

E1035 202603 CCF-GESP C++七级真题-练习

选择题 共15道
01 假设一个算法时间复杂度的递推式是 T(n)=2T(n-1)+1（n为正整数），且T(0)=1，那么这个算法的时间复杂度是（ ）。 2分
登录后查看选项
02 下面关于“唯一分解定理”和“素数筛法”的说法中，错误的是（ ）。 2分
登录后查看选项
03 若字符串A与字符串B的最长公共子序列（LCS）长度为 5，则（ ）。 2分
登录后查看选项
04 对于一棵包含n个顶点（ n≥2 ）的树，其所有顶点的度数之和必定等于（ ）。 2分
登录后查看选项
05 关于哈希表（Hash Table）在不考虑扩容且采用简单均匀哈希函数的前提下，下列说法中错误的是（ ）。 2分
登录后查看选项
06 深度优先搜索（DFS）在遍历图时，每当访问到某个顶点后，选择一个相邻的未访问顶点继续搜索，直到某个顶点的所有相邻顶点均已被访问，则退回到前一顶点继续搜索。该算法主要运用了（ ）。 2分
登录后查看选项
07

下面程序的运行结果为（ ）。

#include <iostream>
#include <algorithm>
bool check(int n, int a[], int k, int dist) {
	int cnt = 1;
	int last = a[0];
	for (int i = 1; i < n; i++) {
		if (a[i] - last >= dist) {
			cnt++;
			last = a[i];
		}
	}
	return cnt >= k;
}
int solve(int n, int a[], int k) {
	std::sort(a, a + n);
	int l = 0;
	int r = a[n - 1] - a[0];
	while (l < r) {
		int mid = (l + r + 1) / 2;
		if (check(n, a, k, mid))
			l = mid;
		else
			r = mid - 1;
	}
	return l;
}
int main() {
	int a[] = {1, 2, 8, 4, 9};
	int n = 5;
	int k = 3;
	std::cout << solve(n, a, k) << std::endl;
	return 0;
}
2分
登录后查看选项
08

下面程序的时间复杂度是（ ），假设数组 的值域范围是 。

##include <iostream>
#include <algorithm>
bool check(int n, int a[], int k, int dist) {
	int cnt = 1;
	int last = a[0];
	for (int i = 1; i < n; i++) {
		if (a[i] - last >= dist) {
			cnt++;
			last = a[i];
		}
	}
	return cnt >= k;
}
int solve(int n, int a[], int k) {
	std::sort(a, a + n);
	int l = 0;
	int r = a[n - 1] - a[0];
	while (l < r) {
		int mid = (l + r + 1) / 2;
		if (check(n, a, k, mid))
			l = mid;
		else
			r = mid - 1;
	}
	return l;
}
int main() {
	int a[] = {1, 2, 8, 4, 9};
	int n = 5;
	int k = 3;
	std::cout << solve(n, a, k) << std::endl;
	return 0;
}
2分
登录后查看选项
09 某二叉树共有 10 个结点，记为 A~J，已知它的先序遍历序列为：A B D H I E C F J G，中序遍历序列为：H D I B E A F J C G，则该二叉树的后序遍历序列是（ ）。 2分
登录后查看选项
10

下面哪一个可能是下图的深度优先遍历序列（ ）。

 2分
登录后查看选项
11

下面这个有向图的强连通分量的个数是（ ）。

 2分
登录后查看选项
12 关于泛洪算法（Flood Fill）的说法，正确的是（ ）。 2分
登录后查看选项
13 有 6 个字符，它们出现的次数分别为： {2, 3, 3, 4, 6, 8} ，现在用哈夫曼编码为这些字符编码，最小加权路径长度 WPL（每个字符的出现次数 它的编码长度，再把每个字符结果加起来）的值为（ ）。 2分
登录后查看选项
14 关于单链表、双链表和循环链表，下列说法正确的是（ ）。 2分
登录后查看选项
15 下列关于树的遍历的说法中，正确的一项是（ ）。 2分
登录后查看选项
判断题 共10道
16 C++ 语言中，表达式 4 ^ 2 的结果类型为 int ，值为 6 。 2分
登录后查看选项
17 C++ 中引用可以重新绑定。 2分
登录后查看选项
18 在 C++ 中，若函数形参为引用类型，则在函数内部对该形参的修改会影响对应的实参。 2分
登录后查看选项
19 如果一个最值问题可以用动态规划在多项式时间内求解，那么也一定存在一种贪心策略，可以在多项式时间内求得最优解。 2分
登录后查看选项
20 使用归并排序对 n 个元素进行排序时，无论最好、最坏还是平均情况，时间复杂度均为 O(n log n)。 2分
登录后查看选项
21 在无向连通图中删除一条边，该图就一定变成非连通图。 2分
登录后查看选项
22

在一个无向图中，每个顶点有不同的编号，在执行深度优先遍历过程中选择下一个顶点时总是优先选择编号

更小的相邻顶点，则从指定顶点开始的遍历序列是唯一的。

 2分
登录后查看选项
23 若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。 2分
登录后查看选项
24 使用 math.h 或 cmath 头文件中的函数，表达式 sin(90) 的结果为 1 。 2分
登录后查看选项
25 在一个无向连通图中，从任意顶点开始进行深度优先遍历，最终得到的 DFS 生成树一定包含图中的所有顶点。 2分
登录后查看选项
编程题 共2道
26

25分
登录后作答
27

25分
登录后作答
登录练习