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

admin2019-08-15 101

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

计算机408

学硕统考专业

相关试题推荐

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns，命中率为p1；若Cache未命中，CPU需直接访问主存，访问时间为t2ns，主存命中率为p2；若所需数据字不在主存中，则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
图的D搜索类似于BFS，不同之处在于使用栈代替BFS中的队列，入／出队列的操作作为入／出栈的操作，即当一个顶点的所有邻接结点被搜索后，下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构，写一个D搜索算法；(2)用D搜索方法
下列几种排序方法中，要求内存量最大的是()。
给定集合S={0，1，2，3，4)，以及优先关系R={0＜1，1＜4，1＜2，2＜3，2＜4，4＜0)。(1)R是偏序关系吗?(2)证明你的结论。
设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数是()。
对于下图G，按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示；(2)假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
已知加权有向图G如下，回答下列问题：(1)画出该有向图G的邻接矩阵；(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。
某主机的MAC地址为00．15．C5．C1．5E．28，IP地址为10．2．128．100(私有地址)。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。Pl每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中：P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

随机试题

背景某酒店工程，建筑面积28700m2，地下1层，地上15层，现浇钢筋混凝土框架结构。建设单位依法进行招标，投标报价执行《建设工程工程量清单计价规范》GB50500—2013。共有甲、乙、丙等8家单位参加了工程投标。经过公开开标、评标，最后确定甲施工单位
A、Shehastofaceacriminalcharge.B、Shewasfoundlyingmotionlessinthesnow.C、Shesearchedforherdaughterinfreezingc
下列哪项不是血瘀证的表现
男孩，生后3天，新生儿听力初筛未通过，进行复筛的时间是在婴儿
《合同法》规定，有下列()情形的，当事人有权请求人民法院撤销其合同。
关于价格水平、总供给和总需求之间的关系，下列说法中错误的是（　　　）。
无论对埃克森还是排名有所下降的沃尔玛而言，2008年无疑都是一个好年景。但对排行榜上的绝大多数公司而言，2008年不仅不幸运，而且能是历史上最糟糕的一年。在2008年中，500家企业的总收入仅为989亿美元，比2007年的6450亿跳水85％，这是财富50
Shethoughtyoucouldtellawell-manneredpersononthewaytheyoccupiedthespacearoundthem.
Indiaistofrugality(节俭)asBethlehemistoJesus.Asrichcountriesenteraneweraof【C1】______,thebestpracticesofthegur
Inmanycountries,suchasFrance,Greece,andJapan,itisoftenmore【B1】______forstudentstopassthecollegeentranceexams

最新回复(0)

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

计算机408

学硕统考专业

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

下列几种排序方法中，要求内存量最大的是()。

给定集合S={0，1，2，3，4)，以及优先关系R={0＜1，1＜4，1＜2，2＜3，2＜4，4＜0)。(1)R是偏序关系吗?(2)证明你的结论。

设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数是()。

已知加权有向图G如下，回答下列问题：(1)画出该有向图G的邻接矩阵；(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。

某主机的MAC地址为00．15．C5．C1．5E．28，IP地址为10．2．128．100(私有地址)。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。

三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。Pl每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中：P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

A、Shehastofaceacriminalcharge.B、Shewasfoundlyingmotionlessinthesnow.C、Shesearchedforherdaughterinfreezingc

下列哪项不是血瘀证的表现

男孩，生后3天，新生儿听力初筛未通过，进行复筛的时间是在婴儿

《合同法》规定，有下列()情形的，当事人有权请求人民法院撤销其合同。

关于价格水平、总供给和总需求之间的关系，下列说法中错误的是（ ）。

Shethoughtyoucouldtellawell-manneredpersononthewaytheyoccupiedthespacearoundthem.

Indiaistofrugality(节俭)asBethlehemistoJesus.Asrichcountriesenteraneweraof【C1】______,thebestpracticesofthegur

Inmanycountries,suchasFrance,Greece,andJapan,itisoftenmore【B1】______forstudentstopassthecollegeentranceexams

关于价格水平、总供给和总需求之间的关系，下列说法中错误的是（　　　）。