2017年西南民族大学计算机导论之数据结构(C语言版)复试实战预测五套卷
● 摘要
一、应用题
1． 输入一个正整数序列（53，17，12，66，58，70，87，25，56，60），试完成下列各题。
（1）按次序构造一棵二叉排序树BS 。
（2）依此二叉排序树，如何得到一个从大到小的有序序列？
（3）画出在此二叉排序树中删除“66”后的树结构。
【答案】（1）构造的二叉排序树如图1所示：
图1 二叉排序树
（2）若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；最后中序遍历左子树。
（3）如图2所示：
图2
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． （1）对于有向无环图，叙述求拓扑有序序列的步骤；
（2）对于图1，写出它的四个不同的拓扑有序序列。
图1
【答案】（1）对有向图，求拓扑序列步骤为：
1）在有向图中选一个没有前驱（即入度为0）的顶点并输出。
2）在图中删除该顶点及所有以它为尾的弧。
3）重复1）和2）, 直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失
败。
（2）拓扑有序序列如图2:
图2 拓扑有序序列
4． 某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效，为0时表示无效，例如控制信号MDRinE 为1表示允许数据从DB 打入MDR ，MDRin 为1表示允许数据从内总线打入MDR 。假设MAR 的输出一直处于使能状态。加法指令“ADD （Rl ）, R0”的功能为（R0）+（（R1））－（R1）, 即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。
图
下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号，请按表
相关内容
相关标签