首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为(48)；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为(49)；深度优先或广度优先搜索遍历的空间复杂度为(50)。
具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为(48)；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为(49)；深度优先或广度优先搜索遍历的空间复杂度为(50)。
admin
2009-02-15
32
问题
具有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
配置WWW服务器是UNIX操作平台的重要工作之一，而Apach是目前应用最为广泛的Web服务器产品之一，(56)是Apache的主要配置文件。URL根目录与服务器本地目录之间的映射关系是通过指令(57)设定；指令Server-Admin的作用是(
N-ISDN是在(41)基础上建立起来的网络，能够提供的最高速率是(42)。网络提供基本接口速率时，传输声音需要使用(43)，一路话音占用的数据传输率是(44)，占用户可用带宽的比例是(45)。
题1：网络协议是计算机网络和分布系统中互相通信的(21)间交换信息时必须遵守的规则的集合。协议的关键成分中(22)是数据和控制信息的结构或格式；(23)是用于协调和进行差错处理的控制信息；定时是对事件实现顺序的详细说明，而网络体系结构则是(24)。
信元是信元交换的单位。为控制差错，在信元中包括CRC校验和，其生成公式为(6)，校验和对(7)进行校验。信元交换采用(8)技术进行复用。在交换过程中，当实施VP交换时，其中VPI、VCI的变化情况是(9)。若在交换过程中出现拥塞，该信息被记录在信元的(10
数据流图是表示软件模型的一种图示方法，它描述数据在软件中流动和被处理变换的过程。数据流图中基本的图形元素包括变换/加工、数据源、数据存储及(8)。
在无线通信中不能采用CSMA/CD方式，这是因为无线通信存在(59)，采用CSMA/CA技术是指(60)，MAC层的分布式协调功能提供(61)，站点发出的确认帧ACK，要在(62)间隔发送。为解决隐蔽站带来的问题，802.11允许(63)。
SSL握手协议定义了对SSL有效载荷进行常规(13)。SSL记录协议把报文中数据分成块，一块的大小是(14)。
在Linux网络配置中，可以通过运行(51)命令来设置主机名字；在不使用DNS和NIS进行地址解析时，为保证解析器能找到主机的IP地址，必须将所使用的主机名字写入(52)文件中；解析器的功能是(53)；Linux中提供名字服务的程序是(54)；配置文件"h
题1：公钥密码是(46)。常用的公钥加密算法有(47)，它可以实现加密和数字签名，它的一个比较知名的应用是(48)，这种应用的协商层用公钥方式进行身份认证，记录层涉及到对应用程序提供的信息的分段、压缩、数据认证和加密。题2：CMM作为软件过程改进的一个指
题1：公钥密码是(46)。常用的公钥加密算法有(47)，它可以实现加密和数字签名，它的一个比较知名的应用是(48)，这种应用的协商层用公钥方式进行身份认证，记录层涉及到对应用程序提供的信息的分段、压缩、数据认证和加密。题2：CMM作为软件过程改进的一个指
随机试题
若完成某分项工程需要某种材料的净耗量为0.95t，损耗率为5％，那么，必需消耗量为（）t。
新加坡公民王颖与顺捷国际信托公司在北京签订协议，将其在中国的财产交由该公司管理，并指定受益人为其幼子李力。在管理信托财产的过程中，王颖与顺捷公司发生纠纷，并诉至某人民法院。关于该信托纠纷的法律适用，下列哪些选项是正确的?(2017年卷一77题，多选)
甲部门是一个利润中心。下列财务指标中，最适合用来评价该部门对公司利润和管理费用贡献的是()。
2012年5月1日，赵某在回家路上被人用木棍从背后击伤；经过调查，赵某于2012年8月1日掌握确切证据证明将其打伤的是钱某，但忙于事务一直未向钱某主张权利；2013年1月1日，赵某因出差遇险无法行使请求权的时间为2个月。赵某请求人民法院保护其权利的诉讼时效
下列不符合旅游合同客体所指的“物”的条件的是()
Windows操作系统通过()来判断文件是不是一个可执行文件。
在计算机语言中有一种逻辑运算，如果两个数同一位止都是0时，其和为零；一个为0、一个为1时或两个都是1时，其和为1。那么，()。
被评估机组为5年前购置，账面价值20万元人民币，评估时该机组已不再生产了，已经被新型机组所取代。经调查和咨询了解到，在评估基准日，其他企业购置新型机组的取得价格为300万元人民币，专家认定被评估机组与新型机组的功能比为0．7，被评估机组尚可使用5年，预计
A、 B、 C、 D、 C
Foralongtime,researchershavetriedtonaildownjustwhatshapesus—orwhat,atleast,shapesusmost.Andovertheyears,
最新回复
(
0
)
