当前位置：问答库＞考研试题

一、应用题

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． 索引顺序存取方法（ISAM ）中，主文件已按关键字排序，为何还需要主关键字索引？

【答案】ISAM 是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是以盘组、柱面和磁道（盘面）三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道（盘面）三级索引。在ISAM 文件上检索记录时，先从主索引（柱面索引的索引）找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止；反之，若找遍该磁道而未找到所查记录，则文件中无此记录。