首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
具有n个顶点e条边的无向图,若用邻接矩阵作为存储结构,则深度优先或广度优先搜索遍历的时间复杂度为(48);若用邻接表作为存储结构,则深度优先或广度优先搜索遍历时的时间复杂度为(49);深度优先或广度优先搜索遍历的空间复杂度为(50)。
具有n个顶点e条边的无向图,若用邻接矩阵作为存储结构,则深度优先或广度优先搜索遍历的时间复杂度为(48);若用邻接表作为存储结构,则深度优先或广度优先搜索遍历时的时间复杂度为(49);深度优先或广度优先搜索遍历的空间复杂度为(50)。
admin
2009-02-15
33
问题
具有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://kaotiyun.com/show/NtxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
帧中继网的虚电路建立在(61),在用户层面采用的协议是(62)。这种网络没有流量控制功能,但增加了拥塞控制功能。如果沿着帧传送方向出现了拥塞,则把帧地址字段中的(63)位设置为1,这样接收方就可通过(64)协议要求发送方降低数据速率。最适合提供帧中继业务的
OSI网络管理标准定义了网管的5大功能。比如对每一个被管理对象的每一个属性设置阈值、控制阈值检查和告警的功能属于(51);接收报警信息、启动报警程序、以各种形式发出警报的功能属于(52);接收告警事件、分析相关信息、及时发现正在进行的攻击和可疑迹象的功能属
N-ISDN是在(41)基础上建立起来的网络,能够提供的最高速率是(42)。网络提供基本接口速率时,传输声音需要使用(43),一路话音占用的数据传输率是(44),占用户可用带宽的比例是(45)。
CSMA(载波监听多路访问)控制策略中有3种坚持退避算法,其中一种是:“一旦介质空闲就发送数据,假如介质是忙的,继续监听,直到介质空闲后立即发送数据;如果有冲突就退避,然后再监听”这种退避算法称为(36)算法。这种算法的主要特点是(37)。CSMA
与线路交换相比,分组交换最大的优点是(11),最大的缺点是(12)。设待传送数据总长度为L位分组长度为P位,其中头部开销长度为H位,源节点到目的节点之间的链路数为h,每个键路上的延迟时间为D秒,数据传输率为Bbit/s,线路交换和虚电路建立连接的时间都为
与线路交换相比,分组交换最大的优点是(11),最大的缺点是(12)。设待传送数据总长度为L位分组长度为P位,其中头部开销长度为H位,源节点到目的节点之间的链路数为h,每个键路上的延迟时间为D秒,数据传输率为Bbit/s,线路交换和虚电路建立连接的时间都为
多路复用技术能够提高传输系统利用率。常用的多路复用技术有(34)。将一条物理信道分成若干时间片,轮换地给多个信号使用,实现一条物理信道传输多个数字信号,这是(35)。将物理信道的总频带宽分割成若干个子信道,每个信道传输一路信号,这是(36)。在光纤中采用的
FDDI的基本编码方法是(46),在此基础上采用(47)编码以获得足够多的同步信息,这样使编码效率提高到(48)。为了消除环网中的时钟偏移,FDDI使用了(49)方案,并规定进入站点缓冲器的数据时钟由输入信号的时钟确定,缓冲器的输出时钟信号由(50)确定。
某校园网工程项目在工程实施过程中,监理工程师收到承建单位的隐蔽工程检验申请后,首先对质量证明资料进行审查,并与(60)在规定的时间内到现场检查。
随机试题
A.Osier吉节B.Negri小体C.Aschoff小体D.环形红斑E.McCallum斑风湿性心内膜炎可有
在土方工程施工中,若采用观察法验槽,则其重点不应选择在()。
施工图预算是______阶段确定建设工程项目造价的依据。()
因铁路、公路、水上、航空事故请求损害赔偿提起的诉讼,由运输始发地、目的地、纠纷发生地或被告住所地人民法院管辖。()
初一语文课上,李老师正情绪激昂地带领学生学习毛泽东的《沁园春.雪》,大家都很投入。这时李老师无意中发现王明正对着语文课本傻笑。李老师走到王明身边才发现他正在偷偷玩手机。李老师非常生气,当即没收了王明的手机,并对他说:“看你以后还认不认真听讲!”李老师的做法
规范
一本书内有3篇文章,第一篇的页数分别是第二篇页数和第三篇页数的2倍和3倍.已知第3篇比第2篇少10页,则这本书共有().
(2004年试题,三(7))设z=f(x2-y2,exy,其中f具有连续二阶偏导数,求
下列关于派生类构造函数和析构函数的说法中,错误的是()。
AboutHomeownershipinAmericaIsthereahousing(住房供给)crisisinAmerica?Orarewesimplyinneedofadjustingasystemtha
最新回复
(
0
)