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

admin2009-02-15 46

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

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

软考中级

内存按字节编址，地址从A4000H到CBFFFH，共有(1)字节。若用存储容量为　32K×8bit的存储器芯片构成该内存，至少需要(2)片。

POP3协议采用(38)模式，当客户机需要服务时，客户端软件或FoxMail与POP3服务器建立(39)连接。(Outlook　Express　FoxMail)与POP3

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

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

ATMwhenreferringtocomputersisadedicated,connectionswitchingtechnologythatorganizesdigitaldatainto53-byte(69)unit

SNMPv1是一个不安全的协议，管理站(Manager)与代理(Agent)之间通过(55)进行身份认证，由于认证信息没有加密，因此是不安全的。1998年公布的SNMPv3定义了基于用户的安全模型USM，其中的认证模型块结合(56)算法形成认证协议，产生了

从文字方面对新系统逻辑模型进行描述的系统分析工具是(7)。

某计算机系统中的进程在“就绪”、“运行”和“等待”三种状态之间转换，进程不可能实现(62)的状态转换。

Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(71)ofthetechnicalr

“小膀胱征”(膀胱挛缩)多见于哪种疾病

患者久痢不愈，下痢稀薄，带有白脓，滑脱不禁，腹痛隐隐，口淡不渴，食少神疲，四肢不温，舌淡苔薄白。脉细弱。治疗应首选

关于基牙的支持作用，哪项是错误的

矢量数据空间分析的基本方法包括()。

影响企业酬薪制度的内在因素有()。

出版单位发行其出版物前，应当按照国家有关规定向()等机构免费送交样本。

【2015年淄博市真题】根据《基础教育课程改革纲要》，教材编写、教学、评估和考试命题的依据是()。

可由规章设定的行政处罚种类是（）。

核电站的发电是利用()。

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

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

软考中级

内存按字节编址，地址从A4000H到CBFFFH，共有(1)字节。若用存储容量为 32K×8bit的存储器芯片构成该内存，至少需要(2)片。

POP3协议采用(38)模式，当客户机需要服务时，客户端软件或FoxMail与POP3服务器建立(39)连接。(Outlook Express FoxMail)与POP3

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

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

ATMwhenreferringtocomputersisadedicated,connectionswitchingtechnologythatorganizesdigitaldatainto53-byte(69)unit

SNMPv1是一个不安全的协议，管理站(Manager)与代理(Agent)之间通过(55)进行身份认证，由于认证信息没有加密，因此是不安全的。1998年公布的SNMPv3定义了基于用户的安全模型USM，其中的认证模型块结合(56)算法形成认证协议，产生了

从文字方面对新系统逻辑模型进行描述的系统分析工具是(7)。

某计算机系统中的进程在“就绪”、“运行”和“等待”三种状态之间转换，进程不可能实现(62)的状态转换。

Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(71)ofthetechnicalr

“小膀胱征”(膀胱挛缩)多见于哪种疾病

患者久痢不愈，下痢稀薄，带有白脓，滑脱不禁，腹痛隐隐，口淡不渴，食少神疲，四肢不温，舌淡苔薄白。脉细弱。治疗应首选

关于基牙的支持作用，哪项是错误的

矢量数据空间分析的基本方法包括()。

影响企业酬薪制度的内在因素有()。

出版单位发行其出版物前，应当按照国家有关规定向()等机构免费送交样本。

【2015年淄博市真题】根据《基础教育课程改革纲要》，教材编写、教学、评估和考试命题的依据是()。

可由规章设定的行政处罚种类是（）。

核电站的发电是利用()。

内存按字节编址，地址从A4000H到CBFFFH，共有(1)字节。若用存储容量为　32K×8bit的存储器芯片构成该内存，至少需要(2)片。

POP3协议采用(38)模式，当客户机需要服务时，客户端软件或FoxMail与POP3服务器建立(39)连接。(Outlook　Express　FoxMail)与POP3

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