首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2017-01-04
99
问题
假设有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
学硕统考专业
相关试题推荐
论述斯巴达的阶级结构、政治制度和社会风尚
简述从十月革命胜利到第二次世界大战爆发前夕苏俄(苏联)与主要资本主义国家关系演变的基本情况。
1962年初,中共召开了中央工作会议,即“七千人大会”,其议题主要是()。
原始群是以()为纽带而组成的社会组织形式。
材料1942年5月,毛泽东指出,对于革命的文艺家,暴露的对象,只能是侵略者、剥削者、压迫者及其在人民中所遗留的恶劣影响,而不能是人民大众。人民大众也是有缺点的,这些缺点应当用人民内部的批评和自我批评来克服。1955年5月,毛泽东在《驳“舆论一律”
1854年,英国外交大臣致函英国驻华公使说:“为了适应外商对农业产品已增加了的需要,新的贸易市场尚待开辟。”1856年,法国外长则指令法国驻华代办强调“商业关系的推广”,并强调“这是一个关系到至高无上权益的问题”。这说明()。
在一个HDLC帧的数据中,如果出现了000111111011这样的流,请问发送到信道上它将会变成()。
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
某模型机的通路结构如下图所示,用寄存器传送语句(如PC→MAR),拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0),Y(R1),源和目的操作数地址均采用变址寻址,第1个参数X为源操作数的形式地址,第2个参数为目的操作数的形
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(e1,e2.…,em);i=l;while(所剩边数>=顶点数){从图中删去ei;若图不再连通,则恢复ei;i=i+l;
随机试题
下列叙述中正确的是()。
卡他性炎是指
正常人血浆pH为
男性,70岁。因听力逐渐减退一年多,来院就诊,经过医生检查发现其骨传导功能正常,空气传导功能障碍。进一步检查,下列哪一项可以不考虑
在以下关于国内生产总值的描述中,哪些描述是正确的?()
利益产品又称()。
美国的学制属于典型的()。
通报用于反映新情况、新问题,行文强调及时快捷。()
首次规定“八议”制度的封建成文法典是()。
YouaregoingtoreadatextaboutstudyingintheUnitedStates,followedbyalistofexamples.Choosethebestexamplefromt
最新回复
(
0
)