2017年内蒙古师范大学计算机与信息工程学院840数据结构与操作系统考研仿真模拟题
● 摘要
一、选择题
1． 将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是（ ）。
I. 父子关系
II. 兄弟关系
III.u 的父结点与v 的父结点是兄弟关系
A. 只有I
B.I 和II
C.I 和III
D.I 、II 和III
【答案】B
【解析】首先，在二叉树中，若结点U 是结点v 的父结点的父结点，那么u*v的关系有如下4种情况：
接下来，根据森林与二叉树的转换规则，将这4种情况还原成森林中结点的关系。其中：
，在原来的森林中U 是V 的父结点的父结点； 情况（1）
，在森林中u 是v 的父结点； 情况（2）
，在森林中u 是v 的父结点的兄弟； 情况（3）
，在森林中u 与v 是兄弟关系。 情况（4）
由此可知，题目中的I 、II 是正确的。
2． 本地用户通过键盘登录系统时，首先获得的键盘输入信息的程序是（ ）。
A. 命令解释程序
B. 中断处理程序
C. 系统调用服务程序
D. 用户登录程序
【答案】B
【解析】外部设备在与计算机连接时有多种方式，中断技术就是一种常用方式。其工作原理是：利用处理机中断信号线，外部设备在需要服务的时候将该线设置为有效，计算机若同意接受
，中断则会停止当前进程的运行，转而服务发出中断的物理设备（注意与陷阱，即软中断有区别）
那么对不同外部设备进行服务的程序代码是不同的，如何找到这些代码呢? 这就要借助中断向量，中断向量一般是由硬件根据中断的类型（不同外设不同）计算所得，或计算机系统在开机配置时所配置的。处理机取得中断向量，其实就是一个物理地址，该地址下存放的是为此中断服务的代码的起始地址。所以，当键盘按下的时候，键盘控制器获得该操作动作，先将键盘扫描码读入键盘缓冲区，再向处理机发出键盘中断，适当的时候（一条指令的末尾或一条原语结束）处理机会响应中断，调用指定服务程序将键盘缓冲区中的键盘扫描码输入到登录进程中去。如此，最先响应键盘的必然是中断处理程序。本题中，像命令解释器（例如cmd 窗口）、系统调用服务和用户登录程序都在中断处理程序后面。
3． 每个结点的度或者为0或者为2的二叉树称为正则二叉树。n 个结点的正则二叉树中有（ ）个叶子。
【答案】D
【解析】二叉树结点总数分别代表度为0，度为1，度为2的结点数）。又在非空二叉树中
：且本题所给树为正则二叉树
，所
以因
此
4． 某容量为256M 的存储器，由若干位的DRAM 芯片构成，该DRAM 芯片的地址引脚和数据引脚总数是：（ ）
A.19
B.22
C.30
D.36
【答案】A
【解析】DRAM 地址线复用，4M 为2的22次方，因此除2为11根，数据线8根。因此地址引脚和数据引脚总数为19根
5． 某计算机主频为1.2GHz ，其指令分为4类，它们在基准程序中所占比例及CPI 如下表所示。
该机的MIPS 数是（ ）
A.100
B.200
C.400
D.600
【答案】C
【解析】基准程序的计算机的主频为为1200MHz ， 该机器的
6． 下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）。
A. 时间片轮转调度算法
B. 短进程优先调度算法
C. 先来先服务调度算法
D. 尚响应比优先调度算法
【答案】D
【解析】时间片轮转法和先来先服务算法都是公平的方法，并未考虑进程等待时间和执行时间，而短进程优先考虑的是进程执行时间。最高响应比优先调度算法是最先执行响应比最尚的进程（响应比=1＋等待时间/估计运行时间）。该算法综合了先来先服务（FCFS ）和短作业优先（SJF ）算法，FCFS 只考虑每个作业的等待时间，而未考虑执行时间的长短。SJF 只考虑执行时间的长短，而未考虑等待时间的长短，HRRN 算法则同时考虑执行时间和等待时间。
7． 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树
B. 哈夫曼树 C.
D. 堆
【答案】D
【解析】堆的定义：
n 个关键字序列
（1）（2）且且或 称为堆，当且仅当该序列满足如下性质（简称为堆性质）： 树
满足第（1）种情况的堆，称为小顶堆；满足第（2）种情况的堆，称为大顶堆。
由堆的定义可知堆可以满足上述性质。
8． 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素a , b , c , d , e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（ ）。
A.b ，a , c , d ，e
B.d ，b , a , c ，e
C.d ，b , c , a ，e