首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2017-01-04
95
问题
假设有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/tQRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列改革内容不是在《天朝天亩制度》中提出的一项是()
简述两德统一的过程。(南京大学1999年世界近现代史真题)
论述近代法国专制制度形成的过程及其影响
二月革命后,俄国为什么会出现两个政权并存的局面?
下列关于清朝军机处的叙述,不正确的是()。
关于《荷马史诗》的叙述不正确的是()。
欧洲协调的第一次会议是指()。
美国的垄断组织主要采取的形式是()。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
在一个双链表中,在*p结点之前插入*q结点的操作是()。
随机试题
因痰而引起的病变有
房地产的需求弹性主要有()。
混凝土预制桩尖强度等级不应低于()。
属于静态投资的费用有()。
下列()只要不超过中国人民银行同期限档次存款利率上限,计结息由各银行自己把握。
一、注意事项1.申论考试是对应考者阅读能力、综合分析能力、提出和解决问题能力、文字表达能力的测试。2.参考时限:阅读资料40分钟,参考作答110分钟。3.仔细阅读给定资料,按照后面提出的“作答要求”作答。二、给定资料1.
根据下面提供的信息完成问题。2011年上半年,上海规模以上社会服务业单位共实现总产出4982.94亿元,比上年同期增长16.1%,占社会服务业总产出的80.8%。其中,规模以上企业实现总产出3982.11亿元,增长16%,占社会服务业企业总产出的
某校规定,对于学校的任一实验室,除非有教师在国际期刊上发表论文,否则没资格申报国家重点实验室。该校甲实验室有教师在国际期刊上发表论文。该校乙实验室有资格申报国家重点实验室。若上述陈述为真,则以下哪项也一定为真?
以下对企业文化与战略的关系表述错误的是()。
HowWorkWillChangeWhenMostofUsLiveto100A)TodayintheUnitedStatesthereare72,000centenarians(百岁老人).Worl
最新回复
(
0
)