数据结构第章图习题.doc
习题7 图7.1 单项选择题1在一个图中，所有顶点的度数之和等于所有边数的_倍。A. 1/2 B. 1 C. 2 D. 4 2任何一个无向连通图的最小生成树 。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_倍。A. 1/2 B. 1 C. 2 D. 44一个有n个顶点的无向图最多有_条边。A. n B. n(n-1) C. n(n-1)/2 D. 2n5具有4个顶点的无向完全图有_条边。A. 6 B. 12 C. 16 D. 206具有6个顶点的无向图至少应有_条边才能确保是一个连通图。A. 5 B. 6 C. 7 D. 87在一个具有n个顶点的无向图中，要连通全部顶点至少需要_条边。A. n B. n+1 C. n-1 D. n/28对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是_。A. n B. (n-1)2 C. n-1 D. n29对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_；所有邻接表中的接点总数是_。 A. n B. n+1 C. n-1 D. n+e A. e/2 B. e C.2e D. n+e 10已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为_；按宽度搜索法进行遍历，则可能得到的一种顶点序列为_。 A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,bbaecdf图 7.1 一个无向图11已知一有向图的邻接表存储结构如图7.2所示。12345324524图7.2 一个有向图的邻接表存储结构 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是_。A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是_。A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v212采用邻接表存储的图的深度优先遍历算法类似于二叉树的_。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历13采用邻接表存储的图的宽度优先遍历算法类似于二叉树的_。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历14判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用_。A. 求关键路径的方法 B. 求最短路径的Dijkstra方法C. 宽度优先遍历算法 D. 深度优先遍历算法15关键路径是事件结点网络中 。A.从源点到汇点的最长路径 B.从源点到汇点的最短路径C.最长的回路 D.最短的回路16下面不正确的说法是 。 （1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小； （2）AOE网工程工期为关键活动上的权之和； （3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。A.（1）B.（2）C.（3）D.（1）、（2）17用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是 。A.逆拓朴有序的B.拓朴有序的C.无序的18在图7.3所示的拓朴排列的结果序列为 。A.125634B.516234C.123456D.521634图7.3有向图19一个有n个顶点的无向连通图，它所包含的连通分量个数为 。A.0B.1C.nD.n+120对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为 。A.k1B.k2C.k1-k2D.k1+k221对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为 。A.k1B.k2C.k1-k2D.k1+k27.2 填空题（将正确的答案填在相应饿空中）1n个顶点的连通图至少_条边。2在无权图G的邻接矩阵A中，若(vi,vj)或vi,vj属于图G的边集合，则对应元素Aij等于_，否则等于_。3在无向图G的邻接矩阵A中，若Aij等于1，则Aji 等于_。4已知图G的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为_，其从顶点v1出发的宽度优先搜索序列为_。v1v3v2v4v5v6v2v5v4v3v5v6v4v6v3 图7.4 图G的邻接表5已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是_。6已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是_。7如果含n个顶点的图形成一个环，则它有 棵生成树。8一个非连通无向图，共有28条边，则该图至少有 个顶点。9遍历图的过程实质上是 。BFS遍历图的时间复杂度为 ，DFS遍历图的时间复杂度为 ，两者不同之处在于 ，反映在数据结构上的差别是 。10一个图的 表示法是唯一的，而 表示法是不唯一的。11有向图中的结点前驱后继关系的特征是 。12若无向图G的顶点度数最小值大于等于 时，G至少有一条回路。13根据图的存储结构进行某种次序的遍历，得到的顶点序列是 的。7.3 综合题1562431已知如图7.5所示的有向图，请给出该图的:（1）每个顶点的入/出度；（2）邻接距阵；（3）邻接表；（4）逆邻接表；（5）强连通分量。图7。5一个有向图badcef161115151516131412212请用克鲁斯卡尔和普里姆两种算法分别为图7.6、图7.7构造最小生成树： （1） 图7.6612132124952015161036154372（2） 图7.73试列出图7.8中全部的拓扑排序序列。123456图7.84请用图示说明图7.9从顶点a到其余各顶点之间的最短路径。543223356abdfce图7.95已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下：(1)请画出该AOE图。(2)计算完成整个计划需要的时间。(3)求出该AOE网的关键路径。645112974247.4 判断题 1求最小生成树的Prim算法在边较少、结点较多时效率较高。（ ） 2图的最小生成树的形状可能不唯一。（ ） 3用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。( )4 邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。( )5 任何有向网络（AOV-网络）拓扑排序的结果是唯一的。( )6 有回路的图不能进行拓扑排序。( )7 存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。( ) 8. 用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为0即可。( )9. 在AOE网中一定只有一条关键路径。( )10. 缩短关键路径上活动的工期一定能够缩短整个工程的工期。( )11. 连通分量是无向图中的极小连通子图。( )12. 强连通分量是有向图中的极大强连通子图。( )7.5 算法设计题 1试以邻接矩阵为存储结构实现图的基本操作：InsertVex (G,v)、InsertArc (G,v,w)、DeleteVex (G,v)和DeleteArc (G,v,w)。2 试以邻接表为存储结构实现算法设计题1中所列图的基本操作。3试以十字链表为存储结构实现算法设计题1中所列图的基本操作。4试以邻接多重表为存储结构实现算法设计题1中所列图的基本操作。5试写一算法由图的邻接链表存储得到图的十字链表存储。 6写一算法，由依次输入图的顶点数目、边的数目、各顶点的信息和各条边的信息建立无向图的邻接多重表。 7试写一个算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（ij）。假设分别基于下述策略：（1） 图的深度优先搜索;（2） 图的宽度优先搜索。 8试修改Prim算法，使之能在邻接表存储结构上实现求图的最小生成森林，并分析其时间复杂度（森林的存储结构为孩子兄弟链表）。 9以邻接表作存储结构实现求从源点到其余各顶点的最短路径的Dijkstra算法。 10给定n个村庄之间的交通图，若村庄i和村庄j之间有道路，则将顶点i和顶点j用边连结，边上的权Wij表示这条道路的长度。现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在那个村庄，才能使离医院最近的村庄到医院的路程最短？试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。2 12 15 6 24 9 4 6 10 4 7 3 3 6 2 景点不少于10个。以图中顶点表示校内各景点。.假设采用邻接表存储，设计一个算法，判断无向图是否连通。若连通则返回；否则返回0。. 假设采用邻接表存储，设计一个算法，判断无向图中顶点i到顶点j是否有路径，若有则返回，否则返回0。7.6 上机实习题目设计一个校园导游程序，为来访的客人提供各种信息查询服务。基本要求： （1）设计你所在学校的校园平面图，所含场所不少于10个。以图中顶点表示校内各场所，存放场所名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 （2）为来访客人提供图中任意场所相关信息的查询。 （3）为来访客人提供图中任意场所的问路查询，即查询任意两个景点之间的一条最短的简单路径。选作：（1） 提供图中任意场所得问路查询，即求任意两个场所之间的所有路径。（2） 校园导游图的场所与道路的修改与扩充功能。习题答案 7.1 1. C2.B3.B4. C5. A6. A7.C8.D9. AC10.DB 11. CB12. A13. D 14.D15.A16.A17.A18.B19.B20.B21.A 7.2 1.n-1 2. 1;0 3. 1 4.v1,v2,v3,v6,v5, v4；v1,v2,v5,v4,v3, v65.求矩阵第i列非零元素之和 6. 将矩阵第i行全部置为零7.n8.99.对每个顶点查找其邻接点的过程；O（e）（e为图中的边数）；O（e）；遍历图的顺序不同；DFS采用栈存储访问过的结点，BFS采用队列存储访问过的结点。10邻接矩阵 邻接表11一个结点可能有若干个前驱，也可能有若干个后继12213唯一(2)完成整个计划需要18天。(3)关键路径为：（V1，V2，V5，V7，V9）和（V1，V2， V5，V8，V9，）7 / 7
