问答题
某网络中的路由器运行OSPF路由协议，表是路由器R1维护的主要链路状态信息(LSI)，图是根据表及R1的接口名构造出来的网络拓扑。
问答题
本题中的网络可抽象为数据结构中的哪种逻辑结构?
【正确答案】本题中的网络可抽象为图结构。
【答案解析】
问答题
针对表中的内容，设计合理的链式存储结构，以保存表中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义，并画出对应表的链式存储结构示意图(示意图中可仅以ID标识结点)。
【正确答案】链式存储结构的数据类型定义如下：
typedef struet
{ unsigned int ID;
unsigned int IP;
}LinkNode; //Link的结构
typedef struct
{ unsigned int Prefix;
unsigned int Mask;
}NetNode; //Net的结构
typedef struet 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; //表头结点
对应表的链式存储结构示意图如下。
[*]
typedef struet
{ unsigned int ID;
unsigned int IP;
}LinkNode; //Link的结构
typedef struct
{ unsigned int Prefix;
unsigned int Mask;
}NetNode; //Net的结构
typedef struet 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; //表头结点
对应表的链式存储结构示意图如下。
| 弧结点的两种基本形态 | |
| Flag=1 | Next |
| ID | |
| IP | |
| Metric | |
| Flag=2 | Next |
| Prefix | |
| Mask | |
| Metric | |
| 表头结点结构示意 |
| Router ID |
| LN_link |
| Next |
【答案解析】
问答题
按照迪杰斯特拉(Dijkstra)算法的策略，依次给出R1到达图中子网192.1.x.x的最短路径及费用。
【正确答案】计算结果如下表所示。
| 目的网络 | 路径 | 代价(费用) | |
| 步骤1 | 192.1.1.0/24 | 直接到达 | 1 |
| 步骤2 | 192.1.5.0/24 | R1→R3→192.1.5.0/24 | 3 |
| 步骤3 | 192.1.6.0/24 | R1→R2→192.1.6.0/24 | 4 |
| 步骤4 | 192.1.7.0/24 | R1→R2→R4→192.1.7.0/24 | 8 |
【答案解析】