首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2018-08-12
66
问题
假设有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/QMRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列事件:①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订,按照时间顺序排列正确的是()。
关于垄断组织的积极作用,不正确的说法是()。
詹天佑自主设计修建了中国第一条铁路是在()。
世界近代史上,世界经济发展经历了两次大的飞跃,即第一次工业革命和第二次工业革命。阅读下面两段材料,回答问题:材料一工业革命的主角——蒸汽机,是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产,主要依靠以人力和经
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
设磁盘的扇区大小为4KB,磁盘转速为15000r/min,磁盘平均寻道时间为4ms,最大数据传输速率为40MB/s,磁盘控制器开销时问为1ms,计算读写一个扇区所需平均时间(不考虑I/O请求队列中的等待时间)。
若无向图G=(V,E)中含有7个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是____。
下面关于B-树和B4一树的叙述中,不正确的是()。
以下有关m阶B一树的说法中正确的有()。Ⅰ.每个结点至少有两棵非空子树Ⅱ.树中每个结点至多有m-1个关键字Ⅲ.所有叶子在同一层上Ⅳ.当插入一个数据项引起B-树结点分裂后,树长高一层
随机试题
细支气管肺泡癌属于下列哪种病理类型的肺癌
某男,28岁。颈侧颌下有肿块如豆,累累如串珠,为
薄荷、荆芥、枇杷叶、陈皮、甘草宜用( )。三棱、槟榔、郁金宜用( )。
甲建设单位与乙设计院签订设计合同,设计费用共30万元,双方在协商定金的数额时发生意见分歧。根据《担保法》的规定,该定金数额最多为()万元。
下列食物中,富含磷的是()。
(2017·重庆)下列选项中,不属于影响迁移的客观原因是()
已知函数f(x)的原函数为
下列各选项中,不属于Internet应用的是()。
Now,thelocationofyourcollege.Somecollegesareinthecenterofhugecities,some【C1】______,andsomearesurroundedbyfi
Therearesomekindsofprisonsintheworldinwhichprisonersaretreatedverycruel.However,thereisaprisoninIcelandwh
最新回复
(
0
)