2018年齐鲁工业大学理学院872数据结构考研仿真模拟五套题
● 摘要
一、应用题
1． 假设Internet 的两个自治系统构成网络如下图所示, 自治系统ASI 由路由器R1连接两个子网构成; 自治系统AS2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、R1与R3的部分接口IP 地址如下图所示。请回答下列问题。
图 网络拓扑结构
(1)假设路由表结构如下所示。请利用路由聚合技术, 给出R2的路由表, 要求包括到达上图中所有子网的路由, 且路由表中的路由项尽可能少。
(2)若R2收到一个目的IP 地址为行传输？
【答案】(1)在AS1中, 子网AS2中, 子
网
; 子网
和子
网
和子网
可以聚合为子网
可以聚合为子
网
, 在, 但缺
少
的IP 分组, R2会通过哪个接口转发该IP 分组？
(3)R1与R2之间利用哪个路由协议交换信息？该路由协议的报文被封装到哪个议的分组中进
单独连接到R2的接口E0。
于是可以得到R2的路由表如下:
(2)该IP 分组的目的IP 地址与路由表中和两个路由
表项均匹配, 根据最长匹配原则, R2将通过E0接口转发该1P 分组。
(3)R1与R2之间利用BGP4(或BGP) 交换路由信息; BGP4的报文被封装到TCP 协议段中进行
传输。
2． 对给定文件(28，07，39，10，65，14，61，17，50，21) 选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。
【答案】快速排序的思想如下:首先将待排序记录序列中的所有记录作为当前待排序区域，以第一个记录的关键字作为枢轴(或支点) ，凡其关键字不大干枢轴的记录均移动至该记录之前，凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列割成两部分:
和
和，且
进行快速排序。快速排序在记录有序时蜕变为起泡排序，
将分
然后再递归地将初始序列:21移动:39移动:17移动:65移动:14移动:
可用“三者取中”法改善其性能，避免最坏情况的出现。
3． 某计算机主存按字节编址, 逻辑地址和物理地址都是32位, 页表项大小为4字节。请回答下列问题。
(1)若使用一级页表的分存储管理方式, 逻辑地址结构为:
则页的大小是多少字节？页表最大占用多少字节？ (2)若使用二级页表的分存储管理方式, 逻辑地址结构为:
设逻辑地址为LA , 请分别给出其对应的页目录号和表索引达式。
(3)采用(1)中的分页存储管理方式, 一个代码段起始逻辑地址为00008000H , 其长度为8KB , 被装载到从物理地址00900000H 开始的连续主存空间中。页表从主存
开始的
物理地址处连续存放, 如下图所示(地址大小自下向上递增) 。请计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这两个页表项中的框号以及代码页面2的起始物理地址。
【答案】(1)因为页内偏移量是12位所以页大小为4KB 页表项数为该一级页表最大为(2)页目录号可表示为:页表索引可表示为:
(3)代码页面1
的逻辑地址为项, 所以第8个页表项的物理地址
=页表起始地址如下图所示。
页表项的字节数
,
。
。 。
, 表明其位于第8个页处, 对应页表中的第8个页表
4． 简述广义表属于线性结构的理由。
【答案】广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性:在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。
5． 设二叉树BT 的存储结构如表:
表 二叉树BT 的存储结构
其中BT 为树根结点的指针，其值为6, Lchild 、Rchild 分别为结点的左、右孩子指针域data 为结点的数据域。试完成下列各题:
(1)画出二叉树BT 逻辑结构；
(2)写出按前序、中序、后序遍历该二叉树所得到的结点序列； (3)画出二叉树的后序线索树。
【答案】(1)二叉树的逻辑结构如图1所示:
相关内容
相关标签