BOK 数据结构数据结构2018-42综合题12 分拟建设一个光通信骨干网络连通 BJ、CS、XA、QD、JN、NJ、TL 和 WH 等 8 个城市，题 42 图中无向边上的权值表示两个城市间备选光纤的铺设费用。请回答下列问题。（1）仅从铺设费用角度出发，给出所有可能的最经济的光纤铺设方案（用带权图表示），并计算相应方案的总费用。（2）题 42 图可采用图的哪种存储结构？给出求解问题（1）所使用的算法名称。（3）假设每个城市采用一个路由器按（1）中得到的最经济方案组网，主机 H1 直接连接在 TL 的路由器上，主机 H2 直接连接在 BJ 的路由器上。若 H1 向 H2 发送一个 TTL = 5 的 IP 分组，则 H2 是否可以收到该 IP 分组？显示本题答案答案（1）题图如下。所有可能的最经济方案为最小生成树，共有两种方案，总费用均为16。（2）存储结构可采用邻接矩阵或邻接表；求解算法为Prim算法或Kruskal算法。（3）在方案1中，TL与BJ间距离过长，TTL=0时会丢弃数据报无法到达，H2不能收到分组；在方案2中，TL与BJ相邻，最短路径长度为1，H2可以收到分组。42
