2018年沈阳师范大学软件学院862计算机应用技术基础综合之计算机组成原理考研强化五套模拟题
● 摘要
一、简答题
1． 指令和数据均存放在内存中，计算机如何区分它们是指令还是数据？
【答案】（1）取指周期中从内存读出的信息流是指令流，它流向控制器；
（1）执行器周期中从内存读出的信息流是数据流，它流向运算器。
2． 总线的一次信息传送过程大致分哪几个阶段? 若采用同步定时协议，请画出读数据的同步时序图。
【答案】总线的一次信息传送过程，大致分为五个阶段：请求总线、总线仲裁、寻址（目的地址）、信息传送、 状态返回（或错误报告）。读数据同步时序图如图所示：
图 读数据同步时序图
二、分析题
3． 图（a ）是有四个部件（控制器）共享总线的、分布式同步SBI 总线定时示意图，每个控制器对应一根数据传送请求线TR ，其优先权次序是
完成一个数据传送。
最高，最低；这四条线又都接到各个控制器，每个控制器内部有一个自己是否可用总线的判别电路。公共时钟信号的周期为T , 每个周期可
图
（1）叙述某个控制器要求使用SBI 总线进行数据传送的实现过程。
（2）图（b ）是图（a ）系统的一个数据传送序列的时序图，试分析其总线控制过程。
【答案】（1）某个控制器要求使用SBI 总线进行数据传送的步骤如下：
①控制器在决定要进行数据传送的下一个周期T ，在本设备对应的请求线上发出TR 信号。 ②在该周期末尾判断优先权更高的TR 线状态。
③ 如果没有更高的TR 请求，则撤掉本身的TR 请求，在下一周期进行数据传送；如果有更高的TR 请求， 则不撤掉本身的TR 请求，继续做步骤②。
（2）图（b ）的时序图表示一个有三个设备先后控制总线，且设备2连续传送两个数据的数传序列。 三个设备（控制器）控制总线的过程如下：
①控制器3在②在
③在
④在期进行数据传送。 结束时，控制器2
识别是高的，所以继续保持，在为高，等待传送机会；而控制器在周期进行数据传送。
以占用T5周1识别没有更高级的请求，故撤去周期进行数据传送。 周期传送数据的同时，升高周期发总线请求控制器1和控制器2在周期发总线请求和 在周结束时，控制器3的判别电路识别没有优先权更高的TR 请求，因而撤掉结束时，控制器2识别没有更高级的请求，便撤掉具有最尚优先权。 ⑤控制器2希望连续传送两个数据，所以在期传送第二个数据，因为
图（a ）中，控制器4没有信号，这是因为它的优先级最低，其他控制器不必获得TR 信号，控制器4传送数据前不需要发请求信号，在没有任何TR 请求的下一周期便可传送数据。不固定分配给任何控制器，只给需连续传送数据（并已获得总线控制制权）的控制器用。
4． 如图表示使用页表的虚实地址转换条件，页表存放在相联存储器中，其容量为8个存储单元，求：
（1）当CPU 按虚拟地址1去访问主存时，主存的实地址是多少？
（2）当CPU 按虚拟地址2去访问主存时，主存的实地址是多少？
（3）当CPU 按虚拟地址3去访问主存时，主存的实地址是多少？
图
【答案】（1）用虚拟地址为1的页号15作为页表检索项，查得页号为15的页在主存中的起始地址为80000, 故将80000与虚拟地址中的页内地址0324相加，求得主存实地址为80324。
（2）同理，主存实地址
（3）虚拟地址3的页号为48, 查页表时，发现此页面在页表中不存在，此时操作系统暂停用户作业程序的执行，转去查页表程序。如该页面在主存中，则将该页号及该页在主存中的起始地址写入主存；如该页面不在主存中，则操作系统要将该页面从外存调入主存，然后将页号及其主存中的起始地址写入页表。
三、综合应用题
5． 一个长度为的升序序列S , 处在第个位置的数为S 的中位数。例如，若序列Sl=（11, 13，15, 17, 19），则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2, 4, 6, 8, 20），则S1和S2的中位数是11。现有两个等长升序序列A 和B ，试设计一个时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C 或C++或JA V A 语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。
【答案】（1）算法的基本设计思想：分别求两个升序序列A 和B 的中位数，设为a 和b 。 ①若a=b，则a 或b 即为所求的中位数。
②否则，若中位数只能出现（a ，b ）范围内，舍弃a 所在序列A 的较小一半，同时舍弃
中位数只能出现（b ，a ）范围内，舍弃1）所在序列B 的较小b 所在序列B 的较大一半。若
一半，同时舍弃a 所在序列A 的较大一半。
③在保留的两个升序序列中求出新的中位数a 和b ，重复上述过程，直到两个序列中只含一个元素时为止，则较小者即为所求的中位数。
（2）用C 语言算法描述如下：