● 邻接矩阵和邻接表是图（网）的两种基本存储结构，对于具有 n个顶点、e条边的图， （59） 。（59）A. 进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关B. 进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C. 采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)D. 采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)

题目

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

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

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

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

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

相似考题

1.邻接矩阵和邻接表是图(网)的两种基本存储结构，对于具有n个顶点、e条边的图，( )。A．进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关B．进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C．采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*c)D．采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为o(n2)

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

3.对于一个具有n个顶点和e条边的无向图，若采用邻接表存储，那么，所有顶点邻接表的长度之和等于____。A．e/2B．eC．2eD．n+e

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

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

 

更多“● 邻接矩阵和邻接表是图(网)的两种基本存储结构,对于具有 n个顶点、e条边的图, (59) 。(59)A. 进行 ”相关问题

  • 第1题：

    17、下面哪一种情况的图最适合采用邻接矩阵进行存储？（）

    A．100个顶点，4000条边的图

    B．1000个顶点，1200条边的图

    C．10000个顶点，100000条边的图

    D．10000个顶点，500条边的图


    CD

  • 第2题：

    5.对于一个具有n个顶点和e条边的无向图，若采用邻接矩阵表示，则该矩阵大小是______


    n;n-1

  • 第3题：

    对于一个具有n个顶点和e条边的无向图，若采用邻接表存储，那么，所有顶点邻接表的长度之和等于（）。

    A．n+e

    B．e/2

    C．e

    D．2e


    C

  • 第4题：

    对于一个具有n个顶点和e条边的无向图，若采用邻接表存储，则邻接表中的结点总数是（)。

    A．e/2

    B．2

    C．2*e

    D．n+e


    C

  • 第5题：

    下面哪一种情况的图最适合采用邻接矩阵进行存储？（）

    A．100个顶点，4000条边的图

    B．1000个顶点，1200条边的图

    C．10000个顶点，100000条边的图

    D．10000个顶点，500条边的图


    D

相关内容