2017年湖北师范大学数据结构(同等学力加试)复试实战预测五套卷
● 摘要
一、应用题
1． 画出对算术表达式
表所示。
表 操作数栈和运算符找的变化过程
求值时操作数栈和运算符栈的变化过程。 求值，过程如【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式
2． 将算术表达式（（a+b）+c*（d+e）+f）*（g+h）转化为二叉树。
【答案】该算术表达式转化的二叉树如图所示。
图
3． 已知一棵二叉树的后序遍历序列为EICBGAHDF , 同时知道该二叉树的中序遍历序列为CEIFGBADH ， 试画出该二叉树。
【答案】该二叉树如图所示：
图
4． 试证明：同一棵二叉树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的
，例如前序后序运对称序。 相对位置出现（即先后顺序相同）
，中序遍历是“左根右”，后序遍历是“左右根”【答案】前序遍历是“根左右”。三种遍历中
只是访问 " 根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位罝出现。
5． 一个ISAM 文件除了主索引外，还包括哪两级索引？
【答案】ISAM 文件有三级索引：磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引一主索引。故还包括的两级索引是盘组和磁道。
6． 某16位计算机主存按字节编码。存取单位为16位；采用16位定长指令格式；CPU 采用单总线结构，主要部分如下图所示。图中为通用寄存器；T 为暂存器；SR 为移位寄存器，可实现直送（mov ）、左移一位（left ）、右移一位（right ） 3种操作，控制信号为Srop , SR的输
ALU 可实现直送A A 加 B （add ）A 减 B （sub ）A 与 B （and ）出信号Srout 控制；（mova ）、、、、
A 或 B （or ）、非 A （not ）、A 加 1 （inc ） 7 种操作，控制信号为
请回答下列问题。
（1）图中哪些寄存器是程序员可见的？为何要设置暂存器T?
（2）控制信号（4）端点和的位数至少各是多少？ （3）控制信号Srout 所控制部件的名称或作用是什么？ 中，哪些端点须连接到控制部件的输出端？
中相应的端点之间添加必要的连线。写出连（5）为完善单总线数据通路，需要在端点
线的起点和终点，以正确表示数据的流动方向。
（6）为什么二路选择器MUX 的一个输入端是2?
【答案】（1）图中程序员可见的寄存器有通用寄存器和程序计数器PC ; 当执行算术或逻辑操作时，由于ALU 本身是没有内部存储功能的组合电路，因此如要执行加法运算，被相加的两个数必须在ALU 的两个输入端同时有效，因此设置暂存器T 用于暂存数据总线发送的数据。
（2）ALUop 和SRop 的位数分别为3，2。
（3）Srout 所控制的部件是状态字寄存器，用来存放ALU 及CPU 的指令状态。
（4）须连接到控制部件的输出端端点有
（5）
（6）数据宽度是16位，以字节编址，输入端是2是为了增加地址获取ALU 的第二个操作数。
【解析】（1）程序员可见的寄存器包括：程序计数器、通用寄存器和状态寄存器。其他的IR 、