首页 › 试卷 › GESP编程能力等级认证 › GESP-C++七级 › 2025年12月CCF-GESP编程能力等级认证C++编程七级真题

2025年12月CCF-GESP编程能力等级认证C++编程七级真题 VIP

GESP-C++七级 共 27 题 2025 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

下面关于C++中形参、实参和定义域的说法中,正确的一项是( )。

  • A 形参是函数定义时所指定的变量,它只在函数内部有效。
  • B 在函数内部,可以修改传入的形参的值,即使该形参是一个常量引用
  • C 实参和形参的类型必须完全一致,否则会导致编译错误。
  • D 使用指针作为形参时,形参是指向实参的地址,因此对该指针赋值会影响实参。
查看答案与解析
答案:A
解析: 函数定义时声明的参数称为形参,其作用域局限于函数体内。调用函数时传递的表达式或变量称为实参,用于初始化对应的形参。形参的类型决定了如何解释传入的实参,但类型匹配允许一定的隐式转换。当形参为常量引用时,不能通过该引用来修改所绑定的对象。使用指针作为形参时,形参保存的是实参地址的副本,对指针所指向内容的修改可能影响外部对象,但改变指针本身不会影响实参。
2. 单选题

已知三个序列: s1 = {3, 1, 8, 2, 5, 6, 7, 4} , s2 = {1, 5, 1, 8, 6, 4, 7, 5, 6}, s3 = {1, 8, 3, 5, 7, 6, 2, 4} 。以下哪个序列是它们的最长公共子序列( )。

  • A {1, 8, 5, 6}
  • B {1, 5, 6, 7}
  • C {1, 8, 6}
  • D {1, 5, 7, 4}
查看答案与解析
答案:A
解析: 确定三个序列的最长公共子序列需逐元素比对,找出在所有序列中按相同顺序出现的最长元素序列。使用动态规划方法,构建多维状态表记录各序列前缀间的公共子序列长度。通过递推更新状态值,依据匹配情况转移状态,最终回溯路径获取最长公共子序列。过程中需保持元素相对顺序不变,且每个元素必须在所有序列中存在并满足顺序约束。
3. 单选题

现有一个地址区间为0-10的哈希表,当出现冲突情况,会往后找第一个空的地址存储(到10冲突了就从开始往后),现在要依次存储(1,3,5,7,9),哈希函数为h(x)=(x^2+x)mod11。。其中 存储在哈希表哪个地址中 ( )。

  • A 1
  • B 2
  • C 3
  • D 4
查看答案与解析
答案:D
解析: 根据哈希函数 h(x) = (x² + x) mod 11 计算每个待存储数值的初始哈希地址。依次处理序列中的数值,对每个数值计算其哈希值,检查对应地址是否为空。若该地址已被占用,则从当前地址开始向后线性探测,即逐个检查下一个地址,直到找到第一个空闲位置进行存储。探测过程在地址10之后回到地址0继续,形成循环。每个数值均按此方式确定最终存储位置。
4. 单选题

在0/1背包问题中,给定一组物品,每个物品有一个重量和价值,背包的容量有限。假设背包的最大容量为W,物品的数量为n ,其中第 个物品的重量为W[i],价值为 V[i]。以下关于0/1背包问题的描述,正确的是( )。

  • A 在解决0/1背包问题时,使用贪心算法可以保证找到最优解,因为物品只能放入一次。
  • B 0/1背包是P问题(多项式时间可解问题),它可以在 O(nW)的时间复杂度内解决。
  • C 0/1背包问题中,动态规划解法的空间复杂度为,但可以通过滚动数组技巧将空间复杂度优化到。
  • D 0/1背包问题中,每个物品只能选择一次,并且子问题之间是独立的,无法重用计算结果。
查看答案与解析
答案:C
解析: 0/1背包问题要求在容量限制下选择物品使总价值最大,每个物品至多选一次。该问题具有最优子结构和重叠子问题特性,适合用动态规划求解。状态定义为前i个物品在容量j下的最大价值,状态转移基于是否选取第i个物品。时间复杂度由状态数和转移代价决定,通常为O(nW)。空间上可利用二维数组存储中间结果,也可通过滚动数组压缩至一维,减少空间使用。贪心策略无法保证全局最优,因局部最优选择不必然导向整体最优。子问题虽独立定义,但计算过程中存在共享子结构,结果可被多次引用。
5. 单选题

一棵深度为6(根节点深度为1)的完全二叉树,节点总数最少有( )。

  • A 31
  • B 32
  • C 63
  • D 64
查看答案与解析
答案:B
解析: 完全二叉树的深度由根节点开始计算,深度为1。深度为h的完全二叉树,其节点数最少的情况出现在第h层只有一个节点时。前h-1层构成一棵满二叉树,节点总数为2^(h-1) - 1。第h层至少有一个节点。将前h-1层节点数与第h层最小节点数相加,得到整棵树的最小节点总数。根据深度值代入计算即可得出结果。
6. 单选题

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

#include <iostream>

int query(int n, int *a, int x) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    if (l == n)
        return -1;
    return l;
}

int main() {
    int n = 10;
    int x = 3;
    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
    std::cout << query(n, num, x) << "\n";
    return 0;
}
  • A 2
  • B 3
  • C 4
  • D 5
查看答案与解析
答案:B
解析: 函数query使用二分查找法在升序数组a中寻找首个不小于x的位置。初始化左边界l为0,右边界r为n。循环条件为l < r,取中点mid。若a[mid] >= x,则目标位置在左半区间,更新r为mid;否则更新l为mid+1。循环结束后,若l等于n,说明无满足条件的元素,返回-1;否则返回l。主函数中调用query传入数组num、长度n和值x,最终输出该函数返回值。
7. 单选题

下面程序中,函数 query 的时间复杂度是( )。

#include <iostream> 

int query(int n, int *a, int x) { 
    int l = 0, r = n; 
    while (l < r) { 
        int mid = l + (r - l) / 2; 
        if (a[mid] >= x) 
            r = mid; 
        else 
            l = mid + 1; 
    } 
    if (l == n) 
        return -1; 
    return l; 
} 

int main() { 
    int n = 10; 
    int x = 3; 
    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7}; 
    std::cout << query(n, num, x) << "\n"; 
    return 0; 
}
  • A O(1)
  • B O(log n)
  • C O(n)
  • D O(n log n)
查看答案与解析
答案:B
解析: 函数 query 使用 while 循环控制变量 l 和 r,初始分别为 0 和 n。每次循环计算 mid 为 (l + r) / 2,并根据 a[mid] 与 x 的大小关系更新 l 或 r。循环中 l 和 r 的范围持续缩小,直到 l >= r 结束。每次迭代将搜索区间大致减半,迭代次数与 n 的对数成正比。循环内部操作为常数时间。最终返回前的判断语句执行时间为常数。整个函数运行时间由循环次数和每次操作的时间复杂度共同决定。
8. 单选题

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

#include <iostream> 
using namespace std; 
int f(int n) { 
  if (n <= 2) return n * 2; 
  return f(n - 1) + f(n - 2); 
} 
int main() { 
  cout << f(5) << endl; 
  return 0; 
  }


  • A 10
  • B 16
  • C 26
  • D 30
查看答案与解析
答案:B
解析: 分析函数f的定义,该函数接受一个整数参数n。当n小于等于2时,返回n的两倍;否则返回f(n-1)与f(n-2)的调用结果之和。程序在main函数中调用f(5),并通过cout输出其返回值。执行过程涉及递归调用,需根据n的不同取值逐步展开f(n-1)和f(n-2)的计算路径,直至所有递归调用均达到边界条件(n ≤ 2),然后逐层回溯求和得出最终返回值。整个过程依赖函数调用栈的展开与合并机制。
9. 单选题

一个简单无向图G有36条边,且每个顶点的度数都为4,则图 的顶点个数为( )。

  • A 9
  • B 12
  • C 18
  • D 36
查看答案与解析
答案:C
解析: 利用图论中边数与顶点度数之和的关系,所有顶点的度数之和等于边数的两倍。设顶点个数为n,每个顶点的度数为4,则总度数为4n。根据关系式,4n等于边数36的两倍。建立等式并求解n。
10. 单选题

下面关于二叉树的说法正确的是( )。

  • A 任意二叉树的中序遍历与后序遍历必定不相同。
  • B 对任意二叉树,若已知先序遍历与后序遍历,则该二叉树唯一确定。
  • C 若二叉树有 个结点,根节点高度为 ,则其高度满足: [log2(n+1)]<=h<=n。
  • D 在二叉树的先序遍历中,根后紧跟的结点一定是根的左孩子。
查看答案与解析
答案:B
解析: 分析二叉树的遍历特性时,需明确先序、中序、后序遍历的访问顺序:先序为根-左-右,中序为左-根-右,后序为左-右-根。遍历序列反映节点访问次序,但无法仅凭先序和后序唯一确定树结构,因缺乏子树划分依据。中序与后序可能在特定结构下相同,如单分支树。高度计算基于完全二叉树的下限,以log2(n+1)为最小可能值。先序遍历中根后的节点取决于是否存在左子树,若存在则为其左孩子,否则为右子树路径上的节点。
11. 单选题

假设一个算法时间复杂度的递推式是 ,和T(0) = 1 ,那么这个算法的时间复杂度是(  )。

  • A
  • B
  • C O(n2)
  • D O(n2 log n)
查看答案与解析
答案:B
这道题暂未补解析。
12. 单选题

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

  • A 3
  • B 4
  • C 5
  • D 6
查看答案与解析
答案:C
这道题暂未补解析。
13. 单选题

对于如下二叉树,下面关于访问的顺序说法错误的是( )。2025.12-7

  • A D E B F H J I G C A 是它的后序遍历序列。
  • B A B C D E F G H I J 是它的广度优先遍历序列。
  • C A B D E C F G H I J 是它的先序遍历序列。
  • D D B E A F C H G J I 是它的中序遍历序列。
查看答案与解析
答案:D
这道题暂未补解析。
14. 单选题

有5个字符,它们出现的次数分别为2次、2次、3次、3次、5次。现在要用哈夫曼编码的方式来为这些字符进行编码,最小加权路径长度WPL(每个字符的出现次数 它的编码长度,再把每个字符结果加起来)的值为( )。2025.12-7

  • A 30
  • B 34
  • C 43
  • D 47
查看答案与解析
答案:B
解析: 将字符的出现次数作为叶子节点的权值,构建哈夫曼树。每次选择当前权值最小的两个节点合并为一个新节点,新节点的权值为两者之和,直至所有节点合并为根节点。每个字符的编码长度等于其对应叶子节点在树中的深度。计算每个字符的权值与其编码长度的乘积,再求总和,即得WPL。
15. 单选题

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

  • A 1, 5, 6, 3, 2, 8, 9, 4, 7
  • B 1, 5, 8, 9, 7, 4, 6, 3, 2
  • C 3, 2, 1, 4, 7, 6, 9, 5, 8
  • D 2, 5, 6, 3, 8, 7, 9, 4, 1
查看答案与解析
答案:B
这道题暂未补解析。

二、判断题

16. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
解析: 分析表达式中运算符的语义,确定其在C++语言标准中的定义;检查操作数的类型,判断是否触发隐式类型转换;依据标准规定的运算符行为,推导表达式的求值过程;根据类型提升规则和运算结果,确定表达式的类型和值的计算方式。
17. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
解析: 分析表达式 sin(90) 的计算过程:首先确认 cmath 头文件中 sin 函数的参数为弧度值,输入 90 为角度数值,需转换为弧度参与运算;函数接受 double 类型参数并返回 double 类型结果;根据正弦函数定义,其输出值域在 [-1, 1] 范围内;实际计算结果取决于输入值对应的弧度精度。
18. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
解析: strcmp函数逐字符比较两个字符串的ASCII值,从左到右依次对比每个字符。当遇到第一个不相等的字符时,返回两个字符ASCII值的差。若所有对应字符均相等,则返回0。字符串"10"和"9"的首字符分别为'1'和'9',其ASCII值决定比较结果。比较过程在首个字符处即确定走向,后续字符不参与判断。
19. 判断题

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

  • A对
  • B错
查看答案与解析
答案:对
解析: 使用动态规划求解最长公共子序列时,状态转移依赖于前一行和当前行的值。通过滚动数组技术,仅保留当前行和上一行的状态,将二维DP表压缩为两个一维数组或单个一维数组循环更新,从而减少空间占用。每次遍历中,依据序列元素是否相等更新当前状态,覆盖旧行数据以实现空间复用。该方法将空间复杂度由O(mn)降至O(n),其中m和n分别为两序列长度。
20. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
解析: 确定图的顶点数n和边数m;获取邻接矩阵存储结构,其规模为n×n;BFS遍历从起始顶点开始,使用队列管理待访问顶点;每轮取出队首顶点,标记为已访问;遍历该顶点在邻接矩阵中的整行,查找所有邻接且未访问的顶点并加入队列;每一行的检查耗时O(n),最多处理n个顶点;总时间由访问所有顶点和检查所有矩阵元素决定;矩阵中每个元素被访问一次,共n²次操作;最终时间复杂度由顶点数n决定。
21. 判断题

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

  • A对
  • B错
查看答案与解析
答案:对
解析: 分析哈希函数的映射行为,确定所有元素被分配至同一槽位的情形;考察链地址法在该槽位形成的链表结构;根据查找操作需遍历链表中节点的过程,推导出比较次数与元素总数的关系;结合时间复杂度定义,衡量输入规模增长时基本操作的执行频次变化趋势。
22. 判断题

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

  • A对
  • B错
查看答案与解析
答案:对
解析: 分析连通无向图的生成树定义,明确生成树是极小连通子图且包含图中所有顶点。根据图论基本性质,生成树中不存在环路,且任意两个顶点间有唯一路径。若生成树边数少于V-1,则无法连通所有顶点;若多于V-1,则必然形成环路。因此生成树的边数与顶点数之间存在确定关系。
23. 判断题

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

  • A对
  • B错
查看答案与解析
答案:对
解析: 分析排序算法的稳定性时,考察相同元素在排序前后相对位置是否保持不变。选择排序在交换过程中可能改变相同元素的相对位置,其机制不保证相等元素的先后顺序。冒泡排序通过相邻元素比较和交换实现,仅在严格大于时交换,相同元素不会发生位置变动,其机制能保持相等元素的原有顺序。两种算法的执行逻辑决定了其是否具备稳定性的特征。
24. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
解析: 分析无向图中每个边连接两个顶点,每条边对两个顶点的度数各贡献1。统计所有顶点的度数时,每条边被计算两次。将所有顶点的度数相加,总和来源于每条边的两次贡献。由此可得度数总和与边数之间存在固定倍数关系。通过枚举图中边与顶点的关联方式,可验证每条边在度数总和中对应两个单位增量。
25. 判断题

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

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

三、简答题

26. 简答题

城市规划

题目描述

A 国有n座城市,城市之间由m条双向道路连接,任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以1,2....,n编号。第i(1≤i≤m)条双向道路连接城市ui与城市vi。

对于城市u和城市v而言,它们之间的连通度d(u,v)定义为从城市u出发到达城市 所需经过的双向道路的最少条数。由于道路是双向的,可以知道连通度满足d(u,v)=d(v,u),特殊地有d(u,u)=0。

现在 A 国正在规划城市建设方案。城市u的建设难度为它到其它城市的最大连通度。请你求出建设难度最小的城市,如果有多个满足条件的城市,则选取其中编号最小的城市。形式化地,你需要求出使得max1≤i≤nd(u,i)最小的u,若存在多个可能的u则选取其中最小的。

输入格式

第一行,两个正整数n,m,表示 A 国的城市数量与双向道路数量。

接下来m行,每行两个整数ui,vi,表示一条连接城市ui与城市vi的双向道路。

输出格式

输出一行,一个整数,表示建设难度最小的城市编号。如果有多个满足条件的城市,则选取其中编号最小的城市。

输入样例 1

3 3
1 2
1 3
2 3

输出样例 1

1

输入样例 2

4 4
1 2
2 3
3 4
2 4

输出样例 2

2

数据范围

对于40的测试点,保证1≤n≤300 。

对于所有测试点,保证1≤n≤2000,1≤m≤2000,1≤ui,vi≤n。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false;">#include &lt;cstdio&gt; #include &lt;algorithm&gt; #include &lt;vector&gt; using namespace std; const int N = 2005; int n, m; vector&lt;int&gt; e[N]; int d[N], mx[N], q[N]; void bfs(int u) {     for (int i = 1; i &lt;= n; i++)         d[i] = n + 1;     d[u] = 0;     q[1] = u;     int ql = 1, qr = 1;     while (ql &lt;= qr) {         int x = q[ql++];         for (auto y : e[x])             if (d[x] + 1 &lt; d[y]) {                 d[y] = d[x] + 1;                 q[++qr] = y;             }     }     mx[u] = d[q[qr]]; } int main() {     scanf("%d%d", &amp;n, &amp;m);     for (int i = 1; i &lt;= m; i++) {         int u, v;         scanf("%d%d", &amp;u, &amp;v);         e[u].emplace_back(v);         e[v].emplace_back(u);     }     int ans = 1;     for (int i = 1; i &lt;= n; i++) {         bfs(i);         if (mx[i] &lt; mx[ans])             ans = i;     }     printf("%d\n", ans);     return 0; }</pre>
这道题暂未补解析。
27. 简答题

学习小组

时间限制:1.0 s

内存限制:512.0 MB

输入样例 1

4
2 1 3 2
1 5 6 3

输出样例 1

12

输入样例 2

8
1 3 2 4 3 5 4 6
0 2 5 6 4 3 3 4

输出样例 2

21

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false;">#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; const int N = 305; int n; int c[N], a[N]; int f[N][N]; int ans; int main() {     scanf("%d", &amp;n);     for (int i = 1; i &lt;= n; i++)         scanf("%d", &amp;c[i]);     for (int i = 1; i &lt;= n; i++)         scanf("%d", &amp;a[i]);          sort(c + 1, c + n + 1);     for (int i = n; i &gt;= 1; i--)         for (int j = 1; j &lt;= n; j++)             for (int k = i; k &lt;= n; k++) {                 int diff = 0;                 if (i &gt; 1)                     diff = c[n - j + 1] - c[j];                 f[j][k] = max(f[j][k], f[j - 1][k - i] + a[i] + diff);                 if (k == n)                     ans = max(ans, f[j][k]);             }          printf("%d\n", ans);     return 0; }</pre>
这道题暂未补解析。