2017年西华师范大学数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 设某计算机的逻辑地址空间和物理地址空间均为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。
2． 如果输入序列为123456, 试问能否通过栈结构得到以下两个序列：435612和135426; 请说明为什么不能或如何才能得到。
【答案】输入序列为123456, 不能得出435612, 其理由是，输出序列最后两元素是12, 前面4个元素（4356）得到后，栈中元素剩12, 且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1; 然后2和3入找，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。
3． 某计算机的CPU 主频为500MHz ，CPI 为5（即执行每条指令平均需要5个时钟周期）。假定某外设的数据传输率为0.5MB/S，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。
（1）在中断方式下，CPU 用于该外设I/O的时间占整个CPU 时间的百分比是多少？
（2）当该外设的数据传输率达到5MB/s时，改用DMA 方式传送数据。假定每次DMA 传送块大小为5000B , 且DMA 预处理和后处理的总开销为500个时钟周期，则CPU 用于该外设I/0时间占整个CTU 时间的百分比是多少？（假设DMA 与CPU 之间没有访存冲突）
【答案】（1）已知主频为500MHz ，则时钟周期=l÷500MHz=2ns，因为CPI=5, 所以每条指令
，数据传输率为0.5MB/S, 所以传送时间平均5×2=10ns。又已知每中断一次传送32位（4个字节）
=4÷0.5MB/s=CPU 用于该外设I/0共需20条指令（中断服务程序包括18条指令+其他开销折
，花费时间=20×l0=200ns。CPU 用于该外设I/0的时间占整个CPU 时间的百分比合2条指令）
=200/8000×100%=0.025×100%=2.5%。
（2）改用DMA 方式传送数据，数据传输率为5MB/S，传送5000B 的时间=5000B÷5MB/s=lms。预处理和后处理的总开销时间=500×2ns=CPU 用于该外设I/0时间占整个CPU 时间的百分比=预处理和后处理的总开销时间÷传送数据的时间=l/1000×l00%=0.001×100%=0.1%。
4． 二叉树的带权路径长度（WPL ）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T ，采用二叉链表存储，节点结构为：
其中叶节点的weight 域保存该结点的非负权值。设root 为指向T 的根节点的指针，设计求T 的WPL 的算法。要求：
（1）给出算法的基本设计思想；
（2）使用C 或C++语言，给出二叉树结点的数据类型定义；
（3）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。
【答案】（1）算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之
和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。
（2）
typedef struct BiNode
（3）具体算法实现如下：
如果当前节点为空节点
//如果当前节点的左右孩子节点都为空，即当前节点为叶子节点，直接返回当前节点的
WPL
//如果当前节点不是叶子节点，则对当前节点的左右子树进行递归，返回左右子树WPL 之和
5． S 是字符数组
，中存放的是该字符串的有效长度，
假设中字符串的内容为
说明下列程序的功能及执行结果。
【答案】本程序的功能是求字符串的nextval 函数，程序执行结果是0110132。
6． 已知有6个顶点（顶点编号为0--5）的有向带权图G , 其邻接矩阵A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。
要求：
（1）写出图G 的邻接矩阵A 。
（2）画出有向带权图G 。
相关内容
相关标签