首页 › 题库 › 信息学奥赛 › 4.1 最小生成树

信息学奥赛-提高级 题库

共 2 道题 · 按题型筛选,点「查看答案」核对解析
章节 4.1 最小生成树 清除
1 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 4.1 最小生成树

一个包含8个顶点的完全图(顶点编号1到8),任意两点之间的边权重等于两顶点编号的差的绝对值,该图的最小生成树总权重是多少?

A
7
B
8
C
9
D
10
答案与解析
正确答案:A

最小生成树是选边构成树且权值和最小。用Kruskal算法,将边权从小到大排序,边权最小的边为(1,2)、(2,3)、(3,4)、(4,5)、(5,6)、(6,7)、(7,8),权值均为1,总和7。

题目详情
2 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 4.1 最小生成树

6 个顶点的连通图的最小生成树,其边数为( )。

A
6
B
5
C
7
D
4
答案与解析
正确答案:B
这道题暂未补解析。
题目详情