中国铁道出版社数据结构(第二版)单元8练习参考答案

1、单元练习判断题(下列各题，正确的请在前面的括号内打V；错误的打X)(V)(1)图可以没有边，但不能没有顶点。(X)(2)在无向图中，(V,V2)与(V2,V)是两条不同的边。(X)(3)邻接表只能用于有向图的存储。(V)(4)一个图的邻接矩阵表示是唯一的。(X)(5)用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。(X)(6)有向图不能进行广度优先遍历。(V)(7)若一个无向图的以顶点V为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。(V)(8)存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角(或下三角)部分就可以了。(X)(9)

2、用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。(V)(10)若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。填空题图常用的存储方式有邻接矩阵和邻接表等。图的遍历有：深度优先搜和广度优先搜等方法。有条边的无向图邻接矩阵中，的个数是n有向图的边也称为弧。图的邻接矩阵表示法是表示顶点之间相邻关系的矩阵。有向图用邻接矩阵存储，其第行的所有元素之和等于顶点的出度。n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为：OW)。n个顶点e条边的图若采用邻接表存储，则空间复杂度为：O(n+e)。设有一稀疏图，则采用邻接表存储比较节

3、省空间。设有一稠密图，则采用邻接矩阵存储比较节省空间。图的逆邻接表存储结构只适用于有向图。个顶点的完全无向图有条边。有向图的邻接表表示适于求顶点的出度。有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点V.的入度。1对于具有n个顶点的图，其生成树有且仅有n-1条边。对n个顶点，e条弧的有向图，其邻接表表示中，需要n+e个结点。从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的遍历。无向图的邻接矩阵一定是对称矩阵。（19）一个连通网的最小生成树是该图所有生成树中权最小的生成树。（20）若要求一个稠密图G的最小生成树，最好用Prim算法来求解。三选择题TOC o 1

4、-5 h z（）在一个图中，所有顶点的度数之和等于图的边数的倍。（）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。（）对于一个具有个顶点的有向图的边数最多有（）。（）在一个具有个顶点的无向图中，要连通全部顶点至少需要（）条边。（）有个结点的有向完全图有条边。（）深度优先遍历类似于二叉树的。.先序遍历.中序遍历.后序遍历.层次遍历7）广度优先遍历类似于二叉树的（D。.先序遍历.中序遍历.后序遍历.层次遍历8）任何一个无向连通图的最小生成树（A。.只有一棵.一棵或多棵.定有多棵可能不存在（）无向图顶点的度是关联于该顶点（）的数目。.顶点.边序号.下标D（0有个顶点的无向图的邻接矩阵

5、是用（.）数组存储。.一维.行歹U.任意行列.行任意列（1对于一个具有个顶点和条边的无向图，采用邻接表表示，则表头向量大小为（）。）。.邻接表表示法.邻接表和逆邻接表表示法12）在图的表示法中，表示形式唯一的是（.邻接矩阵表示法逆邻接表表示法（3在一个具有个顶点条边的图中，所有顶点的度数之和等于（）。14）下列图中，度为3的结点是（B）。.连通图强连通图生成树无环图（16）如下图所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点序列为（D）。（17）如下图所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序列为（A）。18）最小生成树的构造可使用（A）算法。.算法.卡尔算法

6、.哈夫曼算法.迪杰斯特拉算法19）下面关于图的存储结构的叙述中正确的是（A）。用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关（0连通分量是（）的极大连通子图。.树.图无向图.有向图四.应用题（30分）有向图如下图所示，画出邻接矩阵和邻接表解：（1）邻接矩阵101101,2000102）邻接表2已知一个无向图有6个结点，9条边，这9条边依次为（0，1）,（0，2）,（0，4）,（0，5），（1，2），

7、（2，3），（2，4），（3，4），（4，5）。试画出该无向图，并从顶点0出发，分别写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。（5分）解：从顶点0出发的深度优先搜索遍历的结点序列：012345（答案不唯一）从顶点0出发的广度优先搜索遍历的结点序列：012453（答案不唯一）3.已知一个无向图的顶点集为：a,b,c,d,e，其邻接矩阵如下，画出草图，写出顶点a出发按深度优先搜索进行遍历的结点序列。（5分）01001100100001101101101102）深度优先搜索：abdce广度优先搜索：abedc答案不唯一）答案不唯一），并画出它的一棵最小生成树。08101108030131

8、03040110407013070已知某图的邻接矩阵如图,解：（1）0110011001100110（）画出相应的图；2）要使此图为完全图需要增加几条边。2）完全无向图应具有的边数为：n*（n-l）l/2=4*（4-l）/2=6，所以还要增加2条边（如右图）。3已知如图所示的有向图，请给出该图的33出度；顶点123456入度321122出度022313LJK5-EI*1*A1iA3OOOOOO-)0010001000I0Q0I100000.110010-如图，请完成以下操作：2）写出无向带权图的邻接矩阵；（）设起点为，求其最小生成树。33可以直接由原一0000000000邻）命(解（35a5g

9、00008548860g5g206刃6302刃g7038855076543505000000888一0000给定下列网解：邻接矩阵（2）最小生成树g12gg4gg12g20g89gg20g15gg12gg15ggg1048ggg6gg9gg6gggg1210ggg五程序题填空题图G为有向无权图，试在邻接矩阵存储结构上实现删除一条边的操作：DeleteArc（G,v,w）。若无顶点v或w,返回“”；若成功删除，则边数减，并返回“”。（提示：删除一条边的操作，可以将邻接矩阵的第i行全部置0）解：在邻接矩阵表示的图上删除边（或六算法题1编写一个无向图的邻接矩阵转换成邻接表的算法。2.以知有n个顶点的

10、有向图邻接表，设计算法分别实现以下功能:（1）求出图G中每个顶点的出度、入度。（2）求出G中出度最大的一个顶点，输出其顶点序号。3）计算图中度为0的顶点数。1.解：本题思想是逐个扫描邻接矩阵的各个元素，若第i行第j列的元素为1,贝I相应的邻接表的第i个单链表上增加一个j结点。（）求出度的思想：计算出邻接表中第个单链表的结点数即可。求入度的思想：计算出邻接表中结点的结点数即可。2）求最大度的算法3）求度为0的顶点数的算法已知如图所示的有向图，请给出该图的顶点123456入度321122出度022313模拟考题度和出度;解：(1)邻接矩阵(2)从A出发的深度优先遍历的序列:0110000，ABDCEGF（不唯一）100100010010000110110000100100010010000110已知图的邻接表如下，以顶点为出发点，完成下列问题:(