2017年兰州财经大学算法与数据结构(同等学力加试)考研复试核心题库
● 摘要
一、应用题
1． 写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。
【答案】此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。
第一趟：12，23，35，16，25，36， 19，21，16， 47
第二趟：12，16，23，35，16，25，36， 19，21，47
第三趟：12，16，23，16，25，35， 19，21，36， 47
第四趟：12， 16， 16，23， 19， 25， 35， 21， 36，47
第五趟：12，16，16，19，23，25，21，35， 36， 47
第六趟：12，16，16，19，21， 23，25，35， 36， 47
第七趟：12，16，16，19，21，23，25，35， 36， 47
2． 某网络中的路由器运行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 算法找最短路径步骤如下表所示：