假设—个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi(下标)相关的所有弧的时间复杂度是(55)。

admin2013-05-11 95

问题假设—个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi(下标)相关的所有弧的时间复杂度是(55)。

选项 A、O(n)
B、O(e)
C、O(n+e)
D、O(n*e)

答案C

解析与某个顶点、相关的所有弧是指所有以vi为尾和所有以　vi为头的弧。n个顶点的有向图的邻接表含有n个出边表，每个顶点有且只有一个出边表，第i个出边表中的结点表示以顶点v1为尾的弧。每个出边表设置一个头结点，所有头结点构成一个向量，该向量称为顶点表。因为弧是有方向的，所以每一条弧只用一个边表结点来表示，e条弧则有p个结点，因此有，n个顶点和e条弧的有向图的邻接表含有　n个顶点表结点和vi个边表结点。要删除以顶点vi为尾的弧只要删除第i个出边表中的结点就行了，但要删除以顶点vi为头的弧则需在其他出边表中查找顶点信息域为i的结点。为此，需对n个顶点表结点和e个边表结点进行通遍扫描，故其时间复杂度为O(n+e)。

转载请注明原文地址:https://kaotiyun.com/show/knRZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

假设—个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi(下标)相关的所有弧的时间复杂度是(55)。

软件设计师上午基础知识考试

软考中级

在Kerberos认证系统中，用户首先向(1)申请初始票据，然后从(2)获得会话密钥。(2011年上半年试题)(1)

关于选用源路径选择桥的局域网，下列说法__________是正确的。

OSPF协议适用于4种网络。下面的选项中，属于广播多址网络(BroadcastMulti—Access)的是(1)，属于非广播多址网络(NoneBroadcastMulti-Access)的是(2)。(2009年上半年试题)(1)

为了限制路由信息传播的范围，OSPF协议把网络划分成4种区域(Area)，其中(1)的作用是连接各个区域的传输网络，(2)不接受本地自治系统之外的路由信息。(2009年下半年试题)(2)

在一个由多台路由器构成的网络中，一条途经多个路由器的线路断开了，判断是哪一个路由器发生故障的命令是(1)。在发现跨路由器ping不通的情况下，可用配置管理工具收集(2)信息进行分析。(1)

下图是家庭用户安装ADSL宽带网络时的拓扑结构，图中左下角的×是(1)设备，为了建立虚拟拨号线路，在用户终端上应安装(2)协议。(2012年下半年试题)(2)

Soon,　more　of　the　information　we　receive　via　the　Internet　could　come(71)in　digital　wrappers.　　　Wrappers　are　made　up(72)software

Soon,　more　of　the　information　we　receive　via　the　Internet　could　come(71)in　digital　wrappers.　　　Wrappers　are　made　up(72)software

Developing　reliable　software　on　time　and　within(66)represents　a　difficult　endeavor　for　many　organizations.　　　Usually　business　s

胰腺疾病患者每日脂肪摄入量应少于【】

肺和胸膜触诊下列哪项不正确

关于小结节性肝硬化的特征，叙述错误的是

A．七福饮B．还少丹C．转呆丹D．知柏地黄丸E．河车大造丸治疗痴呆脾肾两虚证，应首选

思想品德课的导向性功能主要包括()。①目标导向②价值导向③行为导向④实践导向

某社区居委会有18个居民小组，2000户，年满18周岁的居民有6000人。在()情况下，应当召集居民会议。

心里装着全体人民、唯独没有他自己。焦裕禄同志之所以被誉为县委书记的好榜样、共产党员的光辉典范，之所以深受人民群众爱戴，根本原因在于他视人民群众为衣食父母、诚心诚意当人民公仆。以上材料表明()。

有关多表查询结果，以下说法正确的是______。

______isthecapitalofScotlandsincethe15thcentury.

A、Anhonestpersonnevertellslies.B、Oneshouldn’tbreakapromiseeasily.C、Aninvitationisasignoffriendship.D、Somethin

假设—个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi(下标)相关的所有弧的时间复杂度是(55)。

软件设计师上午基础知识考试

软考中级

在Kerberos认证系统中，用户首先向(1)申请初始票据，然后从(2)获得会话密钥。(2011年上半年试题)(1)

关于选用源路径选择桥的局域网，下列说法__________是正确的。

OSPF协议适用于4种网络。下面的选项中，属于广播多址网络(BroadcastMulti—Access)的是(1)，属于非广播多址网络(NoneBroadcastMulti-Access)的是(2)。(2009年上半年试题)(1)

为了限制路由信息传播的范围，OSPF协议把网络划分成4种区域(Area)，其中(1)的作用是连接各个区域的传输网络，(2)不接受本地自治系统之外的路由信息。(2009年下半年试题)(2)

在一个由多台路由器构成的网络中，一条途经多个路由器的线路断开了，判断是哪一个路由器发生故障的命令是(1)。在发现跨路由器ping不通的情况下，可用配置管理工具收集(2)信息进行分析。(1)

下图是家庭用户安装ADSL宽带网络时的拓扑结构，图中左下角的×是(1)设备，为了建立虚拟拨号线路，在用户终端上应安装(2)协议。(2012年下半年试题)(2)

Soon, more of the information we receive via the Internet could come(71)in digital wrappers. Wrappers are made up(72)software

Soon, more of the information we receive via the Internet could come(71)in digital wrappers. Wrappers are made up(72)software

Developing reliable software on time and within(66)represents a difficult endeavor for many organizations. Usually business s

胰腺疾病患者每日脂肪摄入量应少于【】

肺和胸膜触诊下列哪项不正确

关于小结节性肝硬化的特征，叙述错误的是

A．七福饮B．还少丹C．转呆丹D．知柏地黄丸E．河车大造丸治疗痴呆脾肾两虚证，应首选

思想品德课的导向性功能主要包括()。①目标导向②价值导向③行为导向④实践导向

某社区居委会有18个居民小组，2000户，年满18周岁的居民有6000人。在()情况下，应当召集居民会议。

心里装着全体人民、唯独没有他自己。焦裕禄同志之所以被誉为县委书记的好榜样、共产党员的光辉典范，之所以深受人民群众爱戴，根本原因在于他视人民群众为衣食父母、诚心诚意当人民公仆。以上材料表明()。

有关多表查询结果，以下说法正确的是______。

______isthecapitalofScotlandsincethe15thcentury.

A、Anhonestpersonnevertellslies.B、Oneshouldn’tbreakapromiseeasily.C、Aninvitationisasignoffriendship.D、Somethin

Soon,　more　of　the　information　we　receive　via　the　Internet　could　come(71)in　digital　wrappers.　　　Wrappers　are　made　up(72)software

Soon,　more　of　the　information　we　receive　via　the　Internet　could　come(71)in　digital　wrappers.　　　Wrappers　are　made　up(72)software

Developing　reliable　software　on　time　and　within(66)represents　a　difficult　endeavor　for　many　organizations.　　　Usually　business　s