1、写出影响算法执行的时间效率的主要因素，并指出哪些因素与算法的时间效率直接相关。
2、已知元素的入栈顺序为A,B,C,D,E，在所有可能的出栈顺序中，写出第一个出栈的元素为C 且第二个出栈的元素为D 的所有组合。
3、根据单词 5、有人说，折半查找的时间效率一定比顺序查找的时间效率高，你怎么看待这种说法？为什么？ 二、算法设计题<10’） 1] 中，请写出中序遍历该二叉树的非递归算法。已知一非空完全二叉树存放于数组BT[0..n 三、算法设计题<10’） 写出不带头结点的双向链表的插入排序算法。 四、简答题<4’×5） 1、数据传输控制方式有哪些？ 2、引入线程的目的是什么？ 3、P, V 操作是如何实现互斥的的？ 4、什么是死锁？产生死锁的原因是什么？ 5、什么是文件系统？ 五、判断题<1’×10） 略。<基本上来自于历年真题） 六、解答题<10’） 某机器字长为16 位，采用段页式存储管理算法，页内偏移为12 位，段表和页表内容如下，给出4 个虚拟地址<二进制形式），问哪个地 址产生缺段中断，哪个地址产生缺页中断，哪些地址可以转换为物理地址，并求转换后的物理地址。<地址格式中段号占1 位，段内页号 占3 位，页内偏移为12 位，另外，在给出的页表中，物理块号占6 位，最后又问该机器的最大物理内存是多少<答案：256 KB）。） 七、简答题<4’×4） 1、利用等值演算的方法，写出求命题逻辑公式的主范式的方法。 2、谓词逻辑中的永假式、可满足式、重言式、永真式之间的关系是什么？ xA,3、 xA, A 之间的真值关系是什么？ 4、如何判断公式中某个变元是约束变元还是自由变元？举例说明一个变元可以既是约束的又是自由的。 八、判断下列结论是否成立，并至少用两种方法证明你的判断<6’ + 8’） ( pq |q, r p 1、 r> R(x>>x(P(x>R(x>> |x(Q(x>Q(x>>, x(P(x>2、 1 / 14 九、填空题<1’×8） 1、冯•诺依曼计算机体系包括存储器、运算器、控制器和输入输出设备。 2、在总线同步控制方式种，哪一种速度最快，哪一种对电路故障最敏感？ 3、在程序查询方式、程序中断方式和DMA 方式中，哪一种方式主存与设备间有数据通路，哪一种方式使CPU 与外设串行化？ 4、指令中的操作数分别为立即寻址和寄存器直接寻址时CPU 访问主存的次数分别为多少次？ 5、存储器分层体系是根据程序访问的局部性原理提出的。 十、存储器扩展的题<6’） 某机器字长为16 位，最大物理内存为64 KB，最低地址的8 KB 存放BIOS 程序，其他空间存放用户程序，现有4K×4 的ROM 和4K×4 的SRAM，问各需要多少片？ 十一、Cache 题<8’） 主存大小为2 MB，Cache 大小为8 KB，采用2 路组相联方式，每个Cache 块大小为128 字节。 <1）求主存地址格式及各字段的位数和含义 <2）Cache 的格式 <3）Cache 的Tag 需多少位？ 十二、指令系统的设计<8’） 某机器字长为16 位，有8 个16 位的通用寄存器，请设计一指令系统，要求： <1）共有128 条双操作数指令，且必有一操作数为寄存器直接寻址，另一个操作数有4 种寻址方式，可以是立即寻址、寄存器直接寻址、 寄存器间接寻址或变址寻址，其中立即寻址和变址寻址的偏移量均为16 位； <2）指令所占的位数必须是16 的倍数且要尽可能地短。 要求： <1）写出影响指令系统设计的因素； <2）设计该机器的指令系统，写出各字段的位数和含义。 十三、微程序设计题<10’） 指令为SUB R0, (R1>，其中R0 为目的操作数，采用寄存器直接寻址，R1 为源操作数，寻址方式为寄存器间接寻址，每个机器周期包含 4 个节拍周期，写出该指令执行的详细微操作流程和对应处于有效状态的控制信号。 2 出 00 栈 7年 操 真题 作 一． 。 1．设a,b,c 三个元素的进栈次序是a,b,c，符号PUSH 与POP 分别表示对堆栈进行一次进栈操作和一次<1）请分别写出所有可能的出栈序列以及获得该出栈序列的操作序列； <2）指出不可能出现的出栈序列。 2．对于一个有向图，除了进行拓扑排序，还可以采用什么方法判断图中是否 存在回路？请简述判断原则。 2 / 14 3．请画出在右图3 阶B-树中插入关键字64 以后的B-树的状态。 4．在长度为n 的线性表中进行顺序查找。查找第i 个数据元素的概率为pi， 且分布如下：p1=1/2，p2=1/4，…，pn-1=1/2，pn=1/2 请求出在该线性表中查找成功的平均查找长度<要求写成关于n 的简单表达式形式） 二．请写一非递归算法，该算法在按值严格递增排列的顺序表A[1…n]中采用折半查找法查找值不小于ite m 的 最 小 元 素 。 若 表 中 存 在 这 样 的元素，则算法给出该最小元素在表中的位置，否则，给出信息0。 三．已知非空二叉树采用顺序存储结构，结点的数据信息依次存放于一维数组BT[0…n-1]中<假设每个结点 的 数 据 信 息 为 一 个 非 0 整 数 ； 若数组元素值为0，则表示该元素对应的结点在二叉树中不存在）。请写一算法，生成该二叉树的二叉链表结构。 四 ． 1．假设A 是命题逻辑中的任意公式。证明：存在一个合取范式B，使得A|=B 且B|=A。 2．假设A 是谓词逻辑中的公式，I 是一个解释。假设v1,v2 是I 的两个赋值。考虑以下两个性质： <1）对于<2）A 在断。 五．假设x 是变元符号，P，Q 是一元谓词符号，判断以下公式是否永真： x(P(x>→Q(x>> xQ(x>>。xP(x>→( 试分别使用解释赋值方法、公理化方法和归结方法证明所给出的判断。 六．1．什么是2 ． 进 程 与 PCB，它的三个主要组成部分是什么？ 线 程 最 根 本 的 差 别 是 什 么 ？ A 中的每个自由变元 x，都有 A 在 v1(x>=v2(x>。 I，v2 之下的真值。 I，v1 之下的真值等于 构造A，I，v1，v2 使得<1）不成立而<2）成立。判断当<1）成立时<2）是否成立，并证明所给出的判 3．在分区式存储管理中，什么是“地址重新定位”？动态和静态重新定位的区别是什么？ 4．哪一种RAID 保存两份数据？RAID4 与RAID5 的区别是什么？ 5．什么是FCB，它的三个主要组成部分是什么？ 七1345 ．． 实．． 段缓页时中存式．操 作断<存 C储系 统是A管 C理必由H可判须 比CE以 ）用一P一于 虚般 断操U定拟作 能存系 统发提储 器题的 速出高 的速管度的度理快 。 。 。 。 。 2．分布式操作系统的可靠性要求比单机操作系统的高。 6．死锁是不可避免的。 3 / 14 八．假设有6 个作业正在等待运行，它们所需的运行时间分别是：10，8，6，4，2 和X。不考虑并行、基 于 X 、 在 追 求 最 小 平 均 相 应 时 间 1 ． 运 算 器 的 核 心 是 < ） 。 2．常见的集中式总线判优控制方式有<）、<）和<）三种。 3．CPU 响应中断时需要保护程序断点，这里断点指的是<）的内容，它一般被保存到<）中。 4．浮点数加减法的基本运算过程是<）、<）和<）。 5．条件转移指令所依据的条件来自<）寄存器。 十 ． 1 用16K*8 的SRAM 芯片组成64K*16 的存储器，该存储器按16 位字编址，画出存储器扩展图？ 2．某8 位计算机主存容量32K 字节，组相联Cache 容量2K 字节，每组4 Blocks,每Block 64 个字节后a令 和。再c 4假 设重 h 条C复 a这e无c h样 操 作e 的 开读后数始数的指 令是 空过 的程加； 每，7速个C P U遍比地 址 从< 主 共 。 字 存存储单元0 开始顺序读取2176 个字节数据<即按地址0、1、2 的顺序一直读取到地址单元2175），然8 遍），Cache 速度是主存速度的10 倍，采用LRU 替换算法，假定块替换的时间忽略不计，计算采用C3．某机字长为16 位，采用定长指令格式，指令长度为16 位，包含32 条双地址指令、64 条单地址指段占5 位，请给出该机指令系统的操作码设计方案。 十一。画出微程序控制器的基本组成框图，说明其中各个部件的作用，并结合所画框图，简要说明微程序控制器的基本工作原理。20062．下面算法的功能是<）。 typedef struct node { datatype date。 struct node *link。 } *LinkList。 void FUN(LinkList lista, Linklist listb>{ LinkList p。 for (p=lista。 p->link。 p=p->link>。 p->link=listb。 } 3．若某堆栈初始为空，PUSH 与POP 分别表示对堆栈进行一次进栈与出栈操作，那么，对于输入序列a,b,c,d,e，经过PUSH，PUSH，POP， PUSH，POP，PUSH，PUSH 以后，输出序列是<）。 4．在具有n 个元素的非空队列中插入一个元素或者删除一个元素的操作的时间复杂度采用大O 形式表示为<）。 5．若一棵度为7 的树中有8 个度为1 个结点，有7 个度为2 的结点，有6 个度为3 的结点，有5 个度为4 的结点，有4 个度为5 的结点， 有3 个度为6 的结点，有2 个度为7 的结点，则该树一共有<）个结点。 6．若某非空二叉树采用顺序存储结构，结点的数据信息依次存放于一个一维数组中<假设数组的第一个元 年真题一．填空题 1．删除长度为n 的顺序表的第i 个数据元之前需要移动表中<）个数据元素。<1≦i≦n） 4 / 14 素的下标为1），下标分别为i 和j 的两个结点处在树中同一层的条件是<）。 对应的“判定树”的根结点的左孩子之值<元素在表中的位置）是<）。 9．设已知n 个关键字具有相同的散列函数值，并且采用线性探测再散列方法处理冲突，将这n 个关键字散列到初始为空的地址空间中， 一共发生了<）次散列冲突。 10．按照大顶堆积的定义，对序列<26，5，77，1，61，11，59，15，48，19）进行堆积排序，第二趟排序结束时序列的状态是<）。 二．假设长度为n 的顺序表A 中每一个数据元素均为整型数据，请写出在该顺序表中采用顺序查找发查找值为item 的数据元素的递归算 法。若查找成功，算法返回item 在表中的位置，否则，返回信息-1。<写成非递归算法不得分） 三．选择排序法每一趟排序的基本原理是从当前未排好序的那些元素中选择一个值最小的元素，将其与未排好序的那些元素的第一个元素 交换位置。根据这个原理，请写出对一个带有头结点的单链表按数据域值从小到大进行选择排序的算法。 约定：链结点构造为[data|link]，每一个链结点的数据域中存放一个整型数，但头结点数据域中不存放任何信息；设头结点指针为list。 限制：排序过程中不得申请任何链结点空间，也不得改变任何链结点的数据域内容。 四．1．写出{⊕，←→，→，∧，∨，﹁}的6 个极小完全集，并证明其中一个集的极小完全性。 x(A→B>2．用解释赋值方法、公理系统方法和归结方法三种方法证明以下公式是永真的： xB>。xA→→( xA→At五．对于一般公式A，指出当变元x 和项t 与公式A 之间满足什么关系时，公式 x 是永真的，并证明相应的结论。用例子说明当所 给出的条件不满足时，上述公式可能不永真。 六． 1．进程的基本构造部分是什么？什么是线程？线程于进程最根本的区别是什么？ 2．给出3 状态的基本进程状态图，给出5 状态进程的状态名称。 3．产生死锁的基本原因是什么？产生死锁的必要条件是什么？ 4．存储管理系统的主要功能是什么？ 5．输入输出设备分为几类？请举例说明。 七．判断题。 1．在进程退出后，它的线程还可以继续占有内存。 2．在存储管理中，可变式分区方法比固定式分区方法速度快。 3．无论用什么输入输出方法，申请CPU 中断是必须的。 4．虚拟文件系统就是网络文件系统。 5．交换 6．输入输出的缓冲器 请使用时间为横向坐标轴，并请在图中表明每个进程的“等待”和“运行”两种状态。 1．先来先服务 指令，存储器型操作数分存储器直接、存储器间接和基址寻址三种寻址方式，任意一个通用寄存器可作为基址寄存器，基址寻址的位移量 采用补码表示。 <1）设计并画出指令格式，并说明各个字段的含义。 <2）存储器直接寻址和基址寻址的寻址空间各是多少？ 2．简要说明独立请求总线优先权仲裁方式的工作过程。 3．16K*4 的DRAM 芯片，内部刷新地址记数器应该是多少位？用该芯片构造256K 字节的存储器，应使用多少芯片？ 十．某机主存容量1MB，两路组相联方式<每组仅有两块）的CACHE 容量为64KB，每 个数据块为256 字节。CPU 要顺序访问地址为20184H，58130H，201F5H 和381F0H 等4 个内存字节单元。已知访问开始前CACHE 第1 组<组地址为1）的两数据块均已被占用 <如图，图中Tag 的内容为二进制），CACHE 采用LRU 替换策略。 Tag 00100 Set1 Block 1 01011 1．CACHE 分多少组？ 2．给出主存的地址格式，说明个部分的位数与含义； 3．上述4 个数中哪些数能直接从CACHE 中读取？若能，说明实际访问的是CACHE 中哪一组的哪个数据 6 / 14 块的哪一个字节。 4．4 个数访问结束时Tag 内容如何变化。 十一。某机结构如题所示，该机字长16 位，图中所有寄存器均为16 位，控制器采用同步控制方式，每 个 操 寄 节 信 存拍CPU 作器周 周 数编期 号对期 包 括 4 ）令于 号 有核 效个 是心 状部节 拍基分态 ，的周 址 第控期 ，寻2制。 数据总线及内总线均为16 位，存储器周期与CPU 节拍周期时间相等。加法指令ADD R1，1000H 址，目的操作数R1 是寄存器直接寻址，指令编码长度32 位，第1 个16 位包含了操作码、寻址方式和个16 位是基址寻址的位移量1000H。请给出该指令执行过程的微操作序列和时序安排，并详细列出每个 2005年真题 一．若散列函数为H(key>= i MOD 7,其中，i 为关键字key 的第一个字母在英文字母表中的序号，并且采用线性探测再散列方法处理冲突。 请画出在一个初始状态为空、地址值域为[0..6]的散列表中依次插入下列关键字MON,TUE,WED,THU,FRI,SAT,SUN 以后的散列表。 7 / 14 二、所谓二叉树等价，是指它们不仅具有相同的拓扑结构，而且对应结点中包含相同的数据信息。 假设二叉树采用二叉链表存储结构，链结点构造为[lchild|data|rchild], 请写一递归算法，判断根结点指针分别为T1 与T2 的两棵二叉树是否 等价。若它们等价，算法返回1，否则返回0。<写成非递归算法不得分） 三、已知一具有n 个顶点的有向图G= 是否为该有向图的一个拓扑序列。若是，算法给出信息1，否则，给出信息0。 四、 1．若p1，p2，……，pm 是m 个不同的命题变元，A1，A2，……，An，B，C1，C2，……，Cm 是命题逻辑公式，并且A1，A2，…………An|=B， 证明： 2．用演绎定理证明├ 五、1．在谓词逻辑里，假设A，B 是公式，x 不是B 的自由变元。 BxA B）x若x 是B B 不成立的例子。xA B）xyP(x,y>|=x2．假设P 6．仅当一个进程退出临界区以后，另一进程才能进入相应的临界区。 7．打印机是一类典型的块设备。 8．虚拟存储器的最大存储空间为内存容量与硬盘容量之和。 八、我们将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写 者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读 8 / 14 者”必须等待，直到该“写者”完 成数据访问为止。试用P，V 操作正确实现“读者”与“写者”的同步。 九、1．按传输信息类别，系统总线一般包括<），<）和<）。 2．DRAM 的刷新方式一般有<）和<）两种。 3．中断响应时的保护现场实际上是指保存<）和<）的内容。 4．常见的微指令编码方式包括<），<）和<）三种。 十、1．某计算机的存储系统由Cache、主存和用于虚拟存储的磁盘组成。CPU 总是从Cache 中获得数据。若所访问的字在Cache 中，则 存取它只需要10ns，将所访问的字从主存装入Cache 需要40ns，而将它从磁盘装入主存则需要10us，假定Cache 的命中率为0.9，主存的 命中率为0.6，计算该系统访问一个字的平均存取时间。 2．指令系统格式设计过程中需要考虑哪些要素？并给出简简要说明。 3．某磁盘系统采用DMA 方式进行数据传送，磁盘转速为7200 转/分，分8 个扇区，每扇区1K 字节，磁盘与主存传诵数据的宽度为16 位。假定一条指令执行最长需要10us，是否可以采用一条指令执行结束时响应DMA 请求方案，为什么？ 十一、假设某机的主要部件包括：程序计数器PC，指令寄存器IR，通用寄存器R0、R1、R2、R3，暂存器C、D，算术逻辑运算单元ALU， 位移器SR，存储器地址寄存器MAR，存储器数据寄存器MDR，存储矩阵M，运算器内部采用内部总线连接，机器采用单总线结构。 1） 画出该机器的硬件结构框图，图中注明所需的微操作控制信号，并注明数据流方向； 2） 根据所画硬件结构图，写出传送指令MOV R0， 2、将一个20 阶五角矩阵中所有非零元素压缩存储到一个一维数组中，该一维数组至少应该有<）个数组元素才行。 3、设n 个元素的进栈序列为1、2、3、…、n。出栈序列为P1、P2、…、Pn。若P1=n，则Pi(1<=i<=n>的值为<）。 4、深度为h 的非空完全二叉树中至少有<）个结点。 5、完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中，与数据的存储结构有关系的是<）。 6、若从无向图的任意一个顶点出发进行一次深度优先搜索便可以访问到该图的所有顶点，则该图一定是一个<）图。 7、若一个非连通的无向图最多有28 条边，则该无向图至少有<）个顶点。 8、已知某带权连通无向图采用邻接矩阵存储方法，邻接矩阵以三元组表形式给出，不包括主对角线元素在内的下三角部分元素对应的各个三元组分别为<2，1，7），<3，1，6），<3，2，8），<4，1，9），<4，2，4），<4，3，6），<5，1，MAX），<5，2，4），<5，3，MAX），<5，4，2）。该连通图的最小生成树的权值之和为<）。 9、顺序查找方法、折半查找方法、树型查找方法和散列查找方法这四种方法中，只能在顺序存储结构下才能实现的查找方法是<）。 9 / 14 10、若对序列 2）所有指令中必有一操作数是寄存器直接寻址，另一操作数的寻址方式有4 种：立即寻址，寄存器直接寻址，寄存器间接寻址<间接寄存器为任一16 位寄存器），变址寻址 八、1、某运算部件包含1 个支持8 种算术运算和16 种逻辑运算的ALU，1 个支持4 种操作的位移器，4 个寄存器<每个寄存器有单独的输入和输出控制信号）。所有部件由内部总线连接，运算部件用微程序控制单元控制，引起微程序转移的条件有4 个，控制存储器容量为256 个字。请设计该运算部件控制单元的微指令格式，并详细说明各字段的含义<采用直接编码方式）。 2、简要说明同步控制方式下指令周期、机器周期和时钟周期的含义，以及三者之间的关系。 九、 1、进程 2、虚拟存储技术 10 / 14 3、通道 4、目录 5、死锁 6、文件系统 十、 1、预防死锁的发生可以通过破坏产生死锁的四个必要条件之一来实现。 2、页式存储管理中，用户应将自己的程序划分成若干大小相等的页。 3、因为P、V 操作描述同步、互斥等问题的能力不足，所以有必要引入其他的原语或机制，如send，receive 或Monitor 等。 4、在有虚拟存储器的系统中，可以运行比主存容量还大的程序。 5、设备独立性<或无关性）是指能独立实现设备共享的一种特性。 6、仅当一个进程退出临界区以后，另一进程才能进入相应的临界区。 7、磁带机是一类典型的块设备。 十一、 1、写出P、V 操作的定义。 2、有n+1 个进程A1，A2，…，An 和B，如右图：A1，A2，…，An 通过同一缓冲区各自不 断向B 发消息，B 不断取消息，它必须取走发来的每一个消息。刚开始时缓冲区为空，试 用P、V 操作正确实现之。 十二、一个32 位的虚拟存储系统有两级页表，其逻辑地址形式如下： 第一级页表 31 22 21 12 11 0 第一级页表占22 到31 位，第二级页表占12 到21 位，页内偏移占0 到11 位。一个进程的地址空间为4GB，如果从0*C0000000 开始映射 4MB 大小页表，请问第一级页表所占的4KB 空间映射在什么位置，并说明理由。<注意B 代表字节，一个32 位地址占4 字节） 第二级页表 页内偏移 2003年真题一、 1、数据的存储结构通常可以有<）。 A、两种，它们分别是：顺序存储结构和链式存储结构 B、三种，它们分别是：顺序存储结构、链式存储结构与索引结构 11 / 14 C、三种，它们分别是：顺序存储结构、链式存储结构与散列结构 D、四种，它们分别是：顺序存储结构、链式存储结构、索引结构与散 列结构 2、删除非空线性链表中由指针p 所指链结点的直接后继结点的过程是依次执行动作<）。<设链结点的构造为[data|link]>。 A、r<-link(p>。 link(p><-r。 call RET(r> B、r<-link(p>。 link(p><-link(r>。 call RET(r> C、r<-link(p>。 link(p><-r。 call RET(p> D、link(p><-link(link(p>>。 call RET(p> 3、已知二维数组A[1：4，1：6]采用列序为主序方式存储，每个元素占用4 个存储单元，并且A[3，4]的存储地址为1234，元素A[1，1]的存储地址是<）。 A、1178 B、1190 C、1278 D、1290 4、某堆栈的输入序列为1，2，3，4，下面四个序列中的<）不可能是它的输出序列。 A、1，3，2，4 B、2，3，4，1 C、4，3，1，2， D、3，4，2，1 5、若某完全二叉树的深度为h,则该完全二叉树中至少有<）个结点。 A、2 的h 次幂 B、2 的h+1 次幂 C、2 的h-1 次幂-1 D、2 的h-1 次幂+1 6、若一棵深度为6 的完全二叉树的第6 层有3 个也结点，则该二叉树共有<）个也结点。 A、17 B、18 C、19 D、20 7、已知带权连通无向图G= A、v1,v2,v5,v7 B、v1,v3,v4,v6,v7 C、v1,v3,v4,v5,v7 D、v1,v2,v5,v4,v6,v7 8、下面的说法中，不正确的是<）。 A、折半查找方法不适用于按值有序链接的链表的查找 B、折半查找方法适用于按值有序的顺序表的查找 C、折半查找方法适用于按关键字值有序排列的顺序文件的查找 D、折半查找方法适用于排列连续顺序文件的查找 9、将数据元素2，4，6，8，10，12，14，16，18，20，22 依次存放于一个一维数组中，然后采用折半查找方法查找数组元素16，被比较过的数组元素的轨迹<数组下标）依次为<）。 A、12，18，14，16 B、12，14，18，16 C、6，9，7，8 D、6，7，9，8 10、从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于等于所选元素，而所选元素处在排序的最终位置。这种排序法称为<）。 A、插入排序法 B、泡排序法 C、谢尔排序法 D、快速排序法 二、 1、下列限制条件下，如何从前至后依次输出非空线性表中的最后k 个数据元素？ 限制1：线性表的长度未知，也不允许采用先求出线性表的长度的方法； 12 / 14 限制2：线性表中每个数据元素只允许作一次输入操作。 2、在散列地址范围与散列函数都分别相同的前提下，通常采用链地址法比采用开放地址法处理冲突的时间效率要高，为什么？ 三、已知长度为n 的线性表A 采用顺序存储结构，并且元素按值的大小非递减排列，请写一算法，删除线性表中值相同的多余元素。<该算法完成以后，线性表中数据元素严格按值递增排列） 四、已知非空二叉树的中序序列与后序序列分别存放于数组INOD[1：n]与POSTOD[1：n]中，并且各个结点的数据信息均不相同，请写一非递归算法，生成该二叉树的二叉链表存储结构<设链结点的构造为[lchild|data|rchild],根结点地址有T 给出）。 五、 1、一般情况下，计算机硬件系统有<）、<）和<）三部分组成。 2、用1 位比较法进行两个16 位定点整数补码的乘法运算，共需要进行<）次右移运算。 3、从总体上来看，总线的仲裁方式可以分为<）和<）两种。其中前者又分为链式查询、<）和<）三种优先权仲裁方式。 4、下列指令格式的寻址方式为变址间接寻址，其格式为：[OP|I|X|disp]，其中I 为间接寻址位，I=1 表示间接寻址，I=0 表示直接寻址；X 为变址寄存器号；disp 为位移量。寻址过程为先变址后间接，当I=0 时，操作数有效地址EA=<）；当I=1 时，操作数有效地址EA=<）。<写出表达式）。 六、 1、某计算机主频为800M，每个机器周期平均包含2 个时钟周期，每条指令平均包括2.5 个机器周期，求该计算机的平均指令执行速度为多少MIPS。 2、什么是DRAM 的刷新？为什么DRAM 需要刷新？ 3、详细叙述中断响应和中断处理的过程。 七、 1、某机字长为16 位，采用16 位定长指令格式，机器格式如题七图所示，指令：ADD R1， 2、某微程序控制器采用水平型微指令格式，控制存储器36 位宽，微指令格式包括控制字段、地址选择 13 / 14 字段和次地址字段三部分，控制字段需要表示的微操作共有24 个，地址选择字段用来指明引起微指令转移的条件，这些条件基于8 个不同的标志来建立。 1）设计该微程序控制器的微指令格式，指出各字段各占多少位。 2）控制存储器的容量有多大。 八、某计算机存储系统包括16KB 结构为4 路组相联的Cache,主存容量为16MB，假设Cache 每块大小16Bytes. 1>Cache 和主存各分为多少组？ 2）写出主存的地址格式。 3）Cache 的地址标记 3、在虚存系统中只要磁盘空间无限大，作业就能拥有任意大的编址空间。 4、在内存为M 的分时系统中，当注册的用户有N 个时，每个用户拥有M/N 的内存空间。 5、特殊文件是指其用途由用户特殊规定的文件。 6、信号量机制控制进程同步、互斥的能力与通信机制是等价的。 7、在作业调用时，采用最高响应比优先的作业调度算法可以得到最短的作业平均周转时间。 8、实时系统中的作业周转时间有严格的限制。 9、当前目录的引入，提高了访问文件的效率。 10、打印机是一类典型的块设备。 十一、考虑有三个吸烟者进程和一个经销商进程的系统。每个吸烟者连续不断地吸他做好的烟卷。做一支烟卷需要烟草，纸和火柴三种原料。这三个吸烟者分别掌握有烟草，纸和火柴。经销商源源不断地提供上述三种原料，但他只将其中的两种原料放在桌上，具有另一种原料的吸烟者就可做烟卷并吸烟，且在做完后给经销商发信号，然后经销商再拿出两种原料放在桌上，如此重复。 1、请给出P、V 操作的定义及信号量的物理意义。 2、试设计一个使经销商和吸烟者同步的算法。 十二、有一个虚拟存储系统，一个程序共分为5 页，刚开始时数据区为空，其执行时页面走向为：4，3，2，1，4，3，5，4，3，2，1，5。试给出下列情形下的缺页次数。 1、系统采用先进先出 因篇幅问题不能全部显示，请点此查看更多更全内容