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

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)甲、乙、乙、丙、丁、丁、丁、丁、丁(2)甲、乙、丙、丁、丙、丁、丁、丁6 .使用相邻表存储

2、的图的深度和广度优先搜索扫描算法类似于二叉树的(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、v48 .已知一种图中的最小生成树，每个边的权重之和为(c )，并且该图中的最小生成树，从v1到v6的路径为(g )。a、31 B、38 C、36 D、43e、v1、v3、v6 F、v1、v4、v6 G、v1、v5、v4、v6

3、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、v6c、v1、v4、v2、v3、v6、v5 D、v1、v2、v4、v6、v3、v511、下面的结论正确的是(b )a .在无向图中，边的根数是顶点度数的和。b .在图的结构中，顶点上可以没有任何前体或后继者。在c.n个顶点的无向图中，如果边数大于n-1，则该图必定是连通图d .图的邻接矩阵一定是对称矩阵。12、下面的结论不正确的是(d )。a .无向图的

4、连通分量是该图的极大连通子图。b .有向图用邻接矩阵表示容易求出顶点度数的操作。c .无向图用邻接矩阵表示并且在图中的边数等于邻接矩阵元素之和的一半。d .有向图的邻接矩阵是对称的，有向图的邻接矩阵必须是非对称的。13、下面的结论正确的是(c )。a .在深度优先搜索扫描图表时，与起点相邻的顶点比与起点不相邻的顶点先访问。b .一个图按深度优先搜索遍历的结果是唯一的。c .如果有向图g中包含1个循环，则g的顶点之间不存在拓扑排序。d .图的拓扑排序序列是唯一的。14 .在一个图中，所有顶点的度数之和等于所有边的数量的(c )倍。a、1/2 B、1 C、2 D、4二、填海问题1 .对于具有n个顶

5、点的图，有生成树，只有(n-1 )条边。2 .当在有向图中有n个顶点和e个边时，所有顶点的度数之和为(2e )，其邻接矩阵是关于(对角线)对称的矩阵。3 .具有n个顶点的无向完全图，边的总数为(n(n-1)/2 )条，具有n个顶点的有向完全图，边的总数为(n(n-1 ) )条。4 .在没有图g的邻近矩阵a中，如果边/弧属于(vi，vj )或g的集合，则对应元素ai、 j 等于(1)，否则等于(0)且ai。5 .已知一种图的邻居矩阵表示是校正第I个顶点的入侵度的方法(获得第I列非零元素和)6 .已知图g的邻接表格如图7.1所示，相对于顶点V1的深度优先搜索序列是(V1，v2，v3，v6，v5，v

6、4)，而相对于顶点V1的广度优先搜索序列是(V1，v2，v5，v4)V1143V2V3V4V5V6245352012345图7.17、任意(无循环)有向图，所有节点都可以排列在一个拓扑序列中。 重复拓扑排序方法，直到从图表中选择一个(向前)为0的节点，删除该节点及其(以全部为尾的弧)，并输出所有节点。8 .在aoe网中，从源到宿的每个活动时间的总和最长的路径是关键路径，并且某个工作流被显示为如图7.2所示的aoe网。 事件5的最早完成时间是(15 )。 事件4的最晚开始时间是(十)。 事件5的延迟时间为(4)。 关键路径是(0149 )。1925867304e1=5e3=14e2=9e6=3e

7、7=7e4=4e8=12e5=10e10=10e11=5e14=8e13=8e12=5图7.2e9=6三、综合问题1 .简要阐述有向图和有向图中有哪些记忆结构，说明各结构在图的不同操作中有哪些优势有向图的记忆结构有邻接矩阵、邻接表和邻接多重表，有向图的记忆结构有邻接矩阵、邻接表和十字链表。a )邻接矩阵：判定图中任意2个顶点之间边(或弧)是否相连，容易求出各顶点的程度，此外，也可以进行图的扫描。b )邻接表：容易找到任意顶点的第一个邻接点和下一个邻接点，但是为了判断任意两个顶点之间是否连接了边或圆弧，需要检索第I个和第j个链表。 这并不比邻接矩阵方便，对于图的扫描和有向图的拓扑排序也是可能的。

8、c )十字连锁表：因为容易找到以某顶点为头或尾的弧，所以在容易求出顶点入度和出度的有向图的应用中，十字连锁表是有用的工具。d )邻接多重表：是无向图表的非常有效的内存构造，其中容易求出顶点和边的各种信息。2 .表示下图的邻接表的存储结构。 从顶点1开始进行广度和深度优先搜索扫描。3 .尝试图中所有可能的拓扑排序序列。所有可能的拓扑排序序列包括152364、152634、156234、561234、516234、512634、5123644 .如已知连通网的邻接矩阵图7.3所示，将顶点集合设为，从其表示的顶点试制一个利用Prim算法得到的最小生成树。图7.35 .图7.4示出无向连通网络，要求基于Kruskal算法构建其最小生成树。1235461425483234567图7.46 .对于图7.5所示的有向网络，使用Dijkstra算法尝试获得从源点1到其它顶点的最短路径。526411510431015