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^{n1}-1T(n)2nT(0)(2n−1)2n1−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. 它们的编辑距离为5B. 它们至少有5个公共字符C. 它们最长公共子串长度为5D. 它们一定长度相等答案B题解最长公共子序列长度为5说明存在一个长度为5的公共子序列因此两个字符串至少含有5个公共字符允许重复。编辑距离、最长公共子串长度、字符串长度均无法由此确定。第4题对于一棵包含 n 个顶点n ≥ 2 n \geq 2n≥2的树其所有顶点的度数之和必定等于 。A. n - 1B. 2n - 2C. 2nD.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题下面程序的运行结果为 。#includeiostream#includealgorithmboolcheck(intn,inta[],intk,intdist){intcnt1;intlasta[0];for(inti1;in;i){if(a[i]-lastdist){cnt;lasta[i];}}returncntk;}intsolve(intn,inta[],intk){std::sort(a,an);intl0;intra[n-1]-a[0];while(lr){intmid(lr1)/2;if(check(n,a,k,mid))lmid;elsermid-1;}returnl;}intmain(){inta[]{1,2,8,4,9};intn5;intk3;std::coutsolve(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}k3最大最小距离为3因此输出3。第8题下⾯程序的时间复杂度是 假设数组 的值域范围是D 。#includeiostream#includealgorithmboolcheck(intn,inta[],intk,intdist){intcnt1;intlasta[0];for(inti1;in;i){if(a[i]-lastdist){cnt;lasta[i];}}returncntk;}intsolve(intn,inta[],intk){std::sort(a,an);intl0;intra[n-1]-a[0];while(lr){intmid(lr1)/2;if(check(n,a,k,mid))lmid;elsermid-1;}returnl;}intmain(){inta[]{1,2,8,4,9};intn5;intk3;std::coutsolve(n,a,k)std::endl;return0;}A.O ( n log ⁡ n n log ⁡ D ) O(n\log n n\log D)O(nlognnlogD)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(nlognnlogD)。第9题某二叉树共有10个结点记为A-J已知它的先序遍历序列为ABDHIECFJG中序遍历序列为HDIBEAFJCG则该二叉树的后序遍历序列是 。A. HIDEBJFGCABB. HIDBEJFGCACC. HIDEBJFGCADD. 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,2B. 1,5,8,4,7,9,6,3,2C. 2,5,8,7,9,6,3,4,1D. 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个字符它们出现的次数分别为{233468}现在用哈夫曼编码为这些字符编码最小加权路径长度 WPL每个字符的出现次数 × 它的编码长度再把每个字符结果加起来的值为 。A. 52B. 56C. 60D. 64答案D题解字符频率2,3,3,4,6,8。构造哈夫曼树合并235 → 剩3,4,5,6,8合并347 → 剩5,6,7,8合并5611 → 剩7,8,11合并7815 → 剩11,15合并111526WPL 所有非叶子结点权值和 57111526 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 的二进制 1002 的二进制 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 从任意顶点出发都能访问到所有顶点因此生成树包含所有顶点。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}