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

admin2009-02-15 39

问题若采用邻接矩阵结构存储具有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://www.kaotiyun.com/show/pTxZ777K

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

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

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

IETF定义的多协议标记交换(MPLS)是一种第三层交换技术，MPLS网络由(38)组成，负责为网络流添加/删除标记的是(39)。

当数据在两个VLAN之间传输时需要哪种设备?(59).

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

某Apache服务器的配置文件httpd.conf包含如下所示配置项。在(32)处选择合适的选项，使得用户可通过http：//www.test.cn访问到该Apache服务器；当用户访问http://111.25.4.30:80时，会访问到(33)虚拟主

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

使用CIDR技术把4个网络100.100.0.0/18、100.100.64.0/18、100.100.128.0/18和100.100.192.0/18汇聚成一个超网，得到的地址是(53)。

ISO/IEC9126软件质量模型中第一层定义了6个质量特性，并为各质量特性定义了相应的质量子特性。子特性(9)属于可靠性质量特性。

Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(66)ofthetechnical

公务员医疗补助经费来源于＿＿＿＿＿＿，专款专用、单独管理，与基本医疗保险基金分开核算。

A．耻骨联合B．尿生殖器C．直肠D．前列腺E．子宫

工程咨询单位的()是从事市场中介服务的法律基础，是坚持客观、公正立场的前提条件，是赢得社会信任的重要因素。

下列关于评标委员会在对实质上响应招标文件要求的投标进行报价评估时，除招标文件另有规定外，应当进行修正的情形，说法错误的是()。

注册会计师在制定计划的重要性时，下列()因素可能表明存在一个或多个特定类别的交易、账户余额或披露的重要性水平，这些一个或多个重要性水平可能合理预期影响财务报表使用者依据财务报表作出的经济决策。

《牧童短笛》是贺绿汀创作的一首具有民族风味的()。

老师在管理班级时，让每位学生都轮流当班干部。这属于()模式。

莫里哀曾说：“喜剧的责任，就是通过娱乐来纠正人的缺点。”近年来的法国轻喜剧，尤其擅长_______，用淡淡的笑声拆解社会难题的九连环，具有较高的思想价值和现实意义。　　填入划横线部分最恰当的一项是(　)。

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

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

软考中级

IETF定义的多协议标记交换(MPLS)是一种第三层交换技术，MPLS网络由(38)组成，负责为网络流添加/删除标记的是(39)。

当数据在两个VLAN之间传输时需要哪种设备?(59).

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

某Apache服务器的配置文件httpd.conf包含如下所示配置项。在(32)处选择合适的选项，使得用户可通过http：//www.test.cn访问到该Apache服务器；当用户访问http://111.25.4.30:80时，会访问到(33)虚拟主

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

使用CIDR技术把4个网络100.100.0.0/18、100.100.64.0/18、100.100.128.0/18和100.100.192.0/18汇聚成一个超网，得到的地址是(53)。

ISO/IEC9126软件质量模型中第一层定义了6个质量特性，并为各质量特性定义了相应的质量子特性。子特性(9)属于可靠性质量特性。

Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(66)ofthetechnical

公务员医疗补助经费来源于＿＿＿＿＿＿，专款专用、单独管理，与基本医疗保险基金分开核算。

A．耻骨联合B．尿生殖器C．直肠D．前列腺E．子宫

工程咨询单位的()是从事市场中介服务的法律基础，是坚持客观、公正立场的前提条件，是赢得社会信任的重要因素。

下列关于评标委员会在对实质上响应招标文件要求的投标进行报价评估时，除招标文件另有规定外，应当进行修正的情形，说法错误的是()。

注册会计师在制定计划的重要性时，下列()因素可能表明存在一个或多个特定类别的交易、账户余额或披露的重要性水平，这些一个或多个重要性水平可能合理预期影响财务报表使用者依据财务报表作出的经济决策。

《牧童短笛》是贺绿汀创作的一首具有民族风味的()。

老师在管理班级时，让每位学生都轮流当班干部。这属于()模式。

莫里哀曾说：“喜剧的责任，就是通过娱乐来纠正人的缺点。”近年来的法国轻喜剧，尤其擅长_______，用淡淡的笑声拆解社会难题的九连环，具有较高的思想价值和现实意义。 填入划横线部分最恰当的一项是( )。

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

莫里哀曾说：“喜剧的责任，就是通过娱乐来纠正人的缺点。”近年来的法国轻喜剧，尤其擅长_______，用淡淡的笑声拆解社会难题的九连环，具有较高的思想价值和现实意义。　　填入划横线部分最恰当的一项是(　)。