2017年辽宁大学计算机专业相关知识之数据结构(C语言版)复试实战预测五套卷
● 摘要
一、应用题
1． 已知有6个顶点（顶点编号为0--5）的有向带权图G , 其邻接矩阵A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。
要求：
（1）写出图G 的邻接矩阵A 。
（2）画出有向带权图G 。
（3）求图G 的关键路径，并计算该关键路径的长度。
【答案】（1）由题可以画出待定上三角矩阵的结构图如下（图中? 为待定元素）：
可以看出，第一行至第五行主对角线上方的元素分别为5, 4, 3, 2, 1个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示：
将各元素填入各行即得邻接矩阵：
（2）根据第一步所得矩阵A 容易做出有向带权图G , 如下：
（3）下图中粗线箭头所标识的4个活动组成图G 的关键路径。
由上图容易求得图的关键路径长度为：4+5+4+3 = 16。
2． 设某计算机的逻辑地址空间和物理地址空间均为64KB , 按字节编址。若某进程最多需要6页（Page ）数据存储空间，页的大小为1KB , 操作系统采用固定分配局部置换策略为此进程分配4个页框（PageFrame ）。在时刻260前的该进程访问情况如下表所示（访问位即使用位）。
当该进程执行到时刻260时，要访问的逻辑地址为17CAH 的数据，请回答下列问题： （1）该逻辑地址对应的页号是多少？
（2）若采用先进先出（FIFO ）置换算法，该逻辑地址对应的物理地址是多少? 要求给出计算过程。
（3）若采用时钟（CLOCK ）置换算法，该逻辑地址对应的物理地址是多少? 要求给出计算过程。（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，如图所示）
图
【答案】（1）由题可知计算机的逻辑地址空间和物理地址空间均为64KB=216B, 按字节编址，并且页的大小为IK=210, 故逻辑地址和物理地址的地址格式均为：
地址17CA=0001011111001010B，故可知其逻辑页号为000101B=5。
（2）根据FIFO 算法，需要替换出最早装入的页，故需置换0号页，将5号页装入7号页框中，所以物理地址为0001111111001010B=1FCAH。
（3）根据CLOCK 算法，如果当前指针所指页框的使用位为0, 则替换该页，否则将使用位清零，并将指针指向下一个页框，继续查找。由题可知，将从2号页框开始，前4次查找页框号的顺序为2、4、7、9, 并将对应页框的使用位清零。在第5次查找中，指针指向2号页框，因2号页框的使用位已经为0, 故将2号页框的页将5号装入2号页框，并将其对应使用位设置为1,
所以对应的物理地址为0000101111001010B=0BCAH。
3． 某网络中的路由器运行0SPF 路由协议，如表是路由器R1维护的主要链路状态信息（LSI ），如图是根据表及R1的接口名构造出来的网络拓扑。
表R1所维护的
LSI
图R1构造的网络拓扑
请回答下列问题。
（1）本题中的网络可抽象为数据结构中的哪种逻辑结构？
（2）针对表中的内容，设计合理的链式存储结构，以保存表中的链路状态信息（LSI ）。要求给出链式存储结构的数据类型定义，并画出对应表的链式存储结构示意图（示意图中可仅以ID 标识节点）。
（3）按照迪杰斯特拉（Dijikstra ）算法的策略，依次给出R1到达图中子网192.1.x.x 的最短路径及费用。
【答案】（1）图
（2）使用图的邻接表存储结构进行存储，数据类型定义如下：
相关内容
相关标签