点击 GESP 真题解析合集 可以查看历届 GESP 真题解析。
1. 单选题（每题 2 分，共 30 分）
【答案】: B。
【解析】:
A 错误，冒泡排序是 的，基于比较的排序最快可以做到 。 B 正确，排序的稳定指：排序后，值相等的元素的相对位置不变。快速排序不稳定。 C 错误，归并排序的时间复杂度为 。 D 错误，由 A，B，C 选项的分析可知。
【答案】: C。
【解析】: 由第 16 行 queen(n + 1) 可知是在递归，符合深搜的性质。
【答案】: D。
【解析】: D 选项中，成员变量不能是自身类的对象，也不能是 auto 类型，如果用 static 修饰类，那么修饰的变量，虽然可以在类里面放自身类对象，但是修饰的并不是成员变量。其他选项均正确。
【答案】: C。
【解析】: 简单无向图表示无自环，无重边， 个点的完全图有 条边， 最小是 ，才有 条边。
【答案】: D。
【解析】: D 选项会发生数据元素丢失，其他选项均是常见的哈希冲突解决方案。
【答案】: B。
【解析】: 平衡二叉树有两个条件：首先它是二叉排序树，其次任何节点的左子树和右子树高度差不超过 。根据中序和后序可以唯一确定一棵二叉树，画出这棵二叉树，可以得到只有 B 选项正确。
【答案】: A。
【解析】:
A 正确，二叉排序树的性质。 B 错误，当二叉排序树为直链时，时间复杂度为 。 C 错误，二叉排序树不一定是平衡。 D 错误，由 A，B，C 选项的分析可知。
【答案】: B。
【解析】:
A 错误， sin(x)可能小于 。B 正确， exp(x)一定大于 。C 错误， log(x)可能小于 。D 错误，当 时，这个式子等于 。
【答案】: A。
【解析】: 简单有向图表示无自环，无重边， 个点的有向完全图有 条边，那么 个顶点的完全图需要 条边，还需要 条。
【答案】: C。
【解析】:
选项 A 错误，10 后面不能接 7 选项 B 错误，3 后面不能接 12 选项 C 正确。 选项 D 错误，10 后面不能接 9
【答案】: C。
【解析】:sort 是 的，后面 for 循环枚举是 ，总时间复杂度为 。
【答案】: B。
【解析】: 二分每次规模减半，时间复杂度为 。
【答案】: C。
【解析】: 三层循环，每一层都是 ，总时间复杂度为 。
【答案】: A。
【解析】: 递推或者递归模拟即可。
【答案】: B。
【解析】: 根据邻接矩阵画出图，容易发现最短路为 ，距离为 。
2. 判断题（每题 2 分，共 20 分）
2.1 判断题题面
2.2 判断题解析
第 1 题：。祖冲之发现了圆周率，并计算到了小数第七位。
第 2 题：。^ 表示按位异或运算，2 ^ 3 的结果是 。
第 3 题：。完全二叉树的性质。
第 4 题：。能用 DP 解决的问题不一定能用贪心，例如 01 背包等问题。
第 5 题：。sin(30) 中的 是弧度制。
第 6 题：。广搜可以用于解决最短路，深搜需要搜出所有的路径比较，广搜更合适。
第 7 题：。当该哈希表的每个表项都有元素时，如果待查找元素不在该哈希表中，时间复杂度可以达到 。
第 8 题：。递归只需要递归需要的状态，递推需要一个一个填表，有时候递推的效率更高。
第 9 题：。假设落下的是白子，则可以从该子周围四个有黑子的位置分别开始进行泛洪算法，若某个区间全部是黑子、没有空位，则该区间需要被提掉。
第 10 题：。因为类 B 没有实现类 A 中的纯虚函数 f，若将 B 实例化，则 B 没有办法执行函数 f。
3. 编程题（每题 25 分，共 50 分）
3.1 编程题 1（交流问题）
分析
题目保证交流一定是跨校开展的，如果我们将交流的两个人连一条边，那么 A 校同学的点集合和 B 校同学点集合一定是不相交的，我们一定可以将一个集合中的点染成黑色，另一个集合的点染成白色。
那个这个问题就转化为了，dfs 将整个图进行二分图染色，然后统计图中黑色点的数量和白色点的数量。
代码
#include<bits/stdc++.h>usingnamespacestd;constint maxn = 1e5 + 5;int col[maxn], vis[maxn], cnt[2], n, m, ans;vector<int> g[maxn];voiddfs(int u, int color){ col[u] = color; ++cnt[color];for(int v: g[u]) {if(col[v] == -1) { dfs(v, color ^ 1); } }}intmain(){cin>>n>>m;while(m--) {int u, v;cin>>u>>v; g[u].push_back(v); g[v].push_back(u); }memset(col, -1, sizeof(col));for(int i = 1; i <= n; ++i) {if(col[i] == -1) { cnt[0] = cnt[1] = 0; dfs(i, 0); ans += min(cnt[0], cnt[1]); } }cout<<ans<<" "<<n - ans;return0;}3.2 编程题 2（俄罗斯方块）
分析
本题和我在 2023 年 6 月的 CSP-J 模拟月赛中出的「T4 乐高积木」的思想比较类似，不过本题更为简单和直接，是一个模拟题。
做法很多，我直接套用月赛做法。
我们可以将一系列坐标集合组成的连通块定义为一个坐标的集合，typedef set<node> block，那么现在就是要找到形状不相同的 block。
因为平移之后可以重合算一种方案，那么我们可以把所有的 block 做如下的平移操作：
我们可以将所有的 block 全部平移到坐标原点 。具体操作： 我们找出 block 中 x 和 y 坐标的最小值 minx、miny，那么它可以视为一个平移 矢量，将 block 中的每一个单元格都减去该矢量就可以移动到坐标原点了。 我们将这一步操作定义成一个标准化函数 normalize
代码
#include<bits/stdc++.h>usingnamespacestd;constint maxn = 505;int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};int a[maxn][maxn], n, m;bool vis[maxn][maxn];structnode {int x, y;friendbooloperator < (node a, node b) {return a.x < b.x || a.x == b.x && a.y < b.y; }};typedefset<node> block; // 定义一个俄罗斯方块为坐标集合vector<block> ans; // 用于存放所有俄罗斯方块// 找到木块中最小的 (x, y) 平移到原点block normalize(const block & a){int minx = a.begin() -> x, miny = a.begin() -> y;for(auto item: a) { minx = min(minx, item.x); miny = min(miny, item.y); } block ans;for(auto item: a) { node tmp; tmp.x = item.x - minx, tmp.y = item.y - miny; ans.insert(tmp); }return ans;}boolcheck(int x, int y){return x >= 1 && x <= n && y >= 1 && y <= m;}block cur;voiddfs(int x, int y, int c){ vis[x][y] = true; cur.insert((node){x, y});for(int i = 0; i < 4; ++i) {int nx = x + dx[i], ny = y + dy[i];if(check(nx, ny) && !vis[nx][ny] && a[nx][ny] == c) { dfs(nx, ny, c); } }}intmain(){cin>>n>>m;for(int i = 1; i <= n; ++i) {for(int j = 1; j <= m; ++j) cin>>a[i][j]; }for(int i = 1; i <= n; ++i) {for(int j = 1; j <= m; ++j) {if(!vis[i][j]) { cur.clear(); dfs(i, j, a[i][j]); ans.push_back(cur); } } }set<block> res;for(auto item: ans) res.insert(normalize(item));cout<<res.size();return0;}-完结-
信奥课程咨询或合作，请加微信dimension-s或扫描下方二维码
如果你喜欢这类赛事真题解析文章，欢迎点赞、转发、收藏，让更多人看到这份真诚的分享！
欢迎点击下方名片关注
