首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2019-01-30
83
问题
假设有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/5ZRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
阅读以下史料,并回答问题:“古之有国家迫于危亡者,不过守与奔而已。今以守无人,以奔则无地,所以諰諰然惟冀阁下之见哀而赦已,前者连奉书,愿削去旧号,是天地之间,皆大金之国,而尊无二上,亦何劳师远涉而后为快哉!”(宋高宗致信金兵元帅)
阅读下列材料,回答问题:材料一:列宁说:“我们在夺取政权时便知道,不存在将资本主义制度具体改造成社会主义制度的现存方法……我不知道哪位社会主义者处理过这类问题……我们必须根据实践作出判断。”——摘自《苏联
抗日战争时期,敌后战场与正面战场发挥着不同的作用,下列不属于正面战场的战役是()。
下列有关西欧封建社会的表述,错误的一项是()。
16世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
1217年,英格兰的《森林宪章》允许平民百姓在王室森林中放牧牲畜、挖掘水渠并从事其他农业活动。颁布该宪章的主要目的在于()
下列不属于苏联高度集中的经济政治体制产生的条件的是()。
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
下列各组条约的时间排列顺序正确的是()。①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》
随机试题
已知弯管的两投影,且ab与a’c’为弯管的实长,求作弯管空间夹角α(见图2—43)。
直流电机电刷与换向器接触不良产生的原因有哪些?
我们与自然界的关系既不是“自然界是主人,我们是仆人”的关系,也不是“我们是主人,自然界是仆人”的关系。这反映出()。
患者,女性,26岁。自述脑子反应快,特别灵活,好像机器加了“润滑油”,思维敏捷,概念一个接一个地不断涌现出来,说话的主题极易随环境而改变(随境转移)。可能患有
甲、乙、丙三人系同村农民,村里重新调整土地以后,三人均主张自己对某块土地有承包权。争议发生后,三人互不相让,发展到相互殴打以致毁坏对方的房屋和家具。乡人民政府得知此事后,派工作人员到该村进行调查。后乡政府作出了该块土地的承包权归甲所有的处理决定。乙、丙均对
植物多样性的调查方法为()。
“三表法”
教唆未遂的情形不包括
唯心主义
Thediscussioncenteredonhow______(increase)theirproductioninthecomingyears.
最新回复
(
0
)