(完整word版)第八章试题

《(完整word版)第八章试题》由会员分享，可在线阅读，更多相关《(完整word版)第八章试题（27页珍藏版）》请在装配图网上搜索。

1、!QQPenguin.exe-损坏文件交稍或目录C:Userswindows7AppDataLocal书据结构课程（本科）第八章试题MicrosoftindowsTempraryInternetFilesContent.IE5FKWD34V4已损坏且无法读取请运行chkdskTM.一、单项选择题1. 在无向图中定义顶点的度为与它相关联的（）的数目。A。顶点B。边C。权D.权值52.在无向图中定义顶点Ao顶点序列V与V之间的路径为从V到达V的一个ijijB.边序列Co权值总和)oDo边的条数3.图的简单路径是指（）不重复的路径。Ao权值B.顶点Co边D.边与顶点均4.设无向图的顶点个数为n,则该

2、图最多有（A.n1Bon（n1）/2)条边。Con(n+1)/2D.n(n1)5.n个顶点的连通图至少有（）条边。Aon1B.nCon+1D.06.在一个无向图中，所有顶点的度数之和等于所有边数的（A.3B.2C.1)倍.Do1/2Ao上三角矩阵Bo稀疏矩阵C.对角矩阵D.对称矩阵8.图的深度优先搜索类似于树的（）次序遍历。A.先根B.中根Co后根Do层次9.图的广度优先搜索类似于树的（）次序遍历。A.先根B.中根Co后根Do层次7.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（）o10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构，判断

3、一条边的两个端点是否在同一个连通分量上。Ao位向量B.堆Co并查集Do生成树顶点集合11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能在图中构成（）Ao重边B.有向环Co回路D.权值重复的边12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（)o13.14.15.16.17.18.19.20.21.22.23.24.A.非零Bo非整Co非负Do非正在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少有（）子女.Ao1Bo2Co3D.0设有向图有n个顶点和e条边，采用邻接

4、表作为其存储表示，在进行拓扑排序时，总的计算时间为（）oAoO（nloge）B。O（n+e）C。0（ne）D.0（n2）2设有向图有n个顶点和e条边，采用邻接矩阵作为其存储表示，在进行拓扑排序时，总的计算时间为（）oAoO（nloge）B.0（n+e）C。0（ne）D.0（n2）设G二（V，E）和G二（V，11122A.G是G的子图12CoG是G的连通分量12E）为两个图，如果VV，E2121BoG是G的子图21D.G是G的连通分量21)o有向图的一个顶点的度为该顶点的（）oAo入度B.出度Co入度与出度之和Do（入度+出度）/2一个连通图的生成树是包含图中所有顶点的一个（）子图。Ao极小Bo

5、连通Co极小连通Do无环n（n1）个顶点的强连通图中至少含有（）条有向边。A.n-1Bonn(n-1)/2Don(n-1)在一个带权连通图G中，权值最小的边一定包含在G的（）生成树中。A.某个最小B.任何最小C.广度优先D。深度优先对于具有e条边的无向图，它的邻接表中有（）个边结点。Aoe-1BoeC.2（e-1）D.2e对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（）oAo1，4,5B.1,2,3,5C.1，4,3,5Do1，2，4，3，562198-A具有n个顶点的有向无环图最多可包含（)条有向边.Aon1BonC.n(n1)/2D.n(n1)一个有n个顶点和n条边的无向图一定是

6、（)oAo连通的Bo不连通的Co无环的D.有环的25. 在n个顶点的有向无环图的邻接矩阵中至少有（）个零元素。A。nB。n（n-1）/2C.n（n+1）/2D.n（n-1）26. 对于有向图，其邻接矩阵表示比邻接表表示更易于（）.A。求一个顶点的度B。求一个顶点的邻接点C。进行图的深度优先遍历D.进行图的广度优先遍历27. 在一个有向图的邻接矩阵表示中，删除一条边v,v需要耗费的时间是（）.ijA.O（1）B。O（i）C.O（j）D。O（i+j）28. 与邻接矩阵相比，邻接表更适合于存储（）图。A.无向B。连通C。稀疏D.稠密图29. 设一个有n个顶点和e条边的有向图采用邻接矩阵表示,要计算某

7、个顶点的出度所耗费的时间是（）。A。O（n）B.O（e）C.O（n+e）D。O（n2）30. 为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是（）A。栈B.队列C。二叉树D。树参考答案:1.B2.A3。B4。B5.A6.B7.D8。A9.D10.C11.C12C13。B14.B15.D16.A17.C18。C19。B20。A21。D22。D23。C24。D25。C26。A27。A28.C29.A30。B二、填空题1. 图的定义包含一个顶点集合和一个边集合。其中，顶点集合是一个有穷集合。2. 用邻接矩阵存储图，占用存储空间数与图中顶点个数关，与边数关3. n（n0）个顶点的无向图最多

8、有条边，最少有条边。4. n（n0）个顶点的连通无向图最少有条边._010_5. 若3个顶点的图G的邻接矩阵为100,则图G定是向图。0106. n（n0）个顶点的连通无向图各顶点的度之和最少为(完整word版)第八章试题7. 设图G=(V,E),V=Vo,Vi,V2,VJ,E=(V0,V(V0,V2),(V0,7),(匕，V3)，则从顶012301020313点V开始的图G的不同深度优先序列有种，例如。8. 设图G=(V,E),V=P,Q,R,S,T,E=P,Q,R,T,从顶点P出发，对图G进行广度优先搜索所得的所有序列为和。9. n(n0)个顶点的无向图中顶点的度的最大值为。10. 在重连

9、通图中每个顶点的度至少为。11. 在非重连通图中进行深度优先搜索,则深度优先生成树的根为关节点的充要条件是它至少有个子女。12. (n0)个顶点的连通无向图的生成树至少有条边。13.101个顶点的连通网络N有100条边，其中权值为1,2,3,4,5,6,7,8,9,10的边各10条,则网络N的最小生成树各边的权值之和为.14. 在使用Kruskal算法构造连通网络的最小生成树时,只有当一条候选边的两个端点不在同一个上,才有可能加入到生成树中。15. 深度优先生成树的高度比广度优先生成树的高度。16. 求解带权连通图最小生成树的Prim算法适合于图的情形，而Kruskal算法适合于图的情形。17

10、. 求解最短路径的Dijkstra算法适用于各边上的权值的情形。若设图的顶点数为n,则该算法的时间复杂度为。18. 若对一个有向无环图进行拓扑排序,再对排在拓扑有序序列中的所有顶点按其先后次序重新编号,则在相应的邻接矩阵中所有元素将集中到对角线以上.参考答案：1.非空2。有,无3。n(n1)/2,04.n-15.有6。2(n1)7.4,VVVV(或VVVV,VVVV,VVVV)01320213023103128。PQRST和PRQTS9。n-110。211。212.n113。55014.连通分量15。高16。稠密,稀疏17.非负，0(n2)18。非零(或值为1的)三、判断题1. 一个图的子图可

11、以是空图,顶点个数为0。2. 存储图的邻接矩阵中，矩阵元素个数不但与图的顶点个数有关，而且与图的边数也有关。3. 一个有1000个顶点和1000条边的有向图的邻接矩阵是一个稀疏矩阵。4. 对一个连通图进行一次深度优先搜索(depthfirstsearch)可以遍访图中的所有顶点。5. 有n(n$1)个顶点的无向连通图最少有n-1条边。6. 有n(n$1)个顶点的有向强连通图最少有n条边.7. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以因为某种需要改变顶点的编号。8. 如果无向图中各个顶点的度都大于2，则该图中必有回路.9. 如果有向图中各个顶点的度都大于2，则该图中必有回路。10.

12、 图的深度优先搜索(depthfirstsearch)是一种典型的回溯搜索的例子，可以通过递归算法求解。11. 图的广度优先搜索(breadthfirstsearch)算法不是递归算法。12. 有n个顶点、e条边的带权有向图的最小生成树一般由n个顶点和n-1条边组成。13. 对于一个边上权值任意的带权有向图，使用Dijkstra算法可以求一个顶点到其它各个顶点的最短路径。14. 对一个有向图进行拓扑排序(topologicalsorting),一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。15. 有回路的有向图不能完成拓扑排序。16. 对任何用顶点表示活动的网络(A0V网)进

13、行拓扑排序的结果都是唯一的。17. 用边表示活动的网络(AOE网)的关键路径是指从源点到终点的路径长度最长的路径。18. 对于AOE网络，加速任一关键活动就能使整个工程提前完成。19. 对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。20. 在AOE网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥.如果加速这样的桥上的关键活动就能使整个工程提前完成。21. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。22. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用.7（完整word版）第八

14、章试题23. 邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）24. 存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了。25. 连通分量是无向图中的极小连通子图。26. 强连通分量是有向图中的极大强连通子图。27.在AOE网络中一定只有一条关键路径。参考答案:1.否2。否3。是4.是5。是6.否7.是8。是9.否10.是11.是12。否13.否14.否15.是16.否17。是18.否19。是20。是21.是22.否23.是24.是25.否26.是27。否四、运算题1.设连通图G如图所示。试画出该图对应的邻接矩阵表示,并给

15、出对它执行从顶点V开始的广度优先搜索的结果。492.设连通图G如图所示。试画出该图及其对应的邻接表表示，并给出对它执行从V。开始的深度优先搜索的结果。43.设连通图G如图所示。试画出从顶点V出发的深度优先生成树，指出图G中哪几个顶点是关节点（即万一它失效则通信网络将发生故障）。4(完整word版)第八章试题4. 设连通图G如图所示，(1)如果有关节点，请找出所有的关节点。(2)如果想把该连通图变成重连通图，至少在图中加几条边？如何加？5. 对于如图所示的有向图，试写出：(1) 从顶点出发进行深度优先搜索所得到的深度优先生成树;(2) 从顶点出发进行广度优先搜索所得到的广度优先生成树6. 设有向

16、图G如图所示。试画出从顶点V开始进行深度优先搜索和广度优先搜索得到的DFS生成森林和BFS0生成森林.17. 表示图的另一种方法是使用关联矩阵INC。其中，一行对应于一个顶点，一列对应于一条边。因此，如果边j依附于顶点i,则INCij=1。如果ADJ是图G=(V,E)的邻接矩阵，INC是关联矩阵,试说明在什么条件下将有ADJ二INCINCtI,其中，INCt是矩阵INC的转置矩阵，I是单位矩阵。两个nn的矩阵的乘积C二AB定义为cij,k=0,公式中的u定义为按位力加1定义为按位乘。设无向图G如图所示。试画出该图的邻接矩阵和关联矩阵.8. 设有一个连通网络如图所示。试按如下格式，应用Krusk

17、al算法给出在构造最小生成树过程中顺序选出的各条边。(完整word版)第八章试题（始顶点号，终顶点号，权值）（，,）（,，）（，）（,）（,，）9. 设有一个连通网络如图所示。试采用prim算法从顶点0开始构造最小生成树.（写出加入生成树顶点集合S和选择边Edge的顺序）11S顶点号Edge（顶点，顶点，权值）0(,)0（,，）0（,，）0（，）0（，）010. 计算连通网的最小生成树的Dijkstra算法可简述如下：将连通网所有的边以方便的次序逐条加入到初始为空的生成树的边集合T中。每次选择并加入一条边时，需要判断它是否会与先前加入T中的边构成回路.如果构成了回路，则从这个回路中将权值最大的

18、边退选。如果以邻接矩阵作为连通网的存储结构（仅使用矩阵的上三角部分），并在邻接矩阵的下三角部分记录最小生成树的边信息.试以如下所示的图G为例,画出构造出最小生成树及其邻接矩阵，并在括号内填入每次选择的边和可能去掉的边。(016g1421-059g19Edge=06gg018110260丿选择的边去掉的边（顶点，顶点，权值）（顶点，顶点，权值）(）(）（,）（,）（,）（,）（,）（,）（,）（,）（,）（,）（,）（,）（,）（,）（,）（,）,）（,11. 有八项活动，每项活动要求的前驱如下:活动A0A1A2A3A4A5A6前驱无前驱A0A0A0,A2A1A2,A4A3A7A5,A6(1)

19、试画出相应的A0V网络，并给出一个拓扑排序序列。(2) 试改变某些结点的编号，使得用邻接矩阵表示该网络时所有对角线以下的元素全为0。12. 试对下图所示的AOE网络(1)这个工程最早可能在什么时间结束。(2)确定哪些活动是关键活动.画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成.13. 设带权有向图如图所示。试采用Dijkstra算法求从顶点0到其他各顶点的最短路径和最短路径长度。14.一项工程由六个子工程p1,p2,p6组成。这些子工程之间有下列关系：p1p2,p3p6,p4p3,p2p6,p43，Ee00151915192938El170151927273738如果活动k

20、的最早可能开始时间Ee(k)与最迟允许开始时间El(k)相等，则该活动是关键活动。本题的关键活动为1,3,2，5，它们组成关键路径。这些关键活动中任一个提前完成，整个工程就能提前完成。整个工程最早在43天完成。由关键活动组成的AOV网络如图所示。13.带权有向图如图所示:应用Dijkstra算法求从顶点V。到其他各顶点的最短路径Path和最短路径长度Len的步骤如下：步骤V0V1V2V3V4动作PathLenPathLenPathLenPathLen1VV4ooVV7oo选VV01VV4VVV803VV7oo01参照V调整201VV4012VVV803VV7oo1选VV01VV4012VVV8

21、03VV7VVV1203参照V调整301VV4012VVV803VV7034VVV123选VVV01VV4012VVV803VV7034VVVV10012参照V调整401VV0114012VVV0121803VV70124VVVV01T41102选VVVV01T414. 图G为可能的施工顺序有：p1,p2,p4，p3,p5，p6p1,p4,p2,p3，p5,p6p4，p5,p1,p3，p2，p615. 该图的强连通分量分别为：五、算法分析题1. 已知有向图的邻接矩阵表示及其一个算法描述如下:0111100100A=0001111000（00110丿constintMaxVertices=5；s

22、tructGraph/图的邻接矩阵表示intEdgeMaxVerticesMaxVertices;/有向图邻接距阵intCurrentNode;/有向图当前结点数intCurrentEdges;/当前边数intunknown(inti)intd=0;for(intj=0;jCurrentNode；j+)if(Edgeij！=0)d+；if(Edgeji！=0)d+；returnd;(1) 若定义图的一个对象GraphG,则执行操作G。unknown(3)后的返回值是多少？(2) 试说明该算法的功能及时间复杂度.2. 已知有向图的邻接矩阵表示及其一个操作算法描述如下：r0110100000A=0

23、00111100000010丿constintMaxVertices=5;structGraph/图的邻接矩阵表示intEdgeMaxVerticesMaxVertices；/有向图邻接距阵intCurrentNode；/有向图当前结点数intCurrentEdges;/当前边数voidunknown(inti)intd,j；d=0；for(j=0；jstructVertex/邻接表中顶点的定义Typedata；Edge*adj；;templateclassTypestructGraph/邻接表VertexType*NodeTable;/顶点表intNumVertices；/当前顶点个数int

24、NumEdges;/当前边数intDegreeMaxVertices;/各个顶点的度的记录数组/下列算法是计算有向图中各个顶点的度，并保存在数组Degree中。请在处/填入合适的内容，使其成为一个完整的算法。voidFindDegree()inti;Edgep=NULL;for(i=0;iNumVertices;i+)Degreei=(1);for(i=0;iNumVertices;i+)for(p=NodeTablei.adj；p！=NULL；p=plink)(2);(3)；;4. 已知有向图的邻接表类的表示的形式描述如下：structEdge/邻接表中边结点的定义intdest;/邻接的结

25、点floatcost;/边的权值Edgelink;templateclassTypestructVertex/邻接表中顶点的定义Typedata;Edge*adj;templateNodeTable;/顶点表intNumVertices;/当前顶点个数intNumEdges;/当前边数intDegreeMaxVertices;/各个顶点的度的记录数组/下列算法是计算有向图G中一个顶点Vj的入度.请在处填入合适的内容,/使其成为一个完整的算法。voidFindDegree(inti)intdeg,j;Edgep=NULL；deg=0；for(j=0;jNumVertices;j+)p=NodeT

26、ablej.adj；while(1)p=p-link;if(p=NULL)break;if(p!=NULL)(2);returndeg;5. 已知有向图的邻接表类的表示的形式描述如下：21structEdgeintdest;floatcost;Edge*link;templateclassTypestructTypedata;Edge*adj;templateclassTypestructVertex=NumVertices)cout”错误输入”link=p-link;else(2);deletep;de+;NumEdges=NumEdges-de;6. 已知带权图的邻接矩阵表示和邻接表类表示

27、的形式描述分别如下：(1)邻接矩阵的定义#defineINFINITYINT_MAX/INT_MAX为最大整数，表示constintMaxVertices=20；templateclassTypestructAdjMatrixTypeNodeTable;/顶点表定义floatarrMaxverticesMaxVertices；/邻接矩阵定义intNumVertices;intNumEdges;；(2)邻接表定义structEdgeintdest;floatcost；Edgelink；;templatestructTypedata;Edgeadj；templateclassTypestructV

28、ertexType*NodeTable；intNumVertices；/当前顶点个数/当前边数/邻接表中边结点的定义/邻接的结点/边的权值Vertex/邻接表中顶点的定义AdjTable/邻接表/顶点表/当前顶点个数/当前边数intNumEdges;/下列算法是根据一个图的邻接矩阵建立该图的邻接表，请在处填入合适/的内容，使其成为一个完整的算法。AdjTable*convertM()/将图的邻接矩阵(用this指针指示)转换为邻接表，函数返回邻接表的地址。AdjTableTypeA;Edge*e；ANodeTable=newVertexTypeNumVertices；A-NumEdges=Nu

29、mEdges;ANumVertices=NumVertices；for(inti=0;iNumVertices;i+)ANodeTablei.data=NodeTablei；A-NodeTablei.adj二(1);for(intj=0;jNumVertices;j+)if(arrij！=INFINITYarrij!=0)e=newEdge；(完整word版)第八章试题e-dest=j;e-cost二(2);e-link=A一NodeTablei.adj;(3)returnA；7. 已知带权图的邻接矩阵表示和邻接表类表示的形式描述分别如下:(1)邻接矩阵的定义#defineINFINITYIN

30、T_MAX/INT_MAX为最大整数，表示constintMaxVertices=20;templatestructTypedata;Edge*adj;；templateclassTypestructVertexType*NodeTable；intNumVertices；/当前顶点个数/当前边数/邻接表中边结点的定义/邻接的结点/边的权值Vertex/邻接表中顶点的定义AdjTable/邻接表/顶点表/当前顶点个数/当前边数intNumEdges；/下列算法是根据一个图的邻接表存储结构建立该图的邻接矩阵存储结构,/请在处填入合适的内容，使其成为一个完整的算法AdjMatrixType*conv

31、ertAL()/将图的邻接表(用this指针指示)转换为邻接矩阵，函数返回邻接矩阵的地址.AdjMatrixNodeTable=newVertexTypeNumVertices；A-arr=newfloatMaxverticesMaxVertices；A一NumEdges=NumEdges;A-NumVertices=NumVertices;for(i=0；iNumVertices;i+)(完整word版)第八章试题for(j=0;jNodeTablei二(1);for(i=0;iNumVertices;i+)p=NodeTableioadj;while(p!=NULL)A一arrip一des

32、t二(2);(3)8. 已知图的邻接表和逆邻接表的形式描述如下：structEdge/结点定义intdest;floatcost;Edge*link;templatestructVertexTypedata;Edge*adj;templatestructGraphVertexTypeNodeTable;VertexNumVertices;for(i=0;iNumVertices;i+)OppositNodeTablei。data=NodeTablei.data;OppositNodeTablei.adj=NULL;for(i=0;idest二i;q-cost=p-cost;(1);（完整wor

33、d版）第八章试题OppositNodeTablepdest.adj=q;(2);参考答案：1.1) 执行操作后的返回值是5。2) 算法的功能是计算有向图中一个顶点的度.算法的时间复杂度是0(n),n为图的顶点个数。/2分/2分/2分2.执行操作G.unknown(3)后，图的邻接矩阵为：/3分3.4.5.6.7.8.0000100001000000000n0100丿算法的功能是从图中删除所有与某个顶点相关的边。填空结果(1)0(2) Degreep-dest+(3) Degreei+填空结果(1)p!=NULL&(2)deg+;填空结果(1)p!=NULL&(2)NodeTablej。p/3分

34、/2分/2分/2分dest！=ip-dest!=iadj=plink；填空结果(1)NULL(2) arrij(3) ANodeTablei。adj二e填空结果(1) NodeTablei。data(2) pcost(3)p=plink注:(2),(3)/3分互换也正确)/3分/3分/3分/2分/2分/2分/2分/2分/2分填空结果(1)q一link=OppositNodeTablep一dest。adj/3分(2)p=p-link/3分27六、算法设计题1. 试编写函数用邻接表存储结构实现template：GetFirstNeighbor(intv)/给出顶点位置为v的第一个邻接顶点的位置，如

35、果找不到，则函数返回一1if(v!=1)Edgep=NodeTable(v).adj；/4分if(p!=NULL)returnp-dest;/4分return-1;2. 算法实现如下templateAdjTableNumVertices;for(i=0;iNodeTablei。data;NodeTablei。adj二NULL;cinNumEdges;for(i=0；itailheadweight;k=GetVertexPos(tail)；j=GetVertexPos(head);p=newEdge;p一dest二j;p-cost二weight;p一link=NodeTablek.adj;NodeTablek。adj=p;3. 算法实现如下templateclassTypeintAdjTableType：:GetNextNeighbor(intv,intw)/给出顶点v的邻接顶点w的下一个邻接顶点的位置，若没有下一个邻接顶点，则/函数返回1if(v!=-1)Edge*p=NodeTablev.adj；while(p!=NULL)if(p-dest=wplink!=NULL)returnp-linkdest;elsep=plink;return-1;