点击 GESP 真题解析合集 可以查看历届 GESP 真题解析。
1. 单选题（每题 2 分，共 30 分）
【答案】: B。
【解析】:sin(3.1415926 / 2) 就是数学上的 ，答案为 。
【答案】: D。
【解析】: 。
A 错误，先序遍历是 123。 B 错误，中序遍历是 132。 C 错误，后序遍历是 321。 D 正确。
【答案】: A。
【解析】: A 选项既是 的子序列又是 的子序列，同时是最长的，满足最长公共子序列的定义。
【答案】: D。
【解析】:
A 正确，符合最长上升子序列的定义。 B 正确，符合最长上升子序列的定义。 C 正确，符合最长下降子序列的定义。 D 错误，由 A 和 B 选项可知 D 错误。
【答案】: D。
【解析】:
A 正确，树是一种特殊的图。 B 正确，前序和后序都可以用 DFS 完成，是 DFS 的一种。 C 正确，可以指定任意点为根开始 DFS。 D 错误，后序遍历是深度优先搜索的一种，而不是广度优先搜索。
【答案】: A。
【解析】:HDEBFIGCA 是它的后序遍历，A 选项错误，其他选项均正确。
【答案】: A。
【解析】: A 选项会导致数据丢失，其他选项都是常见的哈希冲突解决方案。
【答案】: C。
【解析】: 运算符 & 是按位与，结果类型为整数类型，A错误。数字 的二进制为 ， 的二进制为 ，所以 3 & 6 = 2。注意 B 和 D 选项中， 为八进制的 ，而 、、 则均为十进制。
【答案】: D。
【解析】:
A 错误，可以只包含两个顶点形成环。 B 错误，环也可以是自环。 C 错误，只能保证弱连通，无法保证强连通。强连通需要任意两个顶点能够相互到达，任意两个顶点都存在一条边不能保证能够相互到达，只能保证至少有一个点可以到达另一个点，是弱连通图。 D 正确，一条边会提供一个入度和一个出度，所以入度和出度的总和就是边数的两倍。
【答案】: B。
【解析】: 图的深搜和二叉树的先序遍历都是基于深度优先搜索。其他选项描述均正确。
【答案】: C。
【解析】: 0 号点(V1)连向的是 3 号点(V4)和 1 号点(V2), 1 号点连向的是 4，2，0 号点，2 号点连向的是 4，3，1 号点，依次类推，可以选出正确选项 C。
【答案】: A。
【解析】: 注意到存边方式是邻接矩阵，0 连向 2，3，距离分别是 12 和 30，1 不连向任何点，2 连向 4，距离是 32，依次类推，可以选出正确答案 A。
【答案】: B。
【解析】: 递推或者递归模拟即可。
【答案】: B。
【解析】: 两层循环次数都是 ，总时间复杂度为 。
【答案】: C。
【解析】:
A 错误，5 后面应该是 6。 B 错误，3 后面应该是 7。 C 正确。 D 错误，8 后面应该是 5。
2. 判断题（每题 2 分，共 20 分）
2.1 判断题题面
2.2 判断题解析
第 1 题：。6 & 5 的结果是 4。
第 2 题：。排序的稳定指：排序后，值相等的元素的相对位置不变。冒泡排序稳定。
第 3 题：。对 进行质因数分解的时间复杂度为 。
第 4 题：。同一个类构造函数可以有多个。
第 5 题：。log() 函数是以自然数 为底的。
第 6 题：。二叉树可以是可以是一条直链，这样就仅有 个点。
第 7 题：。广度优先搜索和图是否连通没有关系，都可以进行遍历。
第 8 题：。如果所有元素都冲突，那么最坏的时间复杂度就是 。
第 9 题：。递归和递推实现动态规划只是实现方式不同，大多数情况下时间复杂度是相同的。
第 10 题：。较大的二维地图如果用递归容易栈溢出，一般不用递归实现。
3. 编程题（每题 25 分，共 50 分）
3.1 编程题 1（黑白翻转）
分析
删除所有的白色节点，剩下的黑色节点需要时一棵树。那么只有位于两个黑色节点路径上的白色节点需要被染成黑色，因为两个黑色节点路径上的点被删了，这两个黑色节点会分别在不同的两个连通块里。
那么对于每一个白色节点，我们需要判断以该白色节点为中心，是否有 个方向（子树或父亲节点方向）包含黑色结点。
具体地：我们从任意结点出发进行 DFS。用 表示以 为根的子树中黑色点的数量，这个可以在 DFS 的时候顺便求出。DFS 时，我们还需要维护每一个点有多少个分支方向中包含黑色点，这个可以通过维护有多少个子树包含黑色点，以及父亲方向是否有黑色点得到。
总时间复杂度为 。
代码
#include<bits/stdc++.h>usingnamespacestd;constint maxn = 1e5 + 5;int a[maxn], cnt[maxn], n, m, totblack, ans;vector<int> g[maxn];voiddfs(int u, int fa){ cnt[u] = (a[u] == 1);int braches = 0; // 统计包含黑色结点的分支数量for(int v: g[u]) {if(v == fa) continue; dfs(v, u); cnt[u] += cnt[v];if(cnt[v] > 0) ++braches; }if(a[u] == 0) { // 判断这个白色点是否需要被染色if(totblack - cnt[u] > 0) ++braches; // 父亲方向if(braches >= 2) ++ans; }}intmain(){cin>>n;for(int i = 1; i <= n; ++i) {cin>>a[i];if(a[i] == 1) ++totblack; }for(int i = 1; i <= n - 1; ++i) {int u, v;cin>>u>>v; g[u].push_back(v), g[v].push_back(u); }if(totblack <= 1) {cout<<0;return0; } dfs(1, 0);cout<<ans;return0;}3.2 编程题 2（区间乘积）
分析
一个数是完全平方数等价于将其质因数分解后所有质因数的指数都是偶数。
因为 ，其中的质数只有 共 个。我们将 进行质因数分解，因为只关心奇偶性，那么我们用一个 位的二进制串表示第 个质数的指数的奇偶性（ 表示偶数， 表示奇数）。这里，我们将这种表示方法我们称为「二进制表示」。
例如，对于 ，我们可以用 表示，低位到高位依次表示质数 的指数奇偶性；再例如，数字 ，就可以用 表示，，可以用 表示，全是 的二进制串就表示每一个质因数的指数都是偶数，也就是完全平方数。 现在，我们可以用一个二进制串来判断一个数是否是完全平方数。
现在我们要判断 区间中的数全部乘起来是否时完全平方数？那么只需要求出这个乘积的二进制表示，就可以进行判断。
对于任意两个数 相乘，乘积的质因数的指数就是 和 的质因数的指数相加。对于判断指数奇偶性的话，实际上就是两者的二进制表示进行异或。
例如，对于 和 的乘积，它的质因数分解为 ，乘积的二进制分解为 ，也就是 的二进制表示 与 的二进制表示 的异或。 那么同理，对于 区间内所有的数的乘积的二进制表示，也就是区间内所有数的二进制表示的异或和。
很容易想到前缀和，设 表示前 个数的二进制表示的异或前缀和。
形式化地描述，我们设 表示将 进行质因数分解后，每一个质因数指数奇偶性对应的二进制串。
现在有
对于区间 的乘积 的二进制表示就可以用 来表示。
现在要求区间 的乘积是完全平方数，也就是它的二进制表示 为 ，即有 成立。
那么，我们枚举每一个数，用一个 map<int, int> 记录目前 sum[i] 出现的次数，枚举到每一个数时，先加上前面异或前缀和出现的次数，在更新当前异或前缀和的次数。
代码
#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;constint maxn = 1e5 + 5;int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};int a[maxn], sum[maxn], st[35], n;voidinit(){for(int i = 1; i <= 30; ++i) { // 1 ~ 30 每个数的二进制表示int x = i;for(int j = 0; j < 10; ++j) {int cnt = 0;while(x % p[j] == 0) { ++cnt; x /= p[j]; }if(cnt % 2 == 1) st[i] |= (1 << j); // 第 j 位指数为奇数 } }}intmain(){ init();cin>>n;map<int, int> mp; mp[0] = 1; // 统计 sum[0] 的次数 ll ans = 0;for(int i = 1; i <= n; ++i) {cin>>a[i]; sum[i] = sum[i - 1] ^ st[a[i]]; ans += mp[sum[i]]; ++mp[sum[i]]; }cout<<ans;return0;}-完结-
信奥课程咨询或合作，请加微信dimension-s或扫描下方二维码
如果你喜欢这类赛事真题解析文章，欢迎点赞、转发、收藏，让更多人看到这份真诚的分享！
欢迎点击下方名片关注
