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

admin2019-08-15 85

问题假设有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://jikaoti.com/ti/vYGjFFFM

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

1956年11月，中共八届二中全会决定开展的全党整风运动要反对的错误倾向是()。
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：甲骨文的发现带有一些偶然性，()最先发现了甲骨文，这也成为了甲骨学史的开端
下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界
已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所
下面关于图的存储的叙述中，正确的是()。
某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下：假定int类型数据用32位补码表示，程序
现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；
设有一个双向链表h，每个结点中除有prior，data和next三个域外，还有一个访问频度域freq，在链表被起用之前，每个结点中的freq域都被初始化为零。每当进行LocateNode(h，x)运算时，令元素值为x的结点中freq域中的值加一，并调整表中
某机字长32位，采用定长操作码，单字长指令，共有机器指令100条，CPU内部有通用寄存器32个，可作变址寄存器用，存储器按字节编址，指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。写出4种寻址方式下，有效地址EA的表达式。
现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2，…，en)；i=1：while(所剩边数＞=顶点数){从图中删去ei；若图不再连通，则恢复ei；i=

随机试题

知人の奥さん：すみません。そちらにうちの主人、________。私：ええ、いらっしゃっていますよ。
胶片未经曝光而显影加工处理后产生的密度称
根据《安全生产管理规定》，项目法人应当将水利工程中的拆除工程和爆破工程发包给具有相应水利水电工程施工资质等级的施工单位。项目法人应当在拆除工程或者爆破工程施工()日前，将下列资料报送水行政主管部门、流域管理机构或者其委托的安全生产监督机构备案
1996年颁布实施的()对老年人的赡养与扶养、社会保障、参与社会发展三大方面的权益及法律责任等做出了明确的法律规定。
绩效考评的()效标的侧重点是考量员工的个人特质。
邓小平历来十分重视农业问题。他强调指出：“农业搞不好，工业就没有希望，吃、穿、用的问题也解决不了。”他告诫我们：“90年代经济如果出问题，很可能出在农业上；如果农业出了问题，多少年缓不过来，整个经济和社会发展的全局就要受到严重影响。”这些话表明农业(
一、注意事项1．申论考试是对考生阅读理解能力、贯彻执行能力、解决问题能力和文字表达能力的测试。2．作答参考时限：阅读材料40分钟，作答110分钟。3．仔细阅读给定的资料，按照后面提出的“作答要求”依次作答。二、给定资料2
简述一般侵权责任的构成要件。
Whenwewantto【C1】______otherpeoplewhatwethink,wecandoitnotonlywiththehelpofwords,butalsoinmany【C2】______way
Whenitcomestoeatingsmartforyourheart,stopthinkingaboutshort-termfixesandsimplifyyourlifewithastraightforward

最新回复(0)

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

计算机408

学硕统考专业

1956年11月，中共八届二中全会决定开展的全党整风运动要反对的错误倾向是()。

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

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

下面关于图的存储的叙述中，正确的是()。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2，…，en)；i=1：while(所剩边数＞=顶点数){从图中删去ei；若图不再连通，则恢复ei；i=

知人の奥さん：すみません。そちらにうちの主人、________。私：ええ、いらっしゃっていますよ。

胶片未经曝光而显影加工处理后产生的密度称

1996年颁布实施的()对老年人的赡养与扶养、社会保障、参与社会发展三大方面的权益及法律责任等做出了明确的法律规定。

绩效考评的()效标的侧重点是考量员工的个人特质。

简述一般侵权责任的构成要件。

Whenwewantto【C1】______otherpeoplewhatwethink,wecandoitnotonlywiththehelpofwords,butalsoinmany【C2】______way

Whenitcomestoeatingsmartforyourheart,stopthinkingaboutshort-termfixesandsimplifyyourlifewithastraightforward

Whenwewantto【C1】otherpeoplewhatwethink,wecandoitnotonlywiththehelpofwords,butalsoinmany【C2】way