2026年3月GESP真题及题解(C++七级): 选择题和判断题（题解）

2026年3月GESP真题及题解(C++七级): 选择题和判断题（题解）

第1题

假设一个算法时间复杂度为递推式是T ( n ) = 2 T ( n − 1 ) + 1 T(n) = 2T(n - 1) + 1T(n)=2T(n−1)+1（ n 为正整数），且T ( 0 ) = 1 T(0) = 1T(0)=1，那么这个算法的时间复杂度是（ ）。

A.O ( n ) O(n)O(n)

B.O ( n log ⁡ n ) O(n\log n)O(nlogn)

C.O ( n 2 ) O(n^2)O(n2)

D.O ( 2 n ) O(2^n)O(2n)

答案：D
题解
递推式 (T(n)=2T(n-1)+1)，(T(0)=1)。展开得
T ( n ) = 2 n T ( 0 ) + ( 2 n − 1 ) = 2 n + 1 − 1 T(n)=2^n T(0)+(2^n-1)=2^{n+1}-1T(n)=2nT(0)+(2n−1)=2n+1−1，故时间复杂度为O ( 2 n ) O(2^n)O(2n)。

第2题

下面关于“唯一分解定理”和“素数筛法”的说法中，错误的是（ ）。

A. 如果预处理出 n 以内每个数的最小质因子，那么可以在O ( log ⁡ n ) O(\log n)O(logn)时间内完成任意一个不超过 n 的整数的质因数分解。

B. 线性筛（欧拉筛）能够保证每个合数只被其最小质因子筛掉一次，这一性质依赖于唯一分解定理。

C. 唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。

D. 唯一分解定理是埃氏筛时间复杂度为O ( n log ⁡ log ⁡ n ) O(n\log \log n)O(nloglogn)的根本原因。

答案：D
题解
A、B、C 均正确。埃氏筛的时间复杂度O ( n log ⁡ log ⁡ n ) O(n\log\log n)O(nloglogn)源于素数分布及调和级数，与唯一分解定理无直接因果，因此 D 错误。

第3题

若字符串A与字符串B的最长公共子序列（LCS）长度为5，则（ ）。

A. 它们的编辑距离为5

B. 它们至少有5个公共字符

C. 它们最长公共子串长度为5

D. 它们一定长度相等

答案：B
题解
最长公共子序列长度为5，说明存在一个长度为5的公共子序列，因此两个字符串至少含有5个公共字符（允许重复）。编辑距离、最长公共子串长度、字符串长度均无法由此确定。

第4题

对于一棵包含 n 个顶点（n ≥ 2 n \geq 2n≥2）的树，其所有顶点的度数之和必定等于（ ）。

A. n - 1

B. 2n - 2

C. 2n

D.n 2 n^2n2

答案：B
题解
树有 n-1 条边，每条边贡献2度，故度数之和为 2(n-1)=2n-2。

第5题

关于哈希表（Hash Table）在不考虑扩容且采用简单均匀哈希函数的前提下，下列说法中错误的是（ ）。

A. 装载因子越大，发生冲突的概率通常越高

B. 开放定址法在删除元素时实现相对复杂

C. 链地址法在最坏情况下查找时间复杂度为 (O(n))

D. 查找哈希表的时间复杂度总是 (O(1))

答案：D
题解
哈希表查找的平均时间复杂度为O ( 1 ) O(1)O(1)，但最坏情况下（如所有元素冲突到同一位置）可达O ( n ) O(n)O(n)，因此“总是O ( 1 ) O(1)O(1)”的说法错误。

第6题

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

A. 分治

B. 贪心

C. 动态规划

D. 回溯

答案：D
题解
深度优先搜索在遇到死胡同时会回退到前一顶点继续探索，这种“前进-回溯”的思想正是回溯法的典型应用。

第7题

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

#include<iostream>#include<algorithm>boolcheck(intn,inta[],intk,intdist){intcnt=1;intlast=a[0];for(inti=1;i<n;i++){if(a[i]-last>=dist){cnt++;last=a[i];}}returncnt>=k;}intsolve(intn,inta[],intk){std::sort(a,a+n);intl=0;intr=a[n-1]-a[0];while(l<r){intmid=(l+r+1)/2;if(check(n,a,k,mid))l=mid;elser=mid-1;}returnl;}intmain(){inta[]={1,2,8,4,9};intn=5;intk=3;std::cout<<solve(n,a,k)<<std::endl;return0;}

A. 2 B. 3 C. 4 D. 5

答案：B

题解
程序通过二分查找寻找在有序数组中选取k个点所能得到的最大最小距离。对于数组{1,2,8,4,9}排序后为{1,2,4,8,9}，k=3，最大最小距离为3，因此输出3。

第8题

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

#include<iostream>#include<algorithm>boolcheck(intn,inta[],intk,intdist){intcnt=1;intlast=a[0];for(inti=1;i<n;i++){if(a[i]-last>=dist){cnt++;last=a[i];}}returncnt>=k;}intsolve(intn,inta[],intk){std::sort(a,a+n);intl=0;intr=a[n-1]-a[0];while(l<r){intmid=(l+r+1)/2;if(check(n,a,k,mid))l=mid;elser=mid-1;}returnl;}intmain(){inta[]={1,2,8,4,9};intn=5;intk=3;std::cout<<solve(n,a,k)<<std::endl;return0;}

A.O ( n log ⁡ n + n log ⁡ D ) O(n\log n + n\log D)O(nlogn+nlogD)

B.O ( n log ⁡ n log ⁡ D ) O(n\log n\log D)O(nlognlogD)

C.O ( n log ⁡ n ) O(n\log n)O(nlogn)

D.O ( n log ⁡ D ) O(n\log D)O(nlogD)

答案：A
题解
程序先排序，时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)；二分查找区间长度为 D（最大间距），每次二分调用 O(n) 的检查函数，故总复杂度为O ( n log ⁡ n + n log ⁡ D ) O(n\log n + n\log D)O(nlogn+nlogD)。

第9题

某二叉树共有10个结点，记为A-J，已知它的先序遍历序列为：ABDHIECFJG，中序遍历序列为：HDIBEAFJCG，则该二叉树的后序遍历序列是（ ）。

A. HIDEBJFGCAB

B. HIDBEJFGCAC

C. HIDEBJFGCAD

D. HIDEBFJGCA

答案：A
题解
已知先序 ABDHIECFJG，中序 HDIBEAFJCG。

• 根为 A，左子树先序 BDHIE，中序 HDIBE → 后序 HIDEB。
• 右子树先序 CFJG，中序 FJCG → 根为 C，左子树先序 FJ，中序 FJ → 后序 JF，右子树 G → 后序 G。
  整体后序：HIDEB + JFG + C + A = HIDEBJFGCA，即选项 A。

第10题

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

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
题解
根据深度优先的算法原理：从起始节点出发，沿着一条路径尽可能深地探索，直到无法继续，然后回溯到上一个节点，继续探索其他分支，直到所有节点都被访问。可得 B 选项正确。

第11题

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

A. 3 B. 4 C. 5 D. 6

答案：B
题解
通过对有向图进行强连通分量分解，计算得 4 个强连通分量，故选 B。

第12题

关于泛洪算法（FloodFill）的说法，正确的是（ ）

A. 泛洪算法只适用于二维网格中的四连通或八连通问题。

B. 泛洪算法必须使用递归方式实现。

C. 泛洪算法本质上是对图进行一次从起点出发的搜索。

D. 泛洪算法只能用于统计连通块个数，不能用于计算面积或周长。

答案：C
题解
泛洪算法本质是从起点出发对图（或网格）进行深度/广度优先搜索，因此 C 正确。它可用于二维或高维，可用递归或迭代实现，且能统计连通块、面积、周长等信息。

第13题

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

B. 56

C. 60

D. 64

答案：D
题解
字符频率：2,3,3,4,6,8。构造哈夫曼树：
合并2+3=5 → 剩3,4,5,6,8
合并3+4=7 → 剩5,6,7,8
合并5+6=11 → 剩7,8,11
合并7+8=15 → 剩11,15
合并11+15=26
WPL = 所有非叶子结点权值和 = 5+7+11+15+26 = 64。

第14题

关于单链表、双链表和循环链表，下列说法正确的是（ ）。

A. 在单链表中，若已知某结点的指针，则可以在 (O(1)) 时间内删除该结点。

B. 循环链表中一定不存在空指针。

C. 在循环双链表中，尾结点的next指针一定为NULL。

D. 在带头结点的循环单链表中，判定链表是否为空只需判断头结点的next是否指向自身。

答案：D
题解
A 错误：单链表中删除给定结点需要前驱，无法 (O(1))（除非是头结点或采用特殊交换值技巧）。
B 错误：循环链表的结点内指针永不为空，但空链表时头指针可能为空，并非“一定不存在空指针”。
C 错误：循环双链表中尾结点的next应指向头结点。
D 正确：带头结点的循环单链表，空表时头结点的next指向自身。

第15题

下列关于树的遍历的说法中，正确的一项是（ ）。

A. 对任意一棵树进行深度优先遍历，所得序列一定唯一。

B. 已知一棵二叉树的先序遍历和后序遍历序列，可以唯一确定这棵二叉树。

C. 已知一棵二叉树的先序遍历和中序遍历序列，可以唯一确定这棵二叉树。

D. 一棵二叉树的中序遍历序列是单调递增的，则该二叉树一定是二叉平衡树。

答案：C
题解
A 错误：深度优先遍历序列不唯一，取决于邻接点访问顺序。
B 错误：先序和后序无法唯一确定二叉树（除非是特殊树）。
C 正确：先序和中序可唯一确定二叉树。
D 错误：中序单调递增说明是二叉搜索树，但不一定是平衡树。

第16题(判断题)

C++ 语言中，表达式4 ∧ 2 4\wedge 24∧2的结果类型为int，值为6。

答案：√
题解
C++ 中^是按位异或运算符，4 的二进制 100，2 的二进制 010，异或得 110 即 6，类型为 int。故正确。

第17题(判断题)

C++ 中引用可以重新绑定。

答案：×
题解
C++ 引用一旦初始化，就不能再指向其他对象，不可重新绑定。

第18题(判断题)

在 C++ 中，若函数形参为引用类型，则在函数内部对该形参的修改会影响对应的实参。

答案：√
题解
引用是实参的别名，对形参的修改直接作用于实参。

第19题(判断题)

如果一个最值问题可以用动态规划在多项式时间内求解，那么也一定存在一种贪心策略，可以在多项式时间内求得最优解。

答案：×
题解
动态规划适用范围更广，许多问题（如 0-1 背包）有动态规划解但贪心无法保证最优。

第20题(判断题)

使用归并排序对 (n) 个元素进行排序时，无论最好、最坏还是平均情况，时间复杂度均为 (O(n\log n))。

答案：√
题解
归并排序始终将数组对半分割并合并，时间复杂度稳定为 (O(n\log n))。

第21题(判断题)

在无向连通图中删除一条边，该图就一定变成非连通图。

答案：×
题解
只有删除桥（割边）才会使图不连通；删除非桥边，图仍连通。

第22题(判断题)

在一个无向图中，每个顶点有不同的编号，在执行深度优先遍历过程中选择下一个顶点时总是优先选择编号更小的相邻顶点，则从指定顶点开始的遍历序列是唯一的。

答案：√
题解
每次选择编号最小的未访问邻接点，使得每一步选择确定，遍历序列唯一。

第23题(判断题)

若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。

答案：×
题解
哈夫曼树不一定是完全二叉树。例如频率均为 1 时，构造的树可能不是完全二叉树。

第24题(判断题)

使用 math.h 或 cmath 头文件中的函数，表达式 sin(90) 的结果为 1。

答案：×
题解
sin 函数的参数是弧度制，90 弧度约 5156.6°，其正弦值并非 1。若要求 90° 的正弦，应写为 sin(90 * M_PI / 180)。

第25题(判断题)

在一个无向连通图中，从任意顶点开始进行深度优先遍历，最终得到的 DFS 生成树一定包含图中的所有顶点。

答案：√
题解
因为图连通，DFS 从任意顶点出发都能访问到所有顶点，因此生成树包含所有顶点。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：
https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}