2017年河南科技大学数据结构复试实战预测五套卷
● 摘要
一、应用题
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到达子网
2． 设散列表为数分别为
：
注：％是求余数运算中，函数码序列为
（2）计算搜索成功的平均搜索长度
表示颠倒十进制数x 的各位，如
的最短路径为
：的最短路径为
：的最短路径为即表的大小为
子网，费用为1 子网，费用为3 子网，费用为4 子网，费用为8
，现采用双散列法解决冲突。散列函数和再哈希函
其
等。若插入的关键
（1）试画出插入这8个关键码后的哈希表；
【答案】（1）插入这8个关键码后的哈希表如表所示：