首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法正确的是( )。 Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题 Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ．广度优先遍历算法类似于树中的后序遍历算法
下列说法正确的是( )。 Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题 Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ．广度优先遍历算法类似于树中的后序遍历算法
admin
2014-04-17
40
问题
下列说法正确的是( )。
Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题
Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ．广度优先遍历算法类似于树中的后序遍历算法
选项
A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅰ、Ⅲ
答案
A
解析
Ⅰ：对于无权图，广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点(这里的距离是指当前顶点到源点路径上顶点的个数)，如图3—8所示。图中各顶点分布在3个层上，同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从1～3的层次顺序来遍历各个顶点的，并在遍历的过程中形成了一棵树，称为广度优先搜索生成树。树的分支总是连接不同层上的顶点，如图3—8中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的(可以用层号来描述其远近)。因此对于无权图，可用广度优先搜索遍历的方法来求最短路径。而对于有权图，当图中各个边的权值相同的时候，就可以类比为无权图(无权图可理解为各边权值为1)，因为各边没有了权的大小之分，则同样可以用广度优先搜索遍历的方式来求最短路径，所以Ⅰ正确。
Ⅱ：从图中的一个顶点进行广度优先搜索可以将与这个顶点连通的顶点全部遍历到，也就找到了该顶点所在的连通分量，因此广度优先遍历可以求出无向图的所有连通分量，所以Ⅱ正确。
Ⅲ：广度优先遍历算法应该是类似于树中的层次遍历算法，所以Ⅲ错误。
综上所述，Ⅰ、Ⅱ正确。
补充：分别使用邻接表、邻接矩阵进行广度、深度优先遍历的时间、空间复杂度的总结。
(1)对于有n个顶点e条边的图采用邻接表表示时，进行深度优先遍历的时间复杂度是O(n+e)，空间复杂度是O(n)。
(2)对于有n个顶点e条边的图采用邻接矩阵表示时，进行深度优先遍历的时间复杂度是O(n
2
)。
(3)对于有n个顶点e条边的图采用邻接表表示时，进行广度优先遍历的时间复杂度是O(n+e)，空间复杂度是O(n)。
(4)对于有n个顶点e条边的图采用邻接矩阵表示时，进行广度优先遍历的时间复杂度是O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/nexi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
体格拉特.帕拉沙尔三世改革的主要内容及其结果。
简要概括基督教的演变。
“改土归流”政策的根本目的是()。
文艺复兴时期，系统提出了国家主权理论的政治思想家是()。
明代中后期，苏州、松江、嘉兴、()、杭州五府，堪称江南最繁华的城市。
建立帝国财政收支总账和元首金库，直接控制和调节全国财政收支的是()。
中国第一个资产阶级革命团体兴中会建立的时间是()。
近代中国派遣第一批留学生是在()。
洋务运动中翻译出《几何原本》后九卷、《代数学》、《重学》等数学、物理方面的科技书籍的翻译家是()。
解析两个战场的地位、作用及相互关系。
随机试题
皮下注射是将药物注入
患者，男，35岁。慢性肾炎病史15年，最近突感乏力、恶心呕吐，常有腿抽筋、皮肤瘙痒，急诊检查肾功能示：BUN30．5mmol／L，Cr768mmol／L，血钾6．8mmol／L，血钠138mmol／L，血氯105mmol／L，最恰当的治疗方
眉心至前发际的骨度分寸是大椎穴至后发际的骨度分寸是
疹的主要特点是
A．疏风清热解毒B．清肝泻火利湿C．利湿清热解毒D．凉血清热解毒E．解毒清暑化湿丹毒发于胸腹腰胯部，红肿疼痛，其治法是
下列哪点不是新生儿坏死性小肠结肠炎的主要临床特点
下列权利中，属于人格权的是()。
下列关于法人的表述，错误的是( )。
如下图，在△OAB中，，AD与BC交于点M．设，以a、b为基底表示．[img][/img]
对SQL语句进行性能调优属于数据库应用系统【1】阶段的任务。
最新回复
(
0
)
