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

admin2009-02-15 21

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

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

软考中级

Windows2000有两种认证协议，即Kerberos和PKI，下面有关这两种认证协议的描述中，正确的是(56)。在使用Kerberos认证时，首先向密钥分发中心发送初始票据(57)，来请求一个会话票据，以便获取服务器提供的服务。

以太网中如果发生介质访问冲突，按照二进制指数后退算法决定下一次重发的时间，使用二进制指数后退算法的理由是(56)。

某计算机系统的可靠性结构是如下图所示的双重串并联结构，若所构成系统的每个部件的可靠度均为0.9，即R=0.9，则该系统的可靠度为(3)。

FTP使用的传输层协议为(29)；FTP默认的控制端口号为(30)。

以下列出的IP地址中，不能作为目标地址的是(51)，不能作为源地址的是(52)。

按照我国现行法律的规定，一个代表团或者多少名以上的代表联名，可以向全国人大提出法律议案【】

患者，女，24岁。自诉右侧颞下颌关节大张口末单声弹响，无疼痛。检查：开口度为52mm，大张口时下颌偏左侧。最可能的诊断是

下列诉讼中，人民法院应按涉外民事诉讼程序办理的有()。

特定区段的划分,应依据影响土地()的区域因素,按土地条件的差异划定。

适用普通程序审理的案件，有特殊情况需要延长审理期限的，由()批准，可以延长6个月。

《1932年华沙牛津规则》解释了多少种贸易术语？(　)

在下列机构中，负责办理派发红股、股息和利息的是(　　)。

分析企业拥有的资源来辨别企业的核心竞争力时分析实物资源比较容易，而分析()比较困难。

教学活动中师生为完成特定的教学任务而组合起来进行活动的结构称()。

Thepurposeoftheeconomists’researchattheUniversityofIowaistoIfmostparticipantsendupwithgreenshares,itmeans

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

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

软考中级

Windows2000有两种认证协议，即Kerberos和PKI，下面有关这两种认证协议的描述中，正确的是(56)。在使用Kerberos认证时，首先向密钥分发中心发送初始票据(57)，来请求一个会话票据，以便获取服务器提供的服务。

以太网中如果发生介质访问冲突，按照二进制指数后退算法决定下一次重发的时间，使用二进制指数后退算法的理由是(56)。

某计算机系统的可靠性结构是如下图所示的双重串并联结构，若所构成系统的每个部件的可靠度均为0.9，即R=0.9，则该系统的可靠度为(3)。

FTP使用的传输层协议为(29)；FTP默认的控制端口号为(30)。

以下列出的IP地址中，不能作为目标地址的是(51)，不能作为源地址的是(52)。

按照我国现行法律的规定，一个代表团或者多少名以上的代表联名，可以向全国人大提出法律议案【】

患者，女，24岁。自诉右侧颞下颌关节大张口末单声弹响，无疼痛。检查：开口度为52mm，大张口时下颌偏左侧。最可能的诊断是

下列诉讼中，人民法院应按涉外民事诉讼程序办理的有()。

特定区段的划分,应依据影响土地()的区域因素,按土地条件的差异划定。

适用普通程序审理的案件，有特殊情况需要延长审理期限的，由()批准，可以延长6个月。

《1932年华沙牛津规则》解释了多少种贸易术语？( )

在下列机构中，负责办理派发红股、股息和利息的是( )。

分析企业拥有的资源来辨别企业的核心竞争力时分析实物资源比较容易，而分析()比较困难。

教学活动中师生为完成特定的教学任务而组合起来进行活动的结构称()。

Thepurposeoftheeconomists’researchattheUniversityofIowaistoIfmostparticipantsendupwithgreenshares,itmeans

《1932年华沙牛津规则》解释了多少种贸易术语？(　)

在下列机构中，负责办理派发红股、股息和利息的是(　　)。