GESP第13次认证真题解析|C++七级真题回顾

一、单选题（每题2分，共30分）

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

A. O(n)

B. O(nlogn) 

C. O(n²)

D. O(2ⁿ)

答案：D

考察知识点： 时间复杂度

解析：时间复杂度是算法执行的指令数目。该时间复杂度的递推式是典型的指数级算法（如：汉诺塔）的递推式，其时间复杂度为O(2^n)。

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

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

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

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

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

答案：D

考察知识点：唯一分解定理、素数筛法

解析：

A正确：预处理最小质因子后，每次除以最小质因子即可分解，次数为O(logn)。

B正确：线性筛的核心就是利用唯一分解定理保证每个合数只被其最小质因子筛掉。

C正确：如果一个数没有被不超过其平方根的质数整除，那么它一定是质数（这是试除法判断素数的原理，由唯一分解定理保证）。

D错误：埃氏筛的时间复杂度为O(nloglogn) 是因为每个质数要筛掉它的倍数，这与唯一分解定理无直接关系；唯一分解定理是数论基本定理，并不决定筛法的时间复杂度。

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

A.它们的编辑距离为5

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

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

D.它们⼀定长度相等

答案：B

考察知识点：最长公共子序列（LCS）

解析：LCS长度为5意味着两个字符串中存在一个长度为5的公共子序列，因此它们至少有5个公共字符（但字符位置不一定连续）。

第4题 对于⼀棵包含n个顶点（n ≥ 2）的树，其所有顶点的度数之和必定等于（ ）。

A. n-1  

B. 2n-2  

C. 2n

D. n²

答案：B

考察知识点：树的性质

解析：树有n 个顶点，则边数为n−1。所有顶点的度数之和等于边数的两倍，即2(n−1)=2n−2。

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

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

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

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

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

答案：D

考察知识点：哈希表

解析：

A正确：装载因子越大，冲突概率越高。

B正确：开放定址法删除元素时不能直接置空，否则影响查找，需要特殊标记。

C正确：链地址法在最坏情况下（所有元素哈希到同一位置）查找时间复杂度为O(n)。

D错误：哈希表在理想情况下查找是O(1)，但最坏情况可能退化为O(n)，且受哈希函数和冲突解决影响，并非总是O(1)。

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

A.分治

B.贪心

C.动态规划

D.回溯

答案：B

考察知识点：贪心算法

解析：题目强调的是“选择一个相邻的未访问顶点”这一步的局部决策，是贪心思想的体现（每次都选一个方向走下去，不全局规划）。而回溯只是实现DFS的手段，不是算法的主要思想归类。

第7题 下面程序的运⾏结果为（ ）。

A. 2

B. 3

C. 4

D. 5                                                                                                

答案：B

考察知识点：二分答案、贪心（最大值最小化问题）

解析：程序实现的是“在有序数组中选取k个数，使得相邻两数的最小距离最大”的经典问题（类似“进击的奶牛”）。输入数组排序后为{1,2,4,8,9}，二分查找最大最小距离。check函数判断能否选出至少k个数使得相邻距离≥dist。初始l=0，r=8，mid从4开始。

当dist=4时，从1开始，可选出1,8（距离7≥4）或1,9（距离8≥4），但只能选出2个数（cnt=2）<3，不满足。

调整后最终得到答案为3（可选出1,4,8或1,4,9，最小距离3）。

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

A. O(nlogn + nlogD)

B. O(nlognlogD)

C. O(nlogn) 

D. O(nlogD)

答案：A

考察知识点：二分答案

解析：排序是O(nlogn),二分是O(nlogD)，所以选A

第9题 某二叉树共有10个结点 ，记为A~J， 已知它的先序遍历序列为：AB D H I E C F J G，中序遍历序列为：H D I B E A FJ 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

知识点：二叉树的遍历

解析：在先序遍历中找根，在中序遍历中确定父子关系。

第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

考察知识点：图的深度优先遍历（DFS）

解析：其它选项都没有施行一条道走到黑的DFS的算法思想。

A选项，1、5、4后仍可访问7，不能回溯访问到8；C选项，2、5、8、7、9、6、3后仍可访问1，不能回溯访问到4；D选项，8、9、6、3、2、5后仍可访问4和8，不能回溯访问1。

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

A. 3

B. 4

C. 5

D. 6

答案: B

考察知识点:

有向图的强通分量

解析: {1，2，6，9，10，11，12，5}、{3，4}、{7，8}、{13，14，16，15}。

第12题 关于泛洪算法（Flood Fill）的说法 ，正确的是（ ）。

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

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

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

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

答案：C

考察知识点：泛洪算法（Flood Fill）

解析：泛洪算法本质是从起点出发的图搜索（DFS或BFS），可用于二维网格连通区域，也可用于图连通分量。

A错误：不仅限于二维网格。

B错误：可以用递归或非递归实现。

C正确。

D错误：可以统计面积、周长等。

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

A. 58

B. 60 

C. 62 

D. 64

答案：D

考察知识点：哈夫曼编码

解析：根据题目模拟即可。

2*3+3*3+6*2+3*3+4*3+8*2=64

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

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

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

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

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

答案：D

考察知识点：链表基本操作

解析：

A错误：单链表中已知结点指针，无法直接删除，还需要找到前驱结点的指针。

B错误：过于绝对，因为空链表可能头指针为空。

C错误：循环双链表中尾结点的next指向头结点，不为NULL。

D正确：带头结点的循环单链表，判断空的条件是头结点的next指向自身。

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

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

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

C.已知一棵二叉树的先序遍历和中序遍历序列 ，可以唯一确定这棵二叉树 。 D.一棵二叉树的中序遍历序列是单调递增的 ，则该二叉树一定是二叉平衡树。

答案：C

考察知识点： 树的遍历

解析：

A错误：树的DFS序列不唯一（如孩子顺序）。

B错误：先序和后序不能唯一确定二叉树（需中序）。

C正确：先序+中序可唯一确定。

D错误：中序单调递增只能说明是二叉搜索树，不一定是平衡树。

二、判断题（每题2分，共20分）

第1题 C++语言中 ，表达式4 ^ 2 的结果类型为int，值为6。

答案：✓

考察知识点：位运算

解析：C++中4^2 是按位异或，4（100）异或2（010）得110（6），结果为int，值为6。

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

答案：✗

考察知识点: C++引用

解析：C++引用一旦初始化，就不能再重新绑定到其他对象。说法错误。

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

答案：✓

考察知识点：C++引用

解析：引用作为形参，函数内修改即修改实参。正确。

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

答案：✗

考察知识点:贪心&DP

解析：动态规划可解的问题不一定存在贪心策略，贪心往往需要最优子结构和贪心选择性质，并非所有DP问题都能贪心。错误。

第5题 使⽤归并排序对n个元素进⾏排序时 ，⽆论最好、最坏还是平均情况 ，时间复杂度均为O(nlogn)。

答案：√

考察知识点:归并排序

解析：归并排序的最好、平均、最坏时间复杂度均是O(nlogn)

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

答案：✗

考察知识点：图的定义及基本图论算法

解析：在无向连通图中，删除一条边后图是否仍然连通，取决于这条边是不是桥（割边）。

如果删除的是桥 → 图会变成非连通图（分成两个部分）

如果删除的是环上的边 → 图仍然连通（可以通过环的另一条路径绕过）

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

答案：✓

考察知识点：唯一遍历序列

解析：因为规则规定“每次都选编号最小的邻居”，所以从起点开始，每一步该走哪个点都是确定的，没有第二种选择，因此整个遍历序列只有一种。

第8题 若所有字符出现频率相同 ，则哈夫曼编码⼀定会得到完全⼆叉树。

第8题

答案：✗

考察知识点：哈夫曼编码

解析： 字符频率相同时，哈夫曼树可能不是完全二叉树。完全二叉树要求最后一层的叶节点都在左侧，哈夫曼树合并过程中并不保证这一点。例如，5个字符时，只有叶节点深度为3、3、2、2、2的树是完全二叉树（下图左），但哈夫曼树可能得到叶节点深度为2、2、3、3、2的二叉树（下图右）。所以说法错误。

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

答案：✗

考察知识点：三角函数

解析：sin(90) 中的90是弧度，不是角度。90弧度约等于5157度，sin值不是1。正确应使用 sin(90 * M_PI / 180)。错误。

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

答案：✓

考察知识点：DFS遍历

解析： 在无向连通图中，从任意顶点出发进行DFS，可以访问所有顶点，因此DFS生成树包含所有顶点。正确。

三、编程题（每题25分，共50分）

3.1     编程题1

试题名称：拆分

时间限制：1.0 s

内存限制：512.0 MB

3.1.1  题目描述

小A想将正整数n拆分成若干个正整数之和，并最大化拆分后的正整数之积。小A希望你帮他计算出拆分后正整数之积的最大值。由于答案可能很大，你只需要求出答案对10⁹取模的结果。

形式化地，n的拆分是满足a₁+...+a_k=n的若干个正整数a₁,...,a_k，其中1≤k≤n。你需要求出n的所有拆分中a₁×...×a_n的最大值对10⁹取模的结果。

3.1.2  输入格式

第一行，一个正整数t，表示数据组数。

对于每组数据:一行，一个整数n，表示给定的正整数。

3.1.3   输出格式

对于每组数据：输出一行，一个整数，表示n拆分后正整数之积的最大值对10⁹取模的结果。

3.1.4   样例

3.1.4.1 输入样例

1

2

3

4

3.1.4.2  输出样例

1

2

3 6

18

755407364

3.1.5  数据范围

对于40%的测试点 ，保证 n ≤ 50。

对于所有测试点 ，保证 1 ≤ t ≤ 10⁴，1 ≤ n ≤ 10⁸。

解析：之所以尽量拆出3，是因为如果拆分中存在一个大于等于5的数x，那么把它拆成3和x−3后，乘积会从x变成3×(x−3)，并且当x≥5时有3×(x−3)>x，所以继续拆出一个3一定能使乘积变大。因此最优拆分中不会保留大于等于5的数，只会剩下2、3、4这几种情况。

而在相同总和下，3通常比2更优，例如3+3的乘积为9，大于2+2+2的乘积8，所以应尽量拆成3。但需要注意，拆分后不应该单独留下1。因为1乘到结果中不会增加乘积，反而会浪费一部分和。具体来说，如果最后得到3和1，那么它们的乘积是3；而把这两个数重新合并并拆成2和2，和仍然是4，但乘积变成4，更大。因此当n除以3的余数为1时，应少拆出一个3，把这部分3+1改成2+2。

3.1.6    参考程序

3.2     编程题2

试题名称：物流网络

时间限制：1.0 s

内存限制：512.0 MB

3.2.1   题目描述

一个物流网络由n个城市和m条双向公路组成。每条公路都有两个属性：

运输费用w_i

景观评分b_i

当一辆运输车从城市1运送货物到城市n时，需要支付经过道路的运输费用之和。

为了推广旅游线路，物流公司推出了一项优惠政策:在运输路径上，可以免除景观评分最高的那条公路的运输费用。如果有多条公路的景观评分同为最大值，则只免除其中一条的费用。

请你计算，从城市1到城市n的最小运输费用。

3.2.2   输入格式

第⼀⾏两个整数n, m，分别表⽰城市数量和公路数量。

接下来m⾏，每⾏四个整数u, v, u, b，表⽰存在⼀条连接城市u和城市v的双向公路，其中W为运输费⽤，b为景观评分。

3.2.3   输出格式

输出一个整数 ，表⽰从城市1到城市n的最⼩费⽤。

如果无法到达，输出-1。

3.2.4   样例

3.2.4.1 输入样例

1

2

3

4

3.2.4.2 输出样例

0

3.2.5  样例解释

路径1 → 2 → 3：费⽤10+20，最⼤美丽值6 (边2- 3)。免除20，总花费10。

路径1 → 3：费⽤100，最⼤美丽值1 (边1- 3)。免除100，总花费0。

最⼩费⽤为0。

3.2.6  数据范围

1 ≤ n ≤ 5000,  1 ≤ m ≤ 5000 ，1 ≤ w, b ≤ 10⁹。

解题思路:

题目大意：给定一个包含n个城市和m条双向公路的物流网络，每条公路有运输费用和景观评分。现在要从城市1到城市n选择一条运输路径，路径上可以免除景观评分最高的一条公路的费用，求最终需要支付的最小费用。如果无法到达城市n，则输出-1。

考虑枚举最终被免除费用的那条边。设当前枚举到的边为r = (u, v)，如果它被免除费用，那么整条路径只能是下面两种形式之一：

1 -> u + r + v -> n

1 -> v + r + u -> n

因为r是被免除的边，所以路径中其它边的景观评分都不能超过r的景观评分。因此可以把所有边按景观评分从小排序后依次加入。

维护两个DP数组：

dp1[x] = 当前已经加入的边中，从1到x的最小费用；

dpn[x] = 当前已经加入的边中，从n到x的最小费用。

初始时，dp1[1] = 0，dpn[n] = 0，其它状态为无穷大。按照排序后的顺序枚举当前边r。对于每条边，需要先用r更新答案，再把r加入当前的图。具体来说，若r = (u, v)，则可以用下面两种方式更新答案，answer的初始值为一个极大值：

answer = min(answer, dp1[u] + dpn[v])

answer = min(answer, dp1[v] + dpn[u])

然后再把r加入当前的图，并从r的两个端点开始更新dp1和dpn。如果通过某条已经加入的边可以让某个点的DP值变小，就继续用这个点向外更新。最后，如果answer仍然是无穷大，说明无法从1到达n，输出-1；否则输出answer。

3.2.7    参考程序

C++/Python/图形化编程

2026年4月15日17:00-6月16日24:00

2026年6月23日9:30-6月27日9:30

1-4级 2026年6月27日  上午09:30-11:30

5-8级 2026年6月27日  下午13:30-16:30

全国各GESP考点内上机考试

登录GESP网站(https://gesp.ccf.org.cn/)进行报名或“CCF GESP”微信公众号报名。

📍第一种方式：GESP网站报名流程

步骤1：在电脑上使用Google Chrome浏览器/Microsoft Edge浏览器/Firefox浏览器进入GESP网站 (https://gesp.ccf.org.cn) ，参加过GESP认证的考生可直接点击【登录】；未参加过GESP的考生需先点击【注册】完成新用户注册→点击【登录】。

步骤2：进入认证列表，在对应的认证名称后点击【立即报名】。

步骤3：按顺序填写考生的报名信息，身份证信息、语言等级都填写完整后，选择考点，所选城市/区没有考点信息显示，则说明该地区暂无考点，请勾选其他城市/区。考点剩余机位数大于0，则可以报名该考点。填写完成后，点击【提交报名】。

步骤4：在报名信息确认界面，仔细核对报名信息后，点击【确认报名】。

注：如需修改考生信息，请点击【修改报名】。

步骤5：进入交费界面，选择支付方式（支付宝/微信）后，点击【确认】，然后扫码支付报名费用。

注：部分省市的考位数量变化较快，如交费页面提示该考点已报满，请点击【我的报名】后点击【取消报名】，重新填写报名信息后再提交。

步骤6：完成支付，认证报名成功。

步骤7：等待审核，已交费考生信息会依次审核。

步骤8：在指定时间内下载、打印准考证。

步骤9：参加认证。

📍第二种方式：GESP公众号报名流程

点击“CCF GESP”公众号底部菜单栏【GESP】→【报名认证】，同意授权，进行登录。登录后，其余报名步骤可参考“第一种方式”指引完成报名。