首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为(47)。
若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为(47)。
admin
2009-02-15
20
问题
若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为(47)。
选项
A、O(n)
B、O(n
2
)
C、O(n
2
+1)
D、以上都不对
答案
B
解析
n个顶点的图的邻接矩阵是一个n阶方阵，有n行n列。从顶点Vi出发，对图进行广度优先遍历，需对矩阵的第i行逐列检测非零元(若a
[j]1，则说明顶点vj与vi之间有边存在，vi就是vi的邻接顶点)。根据广度优先遍历的思想，每一个顶点都要轮换着做出发顶点，即矩阵的每一行都将要被逐列检测。显然，算法中要用一个两重循环来组织逐行逐列的检测操作，所以，算法的时间复杂度是n的平方阶。
转载请注明原文地址:https://kaotiyun.com/show/pTxZ777K
本试题收录于：
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
局域网中某主机的IP地址为172.16.1.12/20，该局域网的子网掩码为(52)，最多可以连接的主机数为(53)。
多形病毒指的是(47)的计算机病毒。
某网络结构如下图所示。在Windows操作系统中，Server1通过安装(28)组件创建Web站点。PCI的用户在浏览器地址栏中输入www.abc.com后无法获取响应页面，管理人员在Windows操作系统下可以使用(29)判断故障发生在网络A内还是网络A
家庭接入Internet可以通过光缆入户，即(41)方式，也可以通过传统的线缆接入。当使用电话线接入时，有多种模式，对称模式的技术有(42)。ADSL接入铜线的传输距离可达(43)km，通过多路复用技术，在这个线路上可同时存在(44)个信道，当使用HFC方
OneofthedifficultiesinbuildinganSQL-likequerylangefortheWebistheabsenceofadatabaseschemaforthishuge,heter
Fast(66)isalsoreferredtoas100BASE-Tor802.3uandisacommunications(67)thatenablescomputersonalocal-areanetworkto
Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(71)ofthetechnicalr
软件设计中划分模块的一个准则是(15)。两个模块之间的耦合方式中，(16)合的耦合度最高，(17)的耦合度最低。一个模块内部的聚敛种类中，(18)内聚的内聚度最高，(19)的内聚度最低。
软件设计中划分模块的一个准则是(15)。两个模块之间的耦合方式中，(16)合的耦合度最高，(17)的耦合度最低。一个模块内部的聚敛种类中，(18)内聚的内聚度最高，(19)的内聚度最低。
软件设计中划分模块的一个准则是(10)。两个模块之间的耦合方式中，(11)的耦合度最高；一个模块内部的内聚种类中，(12)内聚的内聚度最高。
随机试题
没有法定依据或者不遵守法定程序的，行政处罚无效。（）
目前医护人员称呼病人时用姓名，而不用床号，是为了满足病人的
背景资料：某桥梁3号墩为桩承式结构，承台体积约为200m3。，承台基坑开挖深度为4m，原地面往下地层依次为：0～50cm腐殖土，50～280cm黏土，其下为淤泥质土，地下水位处于原地面以下100cm。根据该桥墩的水文地质，施工单位在基坑开挖过程中采取了
“暖风熏得游人醉，直把杭州作汴州”诗句中的“汴州”即现今的()。
Studentsshouldinvolvethemselvesincommunityactivities______theycangainexperienceforgrowth.
人的本质是()。
紧急状态处置，是指公安机关为维护国家安全和社会治安秩序，对突发的重大暴力犯罪、重大治安事件和重大治安灾害事故依法采取的非常措施。（）
CPU功能不包括()。
在信息系统开发中，不属于系统分析员主要工作的是（）
Universalizationofeducationhasbeenapolicypriority,butitstillremainsanunfulfilleddream.Asaconsequence,thespre
最新回复
(
0
)
