发布时间 : 星期五 文章第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={
K8
K1
K4
K5
K6
K2 K3
K7
(2)拓扑序列K1,K2,K3,K4,K8,K5,K6,K7
专业知识 整理分享