问答题假设主存只有a，b，c三个页框，组成a进c出的FIFO队列进程，访问页面的序列是0，1，2，4，2，3，0，2，1，3，2号。若采用：①FIFO算法；②FIFO+LRU算法。用列表法求两种策略的命中率。
问答题试构造对5个元素进行排序，最多只用7次比较的算法。
问答题试述五层协议的网络体系结构的要点，包括各层的主要功能。
问答题已知一个带有头结点的单链表L，其结点结构由两部分组成：数据域data，指针域link。设计一个算法，以最高效的方法实现在单链表中删除数据域最小值结点。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
问答题请用图示说明三级存储体系分别由哪些部分组成，并比较caehe—主存和主存—辅存这两个存储层次的相同点和不同点。
问答题某模型机的数据通路结构如下图所示。用寄存器传送语句(如PC→MAR)，拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0)，Y(R1)，源和目的操作数地址均采用变址寻址，第1个参数X为源操作数的形式地址，第2个参数为目的操作数的形式地址，分别位于指令的第2个和第3个存储字。(2)数据求反指令COM一一(R0)，采用自减型寄存器间接寻址，结果送回自减后的地址单元。
问答题图5．9示出7条指令的微程序流程图，其中一个方框表示一条微指令，框内字母代表微命令码。微指令地址采用断定方式并规定用7位二进制数表示(用八进制写出)，P(i)为判别测试标志，其值由微指令中转移控制字段给出，具体含义如下：P(0)：按微指令下址字段执行下一条微指令P(1)：按指令寄存器IR7，IR6，IR5修改微地址寄存器后3位并按新地址执行下一条微指令P(5)：按进位标志Ci修改微地址寄存器最高位并按新地址执行下一条微指令要求：(1)按微指令①的微地址为起始条件，标出全部微指令的微地址(标在方框右上角)。(2)对标定①、②、③、⑧、的五条微指令，列表写出每条微指令在控存中的地址以及每条微指令的内容。
问答题并发使得处理机的利用率得到提高，其主要原因是处理机与I／O可以同时为多个进程服务，也即处理机与I／O设备真正地并行。但是处理机的利用率提高并不是简单地将两个进程的处理机利用率相加，而是遵循一定的规律。现在有一个计算机系统采用多道程序技术实现了并发，调度算法采用时间片轮转，时间片很小可以不计进程并发时的次序。忽略计算机系统的开销。假设进程创建时间和完全占有CPu运行的确切时间如下表所示。已知其I／O繁忙率为80％，处理机的利用率为20％。请计算并填写下列空格和图表空格处。
问答题设有15 000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素。在快速排序、堆排序、归并排序、基数排序和希尔排序中，宜采用哪种方法并说明理由?
问答题何谓分布式仲裁?
问答题利用IDT132(2K×16)双端口存储器芯片，设计一个8K×32位的双端口存储器，需要多少芯片?
问答题某同构双核处理机结构如图9．7所示。处理机采用两级cache结构，每个核都有自己私有的L1cache，两个核共享L2cache。L1cache行大小为2KB，采用2两路组相联映射，访问延迟为30ns／字。L2共享cache行大小为4KB，采用直接映射方式，访问延迟为80ns／字。主存的访问延迟为200ns／字。处理机字长为32位。已知该处理机上运行的进程含两个线程，代码如下：线程1：intA[1024]；intsa=0；for(i=0；i＜1024；i++){sa=sa+A[i]；}线程2：intB[1024]；intsb=0；for(i=0；i＜＜1024；i++){sb=sb+B[i]；}已知int字长为32位，初始状态下数组A和数组B均存放在主存中，运算结果存放在处理机内的寄存器中。(1)若主存中的数组A和数组B映射到L2cache中的不同行，且在L2cathe中从该行0地址开始存放数组元素。请计算在最坏的情况下，进程执行完毕所需要的时间。(2)若主存中的数组A和数组B映射到L2cache中的同一行，且在L2cache中从该行0地址开始存放数组元素。请计算在最坏的情况下，进程执行完毕所需要的时间。
问答题假设K
1
，…，K
n
是n个关键词，试解答：
(1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K
1
，K
2
，…，K
n
，时，用算法建立一棵以LLINK—RLJNK链接表示的二叉查找树。
(2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。假定该二叉查找树的嵌套括号表示结构为B(A，D(C，E))。
问答题将十进制数20．59375转换成IEEE754标准的64位二进制存储内容。
问答题CPU支持二级存储器结构：其中L
1
cache包含1000个字，存取时间0．01μs，L
2
cache包含100000个字，存取时间0．1μs。假定要存取的一个字在L
1
cache，则CPU能直接存取它；如果它在L
2
cache，则这个字首先传送到L
1
cache，然后再由CPU存取它。为了简化，不考虑CPU确定这个字是在L
1
还是L
2
所需的时间。假定95％的字都是在L
1
cache中找到，求存取一个字的平均时间是多少?
问答题某一计算机系统采用虚拟页式存储管理方式，当前在处理机上执行的某一个进程的页表如下所示，所有的数字均为十进制，每一项的起始编号是0，并且所有的地址均按字节编址，每页的大小为1024B。(1)将下列逻辑地址转换为物理地址，写出计算过程，对不能计算的说明为什么?0793，1197，2099，3320，4188，5332(2)假设程序欲访问第2页，页面置换算法为改进的CLOCK算法，请问该淘汰哪页?如何修改页表?上述地址的转换结果是否改变?变成多少?
问答题有一存储器堆栈。其栈底地址为300，且有a，b，c三个数据依次存放在堆栈中，a放在栈底。CPU中有一硬件堆栈指示器SP，且用通用寄存器R
1
作为数据交换器。试画出数据c出栈以前与出栈以后堆栈、SP与通用寄存器R
1
的状态。
问答题已知某计算机的运算器可以完成算术运算和逻辑运算，A和B为两寄存器，请给出一种方法将A和B两个寄存器的内容互换，但不使用其他暂存寄存器。
问答题分析图8．4逻辑示意图的功能。
问答题设[x]
补
=x
0
．x
1
x
2
…x
n
，求证：
[1／2x]=x
0
．x
0
x
1
x
2
…x
n