2017年湖南师范大学软件工程之数据结构(C语言版)复试仿真模拟三套题
● 摘要
一、应用题
1． 线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有，2个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构? 为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构? 为什么？
【答案】（1）应选择链式存储结构。因为它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O （1）。
（2）应选择顺序存储结构。因为顺序表可以随机存取，时间复杂度为O （1）。
2． 输入一个正整数序列（53，17，12，66，58，70，87，25，56，60），试完成下列各题。
（1）按次序构造一棵二叉排序树BS 。
（2）依此二叉排序树，如何得到一个从大到小的有序序列？
（3）画出在此二叉排序树中删除“66”后的树结构。
【答案】（1）构造的二叉排序树如图1所示：
图1 二叉排序树
（2）若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；最后中序遍历左子树。
（3）如图2所示：
图2
3． 设某计算机的逻辑地址空间和物理地址空间均为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。
4． 设五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现
：
要求用哈希（Hash ）方法将它们存入具有10个位置的表
中。
（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；
（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。
【答案】（1）构造的哈希函数为：哈希函数（2）关键字在表中的位置如表所示：
表 关键字在表中的位置
5． 假设Internet 的两个自治系统构成网络如题图所示，自治系统ASI 由路由器R1连接两个子网构成；自治系统AS2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、R1与R3的部分接口 IP 地址如题图所示。请回答下列问题。
（关键字各字符编码之和）
题图网络拓扑结构
（1）假设路由表结构如下所示。请利用路由聚合技术，给出R2的路由表，要求包括到达题图中所有子网的路由，且路由表中的路由项尽可能少。
（2）若R2收到一个目的IP 地址为194.17.20.200的IP 分组，R2会通过哪个接口转发该IP 分组？
R1与R2之间利用哪个路由协议交换信息？该路由协议的报文被封装到哪个议的分组中（3）
进行传输？
【答案】
（1）在AS1中，子网中，子
网和子网单独连接到的接口可以聚合为子网但缺少子网
于是可以得到R2的路由表如下：
和子网可以聚合为子网在AS2
相关内容
相关标签