首页
登录
从业资格
Prim 算法和 Kruscal 算法都是无向连通网的最小生成树的算法, Pri
Prim 算法和 Kruscal 算法都是无向连通网的最小生成树的算法, Pri
admin
2022-08-02
72
问题
Prim 算法和 Kruscal 算法都是无向连通网的最小生成树的算法, Prim 算法从一个顶点开始,每次从剩余的顶点中加入一个顶点,该顶点与当前的生成树中的顶点的连边权重最小,直到得到一颗最小生成树; Kruscal 算法从权重最小的边开始,每次从不在当前的生成树顶点中选择权重最小的边加入,直到得到一颗最小生成树,这两个算法都采用了()设计策略,且(此空作答)。A.若网较稠密,则Prim算法更好B.两个算法得到的最小生成树是一样的C.Prim算法比Kruscal算法效率更高 D.Kruscal算法比Prim算法效率更高
选项
A.若网较稠密,则Prim算法更好
B.两个算法得到的最小生成树是一样的
C.Prim算法比Kruscal算法效率更高
D.Kruscal算法比Prim算法效率更高
答案
A
解析
Prim 算法和 Kruscal 算法都是基于贪心算法的应用。 Prim 算法的时间复杂度为 O(n2) ,与图中边数无关,该算法适合于稠密图。 Kruskal 算法的时间复杂度只和边有关系,为 O(elog2e) ,由于 Kruskal 算法只与边有关,因此适合求稀疏图的最小生成树。
转载请注明原文地址:https://tihaiku.com/congyezige/2408348.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
传统编译器进行词法分析、语法分析、代码生成等步骤的处理时,前一阶段处理的输出是后
结构化开发方法中,()主要包含对数据结构和算法的设计。对算法设计时,其主要依据来
在软件开发过程中,详细设计的内容不包括( )设计。A.软件体系结构 B.算法
在开发一个字处理软件时,首先快速发布了一个提供基本文件管理、编辑和文档生成功能的
对现有软件系统中一些数据处理的算法进行改进,以提高效率,从而更快地响应用户服务要
不同加密机制或算法的用途、强度是不相同的,一个软件或系统中的加密机制使用是否合理
在结构化分析模型中,( )描述了所有在目标系统中使用和生成的数据对象。A.数据
对一段信息生成消息摘要是防止信息在网络传输及存储过程中被篡改的基本手段,(
加密和解密是明文和密文之间的可逆转换,( )不属于加密算法。A.RSA B.
加密和解密是明文和密文之间的可逆转换,()不属于加密算法。 A.RSA B
随机试题
Doyouknowhowtouseacameraproperly?First,slidethepowerswitchtot
Notonly___asacookeddishallovertheworld,butalsoitisusedinmakingl
[originaltext]Inlargecities,forinstance,London,andcrowdedplacessuch
错位愈合陈旧性颌骨骨折的复位方法是:()A.手法复位 B.牵引复位
男性,50岁,1年来面色苍白、乏力,1个月来出现牙龈出血。化验Hb68g/L,W
在股权投资基金管理人开展资产管理业务时,引入基金托管人是为了引入独立的第三方机构
期货交易所上市交易品种,应当经( )批准。A.中国期货业协会 B.国务院
(2020年真题)根据CAPM模型,已知市场预期收益率为10%,短期国库券利率为
(2020年真题)关于建设工程投标报价的编制,下列说法正确的是()。A.可
关于知识产权法律特征的说法,正确的是()。A.具有财产权和人身权双重属性
最新回复
(
0
)