ARTICLE · 1015479
题解|GESP2026年9月C++七级真题解析
点击 GESP 真题解析合集 可以查看历届 GESP 真题解析。
1. 单选题（每题 2 分，共 30 分）
【答案】: C。
【解析】:5 & 3 = 1, 5 | 3 = 7，。
【答案】: D。
【解析】:
A 选项错误， pow(2, 3)的返回值类型为double。B 选项错误， sin(30)的参数 表述弧度。C 选项错误， sqrt(4)的返回值为double类型。D 选项正确。
【答案】: C。
【解析】: 构造哈夫曼树，每次选两个出现次数少的节点合并。
【答案】: B。
【解析】: 可以递推，也可以用组合数求解， 的格点，会形成 的网格，总共需要走 步，其中有 步往下走，方案数就是 。
【答案】: A。
【解析】: 最坏情况会形成一条链，时间复杂度为 ，平均情况为 。
【答案】: B。
【解析】: 典型的区间 DP 问题，何必顺序为 合并， 合并， 合并。
【答案】: A。
【解析】: BFS每次往外扩展一层，dist[i] 表示到达 i 的最少边数。
【答案】: D。
【解析】: DFS或者BFS搜索网格。
【答案】: C。
【解析】:
A 选项错误，哈希是一个基于概率的算法，不可完全避免冲突。 B 选项错误，在大量元素冲突的时候，查找一个元素可能是 的。 C 选项正确。 D 选项错误，哈希冲突时，查找速度与表中个数有关。
【答案】: B。
【解析】: 参数是引用，共享同一个地址，函数内部改变了，外部的实参 a 也会改变。
【答案】: A。
【解析】: 最长公共子序列模板。
【答案】: D。
【解析】: 只放入了一个 的物品，价值为 。
【答案】: D。
【解析】: 快速排序是不稳定的排序。
【答案】: B。
【解析】: 内层循环是调和级数，总时间复杂度为 。
【答案】: C。
【解析】:p 是 的地址，*(p + 3) 就是 a[4]。
2. 判断题（每题 2 分，共 20 分）
2.1 判断题题面
2.2 判断题解析
第 1 题：。exp 返回 double 类型。
第 2 题：。删除一个元素后不能直接将该位置置空，否则会破坏后续查找的正确性。
第 3 题：。通常情况下频率越高的结点离根越近，但“出现次数更多的叶子结点，其深度总是更小”这一表述过于绝对，存在反例。例如 构造哈夫曼树。
第 4 题：。一条边提供一个入度和一个出度。
第 5 题：。显然正确。
第 6 题：。快排最坏情况下会退化为 。
第 7 题：。滚动数组，倒序枚举背包容量。
第 8 题：。邻接表只存了实际存在的边，遍历一个顶点的邻接点时，不需要遍历所有顶点。
第 9 题：。完全二叉树的性质。
第 10 题：。arr 和 &arr[0] 的值（地址）相同，但它们在C/C++语言中并不总是等价。两者的关键区别在于类型和在特定运算符下的行为。
3. 编程题（每题 25 分，共 50 分）
3.1 编程题 1（必经之路）
分析
这道题的核心是：判断删除某个点后，是否还存在一条“原合法起点到原合法终点”的路径。
如果还存在，说明可以绕开这个点，它就不是必经点；如果不存在，说明所有合法路径都必须经过它，它就是必经点。
设原图中的合法起点集合为 ，合法终点集合为 。对于每个结点 ，暂时禁止经过 ，然后从所有不等于 的合法起点同时进行 BFS 或 DFS：
如果能到达某个不等于 的合法终点，则存在一条绕开 的路径； 否则 是必经点。
这里有一个容易出错的地方：删除 后，不能重新计算合法起点和合法终点。合法起点、合法终点必须按照原图的入度和出度确定。
例如删除一个结点后，它的前驱可能变成出度为 ，但这个前驱并不是原题定义的合法终点，不能把它算进去。
时间复杂度为 ，可以接受。
代码
#include<bits/stdc++.h>usingnamespacestd;constint maxn = 1005;int in[maxn], out[maxn], n, m;bool ed[maxn], vis[maxn];vector<int> st, ans;vector<int> g[maxn];boolcheck(int ban){ // 判断是否存在一条不经过ban的路径memset(vis, false, sizeof(vis));queue<int> q;for(int x: st) {if(x != ban) { vis[x] = true; q.push(x); } }while(!q.empty()) {int u = q.front(); q.pop();if(ed[u]) returntrue; // 到达合法终点for(int v: g[u]) {if(v == ban || vis[v]) continue; vis[v] = true; q.push(v); } }returnfalse;}intmain(){cin>>n>>m;while(m--) {int u, v;cin>>u>>v; g[u].push_back(v), g[v].push_back(u); ++out[u], ++in[v]; }for(int i = 1; i <= n; ++i) {if(in[i] == 0) st.push_back(i);if(out[i] == 0) ed[i] = true; }for(int i = 1; i <= n; ++i) {if(!check(i)) ans.push_back(i); }cout<<ans.size()<<'\n';for(int x: ans) cout<<x<<" ";return0;}3.2 编程题 2（括号序列）
分析
合法括号序列有两个必要条件：
从左到右扫描时，任意前缀中左括号数量不少于右括号数量。 扫描结束后，左右括号数量相等。
定义括号余额 。扫描过程中余额不能小于 ，最后必须等于 。
设 表示处理到第 个字符，目前括号余额为 的方案数。
对于每一个字符，我们都有两种选择：
不选，此时直接继承 选，就要看当前是 (还是)，如果是(，那么 应该来源于 ；如果是)， 来源于对于选的转移，还需要判断前缀括号序列中括号是否合法，即左括号数量是否不少于有括号数量
时间复杂度为 。
代码
#include<bits/stdc++.h>usingnamespacestd;constint maxn = 2005, mod = 1e9;int dp[maxn][maxn], n;string s;intmain(){cin>>n>>s; s = " " + s; dp[0][0] = 1;for(int i = 1; i <= n; ++i) {for(int j = 0; j <= i; ++j) { dp[i][j] = dp[i - 1][j];if(s[i] == '(' && j > 0) { dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod; } elseif(s[i] == ')' && i - 1 >= j + 1) { dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % mod; } } }cout<<dp[n][0];return0;}如果你喜欢这类赛事真题解析文章，欢迎点赞、转发、收藏，让更多人看到这份真诚的分享！