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

admin2009-02-15 45

问题若采用邻接矩阵结构存储具有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)。

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

软考中级

某网络结构如下图所示。除了PCI外其他PC都能访问服务器Server1，造成PC1不能正常访问Server1的原因可能是(39)。

Traditional　Internet　access　methods　like　dial-up　were　so　slow　that　host　computers　were　connected　to　the　dial-up(71)at　the　custom

若每一条指令都可以分解为取指、分析和执行三步。已知取指时间t取指＝4△t，分析时间t分析=3△t，执行时间t执行=5△t。如果按串行方式执行完100条指令需要(2)△t。如果按照流水方式执行，执行完100条指令需要(3)△t。

Multipurpose　Internet　MaiI　Extension　(MIME)　is　a(71)document　messaging　standard　in　the　Internet　enviroment,　with　MIME,　users　can

Inlow-speednetwork,itisusuallyadequatetowaitforcongestiontooccurandthenreacttoitbytellingthesourceofpacke

Withhundredsofmillionsofelectronictransactionstakingplacedaily,businessesandorganizationshaveastrongincentiveto

The　purpose　of　the　requirements　definition　phase　is　to　produce　a　clear,　complete,　consistent,　and　testable(6)of　the　technical　re

Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(66)ofthetechnical

Theappealofadvertisingtobuyingmotivescanbothnegativeandpositiveeffects.Consumersmaybeconvincedtobuyaproduct

A．收缩压升高B．舒张压升高C．收缩压和舒张压都升高，但舒张压升高更明显D．收缩压升高和舒张压下降每搏输出量和心率不变而外周阻力增大时，动脉血压的变化主要是

有关颈椎描述正确的是

患儿1岁，发热两天，体温39℃，鼻塞，稍有咳嗽，微汗，口干而渴，咽部红肿，舌红，苔薄黄，指纹浮紫至风关。治疗选方为

急性白血病并发颅内出血时，错误的护理措施是()。

下图所示均为我国著名林木景观示意图。读图完成下列问题。图中各地林木主要特征及成因的叙述，正确的是()。

为什么说“法治应当优于一人之治”(亚里士多德语)?

2

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

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

软考中级

某网络结构如下图所示。除了PCI外其他PC都能访问服务器Server1，造成PC1不能正常访问Server1的原因可能是(39)。

Traditional Internet access methods like dial-up were so slow that host computers were connected to the dial-up(71)at the custom

若每一条指令都可以分解为取指、分析和执行三步。已知取指时间t取指＝4△t，分析时间t分析=3△t，执行时间t执行=5△t。如果按串行方式执行完100条指令需要(2)△t。如果按照流水方式执行，执行完100条指令需要(3)△t。

Multipurpose Internet MaiI Extension (MIME) is a(71)document messaging standard in the Internet enviroment, with MIME, users can

Inlow-speednetwork,itisusuallyadequatetowaitforcongestiontooccurandthenreacttoitbytellingthesourceofpacke

Withhundredsofmillionsofelectronictransactionstakingplacedaily,businessesandorganizationshaveastrongincentiveto

The purpose of the requirements definition phase is to produce a clear, complete, consistent, and testable(6)of the technical re

Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(66)ofthetechnical

Theappealofadvertisingtobuyingmotivescanbothnegativeandpositiveeffects.Consumersmaybeconvincedtobuyaproduct

A．收缩压升高B．舒张压升高C．收缩压和舒张压都升高，但舒张压升高更明显D．收缩压升高和舒张压下降每搏输出量和心率不变而外周阻力增大时，动脉血压的变化主要是

有关颈椎描述正确的是

患儿1岁，发热两天，体温39℃，鼻塞，稍有咳嗽，微汗，口干而渴，咽部红肿，舌红，苔薄黄，指纹浮紫至风关。治疗选方为

急性白血病并发颅内出血时，错误的护理措施是()。

下图所示均为我国著名林木景观示意图。读图完成下列问题。图中各地林木主要特征及成因的叙述，正确的是()。

为什么说“法治应当优于一人之治”(亚里士多德语)?

2

Traditional　Internet　access　methods　like　dial-up　were　so　slow　that　host　computers　were　connected　to　the　dial-up(71)at　the　custom

Multipurpose　Internet　MaiI　Extension　(MIME)　is　a(71)document　messaging　standard　in　the　Internet　enviroment,　with　MIME,　users　can

The　purpose　of　the　requirements　definition　phase　is　to　produce　a　clear,　complete,　consistent,　and　testable(6)of　the　technical　re