GESP 七级 · 2024 真题
复刻
① 本卷为客观题单卷，合计 25 题 · 50 分，全部为客观题；
② 试卷右上角设有 「提交答卷」 与 「重置考试」 按钮，提交后系统自动判分并显示答题正确情况，请确认全部作答后再行提交；
③ 试卷不显示答案，提交后方可查看每题作答与正确答案的对照；
④ 答卷进度会保留在本地缓存中，刷新或再次打开仍可继续作答；
⑤ 本卷仅供学生练习使用；请勿用于其他用途；题面有问题请联系：i64coder@163.com。
判 分 报 告
客 观 题
下列 C++ 代码的输出结果是（ ）。
01#include <iostream> 02#include <cmath> 03using namespace std; 04int main() { 05 cout << sin(3.1415926 / 2); 06 return 0; 07}
B：3.1415926/2≈π/2，sin(π/2)=1，浮点舍入误差下输出约 0.99999999，四选项中只有 B 最接近 1。
对于如下图的二叉树，说法正确的是（ ）。
D：该二叉树为根 1、右子 2、2 的左子 3：先序 123、中序 132、后序 321，先序与后序恰好互为逆序，选 D。故 D 正确。
已知两个序列 s1={1,3,4,5,6,7,7,8,1}、s2={3,5,7,4,8,2,9,5,1}，则它们的最长公共子序列是（ ）。
A：LCS 要求同时在两个序列中按下标递增出现：{3,5,7,8,1} 在 s1、s2 中都按序出现且长度为 5；B 中 4 在 s2 里位于 5 之后，D 含 s1 没有的 9，均不成立。
有一个序列 {2,7,1,5,6,4,3,8,9}，下列说法错误的是（ ）。
D：最长上升子序列不唯一：{2,5,6,8,9} 与 {1,5,6,8,9} 都是长度 5 的 LIS，D 说 {1,5,6,8,9} 唯一，错误；A、B、C 均正确。
下列关于深度优先搜索和广度优先搜索的说法，错误的是（ ）。
D：二叉树后序遍历是深度优先（先左后右再根），不是广度优先；BFS 必须按层次逐层访问节点，故 D 说法错误，其余选项均正确，故选 D。
已知有如下图所示的树，下列说法中错误的是（ ）。
A：该树后序遍历为 HDEBFIGCA（左右根），A 声称它不是后序，说法错误；BFS 为 ABCDEFGHI、先序为 ABDHECFGI 均正确。
以下哪个方案不能合理解决或缓解哈希表冲突（ ）。
A：丢弃冲突的新元素等于插入失败，数据丢失，不能解决冲突；其余三项（每表项再建哈希表、建二叉排序树、额外哈希表）都合理。故 A 正确。
在 C++ 中，关于运算符 &，下面说法正确的是（ ）。
C：3&6=011₂&110₂=010₂=2；A 中 2&3=2 不是 true，B 中 011、111 按十进制整型与运算结果不为 3，D 按十进制运算结果不是 4。
下面关于图的说法正确的是（ ）。
D：有向图中每条边贡献一个出度和一个入度，故所有顶点入度出度之和等于边数的两倍；A、B、C 对环与强连通的表述不严谨或不完整，故选 D。
图的存储和遍历算法，下面说法错误的是（ ）。
B：图的 DFS 借助栈（递归或显式栈）实现，与二叉树先序遍历原理一致，B 说原理不同是错的；A、C、D 均正确，故选 B。故 B 正确。
如下图所示的邻接表结构，表示的是下列哪个选项中的图？
C：由邻接表读出：V1 连 V4、V2；V2 连 V5、V3、V1；V3 连 V5、V4、V2；V4 连 V1、V3；V5 连 V2、V3，对照四个图只有选项丙满足。
如下图所示的邻接矩阵（inf 表示无穷大），表示的是下列哪个选项中的图？
A：由邻接矩阵读出：0 连 2（权 12）、3（权 30）；1 无边；2 连 4（权 32）等（对称补全），对照选项只有甲满足这些带权边。
下面程序的输出为（ ）。
01#include <iostream> 02using namespace std; 03int fib(int n) { 04 if (n <= 1) 05 return n; 06 return fib(n - 1) + fib(n - 2); 07} 08int main() { 09 cout << fib(6) << endl; 10 return 0; 11}
B：fib(0)=0、fib(1)=1，递推 fib(2)=1、fib(3)=2、fib(4)=3、fib(5)=5、fib(6)=8，输出第 6 项 8。
下面 count_triple 函数的时间复杂度为（ ）。
01int count_triple(int n) { 02 int cnt = 0; 03 for (int a = 1; a <= n; a++) 04 for (int b = a; a + b <= n; b++) { 05 int c = sqrt(a * a + b * b); 06 if (a + b + c > n) 07 break; 08 if (a * a + b * b == c * c) 09 cnt++; 10 } 11 return cnt; 12}
B：外层 a 循环约 n 次，内层 b 从 a 到满足 a+b≤n 约 O(n) 次，c 用 sqrt 直接算出为 O(1)，总复杂度 O(n²)。
下列选项中，哪个可能是下图的深度优先遍历序列（ ）。
C：DFS 能走就走：A 中 5 之后应继续访问其未访问邻点 6 而非 4；B 中 3 之后应为 7；D 中 8 之后应为 5；只有 C 与图吻合。
C++ 语言中，表达式 6 & 5 的结果类型为 int、值为 。（ ）
错。& 是按位与：6=110₂、5=101₂，110₂&101₂=100₂=4，结果类型为 int 但值不是 1，说法错误。故选错。
冒泡排序是稳定的排序算法。（ ）
对。冒泡排序每趟只交换相邻的逆序元素，相等的两个元素永远不会发生位置交换，排序前后的相对顺序保持不变，因此是稳定排序算法。故说法正确。
唯一分解定理（算术基本定理）指出，每个大于 的自然数都可以唯一地分解成若干个素数的乘积。因此，我们可以很容易地对给定的自然数 n 进行质因数分解，时间复杂度仅为 。（ ）
错。质因数分解朴素做法需试除到 √n，时间复杂度 O(√n) 而非 O(log n)；只有预处理出最小质因子表后才能做到 O(log n)。
C++ 语言中，可以为同一个类定义多个构造函数。（ ）
对。构造函数支持重载：同一个类可定义多个参数列表不同的构造函数，创建对象时编译器按实参个数与类型自动选择调用对应的那个。故正确，故对。
使用 math.h 或 cmath 头文件中的对数函数，表达式 log(128) 的结果类型为 double、值约为 。（ ）
错。cmath 中 log 是自然对数 ln：log(128)=ln128≈4.85，不是 7.0；7 是 log2(128) 的结果。
一颗 N 层的二叉树，至少有 个节点。（ ）
错。N 层二叉树最少只需 N 个结点（每层一个结点连成一条链），2^(N−1) 是第 N 层最多结点数或满二叉树的情况，故说法错误。
非连通图不能使用广度优先搜索算法进行遍历。（ ）
错。非连通图可以分别对每个连通分量各做一次 BFS，把所有分量遍历完即可访问全部顶点，因此非连通图同样能 BFS 遍历。故说法正确。
现使用有 N 个表项的哈希表，从 M 个元素中进行查找。该哈希表为解决哈希函数冲突，为每个表项处建立单链表存储冲突元素。其查找操作的最坏情况时间复杂度为 。（ ）
对。链地址法最坏情况是 M 个元素全部哈希到同一条链表上，查找时需顺序扫描该链表，最坏时间复杂度为 O(M)，说法正确。故对，故对。
动态规划有递推实现和递归实现，对于很多问题，通过记录子问题的解，两种实现的时间复杂度是相同的。（ ）
对。递归实现配合记忆化（记录已算子问题的解）后，与递推实现一样每个状态只计算一次，对很多问题两者时间复杂度相同，说法正确。故对，故对。
泛洪算法的递归方法容易造成溢出，因此大的二维地图算法中，一般不用递归方法。（ ）
对。泛洪递归实现每层递归都会压栈，大二维地图递归层数可能极深导致栈溢出，一般改用 BFS 队列实现，从而避免系统栈耗尽。故正确，故对。