02331数据结构

已知无向图G的顶点数为n,边数为e,其邻接表表示的空间复杂度为()。

题目

已知无向图G的顶点数为n,边数为e,其邻接表表示的空间复杂度为()。

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

第1题:

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

A.O(n+e)

B.O(n^2)

C.O(ne)

D.O(n^3)


正确答案:A

第2题:

●无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。若无向图G中的顶点数为n,边数为e,则所有顶点的度数之和为(59)。

(59)

A. n*e

B.n+e

C.2n

D.2e


正确答案:D

第3题:

●具有n个顶点e条边的无向图的邻接表,其边表结点总数为 (50) 。

(50) A.n

B.e

C.2e

D.n+e


正确答案:C
【解析】无向图的邻接表中,第i个边表的结点是表示关联于顶点i的边。同一条无向边关联于两个顶点,因此同一条边在邻接表中用了两个边表结点表示。故e条边的无向图的邻接表,其边表结点总数为2e。

第4题:

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


正确答案:O(n2)

第5题:

对有n个结点、e条边且采用数组表示法(即邻接矩阵存储)的无向图进行深度优先遍历,时间复杂度为( )


答案:A
解析:

第6题:

设某有向无环图的顶点个数为n、弧数为e,那么用邻接表存储该图时,实现上述拓扑排序算法的函数TopSort的时间复杂度是(6)。

若有向图采用邻接矩阵表示(例如,图4-1所示有向图的邻接矩阵如图4-3所示),且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作,那么对于有n个顶点、e条弧的有向无环图,实现上述拓扑排序算法的时问复杂度是(7)。


正确答案:(6)O(n+e) (7)O(n2)
(6)O(n+e) (7)O(n2) 解析:邻接表:对有n个顶点和e条弧的有向图而言,在拓扑排序中,若有向图无环,则每个顶点进出队列各一次,共执行e次,搜索算法时间复杂度是由n和e共同决定的,所以总的时间复杂度为O(n+e)。
当用邻接矩阵:对于每个顶点,查找相邻边的时间复杂度是O(n),一共有n个顶点,所以总的时间复杂度是O(n2)。

第7题:

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

A.O(n2)

B.O(n)

C.O(n-1)

D.O(n+1)


正确答案:A

第8题:

对于一个具有n个顶点的无向图,若采用邻接表数据结构表示,则存放表头节点的数组大小为()

A.n

B.n+1

C.n-1

D.n+边数


正确答案:A

第9题:

设无向图G有n个顶点m条边,则其邻接表中表结点数是()

  • A、n
  • B、2n
  • C、m
  • D、2m

正确答案:D

第10题:

无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。若无向图G中的顶点数为n,边数为e,则所有顶点的度数之和为()

  • A、n×e
  • B、n+e
  • C、2n
  • D、2e

正确答案:D