2017年东华大学F1502C语言与数据结构算法上机测试之数据结构(C语言版)复试仿真模拟三套题
● 摘要
一、应用题
1． 某网络中的路由器运行0SPF 路由协议，如表是路由器R1维护的主要链路状态信息（LSI ），如图是根据表及R1的接口名构造出来的网络拓扑。
表R1所维护的
LSI
图R1构造的网络拓扑
请回答下列问题。
（1）本题中的网络可抽象为数据结构中的哪种逻辑结构？
（2）针对表中的内容，设计合理的链式存储结构，以保存表中的链路状态信息（LSI ）。要求给出链式存储结构的数据类型定义，并画出对应表的链式存储结构示意图（示意图中可仅以ID 标识节点）。
（3）按照迪杰斯特拉（Dijikstra ）算法的策略，依次给出R1到达图中子网192.1.x.x 的最短
路径及费用。
【答案】（1）图
（2）使用图的邻接表存储结构进行存储，数据类型定义如下：
该弧指向路由器的位置，0为没有
该弧指向的网络的网络前缀，空为没有
路由的基础IP ，当adjvex 不为0才有效
指向下一条弧的指针
连接的权值
表结点
第一个结点地址
头节点
链式存储结构示意图如下图所示：
（3
）目标网络
记为
记为
记为
使用dijkstra 算法找最短路径步骤如下表所示：
所以R1到达子网192.1.1.0/24最短路径为：R1到达子网R1到达子网R1到达子网
的最短路径为
：的最短路径为
：的最短路径为
子网，费用为1 子网，费用为3 子网，费用为4 子网，费用为8
2． 在各种排序方法中，哪些是稳定的? 哪些是不稳定的? 并为每一种不稳定的排序方法举出一个不稳定的实例。
【答案】各种排序算法稳定性的归纳如图所示：
相关内容
相关标签