数据结构第六次作业_图文(精).doc

第六次作业一、选择题 1 、在一个无向图中,所有顶点的度数之和等于所有边数的 C倍。(握手定理) A. 1/2 2 、在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的 B 倍。 A. 1/2 3、G 是一个非连通无向图,共有 28 条边,则该图至少有 D 个顶点。 // 首先连通图顶点一定边数最多的情况为各顶点倆俩相连,此时边数为 n(n-1)/2, 则当顶点个数为 8 的时候边数最多为 28 ,又 G 是非连通图,至少有一个独立的点,所以该图至少有 9 个顶点。 4 、有 n 个顶点的图的邻接矩阵使用 B 数组存储的。 A. 一维 C. 任意行 n列 行任意列 5 、对于一个具有 n 个顶点和 e 条边的无向图,采用邻接表表示,则表头数组大小至少为(假设下标为 0 的数组参与使用) C。 A. n-1 B. n+1 D. n+e 6 、下列说法正确的是 C。 A. 有向图的邻接矩阵一定是不对称的 B. 有向图的邻接矩阵一定是对称的 C. 无向图的邻接矩阵一定是对称的 D. 无向图的邻接矩阵可以不对称二、填空题 1 、若无向图 G 中顶点数为 n ,则图 G 至多有 n*(n-1)/2 条边;若 G 为有向图,则图 G 至多有 n*(n-1) 条边。 2 、图的存储结构主要有两种,分别是邻接矩阵和邻接表。 3 、若 G 是有向图,则把邻接到顶点 v 的顶点数目或边数目称为顶点 v的入度; 把邻接于顶点 v 的顶点数目或边数目称为顶点 v的出度。 4 、已知一个图的邻接矩阵表示,计算第 j 个顶点的入度的方法是将第 j 列的 1 的个数相加,计算第 j 个顶点的出度的方法是将第 j 行的 1 的个数相加。 5 、若将图中的每条边都赋予一个权,则称这种带权的图为网络。 6、无论是有向图还是无向图, 顶点数 n 、边数 e 和各顶点的度 D(v i) 之间的关系为: (∑ 1-n ) D(v i) =2e 即n 个顶点的总度数等于边数的两倍,握手定理。 7、若路径上第一个顶点 v 1 与最后一个顶点 v m 重合, 则称这样的简单路径为环或回路。 8、如果图中任意一对顶点都是连通的, 则称此图是连通图;非连通图的极大连通子图叫做连通分量。 9、创建一个邻接矩阵图的复杂度是 O(n*n) ;创建一个链接表图的复杂度是 O(n+e) e 为边数。三、已知一个无向图如下图所示,试给出该图的邻接矩阵和邻接表存储示意图(分别用矩阵和数组链表图表示) ,并编程分别实现该图的邻接矩阵表示和邻接表表示,要求编写两种表示方法的存储结构、相关基本操作,并在主函数中创建该图。// 邻接矩阵表示: #include<iostream> using namespace std; #define NumVertices 6 typedef char VertexData;// 顶点类型 typedef int EdgeData;// 边上权值类型 typedef struct{ VertexData vexlist[NumVertices]; EdgeData edge[NumVertices][NumVertices];// 邻接矩阵 int n;// 定点数 int e;// 边数} MTGraph; void IniMGraph(MTGraph *G)// 初始化邻接表{ for(int i=0; i<NumVertices; i++) for(int j=0; j<NumVertices; j++) G->edge[i][j]=0; G->n=0; G->e=0; } void NewNode(MTGraph *G, VertexData v)// 添加顶点{ G->vexlist[G->n]=v; G->n++; } void DelNode(MTGraph *G, int m)// 删除顶点{ int i, j; if(G->n==0 || m>=NumVertices)// 没有顶点|| 不存在顶点 m return; for(i=m; i<G->n-1; i++)// 顶点 m 后面的顶点前移 G->vexlist[i]=G->vexlist[i+1]; // 删除与第 m 个顶点相连的边// 删掉边数 for(i=0; i<G->n; i++) { if(G->edge[i][m]!=0) G->e--; } // 邻接矩阵降阶 for(i=m; i<G->n-1; i++) for(j=0; j<G->n; j++) G->edge[i][j]=G->edge[i+1][j]; for(i=m; i<G->n-1; i++)