第七章图答案
- 格式：docx
- 大小：126.50 KB
- 文档页数：33
第7章 图
一.选择题
14.C
3
二.判定题
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. 45 5. n(n-1)/2 6 .nid121 7. 9 8. n
9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n 15. N
16. 3 17. 2（N-1） 18. 度 出度 19. 第I列非零元素个数 20.n 2e
21.(1)查找极点的邻接点的进程 (2)O(n+e) (3)O(n+e) (4)访问极点的顺序不同 (5)队列和栈
22. 深度优先 23.宽度优先遍历 24.队列
25.因未给出存储结构，答案不唯一。此题按邻接表存储结构，邻接点按字典序排列。
K B A
J E
I D
C
F
A
D F C
E B
K I
J
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.160
36.O(n2） 37. 50，通过中间极点④ 38. 75 39.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^.nextarc
45.(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)p<>nil
(10)p^.vexj=j
(11)firstadj(g,v0) (12)not visited[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]==0
47.(1)p^.link:=ch[u].head (2)ch[u].head:=p (3)top<>0 (4)j:=top
(5)top:=ch[j].count
(6)t:=t^.link
48.（1）V1 V4 V3 V6 V2 V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，因此结果是不唯一的。本答案是按邻接点升序排列给出的。)
（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，n 3.分块对称矩阵
4．证明：具有n个极点n-1条边的无向连通图是自由树，即没有确信根结点的树，每一个结点都可当根。假设边数多于n-1条，因一条边要连接两个结点，那么必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图再也不是树（在图论中树概念为无回路的连通图）。
5．证明：该有向图极点编号的规律是让弧尾极点的编号大于弧头极点的编号。由于不许诺从某极点发出并回到自身极点的弧，因此邻接矩阵主对角元素均为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，K7
K2，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的简单途径：
（abei），(acgi)，
(acbei)
10．图G的具体存储结构略。
邻接矩阵表示法，有n个极点的图占用n2个元素的存储单元，与边的个数无关，当边数较少时，存储效率较低。这种结构下，对查找结点的度、第一邻接点和下一邻接点、两结点间是不是有边的操作有利，对插入和删除极点的操作不利。
邻接表表示法是极点的向量结构与极点的邻接点的链式存储结构相结合的结构，极点的向量结构含有n（n≥0）个极点和指向各极点第一邻接点的指针，其极点的邻接点的链式存储结构是依照极点的邻接点的实际设计的。这种结构适合查找极点及邻接点的信息，查极点的度，增加或删除极点和边（弧）也很方便，但因指针多占用了存储空间，另外，某两极点间是不是有边（弧）也不如邻接矩阵那么清楚。对有向图的邻接表，查极点出度容易，而查极点入度却困难，要遍历整个邻接表。要想查入度象查出度那样容易，就要成立逆邻接表。无向图邻接表中边结点是边数的二倍也增加了存储量。
十字链表是有向图的另一种存储结构，将邻接表和逆邻接表结合到一路，弧结点也增加了信k1k2k3k4k5k6k7k8k938345976697k1k2k3k4k5k6k7k8k9824519224319 1 3
8 7 5 4 2
6
000100000000000000100000000000010100110000000000000000001000010000011000000000110息（至少弧尾，弧头极点在向量中的下标及从弧尾极点发出及再入到弧头极点的下一条弧的四个信息）。查询极点的出度、入度、邻接点等信息超级方便。
邻接多重表是无向图的另一种存储结构，边结点至少包括5个域：连接边的两个极点在极点向量中的下标，指向与该边相连接的两极点的下一条边的指针，和该边的标记信息（如该边是不是被访问）。边结点的个数与边的个数相同，这是邻接多重表比邻接表优越的地方。
11．
已知极点i，找与i相邻的极点j的规那么如下：在极点向量中，找到极点i，顺其指针找到第一个边结点（假设其指针为空，那么极点i无邻接点）。在边结点中，掏出两极点信息，假设其中有j，那么找到极点j；不然，沿从i发出的另一条边的指针（ilink）找i的下一邻接点。在这种查找进程中，假设边结点中有j，那么查找成功；假设最后ilink为空，，那么极点i无邻接点j。
12．按各极点的出度进行排序。n个极点的有向图，其极点最大出度是n-1，最小出度为0。如此排序后，出度最大的极点编号为1，出度最小的极点编号为n。以后，进行调整，即假设存在弧，而极点j的出度大于极点i的出度，那么将把j编号在极点i的编号之前。此题算法见下面算法设计第28题。
