题12

题12

题目

【2018 统考真题】拟建设一个光通信骨干网络连通 BJ、CS、XA、QD、JN、NJ、TL 和 WH 等 8 个城市, 下图中无向边上的权值表示两个城市之间备选光缆的铺设费用。
请回答下列问题:

1. 仅从铺设费用角度出发, 给出所有可能的最经济的光缆铺设方案 (用带权图表示), 并计算相应方案的总费用。
2. 该图可采用图的哪种存储结构?给出求解问题 1) 所用的算法名称。
3. 假设每个城市采用一个路由器按 1) 中得到的最经济方案组网, 主机 H1 直接连接 TL 的路由器,
   主机 H2 直接连接 BJ 的路由器。若 H1 向 H2 发送一个 TTL=5 的 IP 分组, 则H2是否可以收到该 IP 分组?
   

分析

题24

解

1. 为了求解最经济的方案, 可把问题抽象为求无向带权图的最小生成树。可以采用手动 Prim 算法或 Kruskal 算法作图。注意本题的最小生成树有两种构造, 如下图所示。
   
   方案的总费用为 16 。
2. 存储题中的图可采用邻接矩阵 (或邻接表)。构造最小生成树采用 Prim 算法 (或 Kruskal 算法)。
3. TTL ,即 IP 分组的生存时间 (最大传递距离) 为 5,方案 1 中 TL 和 BJ 的距离过远, TTL 不足以让 IP 分组从 传送到 ,因此 不能收到 IP 分组。而方案 2 中 TL 和 邻近, 可以收到 IP 分组。