数据结构习题第7章

《数据结构习题第7章》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一、选择题1.在一个图中，所有顶点的度数之和等于图的边数的（）倍。A.1/2B.1C.2D.4）倍。2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的A.1/2B.1C.2D.43.有8个结点的无向图最多有（A.14B.284.有8个结点的无向连通图最少有（A.5B.65.有8个结点的有向完全图有（A.14B.28）条边。C.56D.112）条边。C.7D.8）条边。C.56D.112）来实现算法的。D.图）来实现算法的。D.图6.用邻接表表示图进行广度优先遍历时，通常是采用（A.栈B.队列C.树7.用邻接表表示图进行深度优先遍历

2、时，通常是采用（A.栈B.队列C.树8.已知图的邻接矩阵如下，根据深度优先搜索算法，从顶点0出发的遍历序列是（A.0243156B.0136542C.0423165D.013425601111011001001100010011001101011010000110111000109.图的邻接矩阵同题8,根据广度优先搜索算法，从顶点0出发的遍历序列是（）A.0243165B.0135642C.0123465D.012345610.如果从无向图的任一顶点出发进行一次深度优先遍历就能访问图屮所有顶点，则该图一定是（）。A.含有lH］路B.强连通图C

3、.非连通图D.连通图11.在一个带权连通阁G中，权值最小的边一定包含在0的（）生成树中。A.最小B.任何C.深度优先D.广度优先12.用邻接表存储阁所用空间的大小（）。A.只与图的顶点数有关B.只与图的边数有关C.与图的顶点数和边数都有关D.与图的边数的平方有关13.具有n个顶点的连通无向图，其边的个数至少为（）。A.n-1B.nC.n+1D.nlogn6.己知图的邻接表如不，根据深度优先搜索算法，从顶点0出发的遍历序列是（123/02/V013/V2—0—2/A.0132B.0231C.0321D.01237.已知图的邻接表如下，根据广度优

4、先搜索算法，从顶点0出发的遍历序列是（）16.深度优先遍历类似于二叉树的（)C.A.先序遍历B.中序遍历17.广度优先遍历类似于二叉树的（)A.先序遍历B.中序遍历C.18.任何一个无向连通图的最小生成树(A.只有一棵B.—棵或多棵C（注，生成树不唯一，但最小生成树唯一，A.0321B.0123C.0132D.0312后序遍历D.层次遍历后序遍历D.层次遍历）一定有多棵D.可能不存在即边权之和或树权最小的情况唯一）二、填空题1.图的存储结构最常用的有、,遍历图的方法有：、等。2.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的。3

5、.如果n个顶点的图是一个环，则它有棵生成树。4.n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为。5.n个顶点e条边的图，若采用邻接表存储，则空间复杂度为。6.设有一稀疏图G,则G采用存储较省空间。7.设有一稠密图G,则G采用存储较省空间。8.阁的逆邻接表存储结构只适用于阁。9.图的深度优先遍历序列惟一的。10.n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为；若采用邻接表存储时，该算法的时间复杂度为。1.n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的吋间复杂度为；若采用邻接表存储，该算法的时间复杂度为。2.用

6、普里姆（Prim）算法求具有n个顶点e条边的图的最小生成树的时间复杂度力;用克鲁斯卡尔（Kruskal）算法的时间复演度是。3.若要求一个稀疏图G的最小生成树，最好用算法来求解。4.若要求一个稠密图G的最小生成树，最好用算法来求解。5.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。6.求最短路径的Dijkstra算法的时间复杂度是。7.拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。三、判断题1.一个图的邻接矩阵表示是唯一的，邻接表表示也是唯一的。（）2.有向阁用邻接矩阵存储，顶点i的入度

7、等于矩阵中第i行非零元素个数之和。（）3.若一个图的邻接矩阵不是对称矩阵，则该图一定是有向图。（）4.一个无向图的邻接矩阵一定是对称矩阵。（）5.图的简单路径是指顶点和边都不重复的路径。（）6.连通图的生成树是一个极小连通子图。（）7.对于非连通的无向阁进行深度优先搜索可以得到一个生成森林。（）8.BFS生成树的高度一定小于DFS生成树的高度。（）9.拓扑排序可以判断一个有向图是否存在冋路。（）四、简答题1.表示有50个顶点、15条边的冇向图的邻接矩阵冇多少个矩阵元素？该矩阵是否是稀疏矩阵？2.有n个顶点的无向图最多有儿条边，最少有儿条边；如

8、果该图是连通图，则该图最多有几条边，最少有几条边？3.有n个顶点的有向图最多有几条边，最少有几条边；如果该图是强连通图，则该图最多有几条边，最少有几条边？4.对下面