《数据结构单元8练习参考答案.doc》由会员分享，可在线阅读，更多相关《数据结构单元8练习参考答案.doc（12页珍藏版）》请在金锄头文库上搜索。
1、单元练习8一判断题（下列各题，正确的请在前面的括号内打；错误的打 ）（）（1）图可以没有边，但不能没有顶点。（）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。（）（3）邻接表只能用于有向图的存储。（）（4）一个图的邻接矩阵表示是唯一的。（）（5）用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。（）（6）有向图不能进行广度优先遍历。（）（7）若一个无向图的以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。（）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。（）（9）用邻接表法
2、存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。（）（10）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。二填空题（1） 图常用的存储方式有邻接矩阵和 邻接表 等。（2） 图的遍历有： 深度优先搜 和广度优先搜等方法。（3） 有n条边的无向图邻接矩阵中，1的个数是 _2n_。（4） 有向图的边也称为 _ 弧_ 。（5） 图的邻接矩阵表示法是表示 _顶点_之间相邻关系的矩阵。（6） 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 _出度_。（7） n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为： O（n2）
3、。（8） n个顶点e条边的图若采用邻接表存储，则空间复杂度为： O（n+e） 。（9） 设有一稀疏图G，则G采用 _邻接表_存储比较节省空间。（10） 设有一稠密图G，则G采用 _邻接矩阵_存储比较节省空间。（11） 图的逆邻接表存储结构只适用于 _有向_图。（12） n个顶点的完全无向图有 n(n-1)/2_ 条边。（13） 有向图的邻接表表示适于求顶点的 出度 。（14） 有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点Vi的 入度 。（15） 对于具有n个顶点的图，其生成树有且仅有 n-1 条边。（16） 对n个顶点，e条弧的有向图，其邻接表表示中，需要 n+e 个结点。（17） 从
4、图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的 遍历 。（18） 无向图的邻接矩阵一定是 对称 矩阵。（19） 一个连通网的最小生成树是该图所有生成树中 权 最小的生成树。（20） 若要求一个稠密图G的最小生成树，最好用 Prim 算法来求解。三选择题（1）在一个图中，所有顶点的度数之和等于图的边数的( C )倍。 A1/2 B. 1 C. 2 D. 4（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( B )倍。 A1/2 B. 1 C. 2 D. 4（3）对于一个具有n个顶点的有向图的边数最多有（ B ）。 An Bn(n-1) Cn(n-1
5、)/2 D2n（4）在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。 An Bn+1 C n-1 Dn/2（5）有8个结点的有向完全图有( C )条边。 A14 B. 28 C. 56 D. 112（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
6、个顶点的无向图的邻接矩阵是用（ B ）数组存储。 A一维Bn行n列 C任意行n列 Dn行任意列（11）对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（ C ）。 An-1Bn+1 Cn Dn+e（12）在图的表示法中，表示形式唯一的是（ A ）。 A邻接矩阵表示法 B邻接表表示法 C逆邻接表表示法 D邻接表和逆邻接表表示法（13）在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（ C ）。 An Be C 2n D2e（14）下列图中，度为3的结点是（ B ）。12354 AV1 B. V2 C. V3 D. V412354（15）下列图是（ A ）。 A连通图
7、B. 强连通图 C. 生成树 D. 无环图（16）如下图所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点序列为（ D ）。abcfdeA a，b，e，c，d，fB a，c，f，e，b，dC. a，e，b，c，f，dD. a，e，d，f，c，b（17）如下图所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序列为（ A ）。abcfdeA. a，b，e，c，d，fB. a，b，e，c，f，dC. a，e，b，c，f，dD. a，e，d，f，c，b（18）最小生成树的构造可使用（ A ）算法。 Aprim算法 B卡尔算法 C哈夫曼算法 D迪杰斯特拉算法（19）下面关于图的存储
8、结构的叙述中正确的是（ A ）。A 用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关B 用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关 C 用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关 D 用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关（20）连通分量是（ C ）的极大连通子图。 A树 B图 C无向图D有向图四应用题（30分）1有向图如下图所示，画出邻接矩阵和邻接表解：（1）邻接矩阵 1 2 3 4 5（2）邻接表1235243541542 已知一个无向图有6个结点，9条边，这9条边依次为（0，1）,（0，2）,（0，4）,（0，5）
9、，（1，2），（2，3），（2，4），（3，4），（4，5）。试画出该无向图，并从顶点0出发，分别写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。（5分）231D045解：从顶点0出发的深度优先搜索遍历的结点序列：0 1 2 3 4 5（答案不唯一）从顶点0出发的广度优先搜索遍历的结点序列：0 1 2 4 5 3（答案不唯一）3 已知一个无向图的顶点集为：a，b，c，d，e，其邻接矩阵如下，画出草图，写出顶点a出发按深度优先搜索进行遍历的结点序列。（5分）解：acbed（1） （2）深度优先搜索：a b d c e （答案不唯一） 广度优先搜索： a b e d c （答案不唯一） 4网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。2543125431解： 最小生成树： 8 11 10 8 3 4 13 7 3 4 75. 已知某图G的邻接矩阵如图，（1）画出相应的图； （2）要使此图为完全图需要增加几条边。解：134242D31（1）（2） 完全无向图应具有的边数为：n*(n-1)1/2=4*(4-1)/2=6，所以还要增加2条边（如右图）。6已知如图所示的有向图，请给出该图的:（1） 每个顶点的入/出度；（2） 邻接表；（3） 邻接矩阵。解：（1） （2）顶点123456入度321122出度022313（3）7如图，请完成以下操作：（2
