首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2017-01-04
100
问题
假设有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
学硕统考专业
相关试题推荐
简述20世纪20年代末国共两党之外的第三势力。
拜占庭帝国的第二个黄金时代是在()。
改革开放以后,我国农村产业结构巨大的转变表现在()。
下面关于新经济政策的说法不正确的一项是()。
16世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
列宁在()报告中论证了在俄国实现和平过渡的可能性和必要性。
1940年毛泽东的《新民主主义论》:“而所谓民主主义,现在已不是旧范畴的民主主义,已不是日民主主义,而是新范畴的民主主义,而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
假设二叉树采用二叉链表存储结构存储,试设计一个算法,求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。
三个进程P1、P2、P3互斥使用一个包含N(N>0)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统
随机试题
FTP指的是______。
AlanChangwasahandsomeyoungmanwithgoodmanners.Onemorninghewaswalkingalongastreetonhiswaytoanappointment.H
泌尿系结石的主要成分有哪些?
女性,63岁。突然出现右半身活动不利,舌强语謇,兼见面红目赤,眩晕头痛,烦躁,舌红,苔黄,脉弦而有力。针灸治疗除主穴外,应加用
患者,男性,35岁。于大量饮酒和饱餐后突然出现中上腹持续性绞痛,伴有频繁呕吐,吐出食物和胆汁,呕吐后腹痛不减轻。查体:上腹压痛,反跳痛,肠鸣音减弱。测血清淀粉酶1200U/L,诊断为急性胰腺炎。该措施的目的是
下列反垄断政策措施属于政府干预市场结构措施的是()。
短期筹资一般是在一年以内或()到期的筹资。
Ofallthefollowingpairsofwords,____isaminimalpair.
Arsenic,anaturallyoccurringpoisonandcarcinogenfoundingroundwater,isstronglylinkedtoadult-onsetdiabetes,U.S.re
Sevenyearsago,whenIwasvisitingGermany,Imetwithanofficialwhoexplainedtomethatthecountryhadaperfectsolution
最新回复
(
0
)