数据结构习题第七章图答案

第7章图一.选择题1.A2.B3.A4.B5.D6.1B6.2D7.1B7.2C8.A9.A10.1C10.2BDE11.B12.1B12.2B12.3D13.B14.C15.C16.D17.D18.1C18.2C19.AB20.B21.1C21.2A21.3B21.4A22.A23.A24.D25.A26.A27.B28.D29.B30.A31.C32.B二.判断题1.√2.×3.×4.×5.×6.√7.×8.×9.×10.×11.√12.×13.√14.×15.×16.×17.√18.×19.×20.×21.×22.×23.×24.×25.×26.√27.×28.√29.×30.×31.√32.√33.×34.×35.×36.√37.×38.×39.×40.×41.√42.×43.×44.√45.×46.×47.×48.√49.×部分答案解释如下。2.不一定是连通图，可能有若干连通分量11.对称矩阵可存储上（下）三角矩阵14．只有有向完全图的邻接矩阵是对称的16.邻接矩阵中元素值可以存储权值21.只有无向连通图才有生成树22.最小生成树不唯一，但最小生成树上权值之和相等26.是自由树，即根结点不确定35.对有向无环图，拓扑排序成功；否则，图中有环，不能说算法不适合。42.AOV网是用顶点代表活动，弧表示活动间的优先关系的有向图,叫顶点表示活动的网。45.能求出关键路径的AOE网一定是有向无环图46.只有该关键活动为各关键路径所共有，且减少它尚不能改变关键路径的前提下，才可缩短工期。48．按着定义，AOE网中关键路径是从“源点”到“汇点”路径长度最长的路径。自然，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。三．填空题1.有n个顶点，n-1条边的无向连通图2.有向图的极大强连通子图3.生成树4.455.n(n-1)/26.7.98.n9.2(n-1)10.N-111.n-112.n13.N-114.n15.N16.317.2（N-1）18.度出度19.第I列非零元素个数20.n2e21.(1)查找顶点的邻接点的过程(2)O(n+e)(3)O(n+e)(4)访问顶点的顺序不同(5)队列和栈22.深度优先23.宽度优先遍历24.队列25.因未给出存储结构，答案不唯一。本题按邻接表存储结构，邻接点按字典序排列。25题（1）25题（2）26.普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法27.克鲁斯卡尔28.边稠密边稀疏29.O(eloge）边稀疏30.O(n2）O(eloge)31.(1）（Vi，Vj）边上的权值都大的数（2）1负值（3）为负边32.(1)n-1(2)普里姆(3)最小生成树33.不存在环34.递增负值35.16036.O(n2）37.50，经过中间顶点④38.7539.O(n+e）40.(1）活动（2）活动间的优先关系（3）事件（4）活动边上的权代表活动持续时间41.关键路径42.（1）某项活动以自己为先决条件（2）荒谬（3）死循环43.（1）零（2）Vk度减1，若Vk入度己减到零，则Vk顶点入栈（3）环44.（1）pnil(2)visited[v]=true(3)p=g[v].firstarc(4)p=p^.nextarc45.(1)g[0].vexdata=v(2)g[j].firstin(3)g[j].firstin(4)g[i].firstout(5)g[i].firstout(6)p^.vexj(7)g[i].firstout(8)p:=p^.nexti(9)pnil(10)p^.vexj=j(11)firstadj(g,v0)(12)notvisited[w](13)nextadj(g,v0,w)46.(1)0(2)j(3)i(4)0(5)indegree[i]==0(6)[vex][i](7)k==1(8)indegree[i]==047.(1)p^.link:=ch[u].head(2)ch[u].head:=p(3)top0(4)j:=top(5)top:=ch[j].count(6)t:=t^.link48.（1）V1V4V3V6V2V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，所以结果是不唯一的。本答案是按邻接点升序排列给出的。)（2）①top==-1②top=graph[j].count③graph[k].count==0四.应用题1．（1）G1最多n(n-1)/2条边，最少n-1条边(2)G2最多n(n-1)条边，最少n条边(3)G3最多n(n-1)条边，最少n-1条边(注：弱连通有向图指把有向图看作无向图时，仍是连通的)2．n-1，n3.分块对称矩阵4．证明：具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树（在图论中树定义为无回路的连通图）。KBAJEIDCFADFCEBKIJ5．证明：该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素（A[i][j]=1）自然是落到下三角矩阵中；命题的必要条件是要使上三角为0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。（对该类有向无环图顶点编号，应按顶点出度顺序编号。）6．设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n2，即顶点个数的平方，与图的边数无关。7．（1）n(n-1)，n(2)106，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律）（3）使用深度优先遍历，按退出dfs过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行dfs(v)未退出前，出现顶点u到v的回边，则说明存在包含顶点v和顶点u的环。8．(1)（2）开始结点：（入度为0）K1，K2，终端结点（出度为0）K6，K7。（3）拓扑序列K1，K2，K3，K4，K5，K6，K8，K9，K7K2，K1，K3，K4，K5，K6，K8，K9，K7规则：开始结点为K1或K2，之后，若遇多个入度为0的顶点，按顶点编号顺序选择。（4）8（4）邻接表和逆邻接表9．（1）注：邻接矩阵下标按字母升序:abcdefghi（2）强连通分量：（a），(d)，（h），(b，e，i，f，c，g）(3)顶点a到顶点i的简单路径：（abei），(acgi)，(acbei)91387542610．图G的具体存储结构略。邻接矩阵表示法，有n个顶点的图占用n2个元素的存储单元，与边的个数无关，当边数较少时，存储效率较低。这种结构下，对查找结点的度、第一邻接点和下一邻接点、两结点间是否有边的操作有利，对插入和删除顶点的操作不利。邻接表表示法是顶点的向量结构与顶点的邻接点的链式存储结构相结合的结构，顶点的向量结构含有n（n≥0）个顶点和指向各顶点第一邻接点的指针，其顶点的邻接点的链式存储结构是根据顶点的邻接点的实际设计的。这种结构适合查找顶点及邻接点的信息，查顶点的度，增加或删除顶点和边（弧）也很方便，但因指针多占用了存储空间，另外，某两顶点间是否有边（弧）也不如邻接矩阵那么清楚。对有向图的邻接表，查顶点出度容易，而查顶点入度却困难，要遍历整个邻接表。要想查入度象查出度那样容易，就要建立逆邻接表。无向图邻接表中边结点是边数的二倍也增加了存储量。十字链表是有向图的另一种存储结构，将邻接表和逆邻接表结合到一起，弧结点也增加了信息（至少弧尾，弧头顶点在向量中的下标及从弧尾顶点发出及再入到弧头顶点的下一条弧的四个信息）。查询顶点的出度、入度、邻接点等信息非常方便。邻接多重表是无向图的另一种存储结构，边结点至少包括5个域：连接边的两个顶点在顶点向量中的下标，指向与该边相连接的两顶点的下一条边的指针，以及该边的标记信息（如该边是否被访问）。边结点的个数与边的个数相同，这是邻接多重表比邻接表优越之处。11．已知顶点i，找与i相邻的顶点j的规则如下：在顶点向量中，找到顶点i，顺其指针找到第一个边结点（若其指针为空，则顶点i无邻接点）。在边结点中，取出两顶点信息，若其中有j，则找到顶点j；否则，沿从i发出的另一条边的指针（ilink）找i的下一邻接点。在这种查找过程中，若边结点中有j，则查找成功；若最后ilink为空，，则顶点i无邻接点j。12．按各顶点的出度进行排序。n个顶点的有向图，其顶点最大出度是n-1，最小出度为0。这样排序后，出度最大的顶点编号为1，出度最小的顶点编号为n。之后，进行调整，即若存在弧i，j，而顶点j的出度大于顶点i的出度，则将把j编号在顶点i的编号之前。本题算法见下面算法设计第28题。13．采用深度优先遍历算法，在执行dfs(v)时，若在退出dfs(v)前，碰到某顶点u，其邻接点是已经访问的顶点v，则说明v的子孙u有到v的回边，即说明有环，否则，无环。（详见下面算法题13）14．深度优先遍历序列：125967384宽度优先遍历序列：123456789注：（1）邻接表不唯一，这里顶点的邻接点按升序排列（2）在邻接表确定后，深度优先和宽度优先遍历序列唯一（3）这里的遍历，均从顶点1开始15．（1）V1V2V4V3V5V6（2）V1V2V3V4V5V616.(1)16题（3）宽度优先生成树（2）深度优先生成树为节省篇幅，生成树横画，下同。17．设从顶点1开始遍历，则深度优先生成树(1)和宽度优先生成树(2)为：图17(1)图17(2)18．遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。19．（1）邻接矩阵：（6*6个元素）*2字节/元素=72字节邻接表：表头向量6*（4+2）+边结点9*(2+2+4)*2=180字节邻接多重表：表头向量6*（4+2）+边结点9*（2+2+2+4+4）=162字节邻接表占用空间较多，因为边较多，边结点又是边数的2倍，一般来说，邻接矩阵所占空间与边个数无关（不考虑压缩存储），适合存储稠密图，而邻接表适合存储稀疏图。邻接多重表边结点个数等于边数，但结点中增加了一个顶点下标域和一个指针域。（2）因未确定存储结构，从顶点1开始的DFS树不唯一，现列出两个：20．未确定存储结构，其DFS树不唯一，其中之一（按邻接点逆序排列）是12346589710125347689101234512345123546165423（2）关节点有3，1，8，7，221．（1）（2）AFEDBC22．设邻接表（略）中顶点的邻接点按顶点编号升序排列（V1编号为1）（1）广度优先搜索序列：V1V2V3V4V5V6V7V8（2）深度优先搜索序列：V1V2V4V8V5V3V6V723．（1）略（2）V1V2V5V3V4V6(4)V1V2V3V4V5V6(3)(6）见本章五算法设计第6题24．设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列(1)ABGFDEC(2)EACFBDG(3)25．在有相同权值边时生成不同的MST，在这种情况下，用Prim或Kruskal也会生成不同的MST。26．无向连通图的生成树包含图中全部n个顶点，以及足以使图连通的n-1条边。而最小生成树则是各边权值之和最小的生成树。从算法中WHILE（所剩边数=顶点数）来看，循环到边数比顶点数少1（即n-1）停止，这符合n个顶点的连通图的生成树有n-1条边的定义；由于边是按权值从大到小排序，删去的边是权值大的边，结果的生成树必是最小生成树；算法中“若图不再连通，则恢复ei”，含义是必须保留使图连通的边，这就保证了是生成树，否则或者是有回路，或者成了连通分量，均不再是生成树。27．Prim算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal算法，18931075624CAEFBDV1V4V6V5V3V2V1V2V5V3V4V6(5