2017年新疆大学数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 某计算机的CPU 主频为500MHz ，CPI 为5（即执行每条指令平均需要5个时钟周期）。假定某外设的数据传输率为0.5MB/S，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。
（1）在中断方式下，CPU 用于该外设I/O的时间占整个CPU 时间的百分比是多少？ （2）当该外设的数据传输率达到5MB/s时，改用DMA 方式传送数据。假定每次DMA 传送块大小为5000B , 且DMA 预处理和后处理的总开销为500个时钟周期，则CPU 用于该外设I/0时间占整个CTU 时间的百分比是多少？（假设DMA 与CPU 之间没有访存冲突）
【答案】（1）已知主频为500MHz ，则时钟周期=l÷500MHz=2ns，因为CPI=5, 所以每条指令，数据传输率为0.5MB/S, 所以传送时间平均5×2=10ns。又已知每中断一次传送32位（4个字节）=4÷0.5MB/s=
CPU 用于该外设I/0共需20条指令（中断服务程序包括18条指令+其他开销折
，花费时间=20×l0=200ns。CPU 用于该外设I/0的时间占整个CPU 时间的百分比合2条指令）
=200/8000×100%=0.025×100%=2.5%。
（2）改用DMA 方式传送数据，数据传输率为5MB/S，传送5000B 的时间=5000B÷5MB/s=lms。预处理和后处理的总开销时间=500×2ns=
CPU 用于该外设I/0时间占整个CPU 时间的百分比=
预处理和后处理的总开销时间÷传送数据的时间=l/1000×l00%=0.001×100%=0.1%。
2． 阅读下列算法，指出算法A 的功能和时间复杂性。
【答案】功能：将原单循环链表分解成两个单循环链表：其一包括结点h 到结点g 的前驱结点；另一个包括结点g 到结点h 的前驱结点。
时间复杂度：0（n ）。
3． 下图是5阶B 树，画出删去P 后的B 树，再画出删去D 后的B 树。
【答案】删除P 后
删除D 后
4． 某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个时钟周期。