首页 › 题库 › GESP编程能力等级认证 › 6 图论算法及综合应用

GESP-C++八级 题库

共 30 道题 ,第 2 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 6 图论算法及综合应用 清除
21 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.2 最短路径

下面Floyd算法中,横线处应该填入的是( )。

#include <iostream>
using namespace std;

#define N 21
#define INF 99999999
int map[N][N];
int main() {
	int n, m, t1, t2, t3;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				map[i][j] = 0;
			else
				map[i][j] = INF;
		}
	}
	for (int i = 1; i <= m; i++) {
		cin >> t1 >> t2 >> t3;
		map[t1][t2] = t3;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (__________) // 在此处填入选项
					map[i][j] = map[i][k] + map[k][j];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout.width(4);
			cout << map[i][j];
		}
		cout << endl;
	}
}
A
map[i][j] < map[i][k] + map[k][j]
B
map[i][j] > map[i][k] + map[k][j]
C
map[i][j] > map[i][k] - map[k][j]
D
map[i][j] < map[i][k] - map[k][j]
答案与解析
正确答案:B

Floyd算法本质是个DP,或者可以理解为松弛操作:

i和j的最短路如果可以通过中间节点k做更新:

则需要map[i][j]>map[i][k]+map[k][j];选B。

题目详情
22 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

一个无向图包含 n 个顶点,则其最小生成树包含多少条边?(   )。

A

n-1

B

n

C

n+1

D

最小生成树可能不存在。

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
23 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

C++语言中,表达式 '9' ^ 3 的结果值为 '999' 。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
24 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下列C++语言代码,能够安全地输出 arr[5] 的值。

int n = 5; 
int arr[n] = {1, 2, 3}; 
std::cout << arr[5];
A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
25 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

使用 math.h 或 cmath 头文件中的函数,对于 int 类型的变量 x ,表达式 fabs(x) 和 sqrt(x * x) 的结果总是近似相等的。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
26 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

运算符重载是C++语言静态多态的一种典型体现,而使用C语言则无法实现运算符重载。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
27 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

存在一个简单无向图满足:顶点数为6,边数为8,6个顶点的度数分别为3、3、3、3、2、2。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
28 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

已知两个 double 类型的变量 r 和 theta 分别表示一个扇形的圆半径及圆心角(弧度),则扇形的周长可以通过表达式 (2 + theta) * r 求得。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
29 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

从32名学生中选出2人分别担任男生班长和女生班长(男生班长必须是男生,女生班长必须是女生),则共有C(32,3)/2种不同的选法。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
30 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

最小生成树

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 100005;
const int M = 200005;
const long long INF = 1e18;

int n, m;
// 存每条边两端点、权值、边编号数组
int u[M], v[M], w[M], p[M];
// 链式前向星:h表头,id存边编号,nx下一条边,et边计数
int h[N], id[M], nx[M], et;
// 并查集父数组f,mark标记是否是最小生成树树边
int f[N], mark[M];
long long sum_mst, ans[M];
// dep深度,pid记录到达该点的树边编号
int dep[N], pid[N];

// 按边权从小到大排序
bool cmp(int x, int y) {
    return w[x] < w[y];
}

// 带路径压缩并查集查找,0代表根节点
int getf(int u) {
    if (!f[u]) return u;
    return f[u] = getf(f[u]);
}

// 链式前向星加边:x连接编号为p的边
void link(int x, int edge_id) {
    id[++et] = edge_id;
    nx[et] = h[x];
    h[x] = et;
}

// DFS遍历最小生成树,求每个点深度、记录到达当前点的树边pid[x]
void dfs(int x, int fa = 0, int edge_id = 0) {
    dep[x] = dep[fa] + 1;
    pid[x] = edge_id;
    for (int i = h[x]; i; i = nx[i]) {
        // 异或快速求对端:u^v^x 得到另一个端点
        int to = u[id[i]] ^ v[id[i]] ^ x;
        if (to != fa) {
            dfs(to, x, id[i]);
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    // 读入所有边
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &u[i], &v[i], &w[i]);
        p[i] = i;
    }
    // Kruskal:边按权升序
    sort(p + 1, p + m + 1, cmp);

    // 1. Kruskal构建最小生成树
    for (int i = 1; i <= m; ++i) {
        int eid = p[i];
        int x = u[eid], y = v[eid];
        int fx = getf(x), fy = getf(y);
        if (fx == fy) continue;
        // 选为树边,标记并累加MST总权值
        mark[eid] = 1;
        f[fx] = fy;
        sum_mst += w[eid];
        // 加入MST链式前向星
        link(x, eid);
        link(y, eid);
    }

    // 初始化答案:树边暂设无穷INF,非树边初始答案就是MST总和sum_mst
    for (int i = 1; i <= m; ++i) {
        ans[i] = mark[i] ? INF : sum_mst;
    }

    // DFS求MST上每个点深度、对应树边pid
    dfs(1);

    // 重置并查集,用于按非树边更新树边答案
    for (int i = 1; i <= n; ++i) f[i] = 0;

    // 2. 遍历所有非树边,更新路径上树边的替换答案
    for (int i = 1; i <= m; ++i) {
        int eid = p[i];
        if (mark[eid]) continue; // 跳过树边,只处理非树边
        int x = getf(u[eid]), y = getf(v[eid]);
        // 向上爬LCA路径,统一路径上所有树边的答案
        while (x != y) {
            // 保证x更深
            if (dep[x] < dep[y]) swap(x, y);
            // pid[x]是连接x与父节点的树边
            int tree_edge = pid[x];
            // 替换这条树边后的新MST权值
            ans[tree_edge] = sum_mst - w[tree_edge] + w[eid];
            // 并查集向上合并,下次不再处理这条边
            int to = u[tree_edge] ^ v[tree_edge] ^ x;
            f[x] = to;
            x = getf(x);
        }
    }

    // 输出每条边答案:INF代表无法替换,输出-1;否则输出替换后最小生成树权值
    for (int i = 1; i <= m; ++i) {
        if (ans[i] < INF) printf("%lld\n", ans[i]);
        else printf("-1\n");
    }
    return 0;
}
题目详情