没有合适的资源?快使用搜索试试~ 我知道了~
数据结构与算法6.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 97 浏览量
2021-10-10
20:04:32
上传
评论
收藏 77KB DOC 举报
温馨提示
试读
14页
数据结构与算法6.doc
资源推荐
资源详情
资源评论
第六次作业一、选择题、深度优先遍历类似与二叉树的:先根遍历中根遍历后根
遍历层次遍历、广度优先遍历类似与二叉树的:先根遍历中根遍历后根遍历
层次遍历、以下关于开放树的说法错误的选项是:具有 个结点的开放树包含
条边开放树没有回路开放树可以是非连通图在开放树中任意加一条边,一定会产生
回路、关于最小生成树,以下说法错误的选项是:最小生成树是一棵开放树最小
生成树各边的和是所有生成树中最小的任何图都只有一个最小生成树能够产生最小生成树的图,其边
一定有权值、任何一个无向连通图的最小生成树:只有 棵 棵或多棵一定有多
棵可能不存在、在如以下图所示的图中,从顶点 出发,按深度优先遍历,则可能得到的一种顶点的序列
为 和 。、在
如上图所示的图中,从顶点 出发,按广度优先遍历,则可能得到的一种顶点的序列为。
、设网带权的图有 个顶点和 条边,则采用
邻接表存储时,求最小生成树的 算法的时间复杂度为。 !
"、设图有 个顶点和 条边,求解最短路径的 #$% 算法的时间复杂度为。 !
&、最小生成树是指。由连通网所得到的边数最少的生成
树。由连通网所得到的顶点数相对较少的生成树。连通网中所有
生成树中权值之和为最小的生成树。连通网的极小连通子图。、下
面关于工程计划的 ' 网的表达中,不正确的选项是。关键
活动不按期完成就会影响整个工程的完成时间。任何一个关键活动提
前完成,那么整个工程将会提前完成。所有关键活动都提前完成,那
么整个工程将会提前完成。某些关键工程假设提前完成,那么整个工
程将会提前完成。、在 ' 网中,始点和汇点的个数为。
个始点,假设干个汇点假设干个始点,假设干个汇点假设干个始
点, 个汇点 个始点, 个汇点、在以下图所示的无向图中,从顶
点 ( 开始采用 算法生成最小生成树,算法过程中产生的顶点次序为
。(((((((((((((((((
(((((((、在上图所示的途中,采用 )*+# 算法生
成最小生成树,过程中产生的边的次序是。(((((
(((((((((((((((((
((((((((((、如以下图所示的图中,其
中一个拓扑排序的结果是。(,(,(,(,(,(,(,(
(,(,(,(,(,(,(,((,(,(,(,(,(,(,(
(,(,(,(,(,(,(,(
、在以下图所示的 ' 网中,活动 " 的最早开始时间为。
、在上图所示的 ' 网中,活动 的最迟开
始时间为二、填空题、图的遍历有深度优
先遍历和广度优先遍历等方法。、在深度优先搜索和广度优先搜索中,
都采用 (*-./0#*的方式设置第 个顶点为1,而采用 (*-./0
-)的方式标识第 个结点为 $#。、由于深度优先算法的特点,深度
优先往往采用递归的方式实现。、由于广度优先算法的特点,在
广度优先实现过程中,往往要借助于另一种数据结构队列实现。
、在深度优先搜索和广度优先搜索中,在搜索过程中所经过的边都称
为树边。、连通而且无环路的无向图称为开放树。
、对于含有 个顶点 条边的连通图,利用 算法求其最小生成树的
时间复杂度为 ,利用 2)*# 算法求最小生成树的时间
复杂度是 。、顶点表示活动的网简称为 3;边
表示活动的网简称为 '。"、一个含有 个顶点的无向连通图,
其每条边的权重都是 4&,则其最小生成树的权重等于5
。三、已知一个连通图如以下图所示,分别给出一个按深度优先遍历
和广度优先遍历的顶点序列〔假设从顶点 ( 出发〕。并编程分别实现该
图的邻接矩阵表示和邻接表表示,要求编写相关基本操作,并在主函数中
求出深度优先序列和广度优先序列。
((((((&&&(&&(&&&&
(&&(&&&(&&&&(6'(
(((7(((((7(((7(((((7(
(((7(((7深度优先:((((((广度优先:((
((((8#)9$*-48#)9*-:4)*:*;*-<
-%;=3->-<-%;-':-<-%;*-)-$?-@(><
':-$*-<*-)-$5>-<A':B$<-%;*-)-?3->-(-><
':B$5C*-:<A3->B$<-%;*-)-?3->B$
(>#*-.B)3D*!/<-<
AAdjGraph<EE邻接表表示 F'B(*-.B)3D*/<-.B)3D*/<EE深
度优先($G(*@H;=H?-$)-0<$0&<9H<!!
(*-./0FG'<$0&<9H<!!I(*-./GJH!<A($G
@H;=5H-?*-D-$)-0&<':B$5;<$)-99H4(>#*-./(-><
(*-./0KL'<./0$)-!!<;0H4(>#*-./C*-:<1=#
?I(*-.;4@(>/GH;4@(><;0;4>-<;00BLFF
+<AA-.B)3D*/<EE广度优先($G@H;=5H-+
?':B$5;<ML'L'M<N2'BLFFM<$)-99H4(>#*-.+/(-><(*-.
+/0-)<
'BML'L'+M<1=#I'NOM?0K BM4#-<
'ML'L'M<;0H4(>#*-./C*-:<1=#;?I(*-.;4@(>/?
$)-99H4(>#*-.;4@(>/(-><(*-.;4@(>/0KL'<'BML'L';
4@(>M<A;0;4>-<AAA-?@H;=H<
PQH;=JH<3->-(./0?RRRRRRRRRRRRA<':-./.B)3D*/
0??&&&A?&&A?&&&
&A?&&A?&&&A
?&&&&AA<-QH;=JH(<G(*H<$)-99#<GJH
<$)-99#<AEE连接矩阵表示 F'B(*-.B)3D*/<-
.B)3D*/<EE深度优先($G(*NH;=H?-$)-0<
$0&<9H<!!(*-./0FG'<$0&<9H<!!I
(*-./GJH<A($GNH;=5H-?-@<*-D-$)-0&<
$)-99H4(>#*-./<(*-./0KL'<./0$)-<$)-!!<$@0&<
@9H4<@!!H4:./.@/00JJI(*-.@/GH@<A-
.B)3D*/<EE广度优先($GNH;=5H-+?-@<ML'L'M<
N2'BLFFM<$)-99H4(>#*-.+/<(*-.+/0KL'<'BML'L'+M<
1=#I'NOM?0K BM4#-<'ML'L'M<$@0&<@9H
4<@!!?H4:./.@/00JJI(*-.@/?$)-99H
4(>#*-.@/<(*-.@/0KL'<'BML'L'@M<
AAAA-?NH;=H<PNH;=JH<3->-
(./0?RRRRRRRRRRRRA<':-./.B)3D*/0??&&&A
?&&A?&&&&A?&&A
?&&&A?&&&&AA<-NH;=JH(<
-NJH<G(*H<$)-99#<GJH&<$)-99#<A四、基于深
度优先搜索算法,写出求无向图连通分量的算法。-%;=3->-<
-%;-':-<-%;*-)-?3->-(>#*-.B)3D*/<':-
:.B)3D*/.B)3D*/<-<-<ANH;=<$$#(*-.B)3D*/<
-.B)3D*/<($GNH;=5H-?-$)-0&<$)-99H
4(>#*-./<(*-./0-)<
./0$)-<$)-!!<$-@0&<@9H4<@!!H4:./.@/00JJI
(*-.@/GH@<A($G(*NH;=H?$-0&<9H<!!
(*-./0#*<-$)-0&<$-0&<9H<!!I(*-./
?$)-!!<$)-99$)-99STS<GJH<AA-
?NH;=H<':-.B)':*/.B)3D*/<-<44<$-0
&<9<!!$-@0&<@9<@!!44./.@/<3->-(.B)':*/<
$-0&<9<!!(./0RR!&<-NH;=JH(<
G(*H<$)-99#<)-)&<A五、网络 H 的邻接矩阵如下,试画出
该图,并画出它的一棵最小生成树。
剩余13页未读,继续阅读
资源评论
学习使人快乐张
- 粉丝: 14
- 资源: 6万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功