假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )。

admin2019-01-30 35

问题假设有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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

概述罗马共和国早期平民反贵族斗争的原因、过程和意义。
论述罗马共和国早期对外征服的过程和历史意义。
隋统一全国时，与隋军平定岭南地区有关的人员是()。①洗夫人②慕容三藏③孙夫人④裴矩
试述西欧城市兴起的原因、方式及其影响。
下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界
已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列
某机字长32位，采用定长操作码，单字长指令，共有机器指令100条，CPU内部有通用寄存器32个，可作变址寄存器用，存储器按字节编址，指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。(1)分别画出寻址方式由操作码指出和寻址方式由专用字
给定单链表的结点结构typedefstructnode*link；structnode{intitem，linknext；)；将两个升序单链表归并为一个升序单链表。
下图是三个计算机局域网A，B和C，分别包含10台，8台和5台计算机，通过路由器互联，并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61．60．21．80的互联网地址)。LANA和LANB公用一个C类IP地址
设文件索引节点中有7个地址项，其中4个地址项是直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4B。若磁盘索引块和磁盘数据块大小均为256B，则可表示的单个文件最大长度是____。

随机试题

Word2003默认的中文字体是宋体，默认的字号是______。
Intheearly1960sWiltChamberlainwasoneofonlythreeplayersintheNationalBasketballAssociation(NBA)listedatoverseve
A．急性B淋巴细胞白血病B．急性T淋巴细胞白血病C．急性粒细胞白血病D．急性红白血病E．急性巨核细胞白血病
潮气量增加(其他因素不变)时，下列项目中将增加的是
妊娠早期血中高浓度的雌激素和孕激素来自
下列氧化物中既可和稀H2SO4溶液作用，又可和稀NaOH溶液作用的是()。
“经营单位”栏应填()。“商品名称、规格型号”栏应填()。
将①一④句填在横线上，顺序最恰当的一项是()。爱因斯坦非常重视想象力，他说：“_________。严格地说，想象力是科学研究中的实在因素。”①想象力能概括世界上的一切②因为知识是有限的③想象力比知识更重要④并且是知识进化的源泉
如果不考虑学生身心发展的特点，就会导致实际教育活动脱离学生的发展水平，这说明人是教育目的选择、确立的基本依据。()(2016．四川)
阅读下列说明和图，回答以下问题，将解答填入答题纸的对应栏内。【说明】某电子商务系统采用以数据库为中心的集成方式改进购物车的功能，详细需求如下：1．加入购物车。顾客浏览商品，点击加入购物车，根据商品标识从商品表中读取商品信息，并

最新回复(0)

假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )。

计算机408

学硕统考专业

概述罗马共和国早期平民反贵族斗争的原因、过程和意义。

论述罗马共和国早期对外征服的过程和历史意义。

隋统一全国时，与隋军平定岭南地区有关的人员是()。①洗夫人②慕容三藏③孙夫人④裴矩

试述西欧城市兴起的原因、方式及其影响。

下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

给定单链表的结点结构typedefstructnode*link；structnode{intitem，linknext；)；将两个升序单链表归并为一个升序单链表。

Word2003默认的中文字体是宋体，默认的字号是______。

Intheearly1960sWiltChamberlainwasoneofonlythreeplayersintheNationalBasketballAssociation(NBA)listedatoverseve

A．急性B淋巴细胞白血病B．急性T淋巴细胞白血病C．急性粒细胞白血病D．急性红白血病E．急性巨核细胞白血病

潮气量增加(其他因素不变)时，下列项目中将增加的是

妊娠早期血中高浓度的雌激素和孕激素来自

下列氧化物中既可和稀H2SO4溶液作用，又可和稀NaOH溶液作用的是()。

“经营单位”栏应填()。“商品名称、规格型号”栏应填()。

如果不考虑学生身心发展的特点，就会导致实际教育活动脱离学生的发展水平，这说明人是教育目的选择、确立的基本依据。()(2016．四川)