《数据结构第六章》由会员分享，可在线阅读，更多相关《数据结构第六章（2页珍藏版）》请在金锄头文库上搜索。
1、一.填空题1 图有邻接矩阵，邻接表_等存储结构，遍历图有深度优先搜索J度优先搜索_等方法。2. 己知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是_将邻接矩阵的第i行 全部置0_03. 如果有n个顶点的图是一个坏，则它有n_棵生成树。4. 图的BFS生成树的树高比DFS生成树的树高_小或相等。5 拓扑排序算法是通过重复选择具有0 个前驱顶点的过程来完成。1 00 01 01 1二、选择题y 11 11. 在一个图中，所有顶点的度数之和等于图的边数的（）倍。A.l/2 B. 1 C. 2D.4J J2. 图的邻接矩阵如图7.1所示，根据算法，则从顶点坯出发，按深度优先遍100010 10
2、历的结点序列是（）110 0KVqV2V4V3 V1V5 v6B.v0 V1V3V5 v6 v4 v20（）闪1；2内珂1；6丙.刃）珂1?3%172丙）0011013.深度优先遍历类似于二叉树的（A）；广度优先遍历类似于二叉树的（D）。110 0 0 10A.先序遍历 B.中序遍历C.后序遍历 D.层次遍历 4.下面（）算法可以判断出一个有向图是否有环。A.求最小生成树B.拓扑排序C.求最短路径D.求关键路径三、简答题1对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判断下列有关问题？（D图中有多少条边？（2）任意两个顶点i和j是否有边相连？（3）任意一个顶点的度是多少？答：对于
3、n个顶点的无向图和有向图，用邻接矩阵表示时：（1）设m为矩阵中非零元素的个数，那么无向图的边数=m/2,有向图的边数=m。（2）无论是有向图还是无向图，在矩阵中第i行，第j列的元素若为非零值，则该两顶点 有边相连。（3）对于无向图，任一顶点i的度为第i行中非零元素的个数。对于有向图，任一顶点i 的入度为第i列中非零元素的个数，出度为第i行中非零元素的个数，度为入度出度 之和。对于n个顶点的无向图和有向图，用邻接表表示时：（1）对于无向图，图中的边数二边表中结点总数的一半。对于有向图，图中的边数=边表 中结点总数。（2）对于无向图，任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若表中的 a
4、djvex域有另一顶点位置的结点，则表示有边相连。对于有向图，则表示有出边相 连。（3）对于无向图，任意一个顶点的度则由该顶点的边表中结点的个数来决定。对于有向 图，任意一个顶点的出度由该顶点的边表中结点的个数来决定，入度则需遍历各顶 点的边表。（用逆邻接表可容易地得到其入度。）2.对于一个图进行遍历可以得到不同的遍历序列，简述导致遍历序列不唯一的因素。答：导致对一个图进行遍历而得到的遍历序列不惟一的因素有许多，首先，遍历的出发顶点 选择得不惟一，得到的遍历序列显然不是惟一的。即使遍历的出发顶点相同，采用的遍历方 法若不相同，则得到的结呆也是不相同的。另外，即使遍历的出发顶点相同，并且采用同一 种遍历方法，若图的存储结构不相同，则得到的结呆也可能是不相同的。四、编程题1. 写出1、2、2、3、4、5这六个数字的所有排列（提示：将六个数字看成是六个结点），要 求4不能在第三位，3、5不能相连。2. 七桥问题（1）.存储并输出上图。（2）.找出上图中所有闭合路径，并据此证明：不存在一条路径，使从某一定点出发，不重 不漏的经过途中全部七条连线。
