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

admin2017-01-04 98

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

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

答案C

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

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

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

计算机408

学硕统考专业

相关试题推荐

论述近代法国专制制度形成的过程及其影响
简述隋唐民族关系的特点、作用。
中共八大的召开有怎样的历史意义?
1946年5月，中共中央发布的实现“耕者有其田”政策的重要文件是()。
关于中世纪西欧城市发展状况，叙述正确的是()。①城市取得自由或自治，一般以赎买为手段。②城市的自由和自治，一般以封建主或国王颁发的特许证书为凭据。③有的城市集体为封君服军役，并履行封臣的其他义务。④城市可视为
新王朝时期出现了什么类型的墓?()
1908年安庆新军起义是由()领导的。
中国第一条自行设计修建的铁路是在()。
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

随机试题

TTL与门电路正常工作时能带动同类与非门的最大数目称为扇出系数。()
A.脂性肾病B.膜性肾病C.膜增生性肾小球肾炎D.系膜增生性肾小球肾炎引起儿童肾病综合征的最常见原因是
患者男，54岁。因右上颌第一磨牙颊侧牙龈长期瘘管、反复面颊部肿胀而就诊，抗感染治疗后面颊部肿胀消退。本次就诊临床检查见右上颌第一磨牙残冠，牙体破坏严重，患者自诉20年前曾充填(治疗方法不详)，现充填物脱落，周围牙龈无明显红肿，颊侧龈近根尖区仍见瘘管，无明显
接受婚前医学检查的人员对检查结果持有异议的
患者，男性，64岁，肝衰竭。为患者做口腔护理时，护士应重点观察的内容是
特许经营项目合作者选择方式中，()最能体现公开、公平和公正的原则。
下列不属于行政诉讼提起应具备的条件是()。
A公司记账本位币为人民币，2012年有关业务如下：(1)A公司通过收购，持有香港甲上市公司发行在外有表决权股份的80％从而拥有该公司的绝对控制权，甲公司的记账本位币为港币。(2)与境外某公司合资在上海浦东新建乙公司，乙公司的记账本位币为美元，A公司参与
疟疾热寄生虫的血红细胞在120夭后被排除出入体。由于这种寄生虫无法转移到新一代的血红细胞内，在一个人迁移到一个没有疟疾的地区120天后；发生在这个人身上的任何发烧情况都不是由疟疾热寄生虫引起的。以下哪一项如果正确，将最严重地削弱以上的结论?
WCS的3个优点是什么?A、无线规划B、无线设计C、无线管理D、无线RF标识(tag)

最新回复(0)

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

计算机408

学硕统考专业

论述近代法国专制制度形成的过程及其影响

简述隋唐民族关系的特点、作用。

中共八大的召开有怎样的历史意义?

1946年5月，中共中央发布的实现“耕者有其田”政策的重要文件是()。

新王朝时期出现了什么类型的墓?()

1908年安庆新军起义是由()领导的。

中国第一条自行设计修建的铁路是在()。

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

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

TTL与门电路正常工作时能带动同类与非门的最大数目称为扇出系数。()

A.脂性肾病B.膜性肾病C.膜增生性肾小球肾炎D.系膜增生性肾小球肾炎引起儿童肾病综合征的最常见原因是

接受婚前医学检查的人员对检查结果持有异议的

患者，男性，64岁，肝衰竭。为患者做口腔护理时，护士应重点观察的内容是

特许经营项目合作者选择方式中，()最能体现公开、公平和公正的原则。

下列不属于行政诉讼提起应具备的条件是()。

WCS的3个优点是什么?A、无线规划B、无线设计C、无线管理D、无线RF标识(tag)