数据结构习题第7章

第7章图一、选择题1.在一个图中，所有顶点的度数之和等于图的边数的（）倍。A．1/2B.1C.2D.42.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A．1/2B.1C.2D.43.有8个结点的无向图最多有（）条边。A．14B.28C.56D.1124.有8个结点的无向连通图最少有（）条边。A．5B.6C.7D.85.有8个结点的有向完全图有（）条边。A．14B.28C.56D.1126.用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。A．栈B.队列C.树D.图7.用邻接表表示图进行深度优先遍历时，通常是采用（）来实现算法的。A．栈B.队列C.树D.图8.已知图的邻接矩阵如下，根据深度优先搜索算法，从顶点0出发的遍历序列是（）9.图的邻接矩阵同题8，根据广度优先搜索算法，从顶点0出发的遍历序列是（）A．0243165B.0135642C.0123465D.012345610.如果从无向图的任一顶点出发进行一次深度优先遍历就能访问图中所有顶点，则该图一定是（）。A.含有回路B.强连通图C.非连通图D.连通图11.在一个带权连通图G中，权值最小的边一定包含在G的（）生成树中。A．最小B．任何C．深度优先D．广度优先12.用邻接表存储图所用空间的大小（）。A.只与图的顶点数有关B.只与图的边数有关C.与图的顶点数和边数都有关D.与图的边数的平方有关13.具有n个顶点的连通无向图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlognA．0243156B.0136542C.0423165D.0134256010001110110000101101011001100100011001001101111014.已知图的邻接表如下，根据深度优先搜索算法，从顶点0出发的遍历序列是（）15.已知图的邻接表如下，根据广度优先搜索算法，从顶点0出发的遍历序列是（）16.深度优先遍历类似于二叉树的（）A．先序遍历B.中序遍历C.后序遍历D.层次遍历17.广度优先遍历类似于二叉树的（）A．先序遍历B.中序遍历C.后序遍历D.层次遍历18.任何一个无向连通图的最小生成树（）A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题1.图的存储结构最常用的有、，遍历图的方法有：、等。2.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的。3.如果n个顶点的图是一个环，则它有棵生成树。4.n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为。5.n个顶点e条边的图，若采用邻接表存储，则空间复杂度为。6.设有一稀疏图G，则G采用存储较省空间。7.设有一稠密图G，则G采用存储较省空间。8.图的逆邻接表存储结构只适用于图。9.图的深度优先遍历序列惟一的。10.n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为；若采用邻接表存储时，该算法的时间复杂度为。11.n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为；若采用邻接表存储，该算法的时间复杂度为。A．0132B.0231C.0321D.0123A．0321B.0123C.0132D.031212.用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为；用克鲁斯卡尔(Kruskal)算法的时间复杂度是。13.若要求一个稀疏图G的最小生成树，最好用算法来求解。14.若要求一个稠密图G的最小生成树，最好用算法来求解。15.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。16.求最短路径的Dijkstra算法的时间复杂度是。17.拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。三、判断题1.一个图的邻接矩阵表示是唯一的，邻接表表示也是唯一的。（）2.有向图用邻接矩阵存储，顶点i的入度等于矩阵中第i行非零元素个数之和。（）3.若一个图的邻接矩阵不是对称矩阵，则该图一定是有向图。（）4.一个无向图的邻接矩阵一定是对称矩阵。（）5.图的简单路径是指顶点和边都不重复的路径。（）6.连通图的生成树是一个极小连通子图。（）7.对于非连通的无向图进行深度优先搜索可以得到一个生成森林。（）8.BFS生成树的高度一定小于DFS生成树的高度。（）9.拓扑排序可以判断一个有向图是否存在回路。（）四、简答题1.表示有50个顶点、15条边的有向图的邻接矩阵有多少个矩阵元素？该矩阵是否是稀疏矩阵？2.有n个顶点的无向图最多有几条边，最少有几条边；如果该图是连通图，则该图最多有几条边，最少有几条边？3.有n个顶点的有向图最多有几条边，最少有几条边；如果该图是强连通图，则该图最多有几条边，最少有几条边？4、对下面所示的有向图，请回答：该图是强连通图吗？若不是，请画出其强连通分量。BCAEDF五、应用题1.已知如图所示的有向图，请给出该图的:（1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表。2.请对下图的无向带权图：（1）写出它的邻接矩阵，按普里姆算法求其最小生成树；（2）写出它的邻接表，按克鲁斯卡尔算法求其最小生成树。3.已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。4.试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。顶点123456入度出度5.给定下列网G:(1)试着找出网G的最小生成树，画出其逻辑结构图；(2)用两种不同的表示法画出网G的存储结构图；(3)用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。六、算法题1.编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。2.在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操作。（如果要删除所有从第i个顶点出发的边呢？提示：将邻接矩阵的第i行全部置0）3.试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。4.采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。（注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。注2：此题可参见严蔚敏习题集P207-208中有关按“路径”遍历的算法基本框架。）