首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2018-08-12
52
问题
假设有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
学硕统考专业
相关试题推荐
全国高校院系调整的具体时间是()。
1936年苏联宪法规定苏联的国体是()。
世界近代史上,世界经济发展经历了两次大的飞跃,即第一次工业革命和第二次工业革命。阅读下面两段材料,回答问题:材料一工业革命的主角——蒸汽机,是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产,主要依靠以人力和经
下列历史事件发生的先后顺序是()。①“铁幕”演说②马歇尔计划③北大西洋公约
下列哪一事件之后,明与蒙古之间出现了“自宣大至甘肃,不用兵者二十年”的情形?()
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
m阶B一树是一棵()。
随机试题
A、卡方检验B、Cmh检验C、t检验D、非参数检验E、Logistic多元回归分析在药物经济学研究中,对多分类的效果数据,可用
患者女性,65岁。因自觉食欲明显增加半年前来就诊。自觉“长胖很多”。经有关检查示:C﹣肽释放试验结果为空腹580pmol/L,1小时1120pmol/L,2小时1650pmol/L,3小时866pmol/L;糖化血红蛋白11%;24小时尿C肽为18.4μg
评价筛检收益的主要指标是
以下关于压差式液位计的叙述,正确的是()。
关于移动平均线,说法错误的是( )。
下列情形中,不可以申请法律援助的是()
心理咨询师在咨询中使用的提问方式不包括()。求助者的情感症状不包括()。
分半信度所考察的误差来源是()。
《唐律疏议.贼盗律》规定:“诸谋杀人者,徒三年;已伤者,绞;已杀者,斩;诸谋杀制使,若本属府主、刺史、县令及吏卒谋杀本部五品以上官长者,流二千里;诸谋杀期亲尊长、外祖父母、夫、夫之祖父母、父母者,皆斩;诸部曲、奴婢谋杀主者,皆斩。”《唐律疏议.斗
中央处理器(CPU)可以直接访问的计算机部件是______。
最新回复
(
0
)