下列关于生成树的说法中，正确的是( )。

admin2019-12-10 37

问题下列关于生成树的说法中，正确的是( )。

选项 A、最小生成树是指权值之和为最小的生成树，且唯一
B、某图的广度优先生成树的高度一定大于等于深度优先生成树的高度
C、Prime算法和Kruskual算法构造的最小生成树一定相同
D、Prime算法适用于求边稠密的图的最小生成树

答案D

解析 A：最小生成树是指权值之和为最小的生成树，但是不唯一，故A选项错误。
B：由广度优先遍历和深度优先遍历算法可知，深度优先算法构造的生成树的树高大于等于广度优先算法构造的生成树的树高，故B选项错误。
C：当最小生成树不唯一时，这两种算法构造的最小生成树可能相同，也可能不同，故C选项错误。
D：Prime算法的时间复杂度为O(n²)，适合稠密图；Kruskual算法的时间复杂度为O(elog₂e)，适合稀疏图，故D选项正确。

转载请注明原文地址:https://kaotiyun.com/show/I93i777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

下列关于生成树的说法中，正确的是( )。

计算机408

学硕统考专业

假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量

计算机系统采用补码运算是为了()。

分页存储管理中，页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址空间)，会给页表的设计带来什么样的新问题?请给出一种解决方法，分析它的优点和缺点。

下图所示的CPU逻辑框图中，有两条独立的总线和两个独立的存储器。已知指令存储器IM最大容量为16384字(字长18位)，数据存储器DM最大容量是65536字(字长16位)。各寄存器均有“打入”(Rin)“送出”(Rout/)控制命令，但图中未标出。

三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。Pl每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中：P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

患者平素头晕头痛，耳鸣目眩，突然发生口眼喁斜，舌强语謇，或手足重滞，甚则半身不遂，或伴麻木等症，舌质红苔黄，脉弦。诊断为脑血栓形成，其证型是()

国际争端的政治解决方法包括谈判与协商、斡旋与调停、调查与和解。其中，斡旋与调停的区别是()

安全验收评价报告是安全验收评价工作形成的主要成果之一，它的作用：一是帮助企业查隐患、落实整改措施；二是()

为纠正“左”倾办学错误，1961年开始贯彻()的方针。

新民主主义社会的五种经济成分中居于领导地位的是()

(2013下集管)关于无连接的通信，下面描述中正确的是______。

Whatisthemaintopicofthispassage?Accordingtothepassage,howmuchoftheoriginallyforestedareremainedinNebraska

Wouldsomedegreeofwarmingbebadformostsocietiesandnaturalenvironments?"Duringthe20thcentury,"writesDr.Patrick