首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
具有n个顶点e条边的无向图,若用邻接矩阵作为存储结构,则深度优先或广度优先搜索遍历的时间复杂度为(48);若用邻接表作为存储结构,则深度优先或广度优先搜索遍历时的时间复杂度为(49);深度优先或广度优先搜索遍历的空间复杂度为(50)。
具有n个顶点e条边的无向图,若用邻接矩阵作为存储结构,则深度优先或广度优先搜索遍历的时间复杂度为(48);若用邻接表作为存储结构,则深度优先或广度优先搜索遍历时的时间复杂度为(49);深度优先或广度优先搜索遍历的空间复杂度为(50)。
admin
2009-02-15
41
问题
具有n个顶点e条边的无向图,若用邻接矩阵作为存储结构,则深度优先或广度优先搜索遍历的时间复杂度为(48);若用邻接表作为存储结构,则深度优先或广度优先搜索遍历时的时间复杂度为(49);深度优先或广度优先搜索遍历的空间复杂度为(50)。
选项
A、O(n
2
)
B、O(n)
C、O(n-1)
D、O(n+1)
答案
B
解析
不论是深度优先还是广度优先搜索遍历,图中n个顶点都必须被访问一次。从某个顶点出发,要搜索到其他顶点,必须沿着图中的边去找。用邻接矩阵做图的存储结构时,这些边是分布在一个n阶方阵中,要检测出这些边,必须对矩阵中n
2
个元素进行检测,因此,其时间复杂度为O(n
2
)。若用邻接表作为存储结构,只需对代表e条无向边的2e个边表结点进行检测,其时间复杂度为O(e)。深度优先搜索遍历需要用一个栈来保存本身已被访问但可能还有邻接顶点未被访问的那些顶点的序号,每个顶点都要进栈一次,故n个顶点需要开辟n个元素的栈(若用递归算法则由系统开辟)。广度优先搜索遍历需要用一个队列来保存顶点的序号,每个顶点都要进队一次,故队列长度为n,所以深度优先或广度优先搜索遍历的空间复杂度为O(n)。
转载请注明原文地址:https://www.kaotiyun.com/show/NtxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
帧中继网的虚电路建立在(61),在用户层面采用的协议是(62)。这种网络没有流量控制功能,但增加了拥塞控制功能。如果沿着帧传送方向出现了拥塞,则把帧地址字段中的(63)位设置为1,这样接收方就可通过(64)协议要求发送方降低数据速率。最适合提供帧中继业务的
配置WWW服务器是UNIX操作平台的重要工作之一,而Apach是目前应用最为广泛的Web服务器产品之一,(56)是Apache的主要配置文件。URL根目录与服务器本地目录之间的映射关系是通过指令(57)设定;指令Server-Admin的作用是(
OSI网络管理标准定义了网管的5大功能。比如对每一个被管理对象的每一个属性设置阈值、控制阈值检查和告警的功能属于(51);接收报警信息、启动报警程序、以各种形式发出警报的功能属于(52);接收告警事件、分析相关信息、及时发现正在进行的攻击和可疑迹象的功能属
对照ISO/OSI参考模型各个层中的网络安全服务,在物理层可以采用(26)加强通信线路的安全;在数据链路层,可以采用(27)进行链路加密;在网络层可以采用(28)来处理信息内外网络边界流动和建立透明的安全加密信道;在传输层主要解决进程到进程间的加密,最常见
对照ISO/OSI参考模型各个层中的网络安全服务,在物理层可以采用(26)加强通信线路的安全;在数据链路层,可以采用(27)进行链路加密;在网络层可以采用(28)来处理信息内外网络边界流动和建立透明的安全加密信道;在传输层主要解决进程到进程间的加密,最常见
题1:网络协议是计算机网络和分布系统中互相通信的(21)间交换信息时必须遵守的规则的集合。协议的关键成分中(22)是数据和控制信息的结构或格式;(23)是用于协调和进行差错处理的控制信息;定时是对事件实现顺序的详细说明,而网络体系结构则是(24)。
与线路交换相比,分组交换最大的优点是(11),最大的缺点是(12)。设待传送数据总长度为L位分组长度为P位,其中头部开销长度为H位,源节点到目的节点之间的链路数为h,每个键路上的延迟时间为D秒,数据传输率为Bbit/s,线路交换和虚电路建立连接的时间都为
与线路交换相比,分组交换最大的优点是(11),最大的缺点是(12)。设待传送数据总长度为L位分组长度为P位,其中头部开销长度为H位,源节点到目的节点之间的链路数为h,每个键路上的延迟时间为D秒,数据传输率为Bbit/s,线路交换和虚电路建立连接的时间都为
在图4-1所示的系统中,R1、R2、R3为3个加工部件,每个加工部件的失效率均为λ,可靠性均为尺。则该系统的可靠性为(4)。若每个加工部件的平均无故障时间为5000小时,则该系统的平均无故障时间为(5)小时。
在软件的生命周期中,下列说法错误的是(37)。
随机试题
连续X线的最短波长的叙述,正确的是
照片上两个相邻X线吸收不同的组织影像,其影像界限清楚明了的程度称为锐利度,亦即两部分影像密度的转变是逐渐的还是明确的程度;影响锐利度的因素有几何学模糊、移动模糊、增感屏。下列关于半影的叙述,错误的是
共沸制冷剂在一定的压力下发生气化,且具有()。
按照代理权产生的依据不同,可将代理分为()。
钢板桩围堰在黏土中施工时,不宜使用( )下沉办法。
下列属于“5S”生产现场管理活动内容的有()。
由对偶婚向一夫一妻制的变化是父权制确立的标志。( )
下列佛塔中,属于阁楼式的有()。
学习动机
下面叙述中错误的是()。
最新回复
(
0
)