假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点v相关的所有弧的时间复杂度是()。A.O(n)B.O(e)C.O(n+e)D.O(n×e)
假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点v相关的所有弧的时间复杂度是()。
A.O(n)
B.O(e)
C.O(n+e)
D.O(n×e)
B.O(e)
C.O(n+e)
D.O(n×e)
参考解析
解析：由有向图的邻接表存储结构可知，每个顶点v链接的顶点只包含从v发出的弧所指向的顶点，不包含指向v的弧所对应的尾结点。又因为邻接表的结点数是边数与顶点数的总和，所以要删除与某个顶点相关的所有弧时间复杂度为O(n+e)。
相关考题：
● 邻接矩阵和邻接表是图（网）的两种基本存储结构，对于具有 n个顶点、e条边的图， （59） 。（59）A. 进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关B. 进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C. 采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)D. 采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)
邻接矩阵和邻接表是图(网)的两种基本存储结构，对于具有n个顶点、e条边的图，( )。A．进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关B．进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C．采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*c)D．采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为o(n2)
设一个包含N个顶点、E条边的简单有向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧)，则该矩阵的元素数目为(58)，其中非零元素数目为(59)。A．E2B．N2C．N2-E2D．N22+E2
设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是(6)。若有向图采用邻接矩阵表示(例如，图4-1所示有向图的邻接矩阵如图4-3所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时问复杂度是(7)。
● 设一个包含N个顶点、 E条边的简单有向图采用邻接矩阵存储结构 （矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧），则该矩阵的元素数目为 （60） ，其中非零元素数目为 （61） 。
对于具有n个顶点、6条边的图()。A.采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)B.进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C.采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)D.进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关
设一个包含n个顶点、e条弧的简单有向图采用邻接矩阵存储结构（即矩阵元素A[i][j]团等于1或0，分别表示顶点i与顶点j之间有弧或无弧），该矩阵购非零元素数目为（ ）。A.eB.2eC.n-eD.n+e
填空题对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为（）和（）