第7章图.docx
- 文档编号:14192414
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:9
- 大小:69.97KB
第7章图.docx
《第7章图.docx》由会员分享,可在线阅读,更多相关《第7章图.docx(9页珍藏版)》请在冰点文库上搜索。
第7章图
第七章图
一、选择题
1.要连通具有n个顶点的有向图,至少需要()条边。
A.n-lB.nC.n+lD.2n
2.设无向图的顶点个数为n,则该图最多有()条边。
A.n-1B.n(n-1)/2C.n(n+1)/2D.0E.
3.n个结点的完全有向图含有边的数目( )。
A.n*nB.n(n+1)C.n/2D.n*(n-l)
4.一个有n个结点的图,最少有()个连通分量,最多有()个连通分量。
A.0B.1C.n-1D.n
5.用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点序列是()。
A.逆拓扑有序B.拓扑有序C.无序的
6.下面结构中最适于表示稀疏无向图的是(),适于表示稀疏有向图的是()(多选)。
A.邻接矩阵B.逆邻接表C.邻接多重表
D.十字链表E.邻接表
7.下列哪一种图的邻接矩阵是对称矩阵?
()
A.有向图B.无向图
C.AOV网D.AOE网
8.当一个有N个顶点的图用邻接矩阵A表示时,顶点Vi的度是()。
A.
B.
C.
D.
+
9.设下图所示,在下面的5个序列中,符合深度优先遍历的序列有多少?
()
aebdfcacfdebaedfcbaefdcbaefdbc
A.5个B.4个
C.3个D.2个
10.下图中给出由7个顶点组成的无向图。
从顶点1出发,对它进行深度优先遍历得到的序列是(①),而进行广度优先遍历得到的顶点序列是(②)。
①.A.1354267B.1347652C.1534276
D.1247653E.以上答案均不正确
②.A.1534267B.1726453C.l354276
D.1247653E.以上答案均不正确
11.下面哪一方法可以判断出一个有向图是否有环(回路):
()(多选)
A.深度优先遍历B.拓扑排序
C.求最短路径D.求关键路径
12.已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},
E={
A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7
C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V7
13.在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是()。
A.G中有弧
C.G中没有弧
14.下面关于求关键路径的说法不正确的是()。
A.求关键路径是以拓扑排序为基础的
B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D.关键活动一定位于关键路径上
15.下列关于AOE网的叙述中,不正确的是()。
A.关键活动不按期完成就会影响整个工程的完成时间
B.任何一个关键活动提前完成,那么整个工程将会提前完成
C.所有的关键活动提前完成,那么整个工程将会提前完成
D.某些关键活动提前完成,那么整个工程将会提前完成
题号
1
2
3
4
5
6
7
8
9
答案
题号
10
11
12
13
14
15
答案
二、判断题
1.树中的结点和图中的顶点就是指数据结构中的数据元素。
2.在n个结点的无向图中,若边数大于n-1,则该图必是连通图。
3.有e条边的无向图,在邻接表中有e个结点。
4.强连通分量是无向图的极大强连通子图。
5.若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列是存在的。
6.有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素之和的一半。
7.有向图的邻接矩阵是对称的。
8.需要借助于一个队列来实现DFS算法。
9.任何无向图都存在生成树。
10.最小代价生成树是唯一的。
11.拓扑排序算法把一个无向图中的顶点排成一个有序序列。
12.任何有向图的结点都可以排成拓扑排序,而且拓扑序列不唯一。
13.在表示某工程的AOE网中,加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。
14.在AOE图中,关键路径上活动的时间延长多少,整个工程的时间也就随之延长多少。
15.在AOE图中,关键路径上某个活动的时间缩短,整个工程的时间也就必定缩短。
题号
1
2
3
4
5
6
7
8
9
答案
题号
11
12
13
14
15
答案
三、应用题
1.证明:
具有n个顶点和多于n-1条边的无向连通图G一定不是树。
2.证明对有向图的顶点适当的编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
3.考虑右图:
(1)从顶点A出发,求它的深度优先生成树。
(2)从顶点E出发,求它的广度优先生成树。
(3)根据普利姆(Prim)算法,求它的最小生成树。
4.下图是带权的有向图G的邻接表表示法,求:
(1)以结点V1出发深度遍历图G所得的结点序列;
(2)以结点V1出发广度遍历图G所得的结点序列;
(3)从结点V1到结点V8的最短路径;
(4)从结点V1到结点V8的关键路径。
5.请回答下列关于图(Graph)的一些问题:
(1)有n个顶点的有向强连通图最多有多少条边?
最少有多少条边?
(2)表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素?
是否稀疏矩阵?
(3)对于一个有向图,不用拓扑排序,如何判断图中是否存在环?
6.
(1)对于有向无环图,叙述求拓扑有序序列的步骤;
(2)对于以下的图,写出它的四个不同的拓扑有序序列。
7.已知一有向网的邻接矩阵如下,如需在其中一个结点建立娱乐中心,要求该结点距其它各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中心应选址何处?
给出解题过程。
8.请看下边的无向加权图。
(1).写出它的邻接矩阵。
(2).按Prim算法求其最小生成树,并给出构造最小生成树过程中辅助数组的各分量值
辅助数组内各分量值:
Y
Closedge
2
3
4
5
6
7
8
U
V.-U
Vex
Lowcost
Vex
Lowcost
Vex
Lowcost
Vex
Lowcost
Vex
Lowcost
Vex
Lowcost
Vex
Lowcost
Vex
Lowcost
四、算法设计题
1.假定G=(V,E)是有向图,V={1,2,...,N},N>=1,G以邻接矩阵方式存储,G的邻接矩阵为A,即A是一个二维数组,如果i到j有边,则A[i,j]=1,否则A[i,j]=0,请给出一个算法,该算法能判断G是否是非循环图(即G中是否存在回路)
2.试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i<>j)。
注意:
算法中涉及的图的基本操作必须在存储结构上实现。
3.设有向图用邻接表表示,图有n个顶点,表示为1至n,试写一个算法求顶点k的入度(1 4.试编写求无向图G的连通分量的算法。 要求输出每一连通分量的顶点值。 (设图G已用邻接表存储)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 章图