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

《数据结构 习题 第七章 图 答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第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.×

2、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网是用

3、顶点代表活动，弧表示活动间的优先关系的有向图,叫顶点表示活动的网。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.N1

4、6.317.2（N-1）18.度出度19.第I列非零元素个数20.n2e21.(1)查找顶点的邻接点的过程(2)O(n+e)(3)O(n+e)(4)访问顶点的顺序不同(5)队列和栈22.深度优先23.宽度优先遍历24.队列25.因未给出存储结构，答案不唯一。本题按邻接表存储结构，邻接点按字典序排列。KBAJEIDCFADFCEBKIJ25题（1）25题（2）26.普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法27.克鲁斯卡尔28.边稠密边稀疏29.O(eloge）边稀疏30.O(n2）O(eloge)31.(1）（Vi，Vj）边上的权值

5、都大的数（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）p<>nil(2)visited[v]=true(3)p=g[v].firstarc(4)p=p^.nextarc45.(1

6、)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)p<>nil(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^.lin

7、k:=ch[u].head(2)ch[u].head:=p(3)top<>0(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条边(注

8、：弱连通有向图指把有向图看作无向图时，仍是连通的)2．n-1，n3.分块对称矩阵4．证明：具有n个顶点n-1条边的无向连通图是自由树，即