首页 › 题库 › GESP编程能力等级认证 › GESP-C++七级

GESP-C++七级 题库

共 270 道题 ,第 8 / 14 页 · 按题型筛选,点「查看答案」核对解析
141 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

深度优先搜索(DFS)在遍历图时,每当访问到某个顶点后,选择一个相邻的未访问顶点继续搜索,直到某个顶点的所有相邻顶点均已被访问,则退回到前一顶点继续搜索。该算法主要运用了( )。

A
分治
B
贪心
C
动态规划
D
回溯
答案与解析
正确答案:D
深度优先搜索在访问顶点后,选择一个未访问的相邻顶点深入遍历,当无法继续前进时,返回上一顶点尝试其他分支。该过程依赖于系统调用栈或手动维护栈记录路径,每次回退到前一状态以探索其余可能路径。这种机制体现的是在搜索过程中保存状态并在无路可走时退回尝试其他选择的行为模式。分治将问题拆解为独立子问题求解;贪心每一步选择当前最优解;动态规划保存子问题结果避免重复计算;回溯则通过逐步构建解并在不可行时撤销选择继续搜索。
题目详情
142 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

下面程序的运行结果为( )。

#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;
}


A
2
B
3
C
4
D
5
答案与解析
正确答案:B
程序包含两个函数:check 和 solve。check 函数接收数组 a、其长度 n、整数 k 和 dist,判断在排序后的数组中能否选出至少 k 个元素,使得相邻被选元素之间的差值不小于 dist。通过贪心策略遍历数组,统计满足条件的元素个数 cnt,并与 k 比较返回布尔结果。solve 函数先对数组排序,然后使用二分查找确定最大化的最小距离。左边界 l 初始化为 0,右边界 r 初始化为最大值与最小值之差。在 while 循环中,取 mid 为当前尝试的距离,根据 check 结果调整边界:若满足则增大下界,否则减小上界。最终逼近最优解。主函数调用 solve 并输出结果。
题目详情
143 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

下面程序的时间复杂度是( ),假设数组 的值域范围是 。

#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;
}


A
B
C
D
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
144 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

某二叉树共有 10 个结点,记为 A~J,已知它的先序遍历序列为:A B D H I E C F J G,中序遍历序列为:H D I B E A F J C G,则该二叉树的后序遍历序列是( )。

A
H I D E B J F G C A
B
H I D B E J F G C A
C
I H D E B J F G C A
D
H I D E B F J G C A
答案与解析
正确答案:A
根据先序遍历序列确定根节点,结合中序遍历序列划分左右子树。先序序列首元素为当前子树根节点,在中序序列中定位该节点,其左侧为左子树中序序列,右侧为右子树中序序列。通过左右子树结点数量反推先序序列中对应子树的范围。递归构建左右子树结构,直至所有子树均分解至空或单个结点。后序遍历顺序为左子树、右子树、根节点,依据重建的树结构按此顺序收集结点即可得到后序序列。
题目详情
145 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

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

A
1, 5, 4, 8, 7, 9, 6, 3, 2
B
1, 5, 8, 4, 7, 9, 6, 3, 2
C
2, 5, 8, 7, 9, 6, 3, 4, 1
D
8, 9, 6, 3, 2, 5, 1, 4, 7
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
146 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

关于泛洪算法(Flood Fill)的说法,正确的是( )。

A
泛洪算法只适用于二维网格中的四连通或八连通问题。
B
泛洪算法必须使用递归方式实现。
C
泛洪算法本质上是对图进行一次从起点出发的搜索
D
泛洪算法只能用于统计连通块个数,不能用于计算面积或周长。
答案与解析
正确答案:C
泛洪算法是一种基于图搜索的技术,从指定起点出发,遍历所有可达节点,常用于标记或修改连通区域。该算法不限于二维网格,可应用于任意图结构;实现方式包括递归和非递归(如使用栈或队列),无强制要求;其应用不仅限于统计连通块个数,还可用于计算面积、周长等属性。连通性判断取决于访问机制而非维度或方向限制。算法核心为节点访问与扩展,不依赖特定数据结构或实现形式。
题目详情
147 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

有 6 个字符,它们出现的次数分别为: {2, 3, 3, 4, 6, 8} ,现在用哈夫曼编码为这些字符编码,最小加权路径长度 WPL(每个字符的出现次数 它的编码长度,再把每个字符结果加起来)的值为( )。

A
58
B
60
C
62
D
64
答案与解析
正确答案:D
将给定的字符频次按从小到大排列,构建哈夫曼树:每次选取频次最小的两个节点合并为新节点,新节点的权值为两者之和,重复此过程直至只剩一个根节点。合并过程中,每个字符的编码长度等于其在树中的深度。计算最小加权路径长度WPL时,将每个字符的频次乘以其对应编码长度(即合并时参与的层数),累加所有结果。整个过程基于贪心策略,确保频次小的字符路径更长,频次大的字符路径更短,从而使得总加权路径长度最小。
题目详情
148 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

关于单链表、双链表和循环链表,下列说法正确的是( )。

A
在单链表中,若已知某结点的指针,则可以在时间内删除该结点。
B
循环链表中一定不存在空指针
C
在循环双链表中,尾结点的 next 指针一定为 NULL。
D
在带头结点的循环单链表中,判定链表是否为空只需判断头结点的 next 是否指向自身
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
149 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

下列关于树的遍历的说法中,正确的一项是( )。

A
对任意一棵树进行深度优先遍历,所得序列一定唯一。
B
已知一棵二叉树的先序遍历和后序遍历序列,可以唯一确定这棵二叉树
C
已知一棵二叉树的先序遍历和中序遍历序列,可以唯一确定这棵二叉树。
D
一棵二叉树的中序遍历序列是单调递增的,则该二叉树一定是二叉平衡树。
答案与解析
正确答案:C
深度优先遍历的序列唯一性取决于访问子节点的顺序是否固定。先序与后序遍历组合无法唯一确定二叉树结构,因缺乏根节点在序列中的明确分割位置。先序与中序遍历可唯一确定二叉树,先序提供根节点信息,中序区分左右子树范围。中序遍历单调递增仅说明节点值在中序下有序,不保证树形结构满足平衡条件。遍历序列的重建能力依赖于能否划分左右子树区间并定位根节点。
题目详情
150 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

下面这个有向图的强连通分量的个数是( )2026.3。

A
3
B
4
C
5
D
6
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
151 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

C++语言中,表达式 3 ^ 2 的结果类型为 int ,值为 9 。

A
对
B
错
答案与解析
正确答案:错
分析表达式中运算符的语义,确定其在C++语言标准中的定义;检查操作数的类型,判断是否触发隐式类型转换;依据标准规定的运算符行为,推导表达式的求值过程;根据类型提升规则和运算结果,确定表达式的类型和值的计算方式。
题目详情
152 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 1.1 三角函数

使用 cmath 头文件中的正弦函数,表达式 sin(90) 的结果类型为 double ,值约为 1.0 。

A
对
B
错
答案与解析
正确答案:错
分析表达式 sin(90) 的计算过程:首先确认 cmath 头文件中 sin 函数的参数为弧度值,输入 90 为角度数值,需转换为弧度参与运算;函数接受 double 类型参数并返回 double 类型结果;根据正弦函数定义,其输出值域在 [-1, 1] 范围内;实际计算结果取决于输入值对应的弧度精度。
题目详情
153 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

使用 strcmp("10", "9") 比较两个字符串,返回值大于0,说明 "10" 比 "9" 大。

A
对
B
错
答案与解析
正确答案:错
strcmp函数逐字符比较两个字符串的ASCII值,从左到右依次对比每个字符。当遇到第一个不相等的字符时,返回两个字符ASCII值的差。若所有对应字符均相等,则返回0。字符串"10"和"9"的首字符分别为'1'和'9',其ASCII值决定比较结果。比较过程在首个字符处即确定走向,后续字符不参与判断。
题目详情
154 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

求两个长度为 序列的最长公共子序列(LCS)长度时,可以使用滚动数组将空间复杂度从优化到。

A
对
B
错
答案与解析
正确答案:对
使用动态规划求解最长公共子序列时,状态转移依赖于前一行和当前行的值。通过滚动数组技术,仅保留当前行和上一行的状态,将二维DP表压缩为两个一维数组或单个一维数组循环更新,从而减少空间占用。每次遍历中,依据序列元素是否相等更新当前状态,覆盖旧行数据以实现空间复用。该方法将空间复杂度由O(mn)降至O(n),其中m和n分别为两序列长度。
题目详情
155 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

使用邻接矩阵存储一个有 个顶点、 条边的图,对该图进行一次完整的BFS遍历,时间复杂度为。

A
对
B
错
答案与解析
正确答案:错
确定图的顶点数n和边数m;获取邻接矩阵存储结构,其规模为n×n;BFS遍历从起始顶点开始,使用队列管理待访问顶点;每轮取出队首顶点,标记为已访问;遍历该顶点在邻接矩阵中的整行,查找所有邻接且未访问的顶点并加入队列;每一行的检查耗时O(n),最多处理n个顶点;总时间由访问所有顶点和检查所有矩阵元素决定;矩阵中每个元素被访问一次,共n²次操作;最终时间复杂度由顶点数n决定。
题目详情
156 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

使用链地址法处理冲突的哈希表,当所有元素都映射到同一个槽位时,查找操作的最坏时间复杂度为O(n),其中n为元素个数。

A
对
B
错
答案与解析
正确答案:对
分析哈希函数的映射行为,确定所有元素被分配至同一槽位的情形;考察链地址法在该槽位形成的链表结构;根据查找操作需遍历链表中节点的过程,推导出比较次数与元素总数的关系;结合时间复杂度定义,衡量输入规模增长时基本操作的执行频次变化趋势。
题目详情
157 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

一个包含V个顶点的连通无向图,其任何一棵生成树都恰好包含 V-1条边。

A
对
B
错
答案与解析
正确答案:对
分析连通无向图的生成树定义,明确生成树是极小连通子图且包含图中所有顶点。根据图论基本性质,生成树中不存在环路,且任意两个顶点间有唯一路径。若生成树边数少于V-1,则无法连通所有顶点;若多于V-1,则必然形成环路。因此生成树的边数与顶点数之间存在确定关系。
题目详情
158 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

选择排序是一种不稳定的排序算法,而冒泡排序是一种稳定的排序算法。2025.12-7

A
对
B
错
答案与解析
正确答案:对
分析排序算法的稳定性时,考察相同元素在排序前后相对位置是否保持不变。选择排序在交换过程中可能改变相同元素的相对位置,其机制不保证相等元素的先后顺序。冒泡排序通过相邻元素比较和交换实现,仅在严格大于时交换,相同元素不会发生位置变动,其机制能保持相等元素的原有顺序。两种算法的执行逻辑决定了其是否具备稳定性的特征。
题目详情
159 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

在无向图中,所有顶点的度数之和等于边数的两倍。2025.12-7

A
对
B
错
答案与解析
正确答案:错
分析无向图中每个边连接两个顶点,每条边对两个顶点的度数各贡献1。统计所有顶点的度数时,每条边被计算两次。将所有顶点的度数相加,总和来源于每条边的两次贡献。由此可得度数总和与边数之间存在固定倍数关系。通过枚举图中边与顶点的关联方式,可验证每条边在度数总和中对应两个单位增量。
题目详情
160 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 4.1 泛洪算法

在图像处理或游戏开发中,泛洪(flood fill)算法既可以用BFS实现,也可以用DFS实现。2025.12-7

A
对
B
错
答案与解析
正确答案:对
分析泛洪算法的实现机制,明确其可通过广度优先搜索(BFS)或深度优先搜索(DFS)两种遍历方式完成。BFS使用队列结构逐层访问相邻像素,按距离起始点的远近顺序处理;DFS使用栈结构(或递归调用)沿路径深入,直到无法继续再回溯。两种方法均能完整覆盖连通区域,区别在于访问节点的顺序与内存使用模式。算法选择取决于具体执行过程中的数据结构与遍历策略,不改变对连通区域填充的基本功能。
题目详情