2018年齐鲁工业大学信息学院872数据结构考研强化五套模拟题
● 摘要
一、应用题
1． 某16位计算机主存按字节编码。存取单位为16位; 采用16位定长指令格式; CPU 采用单总线结构, 主要部分如下图所示。图中R0〜R3为通用寄存器; T 为暂存器; SR 为移位寄存器, 可实现直送(mov)、左移一位(left)、右移一位(right)3种操作, 控制信号为Srop , SR 的输出信号Srout 控制; ALU 可实现直送A(mova)、A 加B(add)、A 减B(sub)、A 与B(and)、A 或B(or)、非A(not)、A 加1(inc)7种操作, 控制信号为ALUop 。
图
请回答下列问题。
(1)图中哪些寄存器是程序员可见的？为何要设置暂存器T?
(2)控制信号ALUop 和SRop 的位数至少各是多少？
(3)控制信号Srout 所控制部件的名称或作用是什么？
(4)端点①〜⑨中, 哪些端点须连接到控制部件的输出端？
(5)为完善单总线数据通路, 需要在端点①〜⑨中相应的端点之间添加必要的连线。写出连线的起点和终点, 以正确表示数据的流动方向。
(6)为什么二路选择器MUX 的一个输入端是2？
【答案】(1)图中程序员可见的寄存器有通用寄存器R0〜R3和程序计数器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)操作符命令, 传输等都需要控制信号进行控制。
2． 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗? 栈可以用单链表实现吗？
【答案】不能得到序列2，5，3，4，6。因为根据输入序列，2进桟之后，2出栈，3，4，5依次进栈。5出栈，此时栈中剩下3，4。因为4在栈顶，所以4应该比3先出栈，不能得到提供的序列。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。
3． 某32位计算机, CPU 主频为800MHz , Cache 命中时的CPI 为4, Cache 块大小为32字节; 主存采用8体交叉存储方式, 每个体的存储字长为32位、存储周期为40ns ; 存储器总线宽度为32位, 总线时钟频率为200MHz , 支持突发传送总线事务。每次读突发传送总线事务的过程包括:送首地址和命令、存储器准备数据、传送数据。每次突发传送32字节, 传送地址或32位数据均需要一个总线时钟周期。请回答下列问题, 要求给出理由或计算过程。
(1)CPU和总线的时钟周期各为多少？总线的带宽(即最大数据传输率) 为多少？
(2)Cache缺失时, 需要用几个读突发传送总线事务来完成一个主存块的读取？
(3)存储器总线完成一次读突发传送总线事务所需的时间是多少？
(4)若程序BP 执行过程中, 共执行了100条指令, 平均每条指令需进行
为, 不考虑替换等开销, 则BP 的CPU 执行时间是多少？
【答案】(1)因为CPU 主频为800MHz , 故CPU 的时钟周期为:
总线时钟频率为200MHz , 故总线的时钟周期为:
总线宽度为
块。
(3)—次读突发传送总线事务包括一次地址传送和32B 数据传送:用1个总线时钟周期传输地址; 每隔=5tis启动一个体工作(各进行1次存取) , 第一个体读数据花费40ns , 之后数据存取与数
。
(4)BP的CPU 执行时间包括Cache 命中时的指令执行时间和Cache 缺失时带来的额外开销。
次访存, Cache 缺失率。 。 。 , 故总线带宽为(2)因为Cache 块大小为32B , 因此Cache 缺失时需要一个读突发传送总线事务读取一个贮存据传输重叠; 用8个总线时钟周期传输数据。读突发传送总线事务时间:
即执行时间=指令条数*CPI*时钟周期*命中率+访存次数*缺失率*缺失损失。命中时的指令执行时
间:
指令执行过程中Cache 缺失时的额外开销
。
BP 的CPU 执行时间:
=1010ns。
4． 组织待检索文件的倒排表的优点是什么？
【答案】倒排表作为索引的优点是索引记录快，因为从次关键字值直接找到各相关记录的物理记录号，倒排因此而得名(因通常的查询是从关键字查到记录) 。在插入和删除记录时，倒排表随之修改，倒排表中具有相同次关键字的记录号是有序的。
5． 已知有6个顶点(顶点编号为0--5) 的有向带权图G , 其邻接矩阵A 为上三角矩阵, 按行为主序(行优先) 保存在如下的一维数组中。
要求:
(1)写出图G 的邻接矩阵A 。
(2)画出有向带权图G 。
(3)求图G 的关键路径, 并计算该关键路径的长度。
【答案】(1)由题可以画出待定上三角矩阵的结构图如下(图中？为待定元素) :
500ns 。
可以看出, 第一行至第五行主对角线上方的元素分别为5, 4, 3, 2, 1个, 由此可以画出压缩存储数组中的元素所属行的情况, 如下图所示:
将各元素填入各行即得邻接矩阵:
(2)根据第一步所得矩阵A 容易做出有向带权图G , 如下:
相关内容
相关标签