具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为(48)；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为(49)；深度优先或广度优先搜索遍历的空间复杂度为(50)。

admin2009-02-15 25

问题具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为(48)；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为(49)；深度优先或广度优先搜索遍历的空间复杂度为(50)。

选项 A、O(n²)
B、O(n)
C、O(n-1)
D、O(n+1)

答案B

解析不论是深度优先还是广度优先搜索遍历，图中n个顶点都必须被访问一次。从某个顶点出发，要搜索到其他顶点，必须沿着图中的边去找。用邻接矩阵做图的存储结构时，这些边是分布在一个n阶方阵中，要检测出这些边，必须对矩阵中n²个元素进行检测，因此，其时间复杂度为O(n²)。若用邻接表作为存储结构，只需对代表e条无向边的2e个边表结点进行检测，其时间复杂度为O(e)。深度优先搜索遍历需要用一个栈来保存本身已被访问但可能还有邻接顶点未被访问的那些顶点的序号，每个顶点都要进栈一次，故n个顶点需要开辟n个元素的栈(若用递归算法则由系统开辟)。广度优先搜索遍历需要用一个队列来保存顶点的序号，每个顶点都要进队一次，故队列长度为n，所以深度优先或广度优先搜索遍历的空间复杂度为O(n)。

转载请注明原文地址:https://jikaoti.com/ti/Eza7FFFM

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

配置WWW服务器是UNIX操作平台的重要工作之一，而Apach是目前应用最为广泛的Web服务器产品之一，(56)是Apache的主要配置文件。URL根目录与服务器本地目录之间的映射关系是通过指令(57)设定；指令Server-Admin的作用是(

设信道带宽为3000Hz，根据尼奎斯特(Nyquist)定理，理想信道的波特率为(16)波特，若采用QPSK调制，其数据速率应为(17)，如果该信道信噪比为30dB，则该信道的带宽约为(18)。设信道误码率为10-5，帧长为10Kb，差错为单个错，则帧出错

某指令流水线由5段组成，各段所需要的时间如图1-1所示。连续输入10条指令时的吞吐率为(3)。

在无线通信中不能采用CSMA/CD方式，这是因为无线通信存在(59)，采用CSMA/CA技术是指(60)，MAC层的分布式协调功能提供(61)，站点发出的确认帧ACK，要在(62)间隔发送。为解决隐蔽站带来的问题，802.11允许(63)。

在局域网标准中，(28)与FDDI的MAC帧格式较为相似。(29)介质访问控制方法对最短帧长度有要求，(30)对传输线路最短长度有要求。长10km，16Mbit/s，100个站点的令牌环，每个站点引入1位延迟位，信号传播速度位200m/us，则该环上1位延

女性，18岁，1周来高热、恶心、呕吐，嗜睡，皮肤、巩膜黄染，肝区疼痛。ALT150U，胆红素35mg％，HB-sAg(+)。住院2天，出现肝臭，昏迷。因胃肠道广泛出血而死亡。符合肝穿组织的病理变化的是

A、HBsAgB、抗一HBsC、HBeAgD、抗一HBeE、抗一HBc乙肝病毒传染性减低的标志是()

哪些企业应当设置专门的法律事务机构?()。

为了提高设备的本质安全度，在工业锅炉设计上，工程设计人员采用了两个安全阀的设计方案。这种设计理念属于()。

修订后的《公司法》对公司的注册资本制度、公司治理结构、股东权利保护、财务会计制度、合并分立制度等作出了比较全面的修改，增加了()等方面的规定。

的值是()。

毛泽东曾经说过，“西安事变的和平解决成了时局转换的枢纽”。这一“时局转换的枢纽”，主要体现在

设总体X的均值E(X)＝μ，方差D(X)＝σ2，(X1，X2，…，Xn)为取自X的一个简单随机样本，求的相关系数ρ(i≠j；i，j＝1，2，…，n)．

Inordertoearnmoneyforhisfamily,itisnecessaryforhimtogetajob.

Ballroomdancingusedtobeseenassomethingrather【T1】________thatoldpeoplemightdo.Forthepastfiveyearsthough,the【T2