第七章 图 复习题及答案
更新时间:2024-03-21 22:52:01 阅读量: 综合文库 文档下载
- 第七章大风起兮怎么通关过推荐度:
- 相关推荐
第七章 图 复习题及答案
一、选择题
1.在一个图中,所有顶点的度数之和等于所有边的数目的_______倍 A.1/2 B.1 C.2 D.4
2。在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的_______倍。 A.1/2 B.1 C.2 D.4
6.具有6个顶点的无向图至少应该有_______条边才能保证是一个连通图 A.4 B.5 C.6 D.7
7. 一个无向图采用邻接矩阵存储方法,其邻接矩阵一定是一个_______。 A.对称矩阵 B.对角矩阵 C.三角矩阵 D.稀疏矩阵
8.若具有n个顶点的无向图采用邻接矩阵存储方法,则邻接矩阵的大小为________
9.具有n个顶点、e条边的无向图采用邻接表存储方法,该邻接表中一共有________个边结点。
A.n B.2n C.e D.2e
l0.图的深度优先搜索算法类似于二叉树的——。 八.先序遍历 B.中序遍历 C.后序遍历 D.按层次遍历
11.图的广度优先搜索算法类似于二叉树的——。 A.先序遍历 B.中序遍历 C.后序遍历 D.按层次遍历
12.导致图的遍历序列不惟一的因素是————。 A.出发点的不同、遍历方法的不同 B.出发点的不同、存储结构的不同 c.遍历方法的不同、存储结构的不同
D.出发点的不同、存储结构的不同、遍历方法的不同 13.任何一个带权无向连通图的最小生成树——。 A.是惟一的 , B.是不惟一的 C.有可能不惟一 D.有可能不存在
16.判定一个有向图中是否存在回路可以利用——方法 A.求最小生成树 B.求最短路径 C.拓扑排序 D.图的遍历
17.判定一个有向图中是否存在回路除了利用拓扑排序方法以外,还可以利用 ——方法。
A.图的遍历 B.求最小生成树 c.最短路径 D.求关键路径
19.下面的说法中,不正确的是——。 A.AOE网是一个带权的有向图
B AOE网是一个带权且无环路的有向图
C.AOE网是一个带权且无环路的有向连通图
D正常情况下,AOE网中只有一个源点和一个终点 20.AOE网中的关键路径是该网中的——。 A.从源点到终点的最长路径 B.从源点到终点的最短路径 c.最长的回路 D.最短的回路
A.带权连通图的某最小生成树的权值之和一定小于其他生成树的权值之和 B。从源点到终点的最短路径是惟一的 C.任意一个AOV网不一定存在拓扑序列 D.任意一个AOE网中的关键路径是惟一的
答案:
1. 选择C ;2.选择B,结论是显然的;3.选择D;4.选择A;
6.选择B。
由生成树的定义可知,具有6个顶点的无向图至少应该具有5条边才能保证该无向 图是一个连通图,故本题选择B。 7.选择A。
若无向图采用邻接矩阵存储方法,则其邻接矩阵一定是一个对称矩阵。 8.选择D。
具有n个顶点的无向图采用邻接矩阵存储方法,该邻接矩阵是一个n阶方阵,具有 n2个矩阵元素,因此,此题选择D。 9.选择D。
若具有n个顶点、e条边的无向图采用邻接表存储方法,该邻接表由n个链表组成,n个链表中一共有2e个边结点,因此,此题选择D。
10.选择A。
由图的深度优失搜索方法的过程不难看到图的深度优先搜索类似于二叉树的前序遍历过程,故选择A。
11.选择D。
由图的广度优先搜索方法的过程不难看到图的广度优先搜索类似于二叉树的按层次遍历过程,故选择D。
12.选择D。
导致对一个图进行遍历而得到的遍历序列不惟一的因素有许多,首先,遍历的出发顶点选择得不惟一,得到的遍历序列显然不是惟一的。即使遍历的出发顶点相同,采用的遍历方法若不相同,则得到的结果也是不相同的。另外,即使遍历的出发顶点相同,并且采用同一种遍历方法,若图的存储结构不相同,则得到的结果也可能是不相同的。
例如,对于邻接表结构而言,建立邻接表时提供边的信息的先后次序不同,边结点的链接次序也不同,从而会建立不同的邻接表;同一个图的不同邻接表结构会导致不同的遍历结果。因此,本题应该选择D。
13.选择C
一般情况下,带权连通图的最小生成树不一定是惟一的。 14.选择Co
由求解带权连通图的最小生成树的方法可以得到结论。 15.选择Bo
由求解最短路径的迪杰斯特拉(Dijstra)方法可以得到结论。 16.选择C
拓扑排序方法可以判定一个有向图中是否存在回路。 17.选择Do
除了采用拓扑排序方法判定一个有向图中是否存在回路之外,求关键路径的过程也可以判定一个有向图中是否存在回路。
18.选择A。
按照拓扑排序方法对该图进行拓扑排序便可得到结果。 19.选择C9
说法A,B和D是正确的,只有C是错误的 有向图,但它不是连通图,故选择co 20.选择A。
由AOE网的关键路径的定义可以得到结论。 21.选择C
求出该AOE网的关键路径便可以得到结论。 22.选择C
由于带权连通图的某最小生成树的权值之和不一定小于其他生成树的权值之和;对
于一个图而言,从源点到终点的最短路径也不一定是惟一的;任意一个AOE网中的关 键路径也不一定惟一,因此,只有说法c是错误的。的确,任意一个Aov网不一定存 在拓扑序列。 二、综合题
10. 试对右图所示的AOE网络,解答下列问题。 (1) 这个工程最早可能在什么时间结束。
(2) 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[I]。
(3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。 (4) 确定哪些活动是关键活动。画出由所有关键活动构成的图,指出哪些活动加速可使整个工程提前完成。 【解答】
按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l,根据l - e = 0? 来确定关键活动,从而确定关键路径。
1 ? Ve 0 Vl 0 <1, 2> 0 17 17 2 ? 19 19 <1, 3> 0 0 0 3 ? 15 15 <3, 2> 15 15 0 4 ? 29 37 <2, 4> 19 27 8 5 ? 38 38 <2, 5> 19 19 0 6 ? 43 43 <3, 5> 15 27 12 <4, 6> 29 37 8 <5, 6> 38 38 0
e l l-e
此工程最早完成时间为43。关键路径为<1, 3><3, 2><2, 5><5, 6> 三、算法设计
见图实验要求,图的存储结构建立及遍历算法是重点
正在阅读:
第七章 图 复习题及答案03-21
甲俭村委小学2012年度学校安全工作计划05-16
联系实际谈谈如何提高学习者的自我监控能力07-20
B2C网站交互体验层面如何设计08-25
2013中考英语期末复习资料 考点解读(考前必看)06-11
中国音乐大学排名02-15
跳绳对提高学生身体素质的促进作用的探讨10-05
如何提高体育课堂教学效率03-20
常用试剂及标准溶液的配制解析09-15
(完整版)汇编语言实验报告557427706-07
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 复习题
- 第七章
- 答案
- 销售与收款制度
- (目录)2017-2021年中国有机农业前景预测及投资战略研究报告(
- 塔机安拆方案范本
- 廉租房、经济适用房及基础设施项目申请建设可行性研究报告
- 推荐下载 写天使vs魔鬼的作文2300字-最新
- “张范,字公仪,河内修武人也”阅读答案(附翻译)
- 判断一个人的品质秘笈17则
- 2018秋福师《儿童文学》在线作业二1
- 钉道工题库
- 2009年考研政治考前必做三套模拟试题(一)及答案
- 《3-6岁幼儿学习与发展指南》国培资料
- 电机学(华中科技大学出版社)课后答案
- 全国十城市质检试题分类荟萃 之短文改错
- 2017-2023年中国电容式变送器市场动态监测及竞争战略研究报告(
- 高三生物 细胞代谢专题复习 新人教版
- 财政部、国资委 32号令 企业国有资产交易监督管理办法
- 发酵生产中杂菌的检查与防治
- 法律专业大学生公司实习报告
- 关于一的成语
- 化工原理课程设计填料塔