数据结构第六次作业

《数据结构第六次作业》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六次作业一、选择题1、在一个无向图中，所有顶点的度数之和等于所有边数的C倍。（握手定理）A.1/2B.1C.2D.42、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的B倍。A.1/2B.1C.2D.43、G是一个非连通无向图，共有28条边，则该图至少有D个顶点。A.6B.7C.8D.9//首先连通图顶点一定边数最多的情况为各顶点倆俩相连，此时边数为n(n-1)/2,则当顶点个数为8的时候边数最多为28，又G是非连通图，至少有一个独立的点，所以该图至少有9个顶点。4、有n个顶点的图的邻接矩阵使用B数组存储的。A.一维B.n行n列C.任意行n列D.n行任意列5、对于一个具有n个顶点和

2、e条边的无向图，采用邻接表表示，则表头数组大小至少为（假设下标为0的数组参与使用）C。A.n-1B.n+1C.nD.n+e6、下列说法正确的是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、已知一个图的邻接矩阵表示，计

3、算第j个顶点的入度的方法是将第j列的1的个数相加，计算第j个顶点的出度的方法是将第j行的1的个数相加。5、若将图中的每条边都赋予一个权，则称这种带权的图为网络。6、无论是有向图还是无向图，顶点数n、边数e和各顶点的度D(vi)之间的关系为：（∑1-n）D(vi)=2e即n个顶点的总度数等于边数的两倍，握手定理。7、若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的简单路径为环或回路。8、如果图中任意一对顶点都是连通的,则称此图是连通图；非连通图的极大连通子图叫做连通分量。9、创建一个邻接矩阵图的复杂度是O(n*n)；创建一个链接表图的复杂度是O(n+e)e为边数。三、已知一个无向图如下

4、图所示，试给出该图的邻接矩阵和邻接表存储示意图（分别用矩阵和数组链表图表示），并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。//邻接矩阵表示：#includeusingnamespacestd;#defineNumVertices6typedefcharVertexData;//顶点类型typedefintEdgeData;//边上权值类型typedefstruct{VertexDatavexlist[NumVertices];EdgeDataedge[NumVertices][NumVertices];

5、//邻接矩阵intn;//定点数inte;//边数}MTGraph;voidIniMGraph(MTGraph*G)//初始化邻接表{for(inti=0;iedge[i][j]=0;G->n=0;G->e=0;}voidNewNode(MTGraph*G,VertexDatav)//添加顶点{G->vexlist[G->n]=v;G->n++;}voidDelNode(MTGraph*G,intm)//删除顶点{inti,j;if(G->n==0

6、

7、m>=NumVertices)//没有顶点

8、

9、

10、不存在顶点mreturn;for(i=m;in-1;i++)//顶点m后面的顶点前移G->vexlist[i]=G->vexlist[i+1];//删除与第m个顶点相连的边//删掉边数for(i=0;in;i++){if(G->edge[i][m]!=0)G->e--;}//邻接矩阵降阶for(i=m;in-1;i++)for(j=0;jn;j++)G->edge[i][j]=G->edge[i+1][j];for(i=m;in-1;i++)for(j=0;jn-1;j++)G->edge[j][i]=G->edge[j][i+1];//减掉

11、顶点数G->n--;}//判断v1和v2之间有没有边boolIsEdge(MTGraph*G,intv1,intv2){if(v1>=0&&v1n&&v2>=0&&v2n&&v1!=v2)if(G->edge[v1][v2]!=0)returntrue;elsereturnfalse;returnfalse;}//在顶点v1和v2之间建立一条边voidSetSucc(MTGraph*G,int