问答题设一个按位编制的虚拟存储器，它可以满足1K个任务的需要，但在一段较长的时间内一般只有四个任务在使用，故用容量为四行的相连存储器组硬件来缩短被变换的虚地址中的用户位数，每个任务的程序空间最大可达4096个页，每页为512字节，实主存容量为2
20
位，设快表用CAM存储器构成，行数为22，快表的地址是经过散列技术形成的。为减少散列冲突，配有两套独立的相等比较器电路(这时快表的每行包含两个单元，各存放一个进行地址交换的表目)。请设计该地址变换机构：
(1)画出其虚实地址经快表变换的逻辑示意图；
(2)求相连存储器组中每个寄存器的相连比较位数；
(3)求散列变换硬件的输入位数和输出位数；
(4)求每个相等比较器的位数；
(5)求快表的总位数。
问答题键树(Trie)，又称数字查找树，它是一棵度大于等于2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。请用类C语言或类PASCAL语言编写一个在键树T上查找关键字等于给定值KEY的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。
问答题试分析在虚拟存储体系中，有哪些因素影响主存的命中率。
问答题一个由主存和cache组成的二级存储系统，参数定义如下：T
a
为系统平均存取时间，T
1
为cache的存取时间，T
2
为主存的存取时间，H为cache命中率，请写出T
a
与T
1
、T
2
、H参数之间的函数关系式。
问答题分区分配有哪几种?试比较各种分区分配的优缺点。
问答题设从键盘输入一个整数的序列：n，a
1
，a
2
，…，a
n
，其中n表示连续输入整数的个数。
(1)试编写一程序按整数值建立一个二叉排序树。
(2)在(1)的基础上将此二叉树上的各整数按降序写入一磁盘文件中。
问答题有一个不带头结点的单链表list，链表中结点都有两个域：数据域data和指针域link。已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用除该链表以外的任何链结点空间。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或．Java语言描述算法，关键之处给出注释。
问答题图8．6所示的系统是A、B、C三个设备组成的单级中断结构，它要求CPU在执行完当前指令时转向对中断请求进行服务。现假设：Toc为查询链中每个设备的延迟时间；TA、TB、TC分别为设备A、B、C的服务程序所需的执行时间；TS、TR为保存现场和恢复现场所需时间；主存的工作周期TM。试问：①分析CPU处理设备A、B、C的服务程序所需的执行时间。注意：“中断允许”机构在确认一个新中断之前，先要让即将被中断的程序的一条指令执行完毕。②就这个中断请求环境来说，系统在什么情况下达到中断饱和?也就是说，在确保请求服务的三个设备都不会丢失信息的条件下，允许出现中断的极限频率有多高?③如果将系统改为多级中断系统，极限频率如何变化?
问答题指令格式结构如下所示，试分析指令格式及寻址方式特点。
问答题某计算机字长为16位，主存地址空间大小为128KB，按字编址，采用单字指令格式，指令各字段定义如下：转移指令采用相对寻址方式，相对偏移是用补码表示，寻址方式定义如下：请回答下列问题：(1)该指令系统最多可有多少条指令?该计算机最多有多少个通用寄存器?存储器地址寄存器(MAR)和存储器数据寄存器(MDR)至少各需多少位?(2)转移指令的目标地址范围是多少?(3)若操作码0010B表示加法操作(助记符为add)，寄存器R4和R5的编号分别为100B和101B，R4的内容为1234H，R5的内容为5678H，地址1234H中的内容为5678H，地址5678H中的内容为1234H，则汇编语言为add(R4)，(R5)+(逗号前为源操作数，逗号后为目的操作数)对应的机器码是什么(用十六进制表示)?该指令执行后，哪些寄存器和存储单元的内容会改变?改变后的内容是什么?
问答题处理机管理具有哪些功能?它们的主要任务是什么?
问答题用补码运算方法求x+y的值。(1)x=0．1001，y=0．1100(2)x=－0．0100，y=0．1001
问答题一台处理机具有如下指令字格式：其格式表明有8个通用寄用器(长度16位)，X指定寻址模式，主存最大容量为256K字。(1)假设不用通用寄存器也能直接访问主存的每一个操作数，并假设操作码或OP=6位，请问地址码域应分配多少位?指令字长度应有多少位?(2)假设X=11时，指定的那个通用寄存器用作基值寄存器，请提出一个硬件设计规则，使得被指定的通用寄存器能访问1M主存空间中的每一个单元。
问答题有一个处理机，主存容量1MB，字长1B，块大小16B，cache容量64KB。若cache采用全相联映射，对内存地址B0010、CABBE给出相应的标记和字号。
问答题试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。
问答题设某系统采用页式虚拟存储管理，页表存放在主存中。(1)如果一次内存访问用50ns，访问一次主存需用多少时间?(2)如果增加TLB，忽略查找TLB占用的时间，并且75％的页表访问命中TLB，内存的有效访问时间是多少?
问答题如果要实现对8位数据进行汉明校验，需要设置的校验位数有几位?设计该汉明校验码的编码。
问答题设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。
问答题设结点结构为(data，link)，试用一个全局指针p和某种链接结构实现一个队列，画出示意图，并给出入队addq和出队deleq过程，要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
问答题以孩子一兄弟表示法存储的森林的叶子结点数(要求描述结构)。