02331数据结构

假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为（）和（）

题目

假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为（）和（）

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

第1题：

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

第2题：

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

A．n

B．n+1

C．n-1

D．n+e


正确答案：A
解析：此题考的是无向图。

第3题：

对n个顶点和e条边的无向图,采用邻接矩阵和邻接表表示时,求任一顶点度数的时间复杂性分别为()和()。


参考答案：O(n)、O(e/n)

第4题：

对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为（）。


正确答案:n*n（或n行n列）

第5题：

在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（）。

  • A、n
  • B、ne
  • C、e
  • D、2e

正确答案:D

第6题：

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

A、 2*n

B、 2*e

C、 n

D、 e


正确答案: B

第7题：

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


正确答案:n2-2e

第8题：

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

 

第9题：

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


正确答案:O(n2)

第10题：

假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的空间复杂性为（），采用邻接表表示的空间复杂性为（）


正确答案:O（n2）；O（n+e）

更多相关问题
相关内容