2017年哈尔滨商业大学计算机与信息工程学院904数据结构[专业硕士]考研强化模拟题
● 摘要
一、选择题
1． 单处理机系统中，可并行的是（ ）。
I. 进程与进程
II. 处理机与设备
III. 处理机与通道
IV . 设备与设备
A.I 、II 和III
B.I 、II 和IV
C.I 、III 和IV
D.II 、III 和IV
【答案】D
【解析】注意区分并发和并行。在单处理机系统中，进程只能并发。微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的。通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行。显然，设备和设备之间也是可以并行的。
2． 现在有一颗无重复关键字的平衡二叉树（A VL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。
A. 根节点的度一定为2
B. 树中最小元素一定是叶节点
C. 最后插入的元素一定是叶节点
D. 树中最大元素一定是无左子树
【答案】D
【解析】二叉树的中序遍历定义是“若二叉树为空，则空操作；否则：①中序遍历左子树；②访问根节点；③中序遍历右子树”。A 项错误，当树中仅有一个或者两个结点时，根节点的度就可能不为2；B 项错误，树中最小元素是中序遍历时最后访问的节点，当没有右子树时，最后访问的节点是根节点；C 项错误，当最后插入的元素破坏树的平衡后，树会进行调整，使其成为中间节点；D 项正确，由中序遍历的特点可知，左子树的值大于根节点，所以最大元素一定没有左子树。
3． 设栈S 和队列Q 的初始状态为空，元素
后即进队列Q ，若6个元素出队的序列是
A.6
第 2 页，共 69 页 依次通过栈S ，一个元素出栈 则栈S 的容量至少应该是（ ）。
B.4
C.3
D.2
【答案】C
4． n 个结点的线索二叉树上含有的线索数为（ ）。
【答案】C
【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n+1个空链域。
5． —个栈的入栈序列为其出栈序列是若，则则可能取值的个数是（ ）
A.n-3
B.n-2
C.n-1
D. 无法确定
【答案】C
【解析】除了3本身以外，其他的值均可以取到，因此可能取值的个数为n-1。
6． 已知一算术表达式的中缀表达式为其后缀形式为（ ）。
【答案】D
【解析】后缀表达式：在程序语言中，运算符位于两个操作数后面的表达式。
7． 某计算机主频为1.2GHz ，其指令分为4类，它们在基准程序中所占比例及CPI 如下表所示。
该机的MIPS 数是（ ）
A.100
B.200
C.400
D.600
【答案】C
【解析】基准程序的计算机的主频为为1200MHz ， 该机器的
8． 下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务
第 3 页，共 69 页
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先
【答案】B
【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，因此首先排除时 间片轮转算法；因为作业调度算法中没有时间片轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个? 我们可以通过分析得到，非抢占式短任务优先算法不能解决饥饿问题，因为当一个系统短任务源源不断到达是，长任务必然会得不到 调度，产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法，并以高响应比值优先调度。这样，无论短任务或长任务，均可以得到调度，而且，较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有尚响应比优先算法。
9． 某CPU 主频为1.03GHz , 采用4级指令流水线，每个段的执行需要1个时钟周期。假定CPU
执行了100条指令，在其执行过程中没有发生任何流水线阻塞，此时流水线的吞吐率为（ ）
A.
B.
C.
D.
【答案】C
【解析】采用4级流水线执行100条指令，在执行过程中共用
条指令/秒，故答案为C 。
10．float 类型（即IEEE754单精度浮点数格式）能表示的最大正整数是（ ）。
A.
B.
C.
D.
【答案】D 。
【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示，且阶码用移码表示的浮点数。规格化的短 浮点数的真值为：S 为符号位，E 的取值为f 为23位；
故float 类型能表示的最大整数是
11．某同步总线采用数据线和地址线复用方式。其中地址数据线有8根，总线时钟频率为66MHZ , 每个时钟同期传送两次数据。（上升沿和下降沿各传送一次数据）该总线的最大数据传输率是（总线带宽）（ ）
：
A.
第 4 页，共 69 页 条指令/秒
条指令/秒
条指令/秒
条指令/秒 个时钟周期。CPU 的主频是1.03GHz , 也就是说每秒钟有1.03G 个时钟周期。流水线的吞吐率
为