数据结构

n个顶点e条边的图，若采用邻接表存储，则空间复杂度为（）。

题目

n个顶点e条边的图，若采用邻接表存储，则空间复杂度为（）。

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

第1题：

n个顶点、e条边的无向图采用邻接表存储方法,该邻接表中共有()个边结点。

A、e

B、2e

C、n

D、2n


参考答案：B

第2题：

● 具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为 （63） 。


正确答案：D

第3题：

● 邻接矩阵和邻接表是图（网）的两种基本存储结构，对于具有 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”的个数。

 

第4题：

n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为（）。


正确答案:O(n2)

第5题：

对于具有n个顶点、6条边的图()。

A.采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)
B.进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关
C.采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)
D.进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关

答案：A
解析：

第6题：

对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则所有顶点邻接表中的结点总数为( )。

A、 2*n

B、 2*e

C、 n

D、 e


正确答案: B

第7题：

具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为(48)；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为(49)；深度优先或广度优先搜索遍历的空间复杂度为(50)。

A．O(n2)

B．O(n)

C．O(n-1)

D．O(n+1)


正确答案：A

第8题：

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

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

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

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

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


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

第9题：

若具有n个顶点、e条边且不带权的无向图采用邻接矩阵存储，则邻接矩阵中的零元素的数目是（）


正确答案:n2-2e

第10题：

具有n个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（）

  • A、Θ（2n）
  • B、Θ（2e）
  • C、Θ（ne）
  • D、Θ（n+e）

正确答案:D

更多相关问题
相关内容