第7章图练习题与答案 联系客服

发布时间 : 星期五 文章第7章图练习题与答案更新完毕开始阅读a120a10f29ea81c758f5f61fb7360b4c2f3f2a2f

WORD格式可编辑

12.用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。(×) 13.有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零 元素之和的一半。(√)

18.当改变网上某一关键路径上任一关键活动后,必将产生不同的关键路径

(×)

15.不同的求最小生成树的方法最后得到的生成树是相同的.(×) 16、有向图的邻接表和逆邻接表中表结点的个数一定相等。(√) 四、简答题

12.请对下图的无向带权图:

(1)写出它的邻接矩阵,并按普里姆算法求其最小生成 树;

(2)写出它的邻接表,并按克鲁斯卡尔算法求其最小生成 树。

解:设起点为a。可以直接由原始图画出最小生成树,而且最小生成树只有一种 (类)! 邻接矩阵为: 0 4 3 4 0 5 3 5 0

5 5 9

5 9 5 7 0 3 6 3 0 2 5

2 0 6

6 0

5

0 7 6 5 4

最小生成树

5 4

13.已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行

遍历所得的深度优先生成树和广度优先生成树。 解:

3、 图

专业知识 整理分享

WORD格式可编辑

2表示一个地区的通讯网,边表示城市间的通讯线路,边上的权值表示架设线 路花费的代价,请找出能连通每个城市、且总代价最省的n-1条线路。

答: 图2

19.已知有向图如下所示,对该图进行拓扑排序。

GB

A

CEHI

DF

答:拓扑序列为:A、B、C、D、E、F、G、H、I(不唯一)

20.已知图的邻接矩阵为:

V1V2V3V4V5V6V7V8V9V10 V10111000000 V20001100000 V30001010000 V40000011010 V50000001000 V60000000110 V70000000010

专业知识 整理分享

WORD格式可编辑

V80000000001 V90000000001 V100000000000

当用邻接表作为图的存储结构,且邻接表都按序号从大到小排序时,试写出: (1).以顶点V1为出发点的唯一的深度优先遍历; (2).以顶点V1为出发点的唯一的广度优先遍历; (3).该图唯一的拓扑有序序列。

21.已知一数据集合的逻辑结构为:B=(K,R),其中,K={k1,k2,?,k8},

R={,,,,,,, },请回答下面两个问:题 (1)画出这个逻辑结构的图示。 (2)写出关系R的一个拓扑序列。

K8

K1

K4

K5

K6

K2 K3

K7

(2)拓扑序列K1,K2,K3,K4,K8,K5,K6,K7

专业知识 整理分享