42.（10分）某网络中的路由器运行 OSPF路由协议，题 42表是路由器R1维护的主要链路状态信息（LSI），题 42图是根据题 42表及R1的接口名构造出来的网络拓扑。 请回答下列问题。 1）本题中的网络可抽象为数据结构中的哪种逻辑结构? 2）针对题 42表中的内容，设计合理的链式存储结构，以保存题 42 表中的链路状态信息（LSI）。要求给出链式存储结构的数据类型定义，，并画出对应题 42 表的链式存储结构示意图（示意图中可仅以ID标识结点）。 3）按照迪杰斯特拉（Dijkstra）算法的策略，依次给出R1到达题42 图中子网192.1.x.x 的最短路径及费用。
【参考答案及解析】
考察在给出具体模型时，数据结构的应用。该题很多考生乍看之下以为是网络的题目，其实题本身并没有涉及太多的网络知识点，只是应用了网络的模型，实际上考察的还是数据结构的内容。 （1）图（1分） 题中给出的是一个简单的网络拓扑图，可以抽象为无向图。 【评分说明】 只要考生的答案中给出与图含义相似的描述，例如"网状结构"、"非线性结构"等，同样给分。 （2）链式存储结构的如下图所示 其数据类型定义如下∶（3分） typedef struct{ unsigned int ID, IP; }LinkNode; //Link 的结构 typedef structf{ unsigned int Prefix, Mask; }NetNode; //Net 的结构 typedef struct Node{ int Flag; //Flag=1为Link;Flag=2为Net union{ LinkNode Lnode; NetNode Nnode }LinkORNet; unsigned int Metric; struct Node *next; }ArcNode; //弧结点 typedef struct HNode{ unsigned int RouterID; ArcNode *LN link; Struct HNode *next; }HNODE; //表头结点 对应题 42表的链式存储结构示意图如下。（2分） 【评分说明】 ①若考生给出的答案是将链表中的表头结点保存在一个一维数组中（即采用邻接表形式），同样给分。 ②若考生给出的答案中，弧结点没有使用 union定义，而是采用两种不同的结构分别表示 Link 和 Net，同时在表头结点中定义了两个指针，分别指向由这两种类型的结点构成的两个链表，同样给分。 ③考生所给答案的弧结点中，可以在单独定义的域中保存各直连网络 IP 地址的前缀长度，也可以与网络地址保存在同一个域中。 ④数据类型定义中，只要采用了可行的链式存储结构，并保存了题目中所给的LSI信息，例如将网络抽象为一类结点，写出含8个表头结点的链式存储结构，均可参照（1~③的标准给分。 ⑤若考生给出的答案中，图示部分应与其数据类型定义部分一致，图示只要能够体现链式存储结构及题42 图中的网络连接关系（可以不给出结点内细节信息），即可给分。 ⑥若解答不完全正确，酌情给分。 （3）计算结果如下表所示。（4分） 【评分说明】 ①若考生给出的各条最短路径的结果部分正确，可酌情给分。 ②若考生给出的从R1到达子网192.1.x.x的最短路径及代价正确，但不完全符合代价不减的次序，可酌情给分。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！
考察在给出具体模型时，数据结构的应用。该题很多考生乍看之下以为是网络的题目，其实题本身并没有涉及太多的网络知识点，只是应用了网络的模型，实际上考察的还是数据结构的内容。 （1）图（1分） 题中给出的是一个简单的网络拓扑图，可以抽象为无向图。 【评分说明】 只要考生的答案中给出与图含义相似的描述，例如"网状结构"、"非线性结构"等，同样给分。 （2）链式存储结构的如下图所示 其数据类型定义如下∶（3分） typedef struct{ unsigned int ID, IP; }LinkNode; //Link 的结构 typedef structf{ unsigned int Prefix, Mask; }NetNode; //Net 的结构 typedef struct Node{ int Flag; //Flag=1为Link;Flag=2为Net union{ LinkNode Lnode; NetNode Nnode }LinkORNet; unsigned int Metric; struct Node *next; }ArcNode; //弧结点 typedef struct HNode{ unsigned int RouterID; ArcNode *LN link; Struct HNode *next; }HNODE; //表头结点 对应题 42表的链式存储结构示意图如下。（2分） 【评分说明】 ①若考生给出的答案是将链表中的表头结点保存在一个一维数组中（即采用邻接表形式），同样给分。 ②若考生给出的答案中，弧结点没有使用 union定义，而是采用两种不同的结构分别表示 Link 和 Net，同时在表头结点中定义了两个指针，分别指向由这两种类型的结点构成的两个链表，同样给分。 ③考生所给答案的弧结点中，可以在单独定义的域中保存各直连网络 IP 地址的前缀长度，也可以与网络地址保存在同一个域中。 ④数据类型定义中，只要采用了可行的链式存储结构，并保存了题目中所给的LSI信息，例如将网络抽象为一类结点，写出含8个表头结点的链式存储结构，均可参照（1~③的标准给分。 ⑤若考生给出的答案中，图示部分应与其数据类型定义部分一致，图示只要能够体现链式存储结构及题42 图中的网络连接关系（可以不给出结点内细节信息），即可给分。 ⑥若解答不完全正确，酌情给分。 （3）计算结果如下表所示。（4分） 【评分说明】 ①若考生给出的各条最短路径的结果部分正确，可酌情给分。 ②若考生给出的从R1到达子网192.1.x.x的最短路径及代价正确，但不完全符合代价不减的次序，可酌情给分。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！