首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2019-08-15
93
问题
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
选项
A、0(n)
B、0(e)
C、0(n+e)
D、0(ne)
答案
C
解析
删除与某顶点v相关的所有边的过程如下:先删除下标为v的顶点表结点的单链表,出边数最多为n一1,对应时间复杂度为O(n),再扫描所有边表结点,删除所有的入边,对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。
转载请注明原文地址:https://kaotiyun.com/show/EOCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
“葡萄牙人在非洲海岸、印度和整个远东寻找的是黄金,黄金一词是驱使西班牙人横渡大西洋到美洲去的咒语;黄金是白人刚踏上一个新发现的海岸时所要的第一件东西。”欧洲人对黄金的贪婪追求从本质上反映了()
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一,为重新认识三代的历史与文化奠定了基础,开辟了坦途,可称之为中国文化史的里程碑。根据所学知识回答问题:下列有关“甲骨文”的表述,不确切的是()
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
设算术表达式由字符串b表示,其中可以包括三种括号:圆括号、方括号以及花括号,嵌套的顺序随意,如:“{[()]()}”。试编写算法,实现判定给定表达式中所含括号是否正确配对的出现。
若一个栈的输入序列为1,2,3…n,输出序列的第一个元素是i,则第j个输出元素是()。
以下关于图的说法正确的是()。.I在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O,则该图的拓扑序列必定存在Ⅲ在.AOE网中一定只有一条
已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。要求:写出图G的邻接矩阵A。
设有一个双向链表h,每个结点中除有prior,data和next三个域外,还有一个访问频度域freq,在链表被起用之前,每个结点中的freq域都被初始化为零。每当进行LocateNode(h,x)运算时,令元素值为x的结点中freq域中的值加一,并调整表中
若x=103,y=-25,则下列表达式采用8位定点补码运算实现时,会发生溢出的是_______。
随机试题
四分位数间距主要用于()
10个月患儿,已在当地医院诊断为佝偻病活动期,给予治疗,效果不好。为进一步判定诊断是否正确,不需要做下列哪些检查
儿童哮喘诊断标准不正确的是
龋病的形成与下列哪些因素有关A.变形链球菌是主要的致病菌B.血链球菌与唾液链球菌也与龋病有关C.根面龋与粘性放线菌有关D.牙菌斑中的细菌代谢蔗糖产生酸性产物E.以上全部都是
建筑安装工程造价指数一般采用()的形式来表示。
市政公用工程施工中,每一个单位(子单位)工程完成后,应进行()测量。
某地铁区间隧道采用盾构法施工,盾构直径6.5m,盾构区间长1328m,隧道平均覆土11.5m。项目部采取了以下职业健康安全管理措施:措施一、对参加盾构施工的机械工和辅助生产工人进行安全技术知识的教育;措施二、在隧道内安装了轴流式通风机和照明设施;措施
根据海关规定,进出口货物报关单的“贸易方式”栏填写未列名的贸易方式时,应填为“其他贸易”。在下列几种贸易方式中不可填写为“其他贸易”的有()。
Thereiswidespreadconsensusamongscholarsthatsecondlanguageacquisition(MB1SLA)emergedasadistinctfieldofresearchfr
He______awellmeantbutunsuccessfulcampaigntoeaseEastWesttensionscallingforarmsreductionandasummitofthenuclea
最新回复
(
0
)