GESP-C++七级 题库
深度优先搜索(DFS)在遍历图时,每当访问到某个顶点后,选择一个相邻的未访问顶点继续搜索,直到某个顶点的所有相邻顶点均已被访问,则退回到前一顶点继续搜索。该算法主要运用了( )。
下面程序的运行结果为( )。
#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;
}下面程序的时间复杂度是( ),假设数组 的值域范围是 。
#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;
}某二叉树共有 10 个结点,记为 A~J,已知它的先序遍历序列为:A B D H I E C F J G,中序遍历序列为:H D I B E A F J C G,则该二叉树的后序遍历序列是( )。
下面哪一个可能是下图的深度优先遍历序列( )。

关于泛洪算法(Flood Fill)的说法,正确的是( )。
有 6 个字符,它们出现的次数分别为: {2, 3, 3, 4, 6, 8} ,现在用哈夫曼编码为这些字符编码,最小加权路径长度 WPL(每个字符的出现次数 它的编码长度,再把每个字符结果加起来)的值为( )。
关于单链表、双链表和循环链表,下列说法正确的是( )。
下列关于树的遍历的说法中,正确的一项是( )。
C++语言中,表达式 3 ^ 2 的结果类型为 int ,值为 9 。
使用 cmath 头文件中的正弦函数,表达式 sin(90) 的结果类型为 double ,值约为 1.0 。
使用 strcmp("10", "9") 比较两个字符串,返回值大于0,说明 "10" 比 "9" 大。
求两个长度为 序列的最长公共子序列(LCS)长度时,可以使用滚动数组将空间复杂度从优化到。
使用邻接矩阵存储一个有 个顶点、 条边的图,对该图进行一次完整的BFS遍历,时间复杂度为。
使用链地址法处理冲突的哈希表,当所有元素都映射到同一个槽位时,查找操作的最坏时间复杂度为O(n),其中n为元素个数。
一个包含V个顶点的连通无向图,其任何一棵生成树都恰好包含 V-1条边。
选择排序是一种不稳定的排序算法,而冒泡排序是一种稳定的排序算法。2025.12-7
在无向图中,所有顶点的度数之和等于边数的两倍。2025.12-7
在图像处理或游戏开发中,泛洪(flood fill)算法既可以用BFS实现,也可以用DFS实现。2025.12-7
