计算机类

单选题在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（ ）。A O（n）B O（n+e）C O（n2）D O（n3）

题目
单选题
在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（  ）。
A

O（n）

B

O（n+e）

C

O（n2）

D

O（n3）

如果没有搜索结果，请直接 联系老师 获取答案。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案

第1题：

Prim算法求最小生成树的时间为(),对()图比较有利。


参考答案：O(n2)、稠密

第2题：

●对于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．以上都不对


正确答案：B,C
【解析】此题是考查数据结构图的应用。

第3题：

对________,用 Prim算法求最小生成树较为合适。

A、非连通图

B、连通图

C、稀疏图

D、稠密图


正确答案：D

第4题：

对(),用Prim算法求最小生成树较为合适,而Kruskal算法适于构造()图的最小生成树。

A.完全图

B.连通图

C.稀疏图

D.稠密图


参考答案：D,C

第5题：

下面()算法适合构造一个稠密图G的最小生成树。

A.Prim算法

B、Kruskal算法

C.Floyd算法

D、Dijkstra算法


参考答案：A
解释：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏图G的最小生成树。

第6题：

Kruskal算法求最小生成树的时间为(),对()图比较有利。


参考答案：O(elog2e)、稀疏

第7题：

● 邻接矩阵和邻接表是图（网）的两种基本存储结构，对于具有 n个顶点、e条边的图， （59） 。

（59）A. 进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关

B. 进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关

C. 采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)

D. 采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)


正确答案：D
解析：具有n个顶点的有向图可以用一个n*n的方形矩阵表示。假设该矩阵的名称为M，则当<vi，vj>是该有向图中的一条弧时，M[i，j]=1；否则M[i，j]=O。第i个顶点的出度为矩阵中第i行中“1”的个数；人度为第i列中“l”的个数，并且有向图弧的条数等于矩阵中“1”的个数。

 

第8题：

对稀疏图,用 Prim算法求最小生成树较为合适。()

此题为判断题(对，错)。


正确答案：错

第9题：

如果求一个连通图中以某个顶点为根的高度最小的生成树,应采用()

A、深度优先搜索算法

B、广度优先搜索算法

C、求最小生成树的prim算法

D、拓扑排序算法


参考答案：B

第10题：

对于含n个顶点、e条边的无向连通图,利用Prim算法构造最小生成树的时间复杂度(),用Kruskal算法构造最小生成树的时间复杂度为()。

A.O(n)

B.O(n²)

C.O(e)

D.O(eloge)

F.O(e²)


参考答案：B,D

更多相关问题
相关内容