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

admin2019-12-10 36

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

选项 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

学硕统考专业

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

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

假定在一个处理机上执行的操作如下：作业估计服务时间片优先数A103B11C23D14E52这些

某公司的局域网设置如下所示，两个局域网通过路由器连接到NAT、服务器上，并且通过NAT服务器连接到Internet上。局域网1的掩码是192．168．14．0／25，局域网2的掩码是192．168．14．128／25，NAT服务器的内部IP地址为192．1

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

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?

关于DMA方式和通道方式，下列说法中错误的是()。

在OSI参考模型中，下列功能需由应用层的相邻层实现的是

在当代中国，爱国主义与爱社会主义【】

骨髓和外周血中性分叶核粒细胞的碱性磷酸酶染色积分在下列疾病中常见降低或为零的是

下列指标中，描述抽样误差大小的指标是

项目实施的合同策划不包括()。

工程咨询服务的投标文件通常采用()的形式。

下列说法正确的是()

党的群众路线是()。

某商品标价165元，若降价以9折出售，仍可获得10%的利润(相对于进价)，则该商品的进货价为()元。

蒙元时期，蒙古、中亚贵族出资交给回商人经营以获利，这批商人被称为()。

以下关于汇编语言和汇编指令的叙述中，正确的是()。