第7章 图习题及参考答案
更新时间:2023-03-17 09:17:01 阅读量: 综合文库 文档下载
- 经典常谈第7章推荐度:
- 相关推荐
第7章习题
一、单项选择题
1. 在无向图中定义顶点的度为与它相关联的( )的数目。
A. 顶点 B. 边 C. 权 D. 权值
2. 在无向图中定义顶点 vi与vj之间的路径为从vi到达vj的一个( )。
A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数
3. 图的简单路径是指( )不重复的路径。
A. 权值 B. 顶点 C. 边 D. 边与顶点均
4. 设无向图的顶点个数为n,则该图最多有( )条边。
A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)
5. n个顶点的连通图至少有( )条边。
A. n-1 B. n C. n+1 D. 0
6. 在一个无向图中,所有顶点的度数之和等于所有边数的 ( ) 倍。
A. 3 B. 2 C. 1 D. 1/2
7. 若采用邻接矩阵法存储一个n个顶点的无向图,则该邻接矩阵是一个 ( )。
A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵
8. 图的深度优先搜索类似于树的( )次序遍历。
A. 先根 B. 中根 C. 后根 D. 层次
9. 图的广度优先搜索类似于树的( )次序遍历。
A. 先根 B. 中根 C. 后根 D. 层次
10. 在用Kruskal算法求解带权连通图的最小(代价)生成树时,选择权值最小的边的原则是该边不能在
图中构成( )。
A. 重边 B. 有向环 C. 回路 D. 权值重复的边
11. 在用Dijkstra算法求解带权有向图的最短路径问题时,要求图中每条边所带的权值必须是( )。
A. 非零 B. 非整 C. 非负 D. 非正
12. 设G1 = (V1, E1) 和G2 = (V2, E2) 为两个图,如果V1 ? V2,E1 ? E2,则称( )。 A. G1是G2的子图 B. G2是G1的子图
C. G1是G2的连通分量 D. G2是G1的连通分量 13. 有向图的一个顶点的度为该顶点的( )。 A. 入度 B. 出度
C. 入度与出度之和 D. (入度﹢出度))/2
14. 一个连通图的生成树是包含图中所有顶点的一个( )子图。 A. 极小 B. 连通 C. 极小连通 D. 无环 15. n (n>1) 个顶点的强连通图中至少含有( )条有向边。 A. n-1 B. n n(n-1)/2 D. n(n-1)
16. 在一个带权连通图G中,权值最小的边一定包含在G的( )生成树中。 A. 某个最小 B. 任何最小 C. 广度优先 D.深度优先 17. 对于具有e条边的无向图,它的邻接表中有( )个结点。 A. e-1 B. e C. 2(e-1) D. 2e
18. 对于如图所示的带权有向图,从顶点1到顶点5的最短路径为( )。 A.1, 4, 5 B. 1, 2, 3, 5 C. 1, 4, 3, 5 D. 1, 2, 4, 3, 5 4 1 9 6
3 2 1 5
8 5 2 3
1
19. 一个有n个顶点和n条边的无向图一定是( )。 A. 连通的 B. 不连通的 C. 无环的 D. 有环的 20. 对于有向图,其邻接矩阵表示比邻接表表示更易于( )。 A. 求一个顶点的度 B. 求一个顶点的邻接点 C. 进行图的深度优先遍历 D. 进行图的广度优先遍历 21. 与邻接矩阵相比,邻接表更适合于存储( )图。 A. 无向 B.连通 C.稀疏 D. 稠密图
22. 为了实现图的广度优先遍历,BFS算法使用的一个辅助数据结构是( )。 A. 栈 B. 队列 C. 二叉树 D. 树
二、填空题
1. 用邻接矩阵存储图,占用存储空间数与图中顶点个数________关,与边数________关。 2. n (n﹥0) 个顶点的无向图最多有________条边,最少有________条边。 3. n (n﹥0) 个顶点的连通无向图最少有________条边。
?010?4. 若3个顶点的图G的邻接矩阵为?100?,则图G一定是________向图。
????010??5. n (n﹥0) 个顶点的无向图中顶点的度的最大值为________。
6. (n﹥0) 个顶点的连通无向图的生成树至少有________条边。 7. 在使用Kruskal算法构造连通网络的最小生成树时,只有当一条候选边的两个端点不在同一个________
上,才有可能加入到生成树中。
8. 求解带权连通图最小生成树的Prim算法适合于________图的情形,而Kruskal算法适合于________图
的情形。
三、判断题
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
一个图的子图可以是空图,顶点个数为0。
存储图的邻接矩阵中,矩阵元素个数不但与图的顶点个数有关,而且与图的边数也有关。 对一个连通图进行一次深度优先搜索(depth first search)可以遍访图中的所有顶点。 有n (n≥1) 个顶点的无向连通图最少有n-1条边。
如果无向图中各个顶点的度都大于2,则该图中必有回路。 如果有向图中各个顶点的度都大于2,则该图中必有回路。 图的广度优先搜索(breadth first search)算法不是递归算法。
有n个顶点、e条边的带权有向图的最小生成树一般由n个顶点和n-1条边组成。 对于一个边上权值任意的带权有向图,使用Dijkstra算法可以求一个顶点到其它各个顶点的最短路径。 有回路的有向图不能完成拓扑排序。
对任何用顶点表示活动的网络(AOV网)进行拓扑排序的结果都是唯一的。
用边表示活动的网络(AOE网)的关键路径是指从源点到终点的路径长度最长的路径。 对于AOE网络,加速任一关键活动就能使整个工程提前完成。 对于AOE网络,任一关键活动延迟将导致整个工程延迟完成。
在AOE网络中,可能同时存在几条关键路径,称所有关键路径都需通过的有向边为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。
用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中的顶点个数有关,而与图的边数无关。
邻接表只能用于有向图的存储,邻接矩阵对于有向图和无向图的存储都适用。 邻接矩阵只适用于稠密图(边数接近于顶点数的平方),邻接表适用于稀疏图(边数远小于顶点数的平方)
存储无向图的邻接矩阵是对称的,因此只要存储邻接矩阵的下(上)三角部分就可以了。 连通分量是无向图中的极小连通子图。
2
21. 在AOE网络中一定只有一条关键路径。
四、运算题
1. 设连通图G如图所示。试画出该图对应的邻接矩阵表示,并给出对它执行从顶点V0开始的广度优先
搜索的结果。
V0
V2 V1
V5 V4
V3 V7 V8 V6
2. 设连通图G如图所示。试画出该图及其对应的邻接表表示,并给出对它执行从V0开始的深度优先搜
索的结果。
V0
V2 V1 V5 V4
V3 V7
V8 V6
3. 对于如图所示的有向图,试写出: (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树; (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树
①
③ ②
⑤ ④
4. 设有向图G如图所示。试画出从顶点V0开始进行深度优先搜索和广度优先搜索得到的DFS生成森林
和BFS生成森林。 V0 V3 V1 V2
V4
V5 V7 V6
5. 设有一个连通网络如图所示。试按如下格式,应用Kruskal算法给出在构造最小生成树过程中顺序选
出的各条边。
0 6 6
1 1 8 2
7
3 3 5 4 2
6 5 4
3
( 始顶点号,终顶点号, 权值 ) ( , , ) ( , , ) ( , , ) ( , , ) ( , , )
6. 设有一个连通网络如图所示。试采用prim算法从顶点0开始构造最小生成树。(写出加入生成树顶点
集合S和选择边Edge的顺序)
0 9 10 7 1 2 5 7 6 11 8 3 4 5
S: 顶点号 0 0 0 0 0 0 Edge: (顶点,顶点,权值) ( , , ) ( , , ) ( , , ) ( , , ) ( , , )
7. 有八项活动, 每项活动要求的前驱如下:
活动 前驱 A0 无前驱 A1 A0 A2 A0 A3 A0, A2 A4 A1 A5 A2, A4 A6 A3 A7 A5, A6
(1) 试画出相应的AOV网络, 并给出一个拓扑排序序列。
(2) 试改变某些结点的编号, 使得用邻接矩阵表示该网络时所有对角线以下的元素全为0。
8. 试对下图所示的AOE网络
(1) 这个工程最早可能在什么时间结束。
(2) 确定哪些活动是关键活动。画出由所有关键活动构成的图,指出哪些活动加速可使整个工程提前完成。 10 2 4 2 6
1 19 6 4 15 11 5 5 3
9. 设带权有向图如图所示。试采用Dijkstra算法求从顶点0到其他各顶点的最短路径和最短路径长度。 8 0 1 4
4 1 7 2 9 2
5 3 4
4
第7章习题参考答案
一、单项选择题
参考答案: 1. B
2.A 3.B 4.B 5. A 6. B 7. D 8.A 9.D 10.C 11. C 12.A 13.C 14.C 15. B 16. A 17.D 18. D
19.D
20.A
21. C
22. B
二、填空题
参考答案: 1. 有, 无
2. n(n-1)/2, 0 3. n-1 4. 有 5. (n-1)
6. n-1 7. 连通分量 8. 稠密,稀疏
三、判断题
参考答案: 1. 否
2. 否 3. 是
4. 是 5. 是 6. 否 7. 是 8. 否 9. 否 10. 是 11. 否 12. 是 13. 否 14. 是 15. 是 16. 是
17. 否 18.
是 19. 是
20. 否 21. 否
四、运算题
参考答案:
1. 图G对应的邻接矩阵为
??011100000??100110000???100101000???111000110?? G.Edge???010000000??001000000????000100011??000100100????000000100??
执行广度优先搜索的结果为V0V1V3V2V4V7V6V5V8,搜索结果不唯一。
2. 图G对应的邻接表为:
0 V0 1 3 2 ∧
1 V1 0 3 1 ∧
2 V2 0 3 5 ∧
3 V3 0 1 2 6 7 ∧
4 V4 1 ∧
5 V5 2 ∧
6 V6 3 7 8 ∧
7 V7 3 6 ∧ 8 V8 6 ∧
5
正在阅读:
第7章 图习题及参考答案03-17
2016安徽继续教育专用考题答案12-06
大学毕业生的实习报告(优秀5篇)04-02
地藏禅寺因果教育实录(圣云法师讲因果)01-15
花仙谷游记作文1000字07-01
党员干部自我鉴定10-24
日落和晚霞作文400字06-23
中外合作办学谅解备忘录模板-MOU11-17
动物生物化学生化习题12-18
2012年小课题研究08-20
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 习题
- 答案
- 参考
- 幼儿园大班主题计划3篇
- 2015年湖南成人学位英语模拟试题-语法练习
- 2014-2020年中国大数据市场监测与发展前景评估报告 - 图文
- 西方音乐史(课本顺序)
- 浙江教师资格普通话指导:普通话语音系统小常识
- 在全县招商引资工作会议上的表态发言材料
- 2012年江苏省高考数学一轮训练试题考点6:解析几何
- 政府会计准则复习题WORD版
- 北师大版三年级数学下册《第一单元测试卷》(附答案)
- 2012全国两会网民最关注的五个热点话题
- 探、掘、采、供、充系统安全操作规程
- 水文判断题
- 基于J2EE的Blog的设计与实现 - 图文
- 管理学原理 周三多第五版复习题集
- 营销、销售人员驻外管理制度
- 2011年在全省职业健康监督管理工作会议上的讲话
- 2012年高考地理复习专题六:人地协调发展、区域地理环境与人类活动
- 小学一年级语文带拼音的阅读训练(全) - 图文
- 单层厂房结构设计
- 艺考摄影基础理论模拟测试