首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2019-01-30
44
问题
假设有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/5ZRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
乾隆时期,明确规定了驻藏大臣的地位与达赖班禅同等,并实行“金瓶掣签”制度的文件是()。
春秋战国时期,小农经济出现的根本原因是()。
在周初分封中,分封同姓诸侯国、异姓诸侯国,也分封圣王之后,下面属于圣王之后的封国为()。
西汉初年,反驳刘邦“马上治天下”的说法,并向汉帝国治国献策的是()。
中华人民共和国恢复在联合国合法席位的时间是()。
1543年发表解剖学专著《人体结构论》的是()。
设磁盘的扇区大小为4KB,磁盘转速为15000r/min,磁盘平均寻道时间为4ms,最大数据传输速率为40MB/s,磁盘控制器开销时问为1ms,计算读写一个扇区所需平均时间(不考虑I/O请求队列中的等待时间)。
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。(1)分别画出寻址方式由操作码指出和寻址方式由专用字
在下列查找的方法中,平均查找长度与结点个数n无关的查找方法是()。
随机试题
性格的个别差异表现在()。
设二次型f(x1,x2,x3)=2x12-x22+ax32+2x1x2-8x1x3+2x2x3在正交变换x=Qy下的标准形为λ1y12+λ2y22,求a的值及一个正交矩阵Q.
目前我国消费税实行从价定率、从量定额的方法计算应纳税额。对于实行从价定率征收消费税的进口货物,其消费税组成计税价格为()。
组合还款法使得借款人可以在贷款期限内将本金分为几个部分,各部分采用不同还款方式。()
叶公好龙:言不由衷()
“蓝蓝的天空白云飘,白云底下马儿跑……”这段歌词中赞美的蓝天,其蓝色的形成是由于()。
某珠宝商店失窃,甲、乙、丙、丁四人涉嫌被拘审。四人的口供如下:甲:案犯是丙。乙:丁是罪犯。丙:如果我作案,那么丁是主犯。丁:作案的不是我。四个口供中只有一个是假的。如果以上断定为真,则以下哪项是真的?()
求极限:.
"Reworked"asusedinParagraph1means"______".Whichofthefollowingstatementsistrue?
TheCuttingEdgeEconomistsandgovernmentsagreethesedaysonthecrucialimportanceofforeigndirectinvest-ment(FDI).
最新回复
(
0
)