数据结构复习成果三.docx

资源描述

数据结构复习成果三.docx

《数据结构复习成果三.docx》由会员分享，可在线阅读，更多相关《数据结构复习成果三.docx（22页珍藏版）》请在冰点文库上搜索。

数据结构复习成果三.docx

数据结构复习成果三

第七章图

基本概念:

1）.无向图:

在一个图中,如果任意两个顶点构成（vi,vj）属于E是无序的,即顶点之间的连线是没有方向的,则称该图是无向图.v1—v2;v1,v2称为邻接点

2）.有向图:

v1v2:

其中v1是弧尾;为弧;v2为弧头

3）.无向完全图:

在一个无向图中,如果任意两顶点都有一条线直接相连,则称该图为无向完全图;在一个含有n个顶点的无向完全图中,有n（n-1）/2条边

4）.有向完全图:

任意两顶点之间都有方向相反的两条弧相连接,有n（n-1）条弧

5）.顶点的度:

无向:

指附于某顶点的边数.

有向:

入度ID:

出去的弧

出度OD:

进去的弧

6）.简单路径:

序列中除起点和重点外其余顶点不重复出现的路径称为简单路径.

7）.子图:

对于图G=（V,E）,G’=（V’,E’）,若存在V’是V的子集,E’是E的子集,且E’中的边所关联的顶点均为V’中,则称图G’是G的一个子图.

连通的:

在无向图中,如果从一个顶点vi到另一个顶点vj（i!

=j）有路径,则称顶点vi到vj是连通的,

8）（无向）.

连通图:

如果图中任意两顶点都是连通的,则称该图是连通图.

一个连通图的生成树是一个极小连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1条边。

连通分量:

无向图的极大连通子图称为连通分量

9（有向）.

强连通图:

对于有向图来说,若图中任意一对顶点vi和vj（i!

=j）均有从一个顶点vi到另一个顶点vj有路径,也有从vj到vi的路径,则称该有向图是强连通的.

强连通分量:

有向图中的极大强连通子图称做有向图的强连通分量/

选择题

1．设无向图的顶点个数为n，则该图最多有（B）条边。

A．n-1B．n（n-1）/2C．n（n+1）/2D．0E．n2

分析:

无向图中顶点数确定,边数最多的是完全无向图.根据概念3完全无向图的性质得:

有有n（n-1）/2条边

2．一个n个顶点的连通无向图，其边的个数至少为（A）。

A．n-1B．nC．n+1D．nlogn；

分析:

根据连通图的定义:

任意两顶点都是连通的；可知连通无向图的边个数至少为n-1,

3．一个有n个结点的图，最少有（B）个连通分量，最多有（D）个连通分量。

A．0B．1C．n-1D．n

分析:

连通分量:

无向图的极大连通子图称为连通分量,若这n个结点都是连通的,则此时连通分量是最少的,为1个（n个顶点构成一个连通分量）.当这n个顶点没有一条边连接,则此时连通分量是最多的,为n个（n个顶点各自组成一个连通分量）

4．在一个无向图中，所有顶点的度数之和等于所有边数（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。

A．1/2B．2C．1D．4

分析:

无向图中,一条边连接了两个顶点,对于这两个顶点来说,由于这条边的存在,所以这两个顶点的度都自增1,总度数增加2,所以无向图中,一条边可以创造两个度.所以边永远是度的两倍.

有向图中,一条弧连接两个顶点,对于指向的顶点来说,入度加1,对于指出的顶点来说,出度加1,所以有向图中,一条弧可以增加1个入度,增加1个出度,所以有向图中,入度之和和出度之和和弧数是1:

1的关系;

5．下列哪一种图的邻接矩阵是对称矩阵？

（B）

A．有向图B．无向图C．AOV网D．AOE网

分析:

//c7-1.h图的数组（邻接矩阵）存储结构（见图7_1）

#defineINFINITYINT_MAX//用整型最大值代替∞

#defineMAX_VERTEX_NUM26//最大顶点个数

enumGraphKind{DG,DN,UDG,UDN};

//{有向图,有向网,无向图,无向网}

typedefstruct

{

VRTypeadj;//顶点关系类型。

对无权图，

//用1（是）或0（否）表示相邻否；

//对带权图，则为权值

InfoType*info;//该弧相关信息的指针（可无）

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

//二维数组

structMGraph

{

VertexTypevexs[MAX_VERTEX_NUM];//顶点向量

AdjMatrixarcs;//邻接矩阵

intvexnum,arcnum;//图的当前顶点数和弧数

GraphKindkind;//图的种类标志

};

1）如图7-2所示,无向图邻接矩阵中,第i行的值为1表示有由vi发出的弧,比如[0][1]这个点为1表示v1和v2是有边相连的,由于无向图中发向和被发向是相对的,所以[1][0]这个点得值肯定也为1,所以就会出现以对角线对称的情况,但图7-2[1][0]并不是1,这是由于无向图的邻接矩阵的对称性,则可采用压缩存储的方式只存入矩阵的下三角（或上三角）元素.这里就只是存入了上三角.

2）借助于邻接矩阵容易判断任意两个顶点之间是否有边（或弧）相连,并容易求得各个顶点的度.对于无向图,顶点vi的度是邻接矩阵中第i行（或第i列）的元素之和,即:

n-1

TD（　vi　）=∑A[i][j]　（n=MAX_VERTEX_NUM）

j=0

3）

对于有向图，第i行的元素之和为顶点vi的出度OD（vi），第j列的元素之和为顶点vj的入度ID（vj）。

网的邻接矩阵可定义为

AOV-网:

用顶点表示活动,用弧表示活动间的优先关系的有向图称为顶点表示活动的图,简称AOV-网.（用于拓扑排序）

AOE-网:

AOE-网是一个带权的有向无环图,其中,顶点表示事件,弧表示活动,权表示活动持续的时间,通常,AOE-网可用来评估工程的完成时间（关键路径）

6．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（B）。

A．

B．

C．

D．

分析:

邻接矩阵请查看选择题第4题;个人觉得问的是顶点vi的度;说明应该是个无向图（有向图应该问出度和入度）,而无向图的度数为第i行非零元的个数或第i列非零元的个数,

无向图的度数:

第i行非零元的个数或第i列非零元的个数.

有向图的度数:

出度:

第i行非零元个数,入度:

第i列非零元的个数.

7．下面哪一方法可以判断出一个有向图是否有环（回路）：

（B）

A．深度优先遍历B.拓扑排序C.求最短路径D.广度优先遍历

分析:

拓扑排序的作用:

判断能不能顺利完工,有没有环.

拓扑排序:

简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

离散数学中关于偏序和全序的定义：

　　偏序关系:

若集合X上的关系是R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。

　　全序关系:

设R是集合X上的偏序,如果对每个x,y属于X必有xRy或yRx，则称R是集合X上的全序关系。

　　注意：

　　①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。

　　②若图中存在有向环，则不可能使顶点满足拓扑次序。

③一个DAG的拓扑序列通常表示某种方案切实可行。

拓扑排序的步骤:

1）.在有向图中选一个没有前驱的顶点且输出之.

2）.从图中删除该顶点和所有以它为尾的弧.

重复上述两步,直到全部顶点均已输出,或者当前图中不存在无前驱的顶点为止,后一种情况则说明有向图中存在环.

8.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（B）。

A.O（n）B.O（n+e）C.O（n2）D.O（n3）

分析:

只要记住如果用邻接矩阵,那么时间复杂度就是0（n2）,如果用邻接表,时间复杂度就是

0（n+e）;

邻接表:

邻接表是图的一种链式存储结构;具体请看书163页

//c7-2.h图的邻接表存储结构（见图7_16）

#defineMAX_VERTEX_NUM20

enumGraphKind{DG,DN,UDG,UDN};//{有向图,有向网,无向图,无向网}

structArcNode

{

intadjvex;//该弧所指向的顶点的位置

ArcNode*nextarc;//指向下一条弧的指针

InfoType*info;//网的权值指针

};//表结点

typedefstruct

{

VertexTypedata;//顶点信息

ArcNode*firstarc;//第一个表结点的地址，指向第一条依附该顶点的弧的指针

}VNode,AdjList[MAX_VERTEX_NUM];//头结点

structALGraph

{

AdjListvertices;//顶点表

intvexnum,arcnum;//图的当前顶点数和弧数

intkind;//图的种类标志

};

用我的话来说:

ALGraph是用来存放图的总信息,比如顶点数和弧数和图的种类并且指向顶点表（AdjList[MAX_VERTEX_NUM]）,而VNode是用来存放顶点的信息;并用*firstarc指向第一条依附于该顶点的弧的指针,而ArcNode是用来存放依附于某个顶点的弧所指向的顶点的位置并且能够指向下一个弧的指针.具体请看下面这张图和上面代码中的注释.

最小生成树:

构造连通网的最小代价生成树.

求最小生成树的普里姆算法（效率不高,但应试解题快）:

假设N=（V,{E}）是连接网,TE是N上最小生成树中边的集合,算法从U={u0}（u0属于V）,TE={}开始,重复执行下列操作,在所有u属于U,v属于V-U的边（u,v）属于E中查找一条代价最小的边（u0,v0）并入集合TE,同时v0并入U,直到U=V为止.此时TE中必有n-1条边,则T=（V,{TE}）为N的最小生成树.

个人理解:

就是先找到一条最短的边,把这条边的两个顶点连起来,再找与这两个顶点相连的边中最短的一条,再把他们连接起来（这样就找到了3个顶点）,再找与这3个顶点相连的边中最短的一条,再把他们连起来,直到所有顶点都被连起来为止.只要注意不要连成环就行.

9.求解最短路径的Floyd算法的时间复杂度为（D）。

A．O（n）B.O（n+c）C.O（n*n）D.O（n*n*n）

分析:

求解最短路径有两个算法:

一个是迪杰斯算法,另一个就是Floyd弗洛伊德算法;两者的时间复杂度都是O（n3）

10．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（A）。

A．存在B．不存在

分析:

主对角线以下的元素均为零,说明这个有向图图没有环（如果下面有元素,且以主对角线对称的位置也有元素,则表示有环）,没有环则说明拓扑有序序列存在,拓扑排序的内容请查看选择题第7题;

11．一个有向无环图的拓扑排序序列（B）是唯一的。

A．一定B．不一定

分析:

拓扑排序的性质请看选择题第7题;同一时刻没有前驱的结点数可能不止一个,这是拓扑排序的序列解释不唯一的了.

12.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（D）。

A．G中有弧B．G中有一条从Vi到Vj的路径

C．G中没有弧D．G中有一条从Vj到Vi的路径

分析:

若G中有一条从Vj到Vi的路径,那么就会构成一个环了,那就不是拓扑序列了.

13.在用邻接表表示图时，拓扑排序算法时间复杂度为（B）。

A.O（n）B.O（n＋e）C.O（n*n）D.O（n*n*n）

分析:

只要记住如果用邻接矩阵,那么时间复杂度就是0（n2）,如果用邻接表,时间复杂度就是0（n+e）;

邻接表的具体信息请查看选择题第8题

14.关键路径是事件结点网络中（A）。

A．从源点到汇点的最长路径B．从源点到汇点的最短路径

C．最长回路D．最短回路

分析:

关键路径:

由于AOE-网中又些活动可以并行地进行,所以完成工程的最短时间是从开始点到完成点的最大路径的长度（这里所说的路径长度是指路径上各活动持续时间之和,不是路径上弧的数目）,路径长度最长的路径叫做关键路径

15．下列关于AOE网的叙述中，不正确的是（B）。

A．关键活动不按期完成就会影响整个工程的完成时间

B．任何一个关键活动提前完成，那么整个工程将会提前完成

C．所有的关键活动提前完成，那么整个工程将会提前完成

D．某些关键活动提前完成，那么整个工程将会提前完成

分析:

关键路径可能有多条，所以不是任何一个关键活动提前完成，那么整个工程将会提前完成

判断题

1.有e条边的无向图，在邻接表中有e个结点。

（错）

分析:

无向图在邻接表中有2e个结点（a指向b,同时b也会指向a）;

有向图中有e个结点（弧是单向的）;

2.有向图的邻接矩阵是对称的。

（错）

分析:

无向图的邻接矩阵才是对称的.

1．任何无向图都存在生成树。

（错）

分析:

生成树:

生成树是一个连通图G的一个极小的连通子图.包含图G的所有顶点,,但只有n-1条边,并且是连通的.生成树可由遍历过程中所经过的边组成,深度优先遍历得到的生成树称为深度优先生成树；广度优先遍历得到的生成树称为广度优先生成树。

连通图得到的是生成树;

不连通图得到的是生成森林;

4.不同的求最小生成树的方法最后得到的生成树是相同的.（错）

分析:

请查看选择题第8题;最小生成树并不是唯一的,所以即使是同一种求最小生成树的方法最后得到的生成树也是不同的;

5.有环图也能进行拓扑排序。

（错）

6.关键路径是AOE网中从源点到终点的最长路径。

（对）

填空题

1．具有10个顶点的无向图，边的总数最多为45。

分析:

无向图:

n（n-1）/2

有向图:

n（n-1）

2.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要n条弧。

分析:

构成一个环;

3.n个顶点的连通无向图，其边的条数至少为n-1。

分析:

连通图:

如果图中任意两顶点都是连通的,则称该图是连通图.至少n-1条边

2．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有无向图：

2（n-1）；有向图：

n个非零元素。

分析:

这题就是问N个顶点的连通图有多少条边的问题:

无向图至少有n-1条边;有向图至少有n条边

而邻接矩阵中无向图是对称的,所以矩阵中非零元素:

无向图至少有2（n-1）个;有向图至少有n个

5．构造连通网最小生成树的两个典型算法是普里姆算法、克鲁斯卡尔算法。

分析:

求最小生成树的普里姆算法请查看选择题第8题

6.有一个用于n个顶点连通带权无向图的算法描述如下：

（1）．设集合T1与T2，初始均为空；

（2）．在连通图上任选一点加入T1；

（3）．以下步骤重复n-1次：

a.在i属于T1，j不属于T1的边中选最小权的边；

b.该边加入T2。

上述算法完成后，T2中共有n-1条边，该算法称普里姆算法算法，T2中的边构成图的最小生成树。

分析:

求最小生成树的普里姆算法请查看选择题第8题

a.在i属于T1，j不属于T1的边中选最小权的边；指的是与T1相连的边中权值最小的那条边

7．AOV网中,顶点表示活动,弧表示活动间的优先关系。

AOE网中,顶点表示事件,弧表示活动。

8.当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。

（1）．查邻接表中入度为零的顶点，并进栈；

（2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是Vk的入度减1，如为零则进栈；

（3）．若栈空时，输出顶点数小于图的顶点数，说明有环路，否则拓扑排序完成。

分析:

拓扑排序的步骤请查看选择题第7题

算法应用题

1、对n个顶点的无向图，采用邻接矩阵表示，如何判别下列有关问题

1）图中有多少条边？

2）任意两个顶点i和j是否有边相连？

3）任意一个顶点的度是多少？

分析:

邻接矩阵请查看选择题第5题

1）.矩阵中非零元的个数除以2（无向图是对称的）;

2）.查看第i行j列或则第j行i列是否为1（有边相连则为1,没有则为0）;

3）.该顶点所在行或列所有非零元的个数;

2．设G=（V,E）以邻接表存储，试写出深度优先和广度优先序列。

分析:

第一步:

如果邻接表中顺序是按从小到大排的,可以先化成邻接矩阵清楚些:

顶点

第二步:

深度优先遍历:

从v1这一行开始从左到右找第一个非零元;这里找到了v2;v1就不继续查找了;再到v2这一行查找找到了v1,但是v1已经遍历过了;所以继续找,这里找到了v3;v2就不继续查找了;再到v3行查找,同理找到了v4;再查找找到了v5

所以深度优先遍历序列:

v1,v2,v3,v4,v5;

广度优先遍历:

从v1这一行开始从左到右找非零元;这里找到了v2,v3,v4;再到v2这一行查找非零元;找到了v1,但是v1已经遍历过了;直到查到v5位置;再到v3,v4行查找非零元;

所以广度优先遍历序列:

v1,v2,v3,v4,v5;

3、已知一无向图的邻接矩阵如下，求该图从顶点V1出发的广度优先遍历和深度优先遍历序列。

0010010

0001001

1001010

0110111

0001000

1011001

0101010

分析:

分析方法同上;

广度优先遍历:

v1,v3,v6,v4,v7,v2,v5;

深度优先遍历:

v1,v3,v4,v2,v7,v6,v5;

4．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。

分析:

最小生成树的普里姆算法（解答题中最方便的方法）:

请查看选择题第8题;

个人理解:

这里就是先找到最短的是5这条边,所以把2,3连接起来;再找与2,3相连的边中最短的,找到了6,把2,6或则3,6连接起来;再找与2,3,6相连的边中最短的;找到了11,把2和4连接起来…

5、对下面的有向图，试利用DIJKSTRA算法从顶点1到其它顶点的最短路径，并写出执行该算法过程中每次循环的状态。

分析:

先从v1连接各点,找到一条最短的,这条就是v1到该点的最短路径;再从这一点开始连接其他各点,该点到其他点得距离加上v1到该点的距离和v1到各点的距离比较;如果比原来短了,就消掉原来的线,画上新的线,再到这些线中找一条最短的,即为最短路径…

6、对下面的AOE网，求出各项活动的最早开始时间e（i）和最迟开始时间l（i），并回答：

工程完成的最短时间是多少？

哪些是关键活动？

分析:

e（i）表示从前面到i弧尾（弧表示活动）得最长路径;l（i）表示总的最长路径减去从后面到i弧尾（弧表示活动）的最长路径,

当e（i）=l（i）时,e（i）即为关键活动

最长路径为:

v1->v3->v4->v7->v9->v10

最短时间是24,

（1）=0;l

（1）=1;e

（2）=0;l

（2）=0;e（3）=5;l（3）=9;

e（4）=6;l（4）=6;e（5）=6;l（5）=13;e（6）=12;l（6）=16;

e（7）=12;l（7）=12;e（8）=12;l（8）=13;e（9）=15;l（9）=16;

e（10）=15;l（10）=16;e（11）=17;l（11）=17;e（12）=19;l（12）=20;

e（13）=16;l（13）=20;e（14）=22;l（14）=22;

所以关键活动为:

a2,a4,a7,a11,a14

7．下图是带权的有向图G的邻接表表示法，求：

（1）．以结点V1出发深度遍历图G所得的结点序列；

（2）．以结点V1出发广度遍历图G所得的结点序列；

（3）．从结点V1到结点V8的最短路径；

（4）．从结点V1到结点V8的关键路径。

分析:

这里不可以化成邻接矩阵:

因为v2中的顺序不是从小到大的,他是3,5,4的顺序;所以如果化成邻接矩阵的话两种遍历和邻接表的遍历都会不一样.

（1）.深度优先遍历:

v1,v2,v3,v8,v5,v7,v4,v6

（2）.广度优先遍历:

v1,v2,v4,v6,v3,v5,v7,v8

（3）.画出每一步的D[i]（红色为确定的路径）

∞

所以v1到v8的最短路径为56

（4）.这里求的是关键路径（顶点）就用ve（i）=vl（i）来判断（顶点用vi表示）,如果求的是关键活动（弧）就用e（i）=l（i）来判断（弧用ai表示）

第一步:

画出AOE-网图

第二步:

求ve（i）,vl（i）,先有ve求出ve（v8）求出最短时间,在逆推vl（i）

ve（v1）=0;ve（v2）=6;ve（v3）=89;

ve（v4）=17;ve（v5）=51;ve（v6）=50;

ve（v7）=75;ve（v8）=97;

vl（v1）=0;vl（v2）=28;v

展开阅读全文