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

一、应用题

1． 如果输入序列为123456, 试问能否通过栈结构得到以下两个序列：435612和135426; 请说明为什么不能或如何才能得到。

【答案】输入序列为123456, 不能得出435612, 其理由是，输出序列最后两元素是12, 前面4个元素（4356）得到后，栈中元素剩12, 且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1; 然后2和3入找，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。

2． 对下面的关键字集若查找表的装填因子为0.8，采用线性探测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。

【答案】（1）由于装填因子为0.8，关键字有8个，所以表长为

哈希函数，哈希函数为

（2）哈希表如表所示：

表 哈希表

（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，

当其哈希地址为时的查找次数。本例中

（4）算法如下：

第 2 页，共 21 页 用除留余数法设计 故查找失败和查找成功时的平均查找长度分别为：

3． 在树和树中查找关键字时，有什么不同？

树的非终端结点是索引部分，其查找从根开始，从根往下查到关键

. 树还可以在最下层从最小关【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。字后，要继续查到最下层结点，得到查找成功与否的结论。另外，

键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

4． 某程序中有如下循环代码段p :

P 起始地址 为0804 8100H，对应的汇编代码和机器代码如下表所示

假设编译时变量sum 和i 分别分配在寄存器R1和R2中。常量N 在寄存器R6中，数组A 的首地址在寄存器R3中，程序段

执行上述代码的计算机M 采用32位定长指令字，其中分支指令Bne 采用如下格式，

Op 为操作码：Rs 和Rd 为寄存器编号：OFFSET 为偏移量，用补码表示。请回答下列问题，并说明理由。

（1）M 的存储器编址单位是什么？

（2）已知sll 指令实现左移功能，数组A 中每个元素占多少位？

（3）表中bne 指令的OFFSET 字段的值是多少？已知bne 指令采用相对寻址方式，当前PC 内容为bne 指令地址，通过分析表中指令地址和bne 指令内容，推断出bne 指令的转移目标地址计算公式。

（4）若M 采用如下“按序发射、按序完成”的5级指令流水线：IF （取指）、ID （译码及

，且硬件不采取任何转发措施，分取数）、EXE （执 行）、MEM （访存）、WB （写回寄存器）

支指令的执行均引起3个时钟周期阻塞，则P 中哪些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令1 的执行不会因为与指令5的数据相关而发生阻塞？

【答案】（1）由题可知，指令为32为即4个字节，而程序执行时是以4为间隔逐条取指令的，故可知M 的存储器是采用字节编址。

（2）32位，因为sll 中实现左移，而（R2） <<2 R4即左移两位就是乘以4，所以是

位

第 3 页，共 21 页

（3）由Bne 的指令格式可知其OFFSET 为指令的后16位，而Bne 的机器码码为1446 FFFAH，所以Bne 的OFFSET 为FFFAH 即-6。

由题可知Bne 采用相对寻址方式，故有效地址

为当前Bne 指令的地址

即而取完Bne 而PC 的值指令后

，

而要跳转到指令1的地址08048100H ，两者相差了18H 也

就是24个字节，而OFFSET 是-6, 故转移目标地址计算公式为（PC

）

（4）由指令序列可知，指令1需写R4而指令2需读R4, 故指令2会因为数据相关而发生阻塞，同理指令3、指令4也会因为数据相关而发生阻塞；而指令6为分支指令，故其存在控制冒险。因为分支指令会有3个时钟周期的阻塞，故指令1的执行不会因为指令5的数据相关而发生阻塞。

5． 某计算机采用16位定长指令字格式，其CPU 中有一个标志寄存器，其中包含进位/借位标志CF 、零标志ZF 和符号标志NF 。假定为该机设计了条件转移指令，其格式如下：

其中，00000为操作码OP ; C、Z 和N 分别为CF 、ZF 和NF 的对应检测位，某测位为1时表示需检测对应标志，需检测的标志位中只要有一个为1就转移，否则就不转移，例如，

若

OFFSET 是相对偏移则需检测CF 和NF 的值，当CF=1或NF=1时发生转移；

量，用补码表示。转移执行时，转移目标地址为

为请回答下列问题。

（1）该计算机存储器按字节编址，还是按字编址？该条件转移指令向后（反向）最多可跳转最多少条指令？

（2） 某条件转移指令的地址为200CH ，指令内容如下图所示，若该执行

时

则该指令执行后PC 的值是多少？若该指令执行时

则该指令执行后PC 的值又是多少？请给出计算过程。

（3）实现“无符号数比较小于等时转移”功能的指令中，C 、Z 和N 应各是什么？

（4）以下是该指令对应的数据通路示意图，要求给出中部件①〜③的名称或功能说明。 顺序执行时，下条指令地址

第 4 页，共 21 页