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

admin2009-02-15 22

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

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

软考中级

在系统转换的过程中，旧系统和新系统并行工作一段时间，再由新系统代替旧系统的策略称为(19)；在新系统全部正式运行前，一部分一部分地代替旧系统的策略称为(20)。

数据加密标准(DES)是一种分组密码，将明文分成大小(33)位的块进行加密，密钥长度为(34)位。

使用LOC(lines　of　code)度量软件规模的优点是(9)。

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

某网络结构如下图所示。在Windows操作系统中，Server1通过安装(28)组件创建Web站点。PCI的用户在浏览器地址栏中输入www.abc.com后无法获取响应页面，管理人员在Windows操作系统下可以使用(29)判断故障发生在网络A内还是网络A

在层次化网络设计中，(68)不是核心层交换机的设备选型策略。

1台服务器、3台客户机和2台打印机构成了一个局域网(如图5-6所示)。在该系统中，服务器根据某台客户机的请求，将数据在一台打印机上输出。设服务器、各客户机及各打印机的可用性分别为a、b、c，则该系统的可用性为(60)。

关于CT增强扫描的叙述，错误的是

职业健康教育所进行的卫生知识和防护技能教育都是针对职业

关于产褥感染的防治，下述哪项不妥

下列各组中，每个成员都带有定位语素的是()。

(2012)课程设计的目标模式最初源于()。

北京奥组委2005年6月26日宣布()成为2008年北京奥运会主题口号。

行政处分适用于()。

设平面曲线L上一点M处的曲率半径为ρ，曲率中心为A，AM为L在点M处的法线，法线上的两点P，Q分别位于L的两侧，其中P在AM上，Q在AM的延长线AN上，若P，Q满足|AP|．|AQ|=ρ2，称P，Q关于L对称．设L：y=x2／2，P点的坐标为(1／2，1)

Ablindbabyisdoublyhandicapped.Notonlyisitunabletosee,butbecauseitcannotreceivethevisualstimulusfromitsenv

Sincewearesocialbeings,thequalityofourlivesdependsinlargemeasureonourinterpersonal(人与人之间的)relationships.Onestr

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

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

软考中级

在系统转换的过程中，旧系统和新系统并行工作一段时间，再由新系统代替旧系统的策略称为(19)；在新系统全部正式运行前，一部分一部分地代替旧系统的策略称为(20)。

数据加密标准(DES)是一种分组密码，将明文分成大小(33)位的块进行加密，密钥长度为(34)位。

使用LOC(lines of code)度量软件规模的优点是(9)。

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

某网络结构如下图所示。在Windows操作系统中，Server1通过安装(28)组件创建Web站点。PCI的用户在浏览器地址栏中输入www.abc.com后无法获取响应页面，管理人员在Windows操作系统下可以使用(29)判断故障发生在网络A内还是网络A

在层次化网络设计中，(68)不是核心层交换机的设备选型策略。

1台服务器、3台客户机和2台打印机构成了一个局域网(如图5-6所示)。在该系统中，服务器根据某台客户机的请求，将数据在一台打印机上输出。设服务器、各客户机及各打印机的可用性分别为a、b、c，则该系统的可用性为(60)。

关于CT增强扫描的叙述，错误的是

职业健康教育所进行的卫生知识和防护技能教育都是针对职业

关于产褥感染的防治，下述哪项不妥

下列各组中，每个成员都带有定位语素的是()。

(2012)课程设计的目标模式最初源于()。

北京奥组委2005年6月26日宣布()成为2008年北京奥运会主题口号。

行政处分适用于()。

设平面曲线L上一点M处的曲率半径为ρ，曲率中心为A，AM为L在点M处的法线，法线上的两点P，Q分别位于L的两侧，其中P在AM上，Q在AM的延长线AN上，若P，Q满足|AP|．|AQ|=ρ2，称P，Q关于L对称．设L：y=x2／2，P点的坐标为(1／2，1)

Ablindbabyisdoublyhandicapped.Notonlyisitunabletosee,butbecauseitcannotreceivethevisualstimulusfromitsenv

Sincewearesocialbeings,thequalityofourlivesdependsinlargemeasureonourinterpersonal(人与人之间的)relationships.Onestr

使用LOC(lines　of　code)度量软件规模的优点是(9)。

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