首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2018-08-12
65
问题
假设有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://www.kaotiyun.com/show/QMRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
使用天然火最早出现于人类发展过程的哪一阶段?()
三大战役的先后顺序是()
关于垄断组织的积极作用,不正确的说法是()。
下列关于罗马共和国政治制度的叙述,不正确的是()。
三国鼎立局面的关键性战争是()。
世界近代史上,世界经济发展经历了两次大的飞跃,即第一次工业革命和第二次工业革命。阅读下面两段材料,回答问题:材料一工业革命的主角——蒸汽机,是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产,主要依靠以人力和经
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
关于B一树,下列说法中不正确的是()。
随机试题
布雷克床垫公司采用员工轮班制度。每天(24小时)三班,每周七天。轮班安排如下:旱班:6:00—14:00下午班:14:00—22:00晚班:22:00—6:00这样的轮班制度产生了复杂的支付制度。标准时薪是:早班5美
治疗虚劳肺阴虚证,应首选的方剂是
男性,61岁,心绞痛病史3年,近日发作较频繁,药物治疗未能缓解,心肌酶不高。临床诊断为不稳定型心绞痛,急做冠状动脉造影,发现左冠状动脉主干及其分叉处阻塞>90%。紧急处置中,不应包括
甲国发生内战,乙国拟派民航包机将其侨民接回,飞机需要飞越丙国领空。根据国际法相关规则,下列哪些选项是正确的?()
投资规划中,进行资产配置的目标是()。
某城市附近的湖泊,由于城市污水的排入,湖中大量藻类繁殖耗去水中溶解氧进而造成鱼类死亡,该市拟建的城市污水处理厂除了要达到一般二级处理的目标外,还需要把下述()污染物作为污水厂的处理目标。
关于抄送机关的行文规则,不正确的是()。
监护人擅自处分被监护人财产的行为属于()行为。
[2011年]设随机变量X与Y的概率分布分别为且P(X2=Y2)=1.求二维随机变量(X,y)的概率分布;
TipsforThoseWhoTravelAloneA)Whenitcomestotraveling,sometimestakingajourneyalonecanbegreat.Travelingalone
最新回复
(
0
)