首页
登录
从业资格
Prim 算法和 Kruscal 算法都是无向连通网的最小生成树的算法, Pri
Prim 算法和 Kruscal 算法都是无向连通网的最小生成树的算法, Pri
题库
2022-08-02
67
问题
Prim 算法和 Kruscal 算法都是无向连通网的最小生成树的算法, Prim 算法从一个顶点开始,每次从剩余的顶点中加入一个顶点,该顶点与当前的生成树中的顶点的连边权重最小,直到得到一颗最小生成树; Kruscal 算法从权重最小的边开始,每次从不在当前的生成树顶点中选择权重最小的边加入,直到得到一颗最小生成树,这两个算法都采用了(此空作答 )设计策略,且( )。A.分治B.贪心C.动态规划D.回溯
选项
A.分治
B.贪心
C.动态规划
D.回溯
答案
B
解析
Prim 算法和 Kruscal 算法都是基于贪心算法的应用。 Prim 算法的时间复杂度为 O(n2 ) ,与图中边数无关,该算法适合于稠密图。 Kruskal 算法的时间复杂度只和边有关系,为 O(elog2 e) ,由于 Kruskal 算法只与边有关,因此适合求稀疏图的最小生成树。
转载请注明原文地址:https://tihaiku.com/congyezige/2408347.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
有两个N*N的矩阵A和B,想要在微机(PC机)上按矩阵乘法基本算法编程实现计
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数
在开发一个字处理软件时,首先快速发布了一个提供基本文件管理、编辑和文档生成功能的
不同加密机制或算法的用途、强度是不相同的,一个软件或系统中的加密机制使用是否合理
在结构化分析模型中,( )描述了所有在目标系统中使用和生成的数据对象。A.数据
对一段信息生成消息摘要是防止信息在网络传输及存储过程中被篡改的基本手段,(
加密和解密是明文和密文之间的可逆转换,( )不属于加密算法。A.RSA B.
传统编译器进行词法分析、语法分析、代码生成等步骤的处理时,前一阶段处理的输出是后
不同加密机制或算法的用途、强度是不相同的,一个软件或系统中的加密机制使用是否合理
结构化开发方法中,()主要包含对数据结构和算法的设计。对算法设计时,其主要依据
随机试题
[originaltext]Georgehadstolensomemoney,butthepolicehadcaughthima
病理性的持续睡眠状态,可被唤醒,并能正确回答问题称为()(2008)A.
牛蒡子的应付规格是A.牛蒡子 B.牛子 C.炒牛蒡子 D.鼠黏子
A.压力蒸气灭菌 B.干热灭菌 C.干粉消毒 D.环氧乙烷气体灭菌 E.
有关慢性支气管炎患者的治疗措施,错误的是A.缺氧明显者可给予低流量吸氧 B.急
中国共产党创建初期,集中主要精力()。A.发展党的组织 B.领导工人运动
在控制性详细规划的各项指标中,不用百分比表示的有( )。A.绿地率 B.容积
岗位人员规范,即在岗位系统分析的基础上,对某类岗位员工的( )、胜任能力等方面
虚拟企业建立了覆盖供应商、制造商、分销商及顾客的信息网络,这一网络的触角几乎延伸
e=20.33岁,表示A.该受试对象实际存活了20.33年 B.活满60岁的人
最新回复
(
0
)