假设—个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi(下标)相关的所有弧的时间复杂度是(55)。A．O(n)B．O(e)C．O(n+e)D．O(n*e)

题目

假设—个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi(下标)相关的所有弧的时间复杂度是(55)。

A．O(n)

B．O(e)

C．O(n+e)

D．O(n*e)

相似考题

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

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

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

4.●假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是 (55) 。(55) A．O(n)B．O(e)C．O(n+e)D．O(n*e)

更多“假设—个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi(下标)相关的所有弧的时间复杂 ”相关问题

  • 第1题：

    设一个包含N个顶点、E条边的简单有向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧)，则该矩阵的元素数目为(58)，其中非零元素数目为(59)。

    A．E2

    B．N2

    C．N2-E2

    D．N22+E2


    正确答案：B

  • 第2题：

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

    A、 2*n

    B、 2*e

    C、 n

    D、 e


    正确答案: B

  • 第3题：

    设某有向无环图的顶点个数为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)。

  • 第4题：

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

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

    答案：A
    解析：

  • 第5题：

    设一个包含n个顶点、e条弧的简单有向图采用邻接矩阵存储结构（即矩阵元素A[i][j]团等于1或0，分别表示顶点i与顶点j之间有弧或无弧），该矩阵购非零元素数目为（ ）。

    A.e
    B.2e
    C.n-e
    D.n+e

    答案：A
    解析：
    用邻接矩阵存储有向图，图中每一条弧对应矩阵一个非零元素，题目中提到一共有e条弧，所以一共e个非零元素。

    miao__miao 2016-05-13
    请问矩阵是对称矩阵吗，那a-b和b-a都是1，节点数是不是应该是2e
    MegumiIsh 2016-05-14
    是不是对称矩阵看图，如果是无向图表示两个顶点直接的关系，那邻接矩阵是对称矩阵。如果是有向图的话又不一样，每一条弧对应矩阵一个非零元素，比如从节点i到节点j有边，则Aij为一个非零元素。如果从节点j到节点i有边，则Aji为一个非零元素。题目中提到一共有e条弧，所以一共e个非零元素。

  • 第6题：

    具有n个顶点的有向完全图有（） 条弧。

    • A、n
    • B、n*（n-1）
    • C、n*（n+1）
    • D、n*n

    正确答案:B

  • 第7题：

    若在有向图G中存在一条弧i,Vj>，则称顶点Vj（）于顶点Vi。


    正确答案:邻接

  • 第8题：

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


    正确答案:O(n+e)

  • 第9题：

    有一个n个顶点的有向完全图的弧数（）。


    正确答案:n(n-1)

  • 第10题：

    对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为（）和（）


    正确答案:O（n）；O（e/n）

  • 第11题：

    填空题
    对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表和边集数组表示时，求任一顶点度数的时间复杂度依次为（）、（）和（）。

    正确答案： O（n）,O（e/n）,O（e）
    解析： 暂无解析

  • 第12题：

    填空题
    对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为（）和（）

    正确答案： O（n）,O（e/n）
    解析： 暂无解析

  • 第13题：

    假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点VI相关的所有弧的时间复杂度是【】

    A．O(n)

    B．O(e)

    C．O(n+e)

    D．O(n*e)


    正确答案：C

  • 第14题：

    用相邻矩阵A表示图，判定任意两个顶点Vi和Vi，之间都有长度为m的路径相连，则只要检查(40)的第i行第j列的元素是否为0即可。

    从邻接矩阵可以看出，该图共有(41)个顶点。如果是有向图，该图有(42)条弧；如果是无向图，则共有(43)条边。

    A．mA

    B．A

    C．Am

    D．Am-1


    正确答案：C
    解析：(40)～(43)(40)要判断相邻矩阵A中任意两个顶点Vi和Vi之间是否有长度为m的路径相连，只要检查Am的第i行第j的元素是否为0即可，若为0则无，否则就存在。(41-43)邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E)是具有n个顶点的图，顶点序号依次为1，2，…，n，则G的邻接矩阵是n阶方阵，所以该图有3个顶点。如果此图是有向图，则矩阵中非0元素个数即为弧的数目(为4)；如果此图为无向图，则一条边会在矩阵中对应有两个非零元素出现，所以共有两条边。

  • 第15题：

    ● 设一个包含N个顶点、 E条边的简单有向图采用邻接矩阵存储结构 （矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧），则该矩阵的元素数目为 （60） ，其中非零元素数目为 （61） 。


    正确答案：B,C

  • 第16题：

    假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点v相关的所有弧的时间复杂度是()。

    A.O(n)
    B.O(e)
    C.O(n+e)
    D.O(n×e)

    答案：C
    解析：
    由有向图的邻接表存储结构可知，每个顶点v链接的顶点只包含从v发出的弧所指向的顶点，不包含指向v的弧所对应的尾结点。又因为邻接表的结点数是边数与顶点数的总和，所以要删除与某个顶点相关的所有弧时间复杂度为O(n+e)。

  • 第17题：

    在有向图的邻接表中，顶点Vi在表结点中出现的次数是顶点Vi的（）。

    • A、度
    • B、入度
    • C、出度
    • D、依附于顶点Vi的弧数

    正确答案:B

  • 第18题：

    如果无向图G有n个顶点、e条边且用邻接矩阵进行存储，那么深度优先遍历图G的时间复杂度为（）。


    正确答案: O(N2)

  • 第19题：

    有n个顶点的有向图，至少需要（）条弧才能保证是连通的。


    正确答案:n-1

  • 第20题：

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


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

  • 第21题：

    对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表和边集数组表示时，求任一顶点度数的时间复杂度依次为（）、（）和（）。


    正确答案:O（n）；O（e/n）；O（e）

  • 第22题：

    单选题
    在有向图的邻接表中，顶点Vi在表结点中出现的次数是顶点Vi的（）。
    A

    度

    B

    入度

    C

    出度

    D

    依附于顶点Vi的弧数


    正确答案： A
    解析： 暂无解析

  • 第23题：

    填空题
    有n个顶点的有向图，至少需要（）条弧才能保证是连通的。

    正确答案： n-1
    解析： 暂无解析

相关内容