郑州大学
对于含n个顶点、e条边的无向连通图,利用Prim算法构造最小生成树的时间复杂度(),用Kruskal算法构造最小生成树的时间复杂度为()。A.O(n)B.O(n²)C.O(e)D.O(eloge)F.O(e²)
题目
A.O(n)
B.O(n²)
C.O(e)
D.O(eloge)
F.O(e²)
相似问题和答案
第1题：
某无向连通图具有n个顶点e条边，利用克鲁斯卡尔算法生成最小生成树的时间复杂度是________。
A．O(elogn)
B．O(eloge)
C．O(nloge)
D．O(ne)
第2题：
某无向连通图具有n个顶点e条边，利用普利姆算法生成最小生成树的时间复杂度是________。
A．O(nlogn)
B．O(nloge)
C．O(elogn)
D．O(n^2)
第3题：
36、关于最小生成树的求解，下面说法正确的是:
A．求解最小生成树的常用算法有Prim算法，Kruskal算法
B．Kruskal算法每次选择一条最小且不会构成回路权边直至构成一个生成树
C．Prim 算法从一个结点的子图开始构造生成树：选择连接当前子图和子图外结点的最小权边，将相应结点和边加入子图，直至将所有结点加入子图
D．从算法复杂度的角度看，Kruskal算法适用于稀疏图，Prim算法适用于稠密图
第4题：
22、对于n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（）。
A．O(n*n)
B．O(n)
C．O(e)
D．O(nlogn)
第5题：
对某个带权连通图构造最小生成树，以下说法中正确的是（）。 Ⅰ.该图的所有最小生成树的总代价一定是唯一的 Ⅱ.其所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ.用普里姆（Prim）算法从不同顶点开始构造的所有最小生成树一定相同 Ⅳ.使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同
A．仅Ⅰ
B．仅Ⅱ
C．仅Ⅰ、Ⅲ
D．Ⅳ
第6题：
什么样的连通图其最小生成树是唯一的？用Prim和Kruskal算法求最小生成树的时间复杂度各为多少？它们分别更适合于哪类图？
第7题：
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一 个顶点开始，每次从剩余的顶点加入一个顶点，该顶点与当前生成树中的顶占的连边权重 最小，直到得到最小生成树开始，Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点之间的边中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了（ ）设计策略，且（ ）。
A.分治 B.贪心 C.动态规划 D.回溯 A.若网较稠密，则Prim算法更好 B.两个算法得到的最小生成树是一样的 C.Prim算法比Kruscal算法效率更高 D.Kruscal算法比Prim算法效率更高
第8题：
A.完全图
B.连通图
C.稀疏图
D.稠密图
第9题：
●对于n个顶点e条边的无向连通图，利用Prim算法生成最小生成树的时间复杂度为 (24) ，利用Kruskal算法生成最小生成树的时间复杂度为 (25) 。
(24) A．O((n+1)2 )
B．O(n2 )
C．O(n2-1)
D．(n2+1)
(25) A．O(log2e)
B．O(log2e-1)
C．O(elog2e)
D．以上都不对
【解析】此题是考查数据结构图的应用。