若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为(47)。

admin2009-02-15 47

问题若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为(47)。

选项 A、O(n)
B、O(n²)
C、O(n²+1)
D、以上都不对

答案B

解析 n个顶点的图的邻接矩阵是一个n阶方阵，有n行n列。从顶点Vi出发，对图进行广度优先遍历，需对矩阵的第i行逐列检测非零元(若a[j]1，则说明顶点vj与vi之间有边存在，vi就是vi的邻接顶点)。根据广度优先遍历的思想，每一个顶点都要轮换着做出发顶点，即矩阵的每一行都将要被逐列检测。显然，算法中要用一个两重循环来组织逐行逐列的检测操作，所以，算法的时间复杂度是n的平方阶。

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

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

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

相关试题推荐

随机试题

最新回复(0)

若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为(47)。

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

软考中级

使用海明码进行前向纠错，如果冗余位为4位，那么信息位最多可以用至(26)位，假定码字为a6a5a4a3a2a1a0，并且有下面的监督关系式：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6

以太网中如果发生介质访问冲突，按照二进制指数后退算法决定下一次重发的时间，使用二进制指数后退算法的理由是(56)。

在Windows中运行(28)命令后得到如下图所示的结果，该信息表明主机的以太网网卡(29)，图中224.0.0.0是(30)。

SNMPv1是一个不安全的协议，管理站(Manager)与代理(Agent)之间通过(55)进行身份认证，由于认证信息没有加密，因此是不安全的。1998年公布的SNMPv3定义了基于用户的安全模型USM，其中的认证模型块结合(56)算法形成认证协议，产生了

设备间子系统的所有进线终端宜采用(45)来区别各类用途的配线区。

在OSI参考模型中，上层协议实体与下层协议实体之间的逻辑接口叫做服务访问点(SAP)。在Internet数据帧中，目的地址“0x000F781C6001”属于(10)的服务访问点。

OneofthedifficultiesinbuildinganSQL-likequerylangefortheWebistheabsenceofadatabaseschemaforthishuge,heter

Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(71)ofthetechnicalr

Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(71)ofthetechnicalr

就竞争来说,“世上无常胜将军”、“失败是成功之母”这两句话说明的道理是()。

A．丝氨酸B．精氨酸C．苯丙氨酸D．半胱氨酸E．谷氨酸可生成酪氨酸

A．我国最早的中医典籍B．总结了先秦两汉时代的医学成就C．总结了东晋以前的中医急症治疗成就D．我国第一部成药典E．我国现存最早的本草学著作《伤寒论》

患者，女性，25岁。因春游赏花，出现咳嗽、咳痰伴喘息，呼气性呼吸困难。查体：喘息貌，口唇发绀，在肺部可闻及广泛哮鸣音。医疗诊断为支气管哮喘。下面抗炎药物最有效的是

(　　)是产生期货投机的动力。

对残疾儿童的教育要依据()的特征进行。

近代粒子物理学研究表明，物质构成的最小单元是(　)。

社会对教育事业的需求程度最终取决于()。

在不同的剥削制度下，劳动者与生产资料的结合方式不同。在资本主义制度下，资本家与工人的关系是()

设a1=2，an+1=(n=1，2，…)。证明级数收敛。

若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为(47)。

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

软考中级

使用海明码进行前向纠错，如果冗余位为4位，那么信息位最多可以用至(26)位，假定码字为a6a5a4a3a2a1a0，并且有下面的监督关系式：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6

以太网中如果发生介质访问冲突，按照二进制指数后退算法决定下一次重发的时间，使用二进制指数后退算法的理由是(56)。

在Windows中运行(28)命令后得到如下图所示的结果，该信息表明主机的以太网网卡(29)，图中224.0.0.0是(30)。

SNMPv1是一个不安全的协议，管理站(Manager)与代理(Agent)之间通过(55)进行身份认证，由于认证信息没有加密，因此是不安全的。1998年公布的SNMPv3定义了基于用户的安全模型USM，其中的认证模型块结合(56)算法形成认证协议，产生了

设备间子系统的所有进线终端宜采用(45)来区别各类用途的配线区。

在OSI参考模型中，上层协议实体与下层协议实体之间的逻辑接口叫做服务访问点(SAP)。在Internet数据帧中，目的地址“0x000F781C6001”属于(10)的服务访问点。

OneofthedifficultiesinbuildinganSQL-likequerylangefortheWebistheabsenceofadatabaseschemaforthishuge,heter

Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(71)ofthetechnicalr

Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(71)ofthetechnicalr

就竞争来说,“世上无常胜将军”、“失败是成功之母”这两句话说明的道理是()。

A．丝氨酸B．精氨酸C．苯丙氨酸D．半胱氨酸E．谷氨酸可生成酪氨酸

A．我国最早的中医典籍B．总结了先秦两汉时代的医学成就C．总结了东晋以前的中医急症治疗成就D．我国第一部成药典E．我国现存最早的本草学著作《伤寒论》

患者，女性，25岁。因春游赏花，出现咳嗽、咳痰伴喘息，呼气性呼吸困难。查体：喘息貌，口唇发绀，在肺部可闻及广泛哮鸣音。医疗诊断为支气管哮喘。下面抗炎药物最有效的是

( )是产生期货投机的动力。

对残疾儿童的教育要依据()的特征进行。

近代粒子物理学研究表明，物质构成的最小单元是( )。

社会对教育事业的需求程度最终取决于()。

在不同的剥削制度下，劳动者与生产资料的结合方式不同。在资本主义制度下，资本家与工人的关系是()

设a1=2，an+1=(n=1，2，…)。证明级数收敛。

(　　)是产生期货投机的动力。

近代粒子物理学研究表明，物质构成的最小单元是(　)。