2017年东北师范大学数据结构(跨学科加试)复试仿真模拟三套题
● 摘要
一、应用题
1． 某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效，为0时表示无效，例如控制信号MDRinE 为1表示允许数据从DB 打入MDR ，MDRin 为1表示允许数据从内总线打入MDR 。假设MAR 的输出一直处于使能状态。加法指令“ADD （Rl ）, R0”的功能为（R0）+（（R1））－（R1）, 即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。
图
下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。
表
【答案】执行阶段每个节拍（时钟周期）的功能和有效控制信号见下表。
表
2． 某16位计算机中，带符号整数用补码表示，数据Cache 和指令Cache 分离。题表给出了指令系统中部分指令格式，其中Rs 和Rd 表示寄存器，mem 表示存储单元地址，（X ）表示寄存器X 或存储单元X 的内容。
表 指令系统中部分指令格式
该计算机采用5段流水方式执行指令，各流水段分别是取指（IF ）、译码/读寄存器（ID ）、执行/计算有效地址（EX ）、访问存储器（M ）和结果写回寄存器（WB ）, 流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。
（1）若int 型变量x 的值为-513, 存放在寄存器R1中，则执行指令“SHR R1”后，R1的内容是多少？（用十六进制表示）
（2）若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少？
（3）若高级语言程序中某赋值语句为址分别表示为
和b 均为int 型变量，它们的存储单元地
该语句对应的指令序列及其在指令流水线中的执行过程如题图所示。
则这4条指令执行过程中，的ID 段和的IF 段被阻塞的原因各是什么？
图 指令序列及其执行过程示意图
（4）若高级语言程序中某赋值语句为储单元地址分别表示为
【答案】 （1）x 的机器码为1110 1111 1111B, 即指令执行后
（2）至少需要
即指令执行前（Rl ） =FDFFH, 右移lwei 后为1111
个时钟周期数。
x 和a 均为unsigned int 类型变量，它们的存
则执行这条语句至少需要多少个时钟周期? 要求模仿题图画出这
条语句对应的指令序列及其在流水线中的执行过程示意图。
（3）的ID 段被阻塞的原因：因为
与和都存在数据相关，需等到和将结果写回寄存器后，才能读寄存器内容，所以的ID 段被阻塞。
的IF 段被阻塞的原因：因为14的前一条指令在ID 段被阻塞，所以，的IF 段被阻塞。（4）
对应的指令序列为：
这5条指令在流水线中的执行过程如下图所示，执行
语句最少需要17个时钟周期。
3． 已知世界六大城市为：北京（Pe ）、纽约（N ）、巴黎（Pa ）、伦敦（L ）、东京（T ）、墨西哥，下表给定了这六 大城市之间的交通里程：
（M ）
（1）画出这六大城市的交通网络图； （2）画出该图的邻接表表示法；
（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。