数据结构图 作业及部分答案

1、.数据结构习题第七章 图 一、 选择题1、一个有n个顶点的无向图最多有（ C ）条边。A、n B、n(n-1) C、n(n-1)/2 D、2n2、具有4个顶点的无向完全图有（ A ）条边。A、6 B、12 C、16 D、203、具有6个顶点的无向图至少有（ A ）条边才能保证是一个连通图。A、5 B、6 C、7 D、84、设连通图G的顶点数为n，则G的生成树的边数为（ A ）。A、n-1 B、n C、2n D、2n-15、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（ D ）和（ B ）（1） A、abecdf B、acfebd C、acebfd D、acf

2、deb（2） A、abcedf B、abcefd C、abedfc D、acfdeb6、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（ B ）和（ D ）。A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历7、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（ C ）和（ B ）。A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v28、已知一个图如下，在该图的最小生成树中各边上权值之和为（ C ），在该图的最小生成树中，从v1

3、到v6的路径为（ G ）。A、31 B、38 C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v69、正确的AOE网必须是（ C ）A、完全图 B、哈密尔顿图 C、无环图 D、强连通图10、已知一个图如下，则由该图得到的一种拓扑序列为（ A ）。A、v1,v4,v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v511、下面结论中正确的是（ B ）A、在无向图中，边的条数是顶点度数之和。 B、在图结构中，顶点可以没有任何前驱和后继。 C、在n

4、个顶点的无向图中，若边数大于n-1，则该图必定是连通图 D、图的邻接矩阵必定是对称矩阵。12、下面结论不正确的是（ D ）。A、无向图的连通分量是该图的极大连通子图。 B、有向图用邻接矩阵表示容易实现求顶点度数的操作。 C、无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。 D、无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。13、下面结论中正确的是（ C ）。A、按深度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按深度优先搜索遍历的结果是唯一的。 C、若有向图G中包含一个环，则G的顶点间不存在拓扑排序。 D、图的拓扑排序序列是唯一的。14、在

5、一个图中，所有顶点的度数之和等于所有边数的（ C ）倍。A、1/2 B、1 C、2 D、4二、 填空题1、对具有n个顶点的图，其生成树有且仅有( n-1 )条边。2、一个无向图有n个顶点和e条边，则所有顶点的度数之和为（ 2e ），其邻接矩阵是一个关于( 对角线 )对称的矩阵。3、具有n个顶点的无向完全图，边的总数为（ n(n-1)/2 ）条，而有n个顶点的有向完全图，边的总数为（ n(n-1) ）条。4、在无权图G的邻接矩阵A中，若(vi,vj)或属于G的边/弧的集合，则对应元素Aij等于（ 1 ），否则等于（ 0 ），若Aij=1，则Aji等于（ 1 ）。5、已知一个图的邻接矩阵表示，计算

6、第i个顶点的入度方法为（求矩阵第I列非零元素的和 ）6、已知图G的邻接表如图7.1所示，其从顶点V1出发的深度优先搜索序列为( v1,v2,v3,v6,v5,v4 )，其从顶点V1出发的广度优先搜索序列为( v1,v2,v5,v4,v3,v6 )。V1143V2V3V4V5V6245352012345图7.1 7、任何（ 无环 ）的有向图，其所有结点都可以排在一个拓扑序列中，拓扑排序的方法是先从图中选一个（ 前趋 ）为0的结点且输出，然后从图中删除该结点及其（ 所有以它为尾的弧 ），反复执行，直到所有结点都输出为止。8、在AOE网中，从源点到汇点各活动时间总和最长的路径为关键路径，某作业工程表

7、示成如图7.2所示的AOE网。则事件5的最早完成时间是( 15 )。事件4的最迟开始时间是( 10 )。事件5的迟缓时间是( 4 )。关键路径是( 0149 )。1925867304e1=5e3=14e2=9e6=3e7=7e4=4e8=12e5=10e10=10e11=5e14=8e13=8e12=5图7.2e9=6三、 综合题1、 简述无向图和有向图有哪几种存储结构，并说明各种结构在图不同操作中有什么优越性？无向图的存储结构有邻接矩阵、邻接表和邻接多重表，有向图的存储结构有邻接矩阵、邻接表和十字链表。a) 邻接矩阵：可判定图中任意两个顶点之间是否有边(或弧)相连，并容易求得各个顶点的度；此

8、外，对于图的遍历也是可行的。b) 邻接表：容易找到任一顶点的第一个邻接点和下一个邻接点；但要判断任意两个顶点之间是否有边或弧相连，则需搜索第i个及第j个链表，这不如邻接矩阵方便；此外，对于图的遍历和有向图的拓扑排序也是可行的。c) 十字链表：容易找到以某顶点为头或尾的弧，因此容易求得顶点的入度和出度；在有向图的应用中，十字链表是很有用的工具。d) 邻接多重表：是无向图的一种非常有效的存储结构，在其中容易求得顶点和边的各种信息。2、 给出下图邻接表存储结构。从顶点1出发进行广度和深度优先搜索遍历。3、 试列出图中全部可能的拓扑排序序列。全部可能的拓扑排序序列为：152364、152634、156234、561234、516234、512634、5123644、已知连通网的邻接矩阵如图7.3所示，顶点集合为，试画出它所表示的从顶点开始利用Prim算法得到的最小生成树。图7.3 5、图7.4所示为一无向连通网络，要求根据Kruskal算法构造出它的最小生成树。1235461425483234567图7.46、对图7.5所示的有向网，试利用Dijkstra算法求从源点1到其他各顶点的最短路径。5264115