408计算机考研图大题

请回答下列问题。

1）本题中的网络可抽象为数据结构中的哪种逻辑结构？

2）针对题 42 表中的内容，设计合理的链式存储结构，以保存题 42 表中的链路状态信息（LSI）。要求给出链式存储结构的数据类型定义，并画出对应题 42 表的链式存储结构示意图（示意图中可仅以 ID 标识结点）。

3）按照迪杰斯特拉（Dijkstra）算法的策略，依次给出 R1 到达题 42 图中子网 192.1.x.x 的最短路径及费用。

解析：

很多考生乍看之下以为是网络的题目，其实该题本身并没有涉及太多的网络知识点，只是应用了网络的模型，实际上考查的还是数据结构的内容。

（1）图（无向图）

（2）链式存储结构的如下图所示。

其数据类型定义如下：（3 分）

c
typedef struct{
    unsigned int ID, IP;
}LinkNode;                   //Link 的结构
typedef struct{
    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

对应上述链式存储结构的示意图如下。（2 分）

（3）计算结果如下表所示。（4 分）