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

一、综合题

1． 某16位计算机中, 带符号整数用补码表示, 数据Cache 和指令Cache 分离。题44表给出了指令系统中部分指令格式, 其中Rs 和Rd 表示寄存器, mem 表示存储单元地址, (X)表示寄存器X 或存储单元X 的内容。

表 指令系统中部分指令格式

该计算机采用5段流水方式执行指令, 各流水段分别是取指(IF)、译码/读寄存器(ID)、执行/计算有效地址(EX)、访问存储器(M)和结果写回寄存器(WB), 流水线采用“按序发射, 按序完成”方式, 没有采用转发技术处理数据相关, 并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。

(1)若int 型变量x 的值为-513, 存放在寄存器R1中, 则执行指令“SHRR1”后, R1的内容是多少？(用十六进制表示)

(2)若某个时间段中, 有连续的4条指令进入流水线, 在其执行过程中没有发生任何阻塞, 则执行这4条指令所需的时钟周期数为多少？

(3)若高级语言程序中某赋值语句为

别表示为和和b 均为int 型变量, 它们的存储单元地址分。该语句对应的指令序列及其在指令流水线中的执行过程如下图所示。则

这4条指令执行过程中, 的ID 段和的IF 段被阻塞的原因各是什么？

图 指令序列及其执行过程示意图

(4)若高级语言程序中某赋值语句为

元地址分别表示为, x 和a 均为unsignedint 类型变量, 它们的存储单, 则执行这条语句至少需要多少个时钟周期? 要求模仿上图画出这条语

补, 即指令执行前

。 , 右移1wei 后

句对应的指令序列及其在流水线中的执行过程示意图。 【答案】(1)x的机器码为为

(2)至少需要1111B , 即指令执行后个时钟周期数。

(3)的ID 段被阻塞的原因:因为

与和都存在数据相关, 需等到和将结果写回寄存器后, 才能读寄存器内容, 所以的ID 段被阻塞。

的正段被阻塞的原因:因为的前一条指令在HD 段被阻塞, 所以的IF 段被阻塞。

(4)对应的指令序列为:

这5条指令在流水线中的执行过程如下图所示, 执行语句最少需要17个时钟周期。

2． 下列广义表，可以唯一对应一棵二叉树的有（ ）。并归纳出唯一对应的条件。

(1)(A(B(D，E) ，C(F)))

(2)(A(B(D，E) ，C))

(3)(A)

(4)(A(B(C，D(E))))

(5)（ ）

【答案】唯一对应一棵二叉树的有(2)、(3)和(5)。唯一对应的条件:空表、只有一个元素的表、每个子表个数是零或是2的表。

3． 在一棵表示有序集S 的二叉搜索树(binary search tree)中，任意一条从根到叶结点的路径将S 分为3部分:在该路径左边结点中的元素组成的集合S1; 在该路径上的结点中的元素组成的集合S2; 在该路径右边结点中的元素组成的集合S3; 有？为什么？

【答案】该结论不成立。例如，本题中对于任一

f 的左子树上。对于从a 到根结点路径上的所有，可在S2中找到a 的最近祖先f 。a 在，有可能f 在b 的右子树上，因而a 也就在。若对于任意的是否总b 的右子树上，这时a>b，因此a

均有a

4． 输入一个正整数序列(53，17，12，66，58，70，87，25，56，60) ，试完成下列各题。

(1)按次序构造一棵二叉排序树BS 。

(2)依此二叉排序树，如何得到一个从大到小的有序序列？

(3)画出在此二叉排序树中删除“66”后的树结构。

【答案】(1)构造的二叉排序树如图1所示:

图1二叉排序树

(2)若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；最后中序遍历左子树。

(3)如图2所示:

图2

5． 证明:置换选择排序法产生的初始归并段的长度至少为m(m是所用缓冲区的长度) 。

【答案】由置换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时(即初始归并段) ，缓冲区中m 个元素中除最小元素之外，其他m －1个元素均大于第一个选出的元素，即当以后读入元素均小于输出元素时，初始归并段中也至少能有原有的m 个元素。