对含有n个顶点、e条边的带权图求最短路径的Dijkstra算法的时间复杂度为____。A．O(n)B．O(n+e)C．O (n2)D．O(ne)
题目
对含有n个顶点、e条边的带权图求最短路径的Dijkstra算法的时间复杂度为____。
A．O(n)
B．O(n+e)
C．O (n2)
D．O(ne)
相似考题
参考答案和解析
更多“对含有n个顶点、e条边的带权图求最短路径的Dijkstra算法的时间复杂度为____。”相关问题
-
第1题：
Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生。()此题为判断题(对，错)。
正确答案：√
-
第2题：
求最短路径的FLOYD算法的时间复杂度为(16)。
A．O(n)
B．O(n+e)
C．O(n2)
D．O(n3)
正确答案：D
解析：FLOYD算法的时间复杂度为n3。 -
第3题：
n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为（）。
正确答案:O(n2) -
第4题：
n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为（）；若采用邻接表存储，该算法的时间复杂度为（）。
正确答案:O(n2) O(n+e) -
第5题：
n个顶点e条边的图，若采用邻接表存储，则空间复杂度为（）。
正确答案:O(n+e) -
第6题：
n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为（）；若采用邻接表存储时，该算法的时间复杂度为（）。
正确答案:O(n2) O(n+e) -
第7题：
对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表和边集数组表示时，求任一顶点度数的时间复杂度依次为（）、（）和（）。
正确答案:O（n）；O（e/n）；O（e） -
第8题：
填空题n个顶点e条边的图，若采用邻接表存储，则空间复杂度为（）。正确答案： O(n+e)解析： 暂无解析 -
第9题：
填空题用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度（）的次序来得到最短路径的。正确答案： 递增解析： 暂无解析 -
第10题：
填空题如果无向图G有n个顶点、e条边且用邻接矩阵进行存储，那么深度优先遍历图G的时间复杂度为（）。正确答案： O(N2)解析： 暂无解析 -
第11题：
填空题n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为（）；若采用邻接表存储时，该算法的时间复杂度为（）。正确答案： O(n2) O(n+e)解析： 暂无解析 -
第12题：
填空题对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。正确答案： O（n2）,O（elog2e）解析： 暂无解析 -
第13题：
对于含n个顶点、e条边的无向连通图,利用Prim算法构造最小生成树的时间复杂度(),用Kruskal算法构造最小生成树的时间复杂度为()。A.O(n)
B.O(n²)
C.O(e)
D.O(eloge)
F.O(e²)
参考答案：B,D
-
第14题：
对于含有n个顶点的带权连通图，它的最小生成树是指()。A.图中任意一个由n-l条权值最小的边构成的子图
B.图中任意一个由n-1条权值之和最小的边构成的子图
C.图中任意一个由n-1条权值之和最小的边构成的连通子图
D.图中任意一个由n个顶点构成的边的权值之和最小的连通子图答案：D解析：一个连通图的生成树(连通无回路图)是一个极小连通子图。它含有图中全部n个项点，但只有构成一棵树的(n-1)条边。如果小于(n-1)条边，则是非连通图；如果多于(n-1)条边，则一定有回路，因为这条边使得它依附的那两个顶点之间有了第二条路径。但是，有(n-1)条边的图不一定都是生成树。带权连通无向图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。总之，含有n个顶点的带权连通图，它的最小生成树是指图中任意一个由n个顶点构成的边的权值之和最小的连通子图。 -
第15题：
如果无向图G有n个顶点、e条边且用邻接矩阵进行存储，那么深度优先遍历图G的时间复杂度为（）。
正确答案: O(N2) -
第16题：
用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度（）的次序来得到最短路径的。
正确答案:递增 -
第17题：
对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。
正确答案:O（n2）；O（elog2e） -
第18题：
对于含有N个顶点E条边的无向连通图，利用Kruskal算法生成最小代价生成树的时间复杂度为（）。
正确答案:o（elg0） -
第19题：
对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为（）和（）
正确答案:O（n）；O（e/n） -
第20题：
填空题n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为（）。正确答案： O(n2)解析： 暂无解析 -
第21题：
填空题对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表和边集数组表示时，求任一顶点度数的时间复杂度依次为（）、（）和（）。正确答案： O（n）,O（e/n）,O（e）解析： 暂无解析 -
第22题：
填空题对于含有N个顶点E条边的无向连通图，利用Kruskal算法生成最小代价生成树的时间复杂度为（）。正确答案： o（elg0）解析： 暂无解析 -
第23题：
填空题对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为（）和（）正确答案： O（n）,O（e/n）解析： 暂无解析 -
第24题：
填空题n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为（）；若采用邻接表存储，该算法的时间复杂度为（）。正确答案： O(n2) O(n+e)解析： 暂无解析