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

第1题

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

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

点击查看答案

第2题

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

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

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

A、Prim

B、Kruskal

点击查看答案

第3题

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

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

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

A、稀疏

B、稠密

C、完全

D、不完全

点击查看答案

第4题

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

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

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

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

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

点击查看答案

第5题

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

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

A、Kruskal算法

B、Dijkstra算法

C、Floyd算法

D、Prim算法

点击查看答案

第6题

关于解决最小代价生成树问题的Prim算法的下述说法，不正确的是（)。

A.优先队列Q中顶点的键值指这个顶点与A集合中点的最小权边的权重

B.从Q中取出一个顶点的实质是在应用MST性质选择连接A与VA的最小权边

C.算法执行结束后，生成树有n-1个顶点

D.算法以优先队列为空为结束条件

点击查看答案

第7题

设计一个算法：求指定结点在二叉搜索树中的层次。

点击查看答案

第8题

以下关于生成树算法的描述正确的是（)。

A.生成树算法的核心是在网络中生成一棵树，然后所有的数据转发都从树根向各个节点转发，这样就不可能发生广播风暴

B.如果网络中有环路，运行生成树算法通过阻塞掉一些链路以消除环路

C.生成树算法中的树根可以人为控制

D.一个局域网中，可能有多棵生成树

点击查看答案

第9题

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

点击查看答案

第10题

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

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

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

点击查看答案

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