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

一、应用题

1． 如果两个串含有相等的字符，能否说它们相等？

【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。

2． 证明任一结点个数为n 的二叉树的高度至少为0 （logn ）。

【答案】最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n 个结点的二叉树的最低高度是h ，则n 应满足。解此不等式，并考

虑h 是整数. 则有即任一结点个数为n 的二叉树的高度至少为

3． 试证明：同一棵二叉树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的

，例如前序后序运对称序。 相对位置出现（即先后顺序相同）

，中序遍历是“左根右”，后序遍历是“左右根”【答案】前序遍历是“根左右”。三种遍历中

只是访问 " 根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位罝出现。

4． 设G=（V , E）以邻接表存储，如图所示，试画出图1的深度优先生成树和广度优先生成树。

图1

【答案】设从顶点1开始遍历，则深度优先生成树如图2所示，广度优先生成树如图3所示：

图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 、

MAR 和MDR 等 是CPU 的内部工作寄存器，对程序员不可见。

（2）ALU 中共有7种命令，用三位即可区别表示，SR 共有三种命令二位二进制即可表示。 （4）操作符命令，传输等都需要控制信号进行控制。

6． 某计算机的主存地址空间大小为256MB ，按字节编址，指令Cache 和数据Cache 分离，均有8个Cache 行，每个Cache 行大小为64B , 数据Cache 采用直接映射方式。现有两个功能相同的程序A 和B , 其伪代码如下所本：程序A :程序B :

假定int 类型数据用32位补码表示，程序编译时i , j , sum 均分配在寄存器中，数组a 按行优先方式存放，首地址320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。

（1）若不考虑用于Cache —致性维护和替换算法的控制位，则数据Cache 的总容量为多少？ （2）数组数据号从0开始）？

（3）程序A 和B 的数据访问命中率各是多少? 哪个程序的执行时间更短？

【答案】（1）每个Cache 行对应一个标记项，标记项包括有效位、脏位、替换控制位以及标记位。由主存空间大小为256M 可知地址总长度为28位，其中块内地址为log264=6位，Cache 块号为log28=3位，不考虑一致性维护和替换算法的控制位，则Tag 的位数为28-6-3=19位，还需一位有效位，数据Cache 共有8行，故Cache 的总容量为

（2）数组a 在主存的存放位置及其与Cache 之间的映射关系如下图所示： 和各自所在的主存块对应的Cache 行号分别是多少（Cache 行