数据结构与算法5.doc

第五次作业 一、选择题 1、在一个无向图中，所有顶点的度数之和等于所有边数的 C 倍。 A. 1/2 B. 1 C. 2 D. 4 2、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的 B 倍。 A. 1/2 B. 1 C. 2 D. 4 3、G是一个非连通无向图，共有28条边，则该图至少有 D 个顶点。 A. 6 B. 7 C. 8 D. 9 4、有n个顶点的图的邻接矩阵使用 B 数组存储的。 A. 一维 B. n行n列 C. 任意行n列 D. n行任意列 5、对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头数组大小至少为（假设下标为0的数组参与使用） C 。 A. n-1 B. n+1 C. n 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列的数相加 ，计算第j个顶点的出度的方法是 将第j行的数相加 。 5、若将图中的每条边都赋予一个权，则称这种带权的图为 网络 。 6、无论是有向图还是无向图，顶点数n 、边数e 和各顶点的度D(vi)之间的关系为： D(Vi)=2e e=n(n-1)/2 。 若路径上第一个顶点v1 与最后一个顶点vm 重合, 则称这样的简单路径为 回路或环, 则称此图是 连通图 ；非连通图的极大连通子图叫做 连通分量0(n 2 ) ；创建一个链接表图的复杂度是 O（n+e） 三、已知一个无向图如下图所示，试给出该图的邻接矩阵和邻接表存储示意图（分别用矩阵和数组链表图表示），并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。 邻接矩阵: 邻接表存储示意图: 邻接矩阵表示： #includeiostream using namespace std; 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; iNumVertices; i++) for(int j=0; jNumVertices; 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) return; for(i=m; iG-n-1; i++) G-vexlist[i]=G-vexlist[i+1]; for(i=0; iG-n; i++) { if(G-edge[i][m]!=0) G-e--; } for(i=m; iG-n-1; i++) for(j=0; jG-n; j++) G-edge[i][j]=G-edge[i+1][j]; for(i=m; iG-n-1;