GESP-C++七级 题库

共 27 道题 ,第 2 / 2 页 · 按题型筛选,点「查看答案」核对解析
21 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

在无向连通图中删除一条边,该图就一定变成非连通图。

A
正确
B
错误
答案与解析
正确答案:错
分析无向连通图中边的性质,区分桥边与非桥边。桥边是唯一连接两个连通分量的边,删除后图不再连通;非桥边存在于环中,其删除不会破坏图的连通性。判断删除某条边是否导致图不连通,需考察该边是否属于图中的某个环。若边在环中,则存在替代路径保持连通;若边不在任何环中,则为桥边,删除后图分裂为两个连通分量。因此,边的删除对连通性的影响由其在图结构中的位置决定。
题目详情
22 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

在一个无向图中,每个顶点有不同的编号,在执行深度优先遍历过程中选择下一个顶点时总是优先选择编号更小的相邻顶点,则从指定顶点开始的遍历序列是唯一的。

A
正确
B
错误
答案与解析
正确答案:对
深度优先遍历从指定顶点开始,访问当前顶点后,依次选择未被访问的相邻顶点进行递归遍历。当存在多个未访问的相邻顶点时,选择编号最小的顶点作为下一个访问对象。该选择策略在每一步都具有确定性,即在相同状态下每次执行都会选取同一顶点。遍历过程中顶点的访问顺序由起始顶点和每一步的邻接顶点选择规则共同决定。图的结构和顶点编号唯一确定了每一步可选的相邻顶点集合及其排序。由于每一步的选择均依据编号大小进行比较并取最小值,不存在随机或并列情况下的任意选取。因此,从同一顶点出发,按照此规则生成的遍历序列由图的连接关系和顶点编号完全决定。
题目详情
23 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

若所有字符出现频率相同,则哈夫曼编码一定会得到完全二叉树

A
正确
B
错误
答案与解析
正确答案:错
分析字符频率相同时哈夫曼树构建过程中每次选择两个最小频率节点合并的机制;考察该过程是否必然使所有非叶节点都有两个子节点;结合完全二叉树定义,即除最后一层外每层节点均满,且最后一层节点靠左连续排列,判断该结构在等频条件下是否唯一确定;考虑当所有字符频率相同且字符数为2的幂次或非2的幂次时,构建过程中是否存在必须补全左右子树的情况;根据哈夫曼算法的贪心策略,相同频率下任意选取两个节点不影响后续结构生成的可能性。
题目详情
24 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

使用 math.h 或 cmath 头文件中的函数,表达式 sin(90) 的结果为 1 。

A
正确
B
错误
答案与解析
正确答案:错
分析表达式 sin(90) 的计算过程:math.h 或 cmath 中的三角函数接受弧度制输入;角度值 90 需转换为弧度才能得到对应正弦值;直接传入整数 90 视为弧度输入,不等于 π/2 弧度的精确值;标准库函数按 IEEE 浮点规范执行计算,结果为 sin(90 radians),非 sin(90°);若需计算角度制正弦值,需将角度乘以 π/180 转换为弧度后再传入函数。
题目详情
25 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

在一个无向连通图中,从任意顶点开始进行深度优先遍历,最终得到的 DFS 生成树一定包含图中的所有顶 点。

A
正确
B
错误
答案与解析
正确答案:对
深度优先遍历从指定起始顶点出发,沿边访问可达顶点,每条被遍历的边加入生成树。遍历过程中,未访问的相邻顶点被递归访问,直至所有从起始点可达的顶点均被处理。无向连通图中任意顶点对之间存在路径,因此从任一顶点出发的 DFS 可访问全部顶点。生成树由遍历过程中实际使用的边构成,覆盖所有被访问顶点。由于图连通,所有顶点均被访问,故生成树包含全部顶点。遍历顺序不影响顶点覆盖性,只影响边的选择。生成树结构依赖于遍历路径,但顶点集合始终为全集。
题目详情
26 简答题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

拆分

答案与解析
参考答案
#include <cstdio>
using namespace std;
typedef long long ll;
const int mod = 1000000000;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        if (n == 2) {
            puts("2");
            continue;
        }
        if (n == 3) {
            puts("3");
            continue;
        }
        int r = n % 3;
        int q = n / 3;
        ll ans;
        if (r == 0) {
            ans = qpow(3, q);
        } else if (r == 1) {
            ans = qpow(3, q - 1) * 4 % mod;
        } else { // r == 2
            ans = qpow(3, q) * 2 % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}
题目详情
27 简答题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

物流网络

答案与解析
参考答案
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

struct Highway {
  int u, v;
  int fee, b;
  bool operator<(const Highway &other) const {
    return b < other.b;
  }
};

void solve() {
  int n, m;
  cin >> n >> m;
  vector<Highway> highways(m);
  for (int i = 0; i < m; i++) {
    cin >> highways[i].u >> highways[i].v >> highways[i].fee >> highways[i].b;
  }
  sort(highways.begin(), highways.end());

  vector<vector<pair<int, int>>> g(n + 1); // to, fee
  vector<ll> dp1(n + 1, INF);
  vector<ll> dpn(n + 1, INF);
  dp1[1] = 0;
  dpn[n] = 0;
  ll answer = INF;

  auto dijk = [&](int s, vector<ll>& dist) {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
    q.emplace(dist[s], s);
    while (!q.empty()) {
      auto [d, u] = q.top();
      q.pop();
      if (d > dist[u]) continue;
      for (auto [v, w] : g[u]) {
        if (dist[v] > d + w) {
          dist[v] = d + w;
          q.emplace(dist[v], v);
        }
      }
    }
  };

  for (auto &r : highways) {
    int u = r.u, v = r.v;
    int w = r.fee, bb = r.b;
    // 核心:这里 + bb!你原版漏掉了
    if (dp1[u] != INF && dpn[v] != INF)
      answer = min(answer, dp1[u] + dpn[v] + bb);
    if (dp1[v] != INF && dpn[u] != INF)
      answer = min(answer, dp1[v] + dpn[u] + bb);

    // 再加边进图
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
    // 重新跑Dijkstra更新最短路
    dijk(1, dp1);
    dijk(n, dpn);
  }

  if (answer == INF) cout << -1 << '\n';
  else cout << answer << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}
题目详情