问答题图10．12所示为双总线结构机器的数据通路，IR为指令寄存器，PC为程序计数器(具有自增功能)，M为主存(受R／信号控制)，AR为地址寄存器，DR为数据缓冲寄存器，ALU由加、减控制信号决定完成何种操作，控制信号G控制的是一个门电路，另外，线上标注有小圈表示有控制信号，例中yi表示y寄存器的输入控制信号，R1o为寄存器R1的输出控制信号，未标字符的线为直通线，不受控制。“ADDR2，R0”指令完成(R0)+(R0)→R0的功能操作，画出其指令周期流程图(假设该指令的地址已放入PC中)，并在流程图每一个CPU周期右边列出相应的微操作控制信号序列。
问答题假设主存容量为16M×32位，cache容量为64K×32位，主存与cache之间以每块4×32位大小传送数据，请确定全相联映射方式的有关参数，并画出全相联映射方式的存储器地址格式。
问答题写出快速排序的非递归算法。
问答题PPP协议的主要特点是什么?为什么PPP不使用帧的编号?PPP适用于什么情况?
问答题简述中断处理过程(要求尽可能完整)。
问答题什么是USB总线?USB总线有什么特点?USB的数据传输方式有哪些?
问答题某计算机的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／O的时间占整个CPU时间的百分比是多少?(假设DMA与CPU之间没有访存冲突)
问答题已知二叉树T的结点形式为(llink，data，count，rlink)，在树中查找值为X的结点，若找到，则记数(count)加l；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
问答题什么是快重传和快恢复算法?
问答题设变量h放在寄存器r2，数组A的基值放在寄存器r3，请将下面C语句翻译成ARM汇编语言代码。C赋值语句是；A[12]=h+A[8]
问答题试找出分别满足下面条件的所有二叉树： (1)前序序列和中序序列相同。 (2)中序序列和后序序列相同。 (3)前序序列和后序序列相同。 (4)前序、中序、后序序列均相同。
问答题什么是抢占式优先级调度和非抢占式优先级调度?
问答题已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?
(1)关键字自小到大有序(key
1
＜key
2
＜…＜key
n
)；
(2)关键字自大到小逆序(key
1
＞key
2
＞…＞key
n
)；
(3)奇数关键字顺序有序，偶数关键字顺序有序(key
1
＜key
3
＜…，key
2
＜key
4
＜…)；
(4)前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key
1
＜key
2
＜…＜key
m
，key
m+1
＞
key
m+2
＜…＜key
n
，m为中间位置)。
问答题设某计算机有变址寻址、间接寻址和相对寻址等寻址方式，一个指令字长等于一个存储字。设当前指令的地址码部分为001AH，正在执行的指令所在地址为1F05H，变址寄存器中的内容为23AOH。已知存储器的部分地址及相应内容如下表所示。(1)当执行取数指令时，如为变址寻址方式，取出的数为多少?(2)如为间接寻址，取出的数为多少?(3)设计算机每取一个存储字PC自动加1，转移指令采用相对寻址，当执行转移指令时，转移地址为多少?若希望转移到23A0H，则指令的地址码部分应设为多少?
问答题已知某8位机的主存采用半导体存储器，地址码为18位，若使用4K×4位RAM芯片组成该机所允许的最大主存空间，并选用模块条的形式，问： (1)若每个模块条为32K×8位，共需几个模块条? (2)每个模块内共有多少片RAM芯片? (3)主存共需多少RAM芯片?CPU如何选择各模块条?
问答题用128K×8位的SRAM芯片设计一个总容量为512K×16位的存储器，既能满足字节存取，又能满足以16位字的存取。画出存储器芯片的连接图。
问答题设存储器容量为32字，字长64位，模块数m=4，分别用顺序方式和交叉方式进行组织。存储周期T=200ns，数据总线宽度为64位，总线传送周期τ=50ns。问顺序存储器和交叉存储器的带宽各是多少?
问答题假设一条指令的指令周期分为取指令、指令译码、执行指令三个子过程段，且这三个子过程延迟时间相等，即每个子过程延迟时间都为T。假设某程序共同n=10000条指令，请写出如下两种情况下CPU执行该程序所需的时间，画出时空图。(1)指令顺序执行方式；(2)指令流水执行方式。
问答题二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后，此树仍然是一棵二叉排序树，并且高度没有增长(注意：可不考虑被删除的结点是根的情况)。
问答题假定在一个8位字长的计算机中运行如下类C程序段：unsigned int x=134：unsigned int y=246；int m=x；int n=y；unsifined int z1=x－y；unsigned int z2=x+y；int k1=m－n；int k2=m+n；若编译器编译时将8个8位寄存器R1～R8分别分配给变量x、y、m、n、z1、z2、k1和k2。请回答下列问题：(提示：带符号整数用补码表示)(1)执行上述程序段后，寄存器R1、R5和R6的内容分别是什么(用十六进制表示)?(2)执行上述程序段后，变量m和k1的值分别是多少(用十进制表示)?(3)上述程序段涉及带符号整数加／减、无符号整数加／减运算，这四种能否利用同一个加法器及辅助电路实现?简述理由。(4)计算机内部如何判断带符号整数加／减运算的结果是否发生溢出?上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出?