GESP-C++八级 题库
共 27 道题
,第 2 / 2 页
· 按题型筛选,点「查看答案」核对解析
21
判断题
适中
在图论算法中,Kruskal算法和Prim算法都可以用来求解最小生成树,且这两者的贪心策略无论在任何连通无向图上求得的最小生成树总边权和必定相同。( )
A
正确
B
错误
答案与解析
正确答案:对
Kruskal算法通过按边权递增顺序依次选择不构成环的边,逐步连接所有顶点;Prim算法从任意起始顶点出发,每次选择与当前生成树相连且权值最小的边扩展树结构。两种算法均基于贪心策略,每次决策仅依赖当前可选边的最小权值。在任意连通无向图中,若边权唯一确定,则所有最小生成树的总边权和由图的拓扑结构和边权分布共同决定。无论采用何种贪心路径构建,最终生成树的边集可能不同,但其总边权和始终等于该图最小生成树的数学定义所规定的值。算法过程不引入额外约束,故二者求得的总边权和必然一致。
22
判断题
适中
在动态规划问题中,“状态转移方程+递推”和“递归+记忆化搜索”通常是解决同一问题的两种不同实现方式,它们的时间复杂度总是相同的。( )
A
正确
B
错误
答案与解析
正确答案:错
分析动态规划中状态转移方程与递推的实现机制,明确其通过迭代方式按序计算各状态值的过程;分析递归与记忆化搜索的实现机制,明确其以递归调用为基础,在搜索路径中存储已计算状态值的方式;比较两者在处理相同状态空间时的计算次数与访问频率;考察时间复杂度是否由状态总数和每个状态的计算耗时共同决定;确认两种方法在状态计算次数和重复子问题处理上的一致性。
25
判断题
适中
使用倍增法预处理区间最值问题时,预处理的时间复杂度为O(nlogn),查询的时间复杂度为O(1)。( )
A
正确
B
错误
答案与解析
正确答案:对
这道题暂未补解析。
26
简答题
适中
消息查找


答案与解析
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const int C = 2e3 + 5;
const int oo = 1e9;
int n, q;
int r[N], mark[N], pos[N];
int p[C], cnt;
int d[C][C];
int pre[N], suf[N];
int main()
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
{
scanf("%d", &r[i]);
if (r[i])
mark[i] = mark[r[i]] = 1;
}
for (int i = 1; i <= n; i++)
{
if (mark[i])
{
p[++cnt] = i;
pos[i] = cnt;
}
}
for (int i = 1; i <= cnt; i++)
{
for (int j = 1; j <= i; j++)
d[i][j] = oo;
d[i][i] = 0;
for (int j = i; j > 1; j--)
{
d[i][j - 1] = min(d[i][j - 1], d[i][j] + p[j] - p[j - 1]);
if (r[p[j]])
{
int k = pos[r[p[j]]];
d[i][k] = min(d[i][k], d[i][j] + 1);
}
}
}
for (int i = 1; i <= n; i++)
{
pre[i] = pre[i - 1];
if (mark[i])
pre[i] = i;
}
suf[n + 1] = n + 1;
for (int i = n; i; i--)
{
suf[i] = suf[i + 1];
if (mark[i])
suf[i] = i;
}
while (q--)
{
int x, y;
scanf("%d%d", &x, &y);
if (pre[x] < suf[y])
{
printf("%d\n", x - y);
}
else
{
printf("%d\n", x - pre[x] + d[pos[pre[x]]][pos[suf[y]]] + suf[y] - y);
}
}
return 0;
}
27
简答题
适中
子图最短路


答案与解析
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 105;
const int mod = 1e9;
int n, m;
int f[N][N];
int g[N][N];
int ans;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
f[i][j] = mod;
f[i][i] = 0;
}
for (int i = 1; i <= m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
f[u][v] = min(f[u][v], w);
f[v][u] = min(f[v][u], w);
}
for (int l = 1; l <= n; l++)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = f[i][j];
for (int r = l; r <= n; r++)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = min(g[i][j], g[i][r] + g[r][j]);
for (int i = l; i <= r; i++)
for (int j = i; j <= r; j++)
ans = (ans + g[i][j]) % mod;
}
}
printf("%d\n", ans);
return 0;
}