资源描述：
《数据结构第5章图》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、1.选择题（1）在一个图屮，所有顶点的度数之和等于图的边数的（）倍。A.1/2B.1C.2D.4（2）在一个有向图屮，所有顶点的入度之和等于所有顶点的出度之和的（）倍。D.4D.n2)个非零元素。D.n2A.1/2B.1C.2（3）具有n个顶点的有向图最多有（）条边。A.nB.n（n-l）C.n（n+l）（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（A.nB.2（n-l）C.n/2（5）G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。A.7B.8C.9D.10（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图巾所有的顶点，则该图一定是（）
2、图。A.非连通B.连通C.强连通D.有向（7）下面（）算法适合构造一个稠密阁G的最小生成树。A.Prim算法B.Kruskal算法C.Floyd算法D.Dijkstra算法（8）用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。A.栈B.队列C.树D.图（9）用邻接表表示图进行深度优先遍历时,通常借助（）来实现算法。A.栈B.队列C•树D.图（10）深度优先遍历类似于二叉树的（)0A.先序遍历B.中序遍历C.后序遍历D.层次遍历（11）广度优先遍历类似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历D.大或相等（12）图的BFS生成树的树高比DFS
3、生成树的树高（）。A.小B.相等C.小或相等（13）己知图的邻接矩阵如图6.25所示，则从顶点0出发按深度优先遍历的结果是01101011100011A.0243156B.0136542C.0134256D.036154211101010010010000110110100110100010（14）己知图的邻接表如图6.26所示，则从顶点0出发按广度优先遍历的结果是（）,按深度优先遍历的结果是（）。x>--111+d21•H31/1uA.0132--101T-l21--101二H»13/1C.0321vs--1o12
4、Z3B.0231D.0123D.求关键路径阁6.26邻
5、接表（15）下面（）方法可以判断出一个有向图是否有环。A.深度优先遍历B.拓扑排序C.求最短路径1.应用题（1）己知如图6.27所示的有向图，请给出：①每个顶点的入度和出度；②邻接矩阵；③邻接表；④逆邻接表。顶点123456入度321122出度022313—01001•10010010001000100000001010'01100.(4)逆邻接表(3)邻接表12356(2)己知如图6.28所示的无向网,①邻接矩阵；②邻接表；③最小生成树oo43OOOOOOoooo4oo559OOoooo35OO5OOOOoo5oo55OO7654oo9OO7OO3ooooooooOO6
6、3OO2ooooooOO5OO?Avoo6oooo54OOoo6ooc3c5b5c5d7e3f2d4请给出:d5d5e7f3g2h6g6(3)已知图的邻接矩阵如6.29所示。先生成树和广度优先生成树。图6.28无试分别itfl出自顶点1出发进行遍历所得的深度优000000000011001000100000100001000010000100001000010000100001101010000100001000010000000100）010010000图6.29邻接矩图6.30有向M(4)有向网如图6.30所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的S短路径，
7、完成表6.9。Xi=li=2i=3i:4i=5i=6b15（a，b）15（a，b）15（a，b）15（a，b）15（a，b）15（a，b）c2（a，c）d12（a，d）12（a，d）11（a,c,f,d）11（a，cXd）eoo10（a，c，e）10（a,c,e）foo6（a，c，f）gooCO16（a，c，f，g）16（a，c，f，g）14（a，c,f，d,g）s终点集{a，c}{a，c，f}{a，c，f，e}{a，c，f，e，d}{a，c，f，e，d，g}{a，c，f，e，d，g，b}10(5)试对图6.31所示的AOE-网：①求这个工程最早可能在什么时间结束；②求每
8、个活动的S早开始时间和最迟开始时间；③确定哪些活动是关键活动图6.31AOE-网【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间设和最迟允许开始时间V/。然后再计算各个活动的最单可能开始吋间e和最迟允许开始时间/，根据/-e=0?来确定关键活动，从而确定关键路径。123456Ve01915293843VI01915373843<1，2〉<1，3〉<3,2〉<2,4><2,5〉<3,5〉<4,6〉<5,6〉e00151919152938l170152719273738-e1700801280此工程最早完成时间为43。关键路
