第四章图Word格式.docx

第四章图Word格式.docx

《第四章图Word格式.docx》由会员分享，可在线阅读，更多相关《第四章图Word格式.docx（42页珍藏版）》请在冰点文库上搜索。

7、深度优先遍历类似与二叉树的A：

A.先根遍历B.中根遍历C.后根遍历D.层次遍历

8、广度优先遍历类似与二叉树的D：

9、下列关于开放树（FreeTree）的说法错误的是C：

A.具有n个结点的开放树包含n-1条边

B.开放树没有回路

C.开放树可以是非连通图

D.在开放树中任意加一条边，一定会产生回路

10、在如下图所示的图中，从顶点a出发，按深度优先遍历，则可能得到的一种顶点的序列为D。

A.a,b,e,c,d,fB.a,c,f,e,b,d

C.a,e,b,c,f,dD.a,e,d,f,c,b

11、在如上图所示的图中，从顶点a出发，按广度优先遍历，则可能得到的一种顶点的序列为A。

A.a,b,e,c,d,fB.a,b,e,c,f,d

12、设网（带权的图）有n个顶点和e条边，则采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为C。

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

13、设图有n个顶点和e条边，求解最短路径的Floyd算法的时间复杂度为B。

14、最小生成树是指C。

A.由连通网所得到的边数最少的生成树。

B.由连通网所得到的顶点数相对较少的生成树。

C.连通网中所有生成树中权值之和为最小的生成树。

C.v1,v2,v3,v4,v5,v6D.v1,v3,v6,v4,v2,v5

18、在上图所示的途中，采用Cruskal算法生成最小生成树，过程中产生的边的次序是。

A.（v1,v2）,（v2,v3）,（v5,v6）,（v1,v5）B.（v1,v3）,（v2,v6）,（v2,v5）,（v1,v4）

C.（v1,v3）,（v2,v5）,（v3,v6）,（v4,v5）D.（v2,v5）,（v1,v3）,（v5,v6）,（v4,v5）

19、如下图所示的图中，其中一个拓扑排序的结果是。

A.v1→v2→v3→v6→v4→v5→v7→v8

B.v1→v2→v3→v4→v5→v6→v7→v8

C.v1→v6→v4→v5→v2→v3→v7→v8

D.v1→v6→v2→v3→v7→v8→v4→v5

20、在下图所示的AOE网中，活动a9的最早开始时间为B。

A.13B.14C.15D.16

21、在上图所示的AOE网中，活动a4的最迟开始时间为C

A.2B.3C.4D.5

22、设图有n个顶点和e条边，当用邻接表表示该图时，则求解最短路径的Dijkstra算法的时间复杂度为。

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

二、填空题

1、若无向图G中顶点数为n，则图G至多有n（n-1）/2条边；

若G为有向图，则图G至多有n（n-1）条边。

2、图的存储结构主要有两种，分别是邻接矩阵和邻接表。

3、若G是有向图，则把邻接到顶点v的顶点数目或边数目称为顶点v的入度；

把邻接于顶点v的顶点数目或边数目称为顶点v的度。

4、已知一个图的邻接矩阵表示，计算第j个顶点的入度的方法是listofnodePre（G,j），计算第j个顶点的出度的方法是listofnodeSucc（G,j）。

5、若将图中的每条边都赋予一个权，则称这种带权的图为带权图。

6、无论是有向图还是无向图，顶点数n、边数e和各顶点的度D（vi）之间的关系为：

e=

。

7、若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的简单路径为环路。

8、如果图中任意一对顶点都是连通的,则称此图是连通图；

非连通图的极大连通子图叫做连通分量。

9、创建一个邻接矩阵图的复杂度是；

创建一个链接表图的复杂度是。

10、图的遍历有深度优先遍历和广度优先遍历等方法。

11、在深度优先搜索和广度优先搜索中，都采用visited[i]=new的方式设置第i个顶点为new，而采用visited[i]=old的方式标识第i个结点为old。

12、由于深度优先算法的特点，深度优先往往采用的方式实现。

13、由于广度优先算法的特点，在广度优先实现过程中，往往要借助于另一种数据结构

实现。

14、在深度优先搜索和广度优先搜索中，在搜索过程中所经过的边都称为回退边。

15、连通而且无环路的无向图称为开放树。

16、对于含有n个顶点e条边的连通图，利用Prim算法求其最小生成树的时间复杂度为O（n2），利用Kruscal算法求最小生成树的时间复杂度是O（n）。

3、顶点表示活动的网简称为AOV；

边表示活动的网简称为AOE。

17、一个含有n个顶点的无向连通图，其每条边的权重都是a（a>

0），则其最小生成树的权重等于。

18、具有n个顶点的有向图，如果采用邻接矩阵表示该图，则求某顶点到其他各顶点的最短路径的Dijkstra算法的时间复杂度是；

如果采用邻接表表示该图，则时间复杂度为。

19、在用Dijkstra算法求单源最短路径的过程中，将顶点集合V划分为两个集合S和V-S，其中S中的点为最短路径已经确定的点，V-S中的点为最短路径尚未确定的点。

20、求每一对顶点之间的最短路径，可以用两种方法，一种是分别对每个顶点采用算法，另一种方法是。

21、假设有向图的邻接矩阵C的传递闭包为A，则A[i][j]=1表示。

22、有向图的中心点是指具有最小偏心度的点。

三、已知一个无向图如下图所示，试给出该图的邻接矩阵和邻接表存储示意图（画图，分别用矩阵和数组链表图表示），并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。

四、已知一个有向图如下图所示，试给出图的邻接矩阵和邻接表存储示意图（画图，分别用矩阵和数组链表图表示），并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。

五、已知一个图的顶点集为{a,b,c,d,e}，其邻接矩阵如下图，考虑图为无向图和有向图两种情况，分别画出该图。

六、已知一个连通图如下图所示，分别给出一个按深度优先遍历和广度优先遍历的顶点序列（假设从顶点v1出发）。

并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写相关基本操作，并在主函数中求出深度优先序列和广度优先序列。

七、基于深度优先搜索算法，写出求无向图所有连通子图的算法，并求连通分量。

提示：

对于无向图，从任一个顶点出发进行DFS遍历，当本次遍历完成后，其所访问的结点构成一个连通子图；

如果还存在没有访问过的结点，则从中任一个结点出发进行DFS遍历，……，直到所有结点都被访问。

每一次调用DFS后都得到此非连通图的一个连通子图，调用DFS的次数就是连通子图的个数。

八、网络G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。

九、下图是一个无向带权图，请给出该图的邻接矩阵，并分别按Prim算法和Kruskal算法求最小生成树（包括算法代码和画图）。

十、已知如下图所示的AOE网，顶点表示事件，弧及权重表示活动的时间（单位为天）。

找出关键路径，并求出事件v3的最早开始时间，然后编程实现。

十一、已知一个图的顶点集V和边集G分别为V={0,1,2,3,4,5,6,7,8}，E={<

0,1>

<

0,2>

1,3>

1,4>

2,4>

2,5>

3,6>

3,7>

4,7>

4,8>

5,7>

6,7>

7,8>

}，若采用邻接表存储，并且每个顶点邻接表中的边结点都是按照终点序号从大到小的次序连接的，则按照拓扑排序算法，写出得到的拓扑序列，并编程实现。

十二、如下图所示的有向网络，利用Dijkstra算法求从顶点v1到其他各顶点的最短路径（要求写出如教材P155表4-2所示的Dijkstra算法的执行过程），并编程验证。

十三、应用Floyd算法，编程求下图所示有向图的每对顶点之间的最短路径（写出相应的矩阵），并求该图的中心点。

并利用Warshall算法，编程求该图的传递闭包（矩阵）。

思考题1：

跳马周游棋盘问题：

在n×

n（n<

15）的国际象棋上的某一位置（键盘输入）上放置一个马，然后采用象棋中“马走日字”的规则，要求这个马能不重复地走完n×

n个格子，试用计算机求马能够走的一条路径。

用深度优先搜索法

思考题2：

n×

15）国际象棋棋盘上有一个马，要从起点（键盘输入）跳到指定目标（键盘输入），最少跳几步，试用计算机实现。

用广度优先搜索法。

思考题3：

POJ1789要求用Prim算法实现

TruckHistory

TimeLimit:

2000MS

MemoryLimit:

65536K

Description

AdvancedCargoMovement,Ltd.usestrucksofdifferenttypes.Sometrucksareusedforvegetabledelivery,otherforfurniture,orforbricks.Thecompanyhasitsowncodedescribingeachtypeofatruck.Thecodeissimplyastringofexactlysevenlowercaseletters（eachletteroneachpositionhasaveryspecialmeaningbutthatisunimportantforthistask）.Atthebeginningofcompany'

shistory,justasingletrucktypewasusedbutlaterothertypeswerederivedfromit,thenfromthenewtypesanothertypeswerederived,andsoon.

Today,ACMisrichenoughtopayhistorianstostudyitshistory.Onethinghistorianstriedtofindoutissocalledderivationplan--i.e.howthetrucktypeswerederived.Theydefinedthedistanceoftrucktypesasthenumberofpositionswithdifferentlettersintrucktypecodes.Theyalsoassumedthateachtrucktypewasderivedfromexactlyoneothertrucktype（exceptforthefirsttrucktypewhichwasnotderivedfromanyothertype）.Thequalityofaderivationplanwasthendefinedas

1/Σ（to,td）d（to,td）

wherethesumgoesoverallpairsoftypesinthederivationplansuchthattoistheoriginaltypeandtdthetypederivedfromitandd（to,td）isthedistanceofthetypes.

Sincehistoriansfailed,youaretowriteaprogramtohelpthem.Giventhecodesoftrucktypes,yourprogramshouldfindthehighestpossiblequalityofaderivationplan.

Input

Theinputconsistsofseveraltestcases.Eachtestcasebeginswithalinecontainingthenumberoftrucktypes,N,2<

=N<

=2000.EachofthefollowingNlinesofinputcontainsonetrucktypecode（astringofsevenlowercaseletters）.Youmayassumethatthecodesuniquelydescribethetrucks,i.e.,notwooftheseNlinesarethesame.Theinputisterminatedwithzeroattheplaceofnumberoftrucktypes.

Output

Foreachtestcase,yourprogramshouldoutputthetext"

Thehighestpossiblequalityis1/Q."

where1/Qisthequalityofthebestderivationplan.

SampleInput

4

aaaaaaa

baaaaaa

abaaaaa

aabaaaa

SampleOutput

Thehighestpossiblequalityis1/3.

思考题4

POJ2485要求用Kruskal算法实现

Highways

1000MS

TotalSubmissions:

18145

Accepted:

8433

TheislandnationofFlatopiaisperfectlyflat.Unfortunately,Flatopiahasnopublichighways.SothetrafficisdifficultinFlatopia.TheFlatopiangovernmentisawareofthisproblem.They'

replanningtobuildsomehighwayssothatitwillbepossibletodrivebetweenanypairoftownswithoutleavingthehighwaysystem.

Flatopiantownsarenumberedfrom1toN.Eachhighwayconnectsexactlytwotowns.Allhighwaysfollowstraightlines.Allhighwayscanbeusedinbothdirections.Highwayscanfreelycrosseachother,butadrivercanonlyswitchbetweenhighwaysatatownthatislocatedattheendofbothhighways.

TheFlatopiangovernmentwantstominimizethelengthofthelongesthighwaytobebuilt.However,theywanttoguaranteethateverytownishighway-reachablefromeveryothertown.

ThefirstlineofinputisanintegerT,whichtellshowmanytestcasesfollowed.

ThefirstlineofeachcaseisanintegerN（3<

=500）,whichisthenumberofvillages.ThencomeNlines,thei-thofwhichcontainsNintegers,andthej-thoftheseNintegersisthedistance（thedistanceshouldbeanintegerwithin[1,65536]）betweenvillageiandvillagej.Thereisanemptylineaftereachtestcase.

Foreachtestcase,youshouldoutputalinecontainsaninteger,whichisthelengthofthelongestroadtobebuiltsuchthatallthevillagesareconnected,andthisvalueisminimum.

1

3

0990692

9900179

6921790

692

思考题5

POJ1094拓扑排序

SortingItAllOut

10000K

Anascendingsortedsequenceofdistinctvaluesisoneinwhichsomeformofaless-thanoperatorisusedtoordertheelementsfromsmallesttolargest.Forexample,thesortedsequenceA,B,C,DimpliesthatA<

B,B<

CandC<

D.inthisproblem,wewillgiveyouasetofrelationsoftheformA<

Bandaskyoutodeterminewhetherasortedorderhasbeenspecifiedornot.

Inputconsistsofmultipleprobleminstances.Eachinstancestartswithalinecontainingtwopositiveintegersnandm.thefirstvalueindicatedthenumberofobjectstosort,where2<

=n<

=26.Theobjectstobesortedwillbethefirstncharactersoftheuppercasealphabet.ThesecondvaluemindicatesthenumberofrelationsoftheformA<

Bwhichwillbegiveninthisprobleminstance.Nextwillbemlines,eachcontainingonesuchrelationconsistingofthreecharacters:

anuppercaseletter,thecharacter"

<

"

andaseconduppercaseletter.Noletterwillbeoutsidetherangeofthefirstnlettersofthealphabet.Valuesofn=m=0indicateendofinput.

Foreachprobleminstance,outputconsistsofoneline.Thislineshouldbeoneofthefollowingthree:

Sortedsequencedeterminedafterxxxrelations:

yyy...y.

Sortedsequencecannotbedetermined.

Inconsistencyfoundafterxxxrelations.

wherexxxisthenumberofrelationsprocessedatthetime