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

admin2009-02-15 23

问题若采用邻接矩阵结构存储具有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://jikaoti.com/ti/0xa7FFFM

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

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

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

操作数所处的位置，可以决定指令的寻址方式。操作数包含在指令中，寻址方式为(4)；操作数在寄存器中，寻址方式为(5)；操作数的地址在寄存器中，寻址方式为(6)。

通常路由器不进行转发的网络地址是(46)。

常见的软件开发模型有瀑布模型、演化模型、螺旋模型、喷泉模型等。其中(5)模型适用于需求明确或很少变更的项目，(6)模型主要用来描述面向对象的软件开发过程。

关于Windows操作系统中DHCP服务器的租约，下列说法中错误的是(38)。

活动目录(Active　Directory)是由组织单元、域、(36)和域森林构成的层次结构，安装活动目录要求分区的文件系统为(37)。

在配置IIS时，如果想禁止某些IP地址访问Web服务器，应在“默认Web站点”的属性对话框中(34)选项卡中进行配置。IIS的发布目录(35)。

Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(66)ofthetechnical

某承包人为了赶工期，曾在雨中铺筑沥青混凝土，对此造成的质量缺陷，监理工程师应()。

下列句子表述得体的一项是（）

在肠外营养支持疗法中，不属于外周静脉途径的禁忌证的是

男性，30岁，急性阑尾炎，医生检查时病人取左侧卧位后，使其右下肢向后过伸，引起右下腹疼痛此项检查称为

慢性胃炎的饮食护理中哪项应除外

列各项中，符合房产税纳税义务发生时间规定的有()。(2008年)

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

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

软考中级

操作数所处的位置，可以决定指令的寻址方式。操作数包含在指令中，寻址方式为(4)；操作数在寄存器中，寻址方式为(5)；操作数的地址在寄存器中，寻址方式为(6)。

通常路由器不进行转发的网络地址是(46)。

常见的软件开发模型有瀑布模型、演化模型、螺旋模型、喷泉模型等。其中(5)模型适用于需求明确或很少变更的项目，(6)模型主要用来描述面向对象的软件开发过程。

关于Windows操作系统中DHCP服务器的租约，下列说法中错误的是(38)。

活动目录(Active Directory)是由组织单元、域、(36)和域森林构成的层次结构，安装活动目录要求分区的文件系统为(37)。

在配置IIS时，如果想禁止某些IP地址访问Web服务器，应在“默认Web站点”的属性对话框中(34)选项卡中进行配置。IIS的发布目录(35)。

Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(66)ofthetechnical

某承包人为了赶工期，曾在雨中铺筑沥青混凝土，对此造成的质量缺陷，监理工程师应()。

下列句子表述得体的一项是（）

在肠外营养支持疗法中，不属于外周静脉途径的禁忌证的是

男性，30岁，急性阑尾炎，医生检查时病人取左侧卧位后，使其右下肢向后过伸，引起右下腹疼痛此项检查称为

慢性胃炎的饮食护理中哪项应除外

列各项中，符合房产税纳税义务发生时间规定的有()。(2008年)

活动目录(Active　Directory)是由组织单元、域、(36)和域森林构成的层次结构，安装活动目录要求分区的文件系统为(37)。