违法和不良信息举报 联系客服
免费注册 登录

单选题在图采用邻接表存储时，求最小生成树的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题：

若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()。

A.O（0）

B.O（1）

C.O（n）

D.O（n2）


正确答案：C

第2题：

设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为()。

A.O(n+e)

B.O(n^2)

C.O(ne)

D.O(n^3)


正确答案：A

第3题：

对n个顶点和e条边的有向图,以邻接矩阵存储,则求图中某顶点入度的时间复杂度为()。A)O(n)B)O(e)C)O(n＋e)D)O(n2)

A.A

B.B

C.C

D.D


参考答案：A

第4题：

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

A.O(n)

B.O(n²)

C.O(e)

D.O(eloge)

F.O(e²)


参考答案：B,D

第5题：

对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()

A. O(n)

B. O(n2)

C. O(nlog2n)

D. O(n3)


正确答案：B

第6题：

●对于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
【解析】此题是考查数据结构图的应用。

第7题：

对n个关键字作快速排序,在最坏情况下,算法的时间复杂度是()。

A.O(n)

B、O(n2)

C、O(nlog2n)

D、O(n3)


参考答案：B
解释：快速排序的平均时间复杂度为O(nlog2n)，但在最坏情况下，即关键字基本排好序的情况下，时间复杂度为O(n2)。

第8题：

●若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为 (47) 。

(47) A．O(n)

B．O(n2)

C．O(n2+1)

D．以上都不对


正确答案：B
【解析】n个顶点的图的邻接矩阵是一个n阶方阵，有n行n列。从顶点vi出发，对图进行广度优先遍历，需对矩阵的第i行逐列检测非零元(若a[i][j]1,则说明顶点vj与vi之间有边存在，vj就是vi的邻接顶点)。根据广度优先遍历的思想，每一个顶点都要轮换着做出发顶点，即矩阵的每一行都将要被逐列检测。显然，算法中要用一个两重循环来组织逐行逐列的检测操作，所以，算法的时间复杂度是n的平方阶。

第9题：

下列程序段的时间复杂度为()。

A.O(n)

B.O(log2n)

C.O(n3)

D.O(n2)


正确答案：A

第10题：

在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。

A.O(n)

B.O(n+e)

C.O(n2)

D.O(n3)


正确答案：B

更多相关问题
相关内容