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

admin2019-08-15 108

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

选项 A、0(n)
B、0(e)
C、0(n+e)
D、0(ne)

答案C

解析删除与某顶点v相关的所有边的过程如下：先删除下标为v的顶点表结点的单链表，出边数最多为n一1，对应时间复杂度为O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。

转载请注明原文地址:https://kaotiyun.com/show/EOCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化以及相关考古遗址的发现和研究，是近年来史学界关注的一个热点。二里头文化的年代断限是()
如下图所示为一个网络连接的示意图，主机1到主机2采用了SLIP网络连接，SLIP网络可以传输的最大数据段是296字节，主机2和主机3使用了以太网连接。请问：(1)为了使IP不分片，主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。
某计算机采用微程序控制方式，微指令字长32位，采用字段直接编码的控制方式，共有55个微命令，可分为6个互斥组，分别包含1、3、7、8、12、24个微命令。另外，该机共有5个可判定的外部条件，采用断定方式形成后续微指令地址。(1)设计该机微指令的格式，
一个由高速缓冲存储器Cache与主存储器组成的二级存储系统。已知主存容量为1MB，按字节编址，缓存容量为32KB，采用组相联方式进行地址映射与变换，主存与缓存的每一块为64B，缓存共分8组。(1)写出主存与缓存的地址格式(标明各字段名称与位数)
设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。
对于下图G，按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示；(2)假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。假设G=(V，E)是一个具有n个顶点的带权连通无向图，T=(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造从起始顶点u出发的最小生成树T的步骤如下：重复以下

随机试题

PASSAGETWOWhomdoestheword"counterparts"(Para.5)referto?
甲与乙的承包地相邻，甲地靠着排水沟，乙地排水需要流经甲地入沟。乙地的水稻因大雨需要排水，而甲地种的是棉花，乙提出从甲地挖一水渠排水，并答应给甲一定的补偿，但甲怕乙的排水会伤害自己的棉花，拒不同意。于是乙诉至法院。法院应()。A．支持甲，判决乙不得
A、直腿抬高试验B、拾物试验C、Mills征D、Hoffmann征E、抽屉试验对于腰椎结核诊断有意义的是
某拟建离子膜烧碱和聚氯乙烯(PVC)项目位于规划工业区。离子膜烧碱装置以原盐为原料生产氯气、氢气和烧碱。为使离子膜烧碱装置运行稳定，在厂区内设置3台容积为50m。的液氯储罐，液氯储存单元属重大危险源。聚氯乙烯(PVC)生产过程为HCl与乙炔气在H
涉及大量征用土地和移民搬迁，或可能导致原址居民生活方式、工作性质发生大的变化的开发区规划，须设置()。
对国家助学贷款而言，学费和住宿费贷款，银行应当采用()方式，向借款人交易对象(借款人所在学校)支付，按学年(期)发放。
HAMD()。
现代计算机中采用二进制数制是因为二进制数的优点是()。
儒学对生活的________，体现在每一个细微的环节上，每个观念或者行为都可能有一些潜移默化的印记，有时候可能是比较清晰的一种灌输，有时候则是一种生活态度和行为细节上________的顺应。
Whowasthebestpresident?ThatwecanevenaskthequestionisthankstoGeorgeWashingtonwhoshapedtheroleonhisown【M1】

最新回复(0)

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

计算机408

学硕统考专业

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化以及相关考古遗址的发现和研究，是近年来史学界关注的一个热点。二里头文化的年代断限是()

高度为4的4阶B树最多可容纳()个关键字(根是第1层)。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。

PASSAGETWOWhomdoestheword"counterparts"(Para.5)referto?

A、直腿抬高试验B、拾物试验C、Mills征D、Hoffmann征E、抽屉试验对于腰椎结核诊断有意义的是

涉及大量征用土地和移民搬迁，或可能导致原址居民生活方式、工作性质发生大的变化的开发区规划，须设置()。

对国家助学贷款而言，学费和住宿费贷款，银行应当采用()方式，向借款人交易对象(借款人所在学校)支付，按学年(期)发放。

HAMD()。

现代计算机中采用二进制数制是因为二进制数的优点是()。

儒学对生活的________，体现在每一个细微的环节上，每个观念或者行为都可能有一些潜移默化的印记，有时候可能是比较清晰的一种灌输，有时候则是一种生活态度和行为细节上________的顺应。

Whowasthebestpresident?ThatwecanevenaskthequestionisthankstoGeorgeWashingtonwhoshapedtheroleonhisown【M1】

儒学对生活的，体现在每一个细微的环节上，每个观念或者行为都可能有一些潜移默化的印记，有时候可能是比较清晰的一种灌输，有时候则是一种生活态度和行为细节上的顺应。