首页 > 职业资格考试

题目内容（请给出正确答案）

[主观题]

在用Kruskal算法求解带权连通图的最小生成树时，通常采用一个(①)辅助结构，判断一条边的两个端

在用Kruskal算法求解带权连通图的最小生成树时，通常采用一个（①)辅助结构，判断一条边的两个端

点是否在同一个连通分量上，在该算法中选择权值最小的边的原则是该边不能在图中构成(②)，它主要适用于(③)。

A、稀疏

B、稠密

C、完全

D、不完全

查看答案

如果结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装优题宝APP，拍照搜题省时又省心！

更多“在用Kruskal算法求解带权连通图的最小生成树时，通常采用…”相关的问题

第1题

在一个有n个顶点的带权连通图中，有条边，则应该选用()算法来求这个图的最小生成树，从而使计算

在一个有n个顶点的带权连通图中，有条边，则应该选用（)算法来求这个图的最小生成树，从而使计算

在一个有n个顶点的带权连通图中，有条边，则应该选用()算法来求这个图的最小生成树，从而使计算时间较少，

A、Prim

B、Kruskal

点击查看答案

第2题

最短路问题的求解对象只能是简单连通图。（)

点击查看答案

第3题

在求最短路径的算法中，要求所有边上的权值都不能为负值的算法是(①)，虽然允许边上的权值为负值，但不允许在有向回路中出现负值的算法是(②).

在求最短路径的算法中，要求所有边上的权值都不能为负值的算法是（①)，虽然允许边上的权值为负值，但不允许在有向回路中出现负值的算法是（②).

A、Kruskal算法

B、Dijkstra算法

C、Floyd算法

D、Prim算法

点击查看答案

第4题

算法和Kruskal算法求最小生成树的时间各为多少？它们分别适合于哪类图？

点击查看答案

第5题

若图G的顶点取自平面上的点，各顶点间均有联边且权重就是其间的欧氏距离，则G的最小支撑树亦称作

欧氏最小支撑树(Euclidean Minimum Spanning Tree，EMST)，记作EMST(G)。

a)若套用Kruskal或Prim算法构造EMST(G)，各需多少时间？

b)试设计一个算法，在o(nlogn)时间内构造出EMST(G);

c)试证明你的算法已是最优的(亦即，在坏情况下，任何此类算法都需要o(nlogn)时间)。

点击查看答案

第6题

自由树(即无环连通图)T=(V，E)的直径是树中所有顶点对之间最短路径长度的最大值，即T的直径定义

自由树（即无环连通图)T=（V，E)的直径是树中所有顶点对之间最短路径长度的最大值，即T的直径定义

为，这里的路径长度是指路径中所含的边数。编写一个算法求T的直径、并分析算法的时间复杂度。

点击查看答案

第7题

求最小生成树的克鲁斯卡尔（Kruskal)算法耗用的时间与图中______的数目正相关。

求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中______的数目正相关。

点击查看答案

第8题

在轮转调度算法中，一个进程的到达时间是1，完成时间是17，服务时间是4，则带权周转时间是（)。

A.17/4

B.13

C.4

D.16

点击查看答案

第9题

考查某些边的权重不是正数的带权网络。试证明：a)对此类网络仍可以定义最小支撑树——此时，Prim算法是否依然可行？b)若不含负权重环路，则仍可以定义最短路径树——此时，Dijkstra算法是否依然可行？

点击查看答案

第10题

画出图16.17所示两个带权图中的最小生成树

点击查看答案

湖南优积谷网络科技有限公司版权所有 ©2024

湘ICP备16018319号-1 湘公安备案43019002000613号营业执照

违法和不良信息举报电话：400-118-7898

举报/反馈/投诉邮箱：deng＃ujigu.com（请将＃替换成@）