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

admin2019-01-30 89

问题假设有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

学硕统考专业

相关试题推荐

中华人民共和国恢复在联合国合法席位的时间是()。
阅读以下史料，并回答问题：“古之有国家迫于危亡者，不过守与奔而已。今以守无人，以奔则无地，所以諰諰然惟冀阁下之见哀而赦已，前者连奉书，愿削去旧号，是天地之间，皆大金之国，而尊无二上，亦何劳师远涉而后为快哉!”(宋高宗致信金兵元帅)
枢密院
元曲是元代文学的重要成就，涌现出一批优秀作品，下列作者与作品对应错误的是()。
明成祖时期大力推崇理学，以国家力量编写了几部理学的大部头著作，下面不属于其中的是()。
试述西欧城市兴起的原因、方式及其影响。
下列关于《凡尔赛和约》的说法，全部错误的是()。①《凡尔赛和约》中不许德国设防区是莱茵河西岸50公里以内区域②《凡尔赛和约》中，战胜国处置德国的全部海外殖民地的方式是“托管制”③和约有关德国疆界问题，把原属波兰的领上基本上归还波兰④
下列说法中，全部符合历史事实的是()。①阿拉伯阿拔斯王朝的首都是麦地那②穆罕默德死后，他的继承人改称为哈里发，第三任哈里发奥斯曼时期，部分下层莫斯林组建了军事民主派，称为哈瓦立及派③阿拉伯人灭亡了具有1200年历史的波斯帝国的战役是雅穆克
把中国第一次工人运动的高潮推向顶点的是（）。
大部分文件系统以硬盘作为文件存储器。某一个文件系统中，其磁盘物理块的大小为512B，有一个文件，包含了590个逻辑记录，每个记录占255B；其中，为检索方便，采用成组法存储，在每个物理块上只存放2个记录。，文件A在该文件目录中的位置如下图所示。

随机试题

________在宋初自觉地以恢复韩、柳古文的传统为己任，反对五代浮艳文风，标举文统和道统，主张文道合一，有鼓吹复古倡导质朴文风的筚路蓝缕之功。
腹式呼吸增强见于
基底核是位于大脑半球基底部的白质。
通过干扰核酸合成发挥作用的抗真菌药是
采购方式中，()通常是买方竞争的采购方式。
会计分录只能是一借一贷或一贷一借，不允许一借多贷或多借一贷。()
下列选项中，不属于宪法调整的社会关系是()。(2010年单选31)
Johnremovedhisovercoat.
Tounderstandwhysomeonebecomesanoptimistorapessimist,ithelpstounderstandwhatdistinguishesthem.Sayyoucrashyour
Thecoupletoldthedecoratorthattheywantedtheirbedroomgailypainted.Theunderlinedpartmeans

最新回复(0)

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

计算机408

学硕统考专业

中华人民共和国恢复在联合国合法席位的时间是()。

枢密院

元曲是元代文学的重要成就，涌现出一批优秀作品，下列作者与作品对应错误的是()。

明成祖时期大力推崇理学，以国家力量编写了几部理学的大部头著作，下面不属于其中的是()。

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

把中国第一次工人运动的高潮推向顶点的是（）。

________在宋初自觉地以恢复韩、柳古文的传统为己任，反对五代浮艳文风，标举文统和道统，主张文道合一，有鼓吹复古倡导质朴文风的筚路蓝缕之功。

腹式呼吸增强见于

基底核是位于大脑半球基底部的白质。

通过干扰核酸合成发挥作用的抗真菌药是

采购方式中，()通常是买方竞争的采购方式。

会计分录只能是一借一贷或一贷一借，不允许一借多贷或多借一贷。()

下列选项中，不属于宪法调整的社会关系是()。(2010年单选31)

Johnremovedhisovercoat.

Tounderstandwhysomeonebecomesanoptimistorapessimist,ithelpstounderstandwhatdistinguishesthem.Sayyoucrashyour

Thecoupletoldthedecoratorthattheywantedtheirbedroomgailypainted.Theunderlinedpartmeans