首页
登录
从业资格
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从
免费题库
2022-08-02
28
问题
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从一个顶点开始,每次从剩余的顶点加入一个顶点,该顶点与当前生成树中的顶占的连边权重最小,直到得到最小生成树开始,Kruscal算法从权重最小的边开始,每次从不在当前的生成树顶点之间的边中选择权重最小的边加入,直到得到一颗最小生成树,这两个算法都采用了( )设计策略,且( )。问题1选项A.分治B.贪心C.动态规划D.回溯问题2选项A.若网较稠密,则Prim算法更好B.两个算法得到的最小生成树是一样的C.Prim算法比Kruscal算法效率更高D.Kruscal算法比Prim算法效率更高
选项
答案
BA
解析
本题考查算法设计与分析的基础知识。
Prim算法从扩展顶点开始,每次总是”贪心的“选择与当前顶点集合中距离最短的顶点,而Kruscal算法从扩展边开始,每次总是”贪心的“选择剩余的边中最小权重的边,因此两个算法都是基于贪心策略进行的。
Prim算法的时间复杂度为O(n2),其中n为图的顶点数,该算法的计算时间与图中的边数无关,因此该算法适合于求边稠密的图的最小生成树;Kruscal算法的时间复杂度为O(mlgm),其中m为图的边数,该算法的计算时间与图中的顶点数无关,因此该算法适合于求边稀疏的图的最小生成树。当图稠密时,用Prim算法效率更高。但若事先没有关于图的拓扑特征信息时,无法判断两者的优劣。由于一个图的最小生成树可能有多棵,因此不能保证用这两种算法得到的是同一棵最小生成树。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2409629.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
需求分析阶段生成的文档中,用来描述企业中各项业务流程的是()A.数据字典 B
以下加密算法中适合对大量的明文消息进行加密传输的是() A.RSA B.
以下关于解释程序和编译程序的叙述中,正确的是()。A.编译程序和解释程序都生成
聚类的典型应用不包括(请作答此空),()是一个典型的聚类算法。A.商务应用中,
关于聚类算法K-Means和DBSCAN的叙述中,不正确的是()。A.K-Me
聚类的典型应用不包括(),(请作答此空)是一个典型的聚类算法。A.决策树 B
需求分析阶段生成的文档中,用来描述企业中各项业务流程的是()A.数据字典 B
传统编译器进行词法分析、语法分析、代码生成等步骤的处理时,前一阶段处理的输出是后
结构化开发方法中,()主要包含对数据结构和算法的设计。对算法设计时,其主要依据来
在开发一个字处理软件时,首先快速发布了一个提供基本文件管理、编辑和文档生成功能的
随机试题
[originaltext]W:U.S.ConsulateinMarseilles,canIhelpyou?M:Yes,please.
【B1】[br]【B12】A、appreciateB、apologizeC、approveD、accountD此句的意思是“网络的使用使人们减少了和
屋面涂膜防水层的最小平均厚度不应小于设计厚度的:()A.95% B.90%
锚杆安装尺寸检查包括()。A:位置 B:方向 C:深度 D:孔径 E:
根据老年人的生理特点和心理需求,旅游行程的安排应以( )为主。A.静态观赏
旅游市场综合监管工作小组隶属于原国家旅游局。()
早饭时,教师发现淇淇的桌子底下有一些蛋黄被踩得粉碎。看着满地被踩黏的蛋黄,该教师
基金管理人推介股权投资基金时,禁止行为包括() Ⅰ.向投资者预测投资业绩;
2004年以来,某市的商品房价格迅速上涨,一度形成恐慌性抢购的市场局面。市民张某
下列关于限售股个人所得税的税务处理,正确的是()。A.个人转让因依法继承所取得
最新回复
(
0
)