当前位置：问答库＞考研试题

一、应用题

1． 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？

【答案】有两种方法，具体如下：

（1）对该算术表达式（二叉树> 进行后序遍历. 得到表达式的后序遍历序列，再按后缀表达式求值。

（2）递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符（+、

一、*、/等） 进行求值。

2． 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，则它的中序前驱结点没有右孩子。

【答案】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点：叶结点或仅有右子树的结点；而其中序前驱是其左子树上按中序遍历的最后个结点：叶结点或仅有左子树的结点。命题得证。

3． 在如图1所示的伙伴系统中，回收两块首地址分别为768及128、大小为的存储块，请画出回收后该伙伴系统的状态图。

图1

【答案】因为

小为

因为所以768和所以首址大小为互为伙伴，伙伴合并后，首址为768，块大的块和首址512、大小为的块合并，成为首址

将其插入可利用空间表中。回其伙伴地址为512、；大小为的空闲块。因为收后该伙伴系统的状态图如图2所示：

图2 回收后该伙伴系统的状态图

4． 试比较顺序文件、索引非顺序文件、索引顺序文件、哈希文件的存储代价，检索、插入、删除记录时的优点和缺点。

【答案】（1）顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序文件不能像顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”，只能通过复制整个文件实现上述操作。

（2）索引非顺序文件适合随机存取，不适合顺序存取，因主关键字未排序，若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织，因主文件有序，既可顺序存取也可随机存取。索引非顺序文件是稠密索引，可以“预查找”，索引顺序文件是稀疏索引，不能“预查找”，但由于索引占空间较少，管理要求低，提高了索引的查找速度。

（3）散列文件也称直接存取文件，根据关键字的哈希函数值和处理冲突的方法，将记录散列到外存上。这种文件组织只适用于像磁盘那样的直接存取设备，其优点是文件随机存放，记录不必排序，插入、删除方便，存取速度快，无需索引区，节省存储空间。缺点是散列文件不能顺序存取，且只限于简单查询。经多次插入、删除后，文件结构不合理，需重组文件，这很费时。

5． 某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 、