数据结构单元练习8.doc

单元练习8` 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ） （√）（1）图可以没有边，但不能没有顶点。 （ㄨ）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。 （ㄨ）（3）邻接表只能用于有向图的存储。 （√）（4）一个图的邻接矩阵表示是唯一的。 （ㄨ）（5）用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。 （ㄨ）（6）有向图不能进行广度优先遍历。 （√）（7）若一个无向图的以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。 （√）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。 （ㄨ）（9）用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。 （√）（10）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。 二．填空题 图常用的存储方式有邻接矩阵和 邻接表 等。 图的遍历有： 深度优先搜 和广度优先搜等方法。 有n条边的无向图邻接矩阵中，1的个数是 _2n____。 有向图的边也称为 _ 弧___ 。 图的邻接矩阵表示法是表示 __顶点____之间相邻关系的矩阵。 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 __出度____。 n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为： O（n2） 。 n个顶点e条边的图若采用邻接表存储，则空间复杂度为： O（n+e） 。 设有一稀疏图G，则G采用 _邻接表____存储比较节省空间。 设有一稠密图G，则G采用 _邻接矩阵____存储比较节省空间。 图的逆邻接表存储结构只适用于 __有向____图。 n个顶点的完全无向图有 n(n-1)/2_ 条边。 有向图的邻接表表示适于求顶点的 出度 。 有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点Vi的 入度 。 对于具有n个顶点的图，其生成树有且仅有 n-1 条边。 对n个顶点，e条弧的有向图，其邻接表表示中，需要 n+e 个结点。 从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图 的 遍历 。 无向图的邻接矩阵一定是 对称 矩阵。 一个连通网的最小生成树是该图所有生成树中 权 最小的生成树。 若要求一个稠密图G的最小生成树，最好用 Prim 算法来求解。 三．选择题 （1）在一个图中，所有顶点的度数之和等于图的边数的( C )倍。 A．1/2 B. 1 C. 2 （2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( B )倍。 A．1/2 B. 1 C. 2 （3）对于一个具有n个顶点的有向图的边数最多有（ B ）。 A．n B．n(n-1) C．n(n-1)/2 D．2n （4）在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。 A．n B．n+1 C． n-1 D．n/2 （5）有8个结点的有向完全图有( C )条边。 A．14 B. 28 C. 56 （6）深度优先遍历类似于二叉树的( A )。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 （7）广度优先遍历类似于二叉树的( D )。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 （8）任何一个无向连通图的最小生成树( A )。 A．只有一棵 B．一棵或多棵 C．一定有多棵 D．可能不存在 （9）无向图顶点v的度是关联于该顶点（ B ）的数目。 A．顶点 B．边 C．序号 D．下标 （10）有n个顶点的无向图的邻接矩阵是用（ B ）数组存储。 A．一维 B．n行n列 C．任意行n列 D．n行任意列 （11）对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（ C