首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2017-01-04
58
问题
假设有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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述第二国际建立的社会历史条件。
毛泽东认为,社会主义这个阶段可分为两个阶段,包括()。
光绪元年七月,清政府迫于()强烈要求派一位使臣到其国,()成为中国第一个驻外公使
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
解放军渡江战役中横渡长江的东西两个攻击点是()。
以孙中山为首的革命派和以康有为代表的维新派,是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()
下列哪一事件之后,明与蒙古之间出现了“自宣大至甘肃,不用兵者二十年”的情形?()
某汽车轮渡口,过江渡船每次能载10辆车过江。过江车辆分为客车类和汽车类,上渡船有如下规定:同类车先到先上船,客车先于货车上船,且每上4辆客车,才允许上一辆货车,若等待客不足4辆,则以货车代替,若无货车等待允许客车都上船。写一算法模拟渡口管理。
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(el,e2,…,em);i=1;while(所剩边数>=顶点数){从图中删去ei;若图不再连通。则恢复ei;i=
利用栈求表达式的值时,设立运算数栈OPND。假设OPND只有两个存储单元,在下列表达式中,不发生溢出的是()。
随机试题
将原材料转变为成品的过程称为生产过程。()
简述第二次社会大分工产生的主要结果。
Windows提供了各种系统工具来帮助用户管理系统,其中的_______可以重新安排磁盘上的文件、程序以及未使用的空间,以便程序运行更快。
腹部手术术后早期出现肺功能不全最常见的诱因是
嗜铬细胞瘤产生的肽类激素中,能引起面部潮红的是
男,40岁,推销员,自述半小时前又突然感到气紧,胸闷.心悸,头晕,出汗,认为生命垂危,被送来急诊。近2月来,这种情况发生过3次。每次持续约0.5-1小时,发病间隙期一切正常,发病与饮食无关最适宜的急诊处理是
A、桂枝茯苓丸B、妇科千金片C、干金止带丸D、益母草胶囊E、妇炎平胶囊某女,50岁,宿患癥块。证属瘀血积滞,治当活血、化瘀、消癥,宜选用的成药是()。
某企业适用的城市维护建设税税率为7%,2016年3月份该企业应交纳增值税200000元、土地增值税30000元、营业税100000元、消费税50000元、资源税20000元,3月份该企业应记入“应交税费——应交城市维护建设税”科目的金额为()元。
适龄儿童、少年因身体状况需要延缓入学或者休学的,其父母或者其他法定监护人应当提出申请,由()批准。
A、It’sopenonlytoteachersandpostgraduates.B、Hecanstudythereifheiswritingaresearchpaper.C、Seniorstudentscanen
最新回复
(
0
)