考研计算机专业基础综合（综合应用题）模拟试卷3（共100题）

考研计算机专业基础综合（综合应用题）模拟试卷3（共5套）（共100题）考研计算机专业基础综合（综合应用题）模拟试卷第1套一、综合应用题(本题共20题，每题1.0分，共20分。)1、线性表(a1，a2，a3，…，an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。(3)分别给出算法各部分的时间复杂度。标准答案：(1)顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找方法。(2)算法的设计如下：voidsearchExchangeInsert(ElemTypea[]，ElemTypex){intlow=0：inthigh=n一1：intmid；／／low和high指向线性表下界和上界的下标while(low＜=high){mid=(low+high)／2；／／找中间位置if(a[mid]==x)break；／／找到x，退出while循环elseif(a[mid]＜x)low=mid+1；／／~tj中点mid的右部去查elsehigh=mid一1：／／到中点mid的左部去查}if(a[mid]==x&&mid!=n){／／若最后一个元素与x相等，／／则不存在与其后继交换的操作t=a[mid]；a[mid]=a[mid+1]；a[mid+1]=t；}／／数值x与其后继元素位置交换if(low＞high){／／查找失败，插入数据元素xinti；for(i=n—1：i＞high；i一一)a[i+1]=a[i]；／／后移元素a[low]=x；／／插入x}／／结束插入}(3)在利用折半查找的方法查找x的过程中时间复杂度为O(nlog2n)；交换元素位置时的时间复杂度为O(1)；当查找不成功时，插入元素时的时间复杂度为O(n)。知识点解析：暂无解析2、设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空、右子树非空的结点的数据域的值。标准答案：(1)递归算法voidDecPrint(BSTreet){／／递减序输出二叉排序树t中所有左子树为空、右子树非空的结点数据域的值if(t){DecPrint(t一＞rchild)：if(!t一＞lchild&&t一＞rchild)printf(t一＞data：4)；DecPrint(t一＞lchild)：}}(2)非递归算法voidDecPrint(BSTreet){／／递减序输出二叉排序树t中所有左子树为空、右子树非空的结点的值BSTrees[]；／／s是二叉排序树结点指针的栈，容量足够大inttop=0：while(t||top＞0){while(t){s[++top]=t；t=t-＞rchild；}／／沿右分支向下if(top＞0){t=s[top--]；if(!t一＞lchild&&t一＞rchild)printf(t一＞data：4)：t=t一＞lchild；／／去左分支}／／if}／／while}／／算法结束知识点解析：暂无解析3、某模型机的数据通路结构如下图所示。用寄存器传送语句(如PC→MAR)，拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVx(R0)，Y(R1)，源和目的操作数地址均采用变址寻址，第1个参数X为源操作数的形式地址，第2个参数为目的操作数的形式地址，分别位于指令的第2个和第3个存储字。(2)数据求反指令COM一一(R0)，采用自减型寄存器间接寻址，结果送回自减后的地址单元。标准答案：(1)MOVX(R0)，Y(R1)指令执行流程中的前3步是完成取指令都有的公操作；接下来的5步是去主存中取源操作数，把取出的数放在暂存器C中；然后的4步是形成目的操作数地址；最后2步完成传送操作。①PC→MAR，Read；取指令②M→MDR→IR③PC+1→PC④PC→MAR，Read；取源操作数形式地址⑤M→MDR→C⑥PC+1→PC⑦C+R0→MAR，Read；形成源操作数有效地址，并取源操作数⑧M→MDR→C：源操作数暂存C中⑨PC→MAR，Read；取目的操作数形式地址⑩M→MDR→DPC+1→PCD+R1→MAR；形成目的操作数有效地址C→MDR；将源操作数送存储器数据寄存器MDR｝M，Write；将源操作数写入目的有效地址中(2)COM一一(R0)指令执行流程中的前3步是取指令操作；接下来的2步是去主存中取源操作数，把取出的数放在暂存器D中：然后将D的内容取反，写入目的地址中。①PC→MAR，Read；取指令②M→MDR→IR③PC+I→PC④R0→1→R0，R0-1→MAR，Read;修改R0的内容(源和目的操作数地址)⑤M→MDR→D；取出源操作数⑥D→MDR；将源操作数取反⑦MDR→M，Write；写入目的地址中知识点解析：暂无解析4、已知一个双向链表，其结点结构为数据域data、左指针域Uink、右指针域rlink；设指针P指向双向链表中的某个结点。写出一个算法，实现P所指向的结点和它的前缀结点之间顺序的互换。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。标准答案：(1)算法的基本思想：已知双向循环链表中的一个结点P，与前驱交换涉及4个结点(P结点，前驱结点，前驱的前驱结点，后继结点)、6条链。(2)算法的设计如下：typedefstructDuLNode{intdata；structDuLNode*llink，*rlink：}DuLNode*Linkedlist；voidExchange(LinkedListP){／／将P所指结点与其前驱结点交换Linkedlist*q：q=p一>llink；q->llink->rlink=P：／／p的前驱的前驱之后继为Pp->llink=q->llink：／／p的前驱指向其前驱的前驱q->rlink=p一>rlink；／／p的前驱的后继为P的后继q->llink=P：／／p与其前驱交换P->rlink->llink=q：／／p的后继的前驱指向原P的前驱p->rlink=q：／／p的后继指向其原来的前驱}知识点解析：暂无解析5、G=(V，E)是一个带有权的连通图，如图所示。(1)什么是G的最小生成树?(2)G如图所示，请找出G的所有最小生成树。标准答案：(1)无向连通图的生成树包含图中全部n个顶点，以及足以使图连通的n—1条边。而最小生成树则是各边权值之和最小的生成树。(2)最小生成树有两棵。下面给出顶点集合和边集合，编以三元组(Vi，Vj，W)形式，其中W代表权值。V(G)={1，2，3，4，5}El(G)={(4，5，2)，(2，5，4)，(2，3，5)，(1，2，7)}；E2(G)={(4，5，2)，(2，4，4)，(2，3，5)，(1，2，7)}提示：此题考查的知识点是最小生成树的定义。该题说明图的最小生成树不唯一，但权值和唯一，出现两个或两个以上的情况是因为有权值相同的边。牢记Prim(选图的顶点)、Kruskal(选图的边，边上权值排序)两种算法的区别及算法步骤。知识点解析：暂无解析6、CPU执行一段程序时，Cache完成存取的次数为5000次，主存完成存取的次数为200次。已知Cache存取周期为40ns，主存储取周期为160ns。求：(1)Cache的命中率H。(2)Cache-主存系统的访问效率e。(3)平均访问时间T。标准答案：(1)命中率H=Nc／(Nc+Nm)=5000÷(5000+200)=5000÷5200=0．96(2)主存慢于Cache的倍率：R=Tm／Tc=160ns÷40ns=4访问效率：e=1÷[r+(1一r)H]=1÷[4+(1—4)×0．96]=89．3％(3)平均访问时间：Ta=Tc／e=40÷0．893=45ns知识点解析：暂无解析7、下图是一个简化的CPU与主存连接结构示意图(图中省略了所有多路选择器)。其中有一个累加寄存器AC、一个状态寄存器和其他四个寄存器(主存地址寄存器MAR、主存数据寄存器MDR、程序计数器PC和指令寄存器IR)，各部件及其之间的连线表示数据通路，箭头表示信息传送方向。要求：(1)写出图中a、b、c、d四个寄存器的名称。(2)简述图中指令从主存取到控制器的过程。(3)说明数据从主存取出、运算、写回主存所经过的数据通路(假定数据地址已在MAR中)。标准答案：(1)b单向连接微控制器，由微控制器的作用不难得知b是指令寄存器(IR)；a和c直接连接主存，只可能是MDR和MAR，c到主存是单向连接，a和主存双向连接，根据指令执行的特点，MAR只单向给主存传送地址，而MDR既存放从主存中取出的数据又要存放将要写入主存的数据，因此c为主存地址寄存器(MAR)，a为主存数据寄存器(MDR)。d具有自动加1的功能，且单向连接MAR，不难得出为程序计数器(PC)。因此，a为MDR，b为IR，c为MAR，d为PC。(2)先从程序计数器(PC)中取出指令地址，将指令地址送入主存地址寄存器(MAR)，在相关的控制下从主存中取出指令送至主存数据寄存器(MDR)，然后将MDR中的指令送至指令寄存器(IR)，最后流向微控制器，供微控制器分析并执行指令。因此，取指令的数据通路为：PC→MAR，M(MAR)→MDR→IR→控制器。(3)与(2)的分析类似，根据MAR中的地址去主存取数据，将取出的数据送至主存数据寄存器(MDR)，然后将MDR中的数据送至ALu进行运算，运算的结果送至累加器(AC)，运算结束后将AC中的结果送至MDR，最后将MDR中的数据写入主存。因此，从主存取出、运算和写回主存所经过的数据通路为：MAR→M，M(MAR)→MDR→ALU，ALU→AC，AC→MDR→M(MAR)。知识点解析：暂无解析8、兄弟俩共同使用一个账号，每次限存或取10元，存钱与取钱的进程分别如下所示：intamount=0：SAVE(){intm1：m1=amount：m1=m1+10：amount=m1：}TAKE(){intm2；m2=amount：m2=m2一10：amount=m2：}由于兄弟俩可能同时存钱和取钱，因此两个进程是并发的。若哥哥先存了两次钱，但在第三次存钱时弟弟在取钱。请问：(1)最后账号amount上面可能出现的值是多少?(2)如何用P、V操作实现两并发进程的互斥执行?标准答案：本题考查P、V操作实现进程的互斥。(1)哥哥存两次钱后，共享变量amount的值为20。哥哥的第三次存钱与弟弟的取钱同时进行，如果两者顺序执行，则最后amount的值为20；如果在一个进程的执行过程中进行CPU调度，转去执行另一进程，则最后amount的值取决于amount=m1及amount=m2的执行先后次序，若前者先执行，则最后amount的值为10，若后者先执行，则最后amount的值为30。因此，最后账号amount上可能出现的值有10、20、30。(2)在上述问题中，共享变量amount是一个临界资源，为了实现两并发进程对它的互斥访问，可为它设置一初值为1的互斥信号量mutex，并将上述算法修改为：intamount=0；semaphoremutex=1；／／g斥访问amount变量的信号量cobegin{processSAVE(){intm1；P(mutex)：m1=amount：m1=m1+10：amount=m1；V(mutex)：}processTAKE(){intm2；P(mutex)；m2=amount：m2=m2—10；amount=m2；V(mutex)；}}coend知识点解析：暂无解析9、在采用首次适应算法回收内存时，可能出现哪几种情况?应怎样处理这些情况?标准答案：(1)回收区与插入点的前一个分区相邻接，此时可将回收区与插入点的前一分区合并，不再为回收分区分配新表项，而只修改前邻接分区的大小。(2)回收区与插入点的后一分区相邻接，此时合并两区，然后用回收区的首址作为新空闲区的首址，大小为两者之和。(3)回收区同时与插入点的前后两个分区邻接，此时将三个分区合并，使用前邻接分区的首址，大小为三区之和，取消后邻接分区的表项。(4)回收区没有邻接空闲分区，则应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址，插入到空闲链中的适当位置。知识点解析：暂无解析10、为什么说分段系统较之分页系统更易于实现信息共享和保护?标准答案：(1)对于分页系统，每个页面是分散存储的，为了实现信息共享和保护，则页面之间需要一一对应起来，为此需要建立大量的页表项。(2)对于分段系统，每个段都从0开始编址，并采用～段连续的地址空间，这样在实现共享和保护时，只需为所要共享和保护的程序设置一个段表项，将其中的基址与内存地址一一对应起来即可。知识点解析：暂无解析11、什么是地址重定位?怎样区分静态重定位和动态重定位?各有什么优缺点?标准答案：(1)地址重定位：把作业地址空间中使用的逻辑地址变换成主存中物理地址的过程。(2)静态重定位是在程序运行之前由装配程序完成的，动态重定位是在程序执行过程中由硬件地址变换机构实现的。(3)静态重定位的主要优点是，无须增加硬件地址变换机构，因此可在一般计算机上实现。(4)静态重定位的主要缺点有：第一，要求给每个作业分配一个连续的存储空间，且在作业的整个执行期间不能再移动，因此也就不能实现重新分配主存，不利于主存空间的充分利用。第二，用户必须事先确定所需的存储量，若所需的存储量超过可用存储空间，用户必须考虑覆盖结构。第三，用户之间难以共享主存中的同一程序副本。(5)动态重定位的主要优点有：第一，用户作业不要求分配连续的存储空间。第二，用户作业在执行过程中可以动态申请存储空间和在主存中移动。第三，有利于程序段的共享。(6)动态重定位的主要缺点有：第一，需要附加的硬件支持。第二，实现存储管理的软件算法比较复杂。知识点解析：暂无解析12、一个UNIX文件F的存取权限为rwxr-x---，该文件的文件主uid=12，gid=1，另一个用户的uid=6，gid=1，是否允许该用户执行文件F?标准答案：F的存取权限为rwxr-x---，表示文件主可对F进行读、写及执行操作，同组用户可对F进行读及执行操作，但其他用户不能对F操作。因为另一用户的组标识符gid相同，所以允许该用户执行文件F。知识点解析：暂无解析13、计算机网络是由哪些元素组成的?标准答案：计算机网络由网络软件和网络硬件两大部分组成。网络软件主要包括：网络协议、通信软件、网络操作系统等；网络硬件主要包括网络结点(又称网络单元)和通信链路。知识点解析：暂无解析14、网络层有哪些设备?各自的特点有哪些?标准答案：(1)路由器在互联网中，两台主机之间传送数据的通路有很多条，数据包从一台主机出发，中途要经过多个站点才能到达另一台主机。这些中间站点通常由被称为路由器的设备担当，其作用就是为数据包选择一条合适的传送路径。路由器工作在OSI模型的网络层，是根据数据包中的逻辑地址(网络地址)而不是MAC地址来转发数据包的。路由器的主要工作是为经过路由器的每个数据包寻找一条最佳传输路径，并将该数据包有效地传送到目的站点。路由器不仅有网桥的全部功能，还具有路径的选择功能，可根据网络的拥塞程度自动选择适当的路径传送数据。路由器与网桥的不同之处在于，它并不是使用路由表来找到其他网络中指定设备的地址，而是依靠其他的路由器来完成任务。也就是说，网桥是根据路由表来转发或过滤数据包，而路由器是使用它的信息来为每一个数据包选择最佳路径。路由器有静态和动态之分。静态路由器需要管理员来修改所有的网络路由表，一般只用于小型的网间互联：而动态路由器能根据指定的路由协议来完成修改路由器信息。(2)第三层交换机随着技术的发展，有些交换机也具备了路由的功能。这些具有路由功能的交换机要在网络层对数据包进行操作，因此被称为第三层交换机。知识点解析：暂无解析15、设有一个n×n的上三角矩阵(aij)，将其上三角中的元素按先行后列的顺序存于数组B[m]中，使得B[k]=aij且k=f1(i)f2(j)+c，请推导出函数f1、f2和常数c，要求f1和f2中不含常数项。标准答案：上三角矩阵第1行有n个元素，第i一1行有n一(i一1)+1个元素，第1行到第i一1行是等腰梯形，而第i行上第j个元素(即aij)是第i行上第j-i+1个元素，故元素aij在一维数组中的存储位置(下标k)为：k=(n+(n一(i一1)+1))(i一1)／2+(j-i+1)=(2n-i+2)(i一1)／2+j-i+1进一步整理为：知识点解析：暂无解析16、设有15000个无序的元素，希望用最快的速度挑选出其中前10最大的元素。在快速排序、堆排序、归并排序、基数排序和希尔排序中，宜采用哪种方法并说明理由?标准答案：上面所说的几种排序方法中，排序速度都很快，但快速排序、归并排序、基数排序和希尔排序都是在排序结束后才能确定数据元素的全部序列，而排序过程中无法知道部分连续位置上的最终元素。而堆排序则是每次输出一个堆顶元素(即最大或最小值的元素)，然后对堆进行再调整，保证堆顶元素总是当前剩下元素的最大或最小的，从而可知，如果在一个大量数据的文件中，如含有15000个元素的记录文件中选取前10个最大的元素，宜采用堆排序。知识点解析：暂无解析17、操作系统必须具备的功能有哪些?标准答案：(1)用户接口：操作系统与用户的接口也简称为用户接口。(2)处理机管理：处理机管理的主要任务是对处理机的分配和运行实施有效管理。(3)存储管理：存储管理的主要任务包括为多道程序的并发运行提供良好环境，为用户使用存储器提供方便，提高存储器的利用率，为尽量多的用户提供足够大的存储空间。(4)设备管理：设备管理的主要任务有：为用户分配I／O设备，完成用户程序请求的I／O操作，提高CPU和输入／输出设备的利用率，改善人机界面。(5)文件管理：现代计算机系统的外部存储器中，都以文件形式存放着大量的信息。操作系统必须配置相应的文件管理机构来管理这些信息。知识点解析：暂无解析某多道程序设计系统配有一台处理器和两台外设101、102，现有3个优先级由高到低的J1、J2、J3都已装入了主存，它们使用资源的先后顺序和占用时间分别是：j1：IO2(30ms)，CPU(10ms)；IO1(30ms)，CPU(10ms)；J2：IO1(20ms)，CPU(20ms)；IO2(40ms)；J3：CPU(30ms)，IO1(20ms)。处理器调度采用可抢占的优先数算法，忽略其他辅助操作时间，回答下列问题。18、分别计算作业J1、J2和J3从开始到完成所用的时间。标准答案：为了清楚地描述作业执行情况，我们对题目假设的情况分析如下：J1占用IO2传输30ms时，J1传输完成，抢占J2的CPU，运行10ms，再传输30ms，运行10ms，完成。J1从开始到完成所用的时间为：30+10+304+10=80(ms)。J2与其并行地在I1上传输20ms，抢占J3的CPU，J2运行10ms后，被J1抢占CPU，等待10ms之后，J2再次得到CPU，运行10ms，J2启动IO2传输，40ms完成。J2从开始到完成所用的时间为：20+10+10+10+40=90(ms)。J3在CPU上执行20ms，被J2抢占CPU，等待30ms，再运行10ms，等待10ms，J3启动IO1运行20ms的传输，完成。J3从开始到完成所用的时间为20+304-10+10+20=90(ms)。知识点解析：暂无解析19、3个作业全部完成时CPU的利用率。标准答案：三个作业全部完成时，CPU的利用率为(10+20+30+10)／90=7／9=7．8％。知识点解析：暂无解析20、3个作业全部完成时外设IO1的利用率。标准答案：三个作业全部完成时，外设IO1的利用率为(20+30+20)／90=7／9=78％。知识点解析：暂无解析考研计算机专业基础综合（综合应用题）模拟试卷第2套一、综合应用题(本题共20题，每题1.0分，共20分。)1、什么是AND信号量?请利用AND信号量写出生产者一消费者问题的解法。标准答案：此题主要考查进程与死锁的相关转换内容。(1)为解决并行所带来的死锁问题，在wait操作中引入AND条件，其基本思想是将进程在整个运行过程中所需要的所有临界资源一次性地全部分配给进程，用完后一次性释放。(2)解决生产者一消费者问题可描述如下：varmutex，empty，full：semaphore：=1，n，0；buffer．array[0．．n一1]ofitem；in，out：integer：=0，0；beginparbeginproducer：beginrepeatproduceaniteminnextp；wait(empty)：wait(s1，s2，s3，…，sn)：／／s1，s2，s3，…，sn为执行生产者进程除empty外其余的条件wait(mutex)；buffer(in)：=nextp：in：=(in+1)modn：signal(mutex)：signal(full)；signal(s1，s2，s3，…，sn)；untilfalse；endconsumer：beginrepeatwait(full)；wait(k1，k2，k3，…，kn)：／／k1，k2，k3，…，kn为执行生产者进程除full外其余的条件wait(mutex)；nextc：=buffer(out)：out：=(out+1)modn；signal(mutex)；signal(empty)；signal(k1，k2，k3，…，kn)；consumetheiteminnextc；untilfalse；endparendend知识点解析：暂无解析2、设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。标准答案：表达式中的括号有以下三对：’(’、’)’、’[’、’]’、’{’、’}’，使用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对；否则，结论表达式括号不配对。intMatch(LinkedListla){／／算术表达式存储在以la为头结点的单循环链表中，本算法判断括号是否正确配对charS[]；／／s为字符栈，容量足够大P=la一＞link；／／p为工作指针，指向待处理结点StackInit(S)；／／初始化栈swhile(P!=la){／／循环到头结点为止switch(p-＞ch){case’(’：push(s，p-＞ch)；break；case’)’：if(StackEmpty(s)||StackGetTop(s)!=’(’){printf(”括号不配对＼n”)；return(0)：}elsepop(S)：break；case’[’：push(s，p一＞ch)；break；case’[’：if(StaekEmpty(s)IlStackGetTop(s)!=’[’){printf(”括号不配对＼n”)；return(0)；}elsepop(S)；break；case’{’：push(s，p-＞ch)；break；case’}’：if(StackEmpty(s)IIStackGetTop(s)!=’{’){printf(”括号不配对＼n”)；return(0)；}elsepop(s)：break；}P=p-＞link；／／后移指针}／／whileif(StackEmpty(s))fprintf("括号配对＼n")；return(1)；}else{printf(”括号不配对＼n”)；return(0)；}}知识点解析：暂无解析3、计算机网络由哪些部分组成?什么是通信子网和资源子网?试述这种层次结构观的特点以及各层的作用。标准答案：(1)计算机网络由通信子网和资源子网组成。(2)资源子网是指计算机网络资源的拥有者，它们为网络提供资源。通信子网是由通信控制处理机构成的，为资源子网提供信息传输服务。(3)通信控制处理机构成的通信子网是网络的内层，或骨架层，是网络的重要组成部分。网上主机负责数据处理，是计算机网络资源的拥有者，它们组成了网络的资源子网，是网络的外层。通信子网为资源子网提供信息传输服务，资源子网上用户间的通信是建立在通信子网的基础上。没有通信子网，网络不能工作，而没有资源子网，通信子网的传输也失去了意义，两者合起来组成了统一的资源共享的两层网络。将通信子网的规模进一步扩大，使之变成社会公有的数据通信网。知识点解析：暂无解析4、简述为什么在传输连接建立时要使用三次握手，如不建立连接可能会出现什么情况?标准答案：我们知道，三次握手完成两个重要的功能，既要双方做好发送数据的准备工作(双方都知道彼此已准备好)，也要允许双方就初始序列号进行协商，这个序列号在握手过程中被发送和确认。现在把三次握手改成仅需要两次握手，死锁是可能发生的。作为例子，考虑计算机A和B之间的通信，假定B给A发送一个连接请求分组，A收到了这个分组，并发送了确认应答分组。按照两次握手的协定，A认为连接已经成功地建立了，可以开始发送数据分组。可是，B在A的应答分组在传输中被丢失的情况下，将不知道A是否已准备好，不知道A建议什么样的序列号，B甚至怀疑A是否收到自己的连接请求分组。在这种情况下，B认为连接还未建立成功，将忽略A发来的任何数据分组，只等待连接确认应答分组。而A在发出的分组超时后，重复发送同样的分组，这样就形成了死锁。知识点解析：暂无解析5、今有4级流水线分别完成取值、指令译码并取数、运算、送结果四步操作，现假设完成各步操作的时间依次为100ns，100ns，80ns，50ns。请回答下列问题：(1)流水线的操作周期应设计为多少?(2)若相邻两条指令发生数据相关，而且在硬件上不采取措施，那么第二条指令要推迟多少时间进行?(3)如果在硬件设计上加以改进，至少需推迟多少时间?标准答案：(1)流水线的操作时钟周期t按四步操作中最长时间来考虑，所以t=100ns。(2)两条指令发生数据相关冲突情况：ADDR1，R2，R3；R2+R3→R1SUBR4，R1，R5；R1一R5→R4两条指令在流水线中执行情况如下表所示。ADD指令在时钟4时将结果写入寄存器堆(R1)，但SUB指令在时钟3时读寄存器堆(R1)。本来ADD指令应先写入R1，SUB指令后读R1，结果变成SUB指令先读R1，ADD指令后写R1，因而发生两条指令间的数据相关，如果硬件上不采取措施，第2条指令SUB至少应推迟2个操作时钟周期(2×100ns)。(3)如果硬件上加以改进(采取旁路技术)，可推迟1个操作时钟周期(100ns)。知识点解析：暂无解析6、已知一棵二叉树的前序序列为：A，B，D，G，J，E，H，C，F，I，K，L；中序序列为：D，J，G，B，E，H，A，C，K，I，L，F。(1)写出该二叉树的后序序列。(2)画出该二叉树。(3)求该二叉树的高度以及该二叉树中度为2、1、0的结点个数。标准答案：此题只需从前序序列、中序序列得到唯一确定的二叉树即可。(1)J，G，D，H，E，B，K，L，I，F，C，A。(2)二叉树的形式如下图所示：(3)高度是5，度为0的结点个数为4，度为1的结点个数为5，度为2的结点个数为3。知识点解析：暂无解析7、计算机硬件系统由哪几个功能部件组成?每个部件完成的主要功能是什么?标准答案：计算机硬件是由运算器、控制器、存储器、输入设备和输出设备组成的。运算器：数据处理，完成算术运算和逻辑运算。控制器：从存储器中取出指令，并进行指令译码。存储器：存储数据与程序。输入设备：输入数据，并且把人读数据变为机读数据。输出设备：输出数据，并且把机读数据变为人读数据。它们是通过总线连接在一起的，其中总线包括数据总线、地址总线和控制总线。知识点解析：暂无解析8、某指令流水线分为五级，分别完成取址(IF)、译码并取数(ID)、执行(EX)、访存(MEM)、写结果(WR)。设完成各阶段操作的时间依次为：90ns，60ns，70ns，100ns，50ns。试问：流水线的时钟周期应取何值?若第一条和第二条指令发生数据相关，第二条指令需推迟多少时间才能不发生错误?若相邻两条指令发生数据相关，而不推迟第二条指令的执行可采取什么措施?标准答案：流水线的时钟周期应取其中最长的时间段，即100ns。第二条指令需推迟300ns(即等待上一条指令完成EX、MEM、WR三个周期后才能开始ID，才能不发生错误。若相邻两条指令发生数据相关而不推迟第二条指令的执行，可采取的措施是在访存与执行之间设置相关专用通路。知识点解析：暂无解析9、某计算机有如下部件：ALU，移位器，主存M，主存数据寄存器MDR，主存地址寄存器MAR，指令寄存器IR，通用寄存器R0一R1，暂存器C和D。(1)请将各逻辑部件组成一个数据通路，并标明数据流向。(2)画出“ADDR1，(R2)+”指令的指令周期流程图，指令功能是(R1)+((R2))→R1。标准答案：(1)各功能部件连接成如下图所示数据通路：(2)此指令为RS型指令，一个操作数在R1中，另一个操作数在R2为地址的内存单元中，相加结果放在R1中。送当前指令地址到MAR，取当前指令到IR，PC+1，为取下条指令做好准备。提示：①取R1操作数→C暂存器。②送地址到MAR。③取出内存单元中的操作数→D暂存器。④相加后将和数→R1。知识点解析：暂无解析10、有一台磁盘机，平均寻道时间为30ms，平均旋转等待时间为120ms，数据传输速率为500B／ms，磁盘机上存放着1000件每件3000B的数据。现欲把一件数据取走，更新后再放回原处。假设一次取出或写入所需时间为：平均寻道时间+平均等待时间+数据传送时间。另外，使用cPu更新信息所需时间为4ms，且更新时间同输入／输出操作不相重叠。试问：(1)更新磁盘上全部数据需要多少时间?(2)若磁盘及旋转速度和数据传输率都提高一倍，更新全部数据需要多少时间?标准答案：(1)磁盘上总数据量为1000×3000B=3000000B读出全部数据所需时间为3000000B÷500B／ms=6000ms重新写入全部数据所需时间为6000ms。所以，更新磁盘上全部数据所需的时间为2x(平均寻道时间+平均等待时间+数据传送时间)+CPU更新时间=2×(30+120+6000)ms+4ms=12304ms(2)磁盘机旋转速度提高一倍后，平均等待时间为60ms；数据传输率提高一倍后，数据传送时间变为3000000B÷1000B／ms=3000ms更新全部数据所需时间为2×(30+60+3000)ms+4ms=6184ms知识点解析：暂无解析11、磁盘机由6个盘片组成，其中专设1个盘面为伺服面，其他的盘面作为记录数据的盘面。盘存储区域内直径为6．1cm，外直径为12．9cm，道密度为220tpm，位密度为6000bpm，平均寻道时间为10ms，磁盘转速为7200rpm。假定π=3，试计算：(1)数据盘面数和柱面数；(2)盘组容量是多少字节?(3)数据传输率是多少字节／秒?(4)从任一磁道读取80000个字节数据的平均存取时间是多少?(5)假定系统配备上述磁盘机15台，每个磁道分为64个扇区，试为该磁盘系统设计一个地址方案。标准答案：磁盘机有多个盘片，每个盘片有两个盘面，每个盘面上有若干磁道，各记录面上相同编号(位置)的诸磁道构成一个圆柱面。通常将一条磁道划分为若干个段，每个段称为一个扇区或扇段，每个扇区存放一个定长信息块。(1)由于磁盘机有一个盘面是伺服盘，实际的数据盘面数=6×2—1=11(个)柱面数=[(外直径一内直径)／2]×道密度=[(12．9—6．1)／2]×220=748(个)(2)以最内圈磁道的周长当作每条磁道的长度，故该盘组的存储容量(非格式化容量)为：位密度×内圈磁道的周长×柱面数×数据盘面数=6000×π×6．1×748×11=903434400b=112929300B(3)数据传输率=转速×每道的容量=120转／s×13725B=1647000B／s(4)磁盘旋转一圈时间为×60≈8．3ms平均存取时间=平均寻道时间+平均等待时间+读取数据的时间=10+8．3／2+80000／1647000=10+4．15+48．6=62．75ms(5)磁盘系统共15台磁盘机，驱动器号(4位)；共有748个圆柱面，柱面号(10位)；共有11个记录面，记录面号(4位)；每个磁道有64个扇区，扇区号(6位)。最终的地址方案是：驱动器号(4位)，柱面号(10位)，记录面号(4位)，扇区号(6位)。知识点解析：暂无解析12、兄弟俩共同使用一个账号，每次限存或取10元，存钱与取钱的进程分别如下所示：intamount=0：SAVE(){intm1：m1=amount：m1=m1+10：amount=m1：}TAKE(){intm2；m2=amount：m2=m2一10：amount=m2：}由于兄弟俩可能同时存钱和取钱，因此两个进程是并发的。若哥哥先存了两次钱，但在第三次存钱时弟弟在取钱。请问：(1)最后账号amount上面可能出现的值是多少?(2)如何用P、V操作实现两并发进程的互斥执行?标准答案：本题考查P、V操作实现进程的互斥。(1)哥哥存两次钱后，共享变量amount的值为20。哥哥的第三次存钱与弟弟的取钱同时进行，如果两者顺序执行，则最后amount的值为20；如果在一个进程的执行过程中进行CPU调度，转去执行另一进程，则最后amount的值取决于amount=m1及amount=m2的执行先后次序，若前者先执行，则最后amount的值为10，若后者先执行，则最后amount的值为30。因此，最后账号amount上可能出现的值有10、20、30。(2)在上述问题中，共享变量amount是一个临界资源，为了实现两并发进程对它的互斥访问，可为它设置一初值为1的互斥信号量mutex，并将上述算法修改为：intamount=0；semaphoremutex=1；／／g斥访问amount变量的信号量cobegin{processSAVE(){intm1；P(mutex)：m1=amount：m1=m1+10：amount=m1；V(mutex)：}processTAKE(){intm2；P(mutex)；m2=amount：m2=m2—10；amount=m2；V(mutex)；}}coend知识点解析：暂无解析13、网络协议的三个要素是什么?各有什么含义?标准答案：网络协议：为完成网络通信而建立的规则、标准或约定。由以下三个要素组成：(1)语法：即数据与控制信息的结构或格式。(2)语义：即需要发出何种控制信息，完成何种动作以及作出何种响应。(3)同步：即事件实现顺序的详细说明。知识点解析：暂无解析14、数据链路层中的链路控制包括哪些功能?标准答案：数据链路层中的链路控制功能有：①链路管理。②帧定界。③流量控制。④差错控制。⑤将数据和控制信息区分开。⑥透明传输。⑦寻址。知识点解析：暂无解析15、有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈(即C第一个且D第二个出栈)的次序有哪几个?标准答案：3个：C，D，E，B，A；C，D，B，E，A；C，D，B，A，E。提示：此题考查的知识点是栈的后进先出特点。按题意，C先出，说明A，B已入栈，D出栈再出栈，E可以入栈就出栈，可以有序列C，D，E，B，A。也可以B先出E再入，再出，得序列C，D，B，E，A。还可以B，A都出栈后，E再入栈出栈，得序列C，D，B，A，E。只有这三种情况。知识点解析：暂无解析16、试比较脱机I／／O和联机I／O。标准答案：(1)脱机输入／输出方式是为了解决人机矛盾及CPU和I／O设备之间速度不匹配而提出的。它减少了CPU的空闲等待时间，提高了I／O速度，具体内容是将用户程序和数据在一台外围机的控制下，预先从低速输入设备输入到磁带上，当CPU需要这些程序和数据时再直接从磁带机高速输入到内存，从而大大加快了程序的输入过程，减少了CPU等待输入的时间，这就是脱机输入技术；当程序运行完毕或告一段落，CPU需要输出时，无须直接把计算结果送至低速输出设备，而是把结果高速地输出到磁带上，然后在外围机的控制下，把磁带上的计算结果由相应的输出设备输出，这就是脱机输出技术。(2)若这种输入／输出操作在主机控制下进行则称为联机输入/输出方式。知识点解析：暂无解析某系统有R1、R2和R3三种资源，在T0时刻P1、P2、P3和P4四个进程对资源的占用和需求情况如下表所示，此时系统的可用资源向量为(2，1，2)。试问：17、系统是否处于安全状态?如安全，请给出一个安全序列。标准答案：利用安全性算法对T0时刻的资源分配情况进行分析，可得到如下表所示的安全性检测情况。可以看出，此时存在一个安全序列{P2，P3，P4，P1}，故该系统是安全的。知识点解析：暂无解析18、如果此时P1和P2均发出资源请求向量Request(1，0，1)，为了保证系统的安全性，应该如何分配资源给这两个进程，7说明你所采用的策略的原因。标准答案：若此时P1发出资源请求Request1(1，0，1)，按银行家算法进行检查：Request1(1，0，1)≤Need1(2，2，2)Request1(1，0，1)≤AVailable(2，1，2)试分配并修改相应的数据结构，由此形成的资源分配情况如下表所示。知识点解析：暂无解析19、如果(2)中两个请求立即得到满足，系统此刻是否处于死锁状态?标准答案：如果(2)中两个请求立即得到满足，此刻系统并没有立即进入死锁状态，因为这时所有进程没有提出新的资源申请，全部进程均没有因资源请求没有得到满足而进入阻塞状态。只有当进程提出资源请求，且全部进程都进入阻塞状态时，系统才处于死锁状态。知识点解析：暂无解析20、空闲磁盘空间的管理常采用哪几种方式?UNIX系统采用的是何种方式?标准答案：空闲磁盘空间的管理常采用以下几种方法：(1)空闲表法：属于连续分配方式，它与内存管理中的动态分区分配方式相似。(2)空闲链表法：将所有空闲盘区链接成一条空闲链。根据构成链的基本元素不同，可分为空闲盘块链和空闲盘区链。(3)位示图法。利用二进制的一位来表示磁盘中每一个盘块的使用情况，磁盘上的所有盘块都有一个二进制位与之对应，从而由所有盘块所对应的位构成一个集合，即位示图。(4)成组链接法。结合空闲表法和空闲链表法而形成。UNIX系统采用的是成组链接法。知识点解析：暂无解析考研计算机专业基础综合（综合应用题）模拟试卷第3套一、综合应用题(本题共20题，每题1.0分，共20分。)1、为什么要引入段页式存储管理?说明在段页式存储管理系统中的地址变换过程。标准答案：(1)为了获得分段在逻辑上的优点和分页在管理存储空间方面的优点，兼用分段和分页两种方法，设计出了段页式存储管理技术来实现对存储器的管理。(2)地址变换过程如下：首先，由段表控制寄存器确定段表在主存中的位置。其次，将虚地址中的段号和控制寄存器中的段表大小比较，以确保其访问的有效性。最后，硬件地址转换机构根据虚地址中的段号S，得到欲访问段在该作业的段表中的表目，并验证存取权限，以确保本次存储访问是允许的。然后，检查分段存在标识(判状态位)，如果访问的段在主存，则通过段表找到该段的页表存放地址，再根据虚地址中的页号P查页表，找到该页所对应的内存块号与虚地址中的页内地址d相加形成物理地址；若访问的分段不在主存，则由硬件产生缺段中断。如果一完整的分段不在主存，则说明该段所有的页面均不在主存，因而也没有相应的页表。操作系统对缺页中断响应后，必须重新构造其页表，并装入一个或多个所需的页面。此时，开始继续执行本次的存储访问。当页表的位置和大小确定后，其存储访问过程如先前描述过的页面系统一样进行。知识点解析：暂无解析2、段页式存储管理方式中如何实现地址变换?标准答案：首先，必须配置一段表寄存器，在其中存放段表始址和段长TL。进行地址变换时，先利用段号S，与段长TL进行比较，若S＜TL，表示未越界(若S≥TL，表示段号太大，访问越界，产生越界中断信号)，于是利用段表始址和段号来求出该段对应的段表项在段表中的位置，从中求出该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再用块号b和页内地址构成物理地址。知识点解析：暂无解析3、二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后，此树仍然是一棵二叉排序树，并且高度没有增长(注意：可不考虑被删除的结点是根的情况)。标准答案：在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。voidDelete(BSTreebst，keytypeX){／／在二叉排序树bst上，删除其关键字为X的结点BSTreef，P=bst：while(P&&p一＞key!=X)／／查找值为X的结点if(p一＞key＞X){f=P；p=p-＞lehild；}else{f=p；P=p一＞rehild；}if(P==null){prinff(”无关键字为x的结点＼n”)；exit(0)：}if(p-＞lchild==null){／／被删结点无左子树if(f一＞lchild==P)f一＞lchild=P一＞rchild；／／将被删结点的右子树接到其双亲上elsef一＞rchild=p一＞rchild；}else{q=p；s=p-＞lchild；／／被删结点有左子树while(s-＞rchild!=null)／／查左子树中最右下的结点(中序最后结点){q=s；s=s-＞rchild；}p-＞key=s-＞key；／／结点值用其左子树最右下的结点的值代替if(q==p)p一＞lchild=s一＞lchild；／／被删结点左子树的根结点无右子女elseq-＞rchild=s-＞lchild：／／s是被删结点左子树中序序列最后一个结点free(s)；}}知识点解析：暂无解析4、试述CSMA／CD介质访问控制技术的工作原理。标准答案：CSMA／CD介质访问控制技术被广泛应用于以太网中。CSMA／CD的工作原理是：当某个站点要发送数据时，它首先监听介质：(1)如果介质是空闲的，则发送；(2)如果介质是忙的，则继续监听，一旦发现介质空闲，就立即发送：(3)站点在发送帧的同时需要继续监听是否发生冲突(碰撞)，若在帧发送期间检测到冲突，就立即停止发送，并向介质发送一串阻塞信号以强化冲突，保证让总线上的其他站点都知道已发生了冲突；(4)发送了阻塞信号后，等待一段随机时间，返回步骤(1)重试。知识点解析：暂无解析5、CSMA／CA是如何实现“冲突避免”的?标准答案：采用三种机制来实现：预约信道、正向确认和RTS／CTS机制。(1)预约信道。发送站点利用“传输持续时间”字段向所有其他无线站点通告本站点将要占用信道多长时间，以便让其他站在这段时间内不要发送数据，以避免冲突。(2)正向确认机制。IEEE802．11规定若接收站点正确收到以它为目的地的数据帧时，就应向发送数据帧的站点发送一个ACK帧作为接收成功的肯定回答，否则将不采取任何动作。发送站点在发送完数据帧的规定时间内若没有收到ACK帧，就需要多次重发数据帧，直到收到ACK帧为止。(3)RTS／CTS机制。通过请求发送RTS／允许发送CTS选项，以解决隐蔽站的冲突问题。知识点解析：暂无解析6、说明页表的组成与程序逻辑地址到内存物理地址的变换过程。快表是一定要有的吗?说明快表内容的组成与读写原理。标准答案：页表由若干表项组成，每个虚页号对应页表中的一个表项，表项的内容可以由如下部分组成：最重要的是一个虚页被分配在主存中的实际页号，还可能包括页装入(有效)位、修改标记位、替换控制位、其他保护位等组成的控制位字段。地址变换过程：用虚地址中的虚页号与页表基地址相加，求出对应该虚页的页表表项在主存中的实际地址，从该表项的实页号字段取出实页号再拼上虚地址中的页内地址，就得到读主存数据用的实际地址。为了解决当要读页内的某个存储单元时，需读两次主存才能取得要读的数据的问题(读两次主存过程：首先要读一次主存，通过查页表求出实存地址，然后再读一次主存)，设立一个完全用快速硬件实现的容量很小的快速页表，又称转换旁路缓冲器，用于存放在页表中使用最频繁的、为数不多的那些表项的内容。快表主要有虚页号和实页号两项内容。经快表实现的地址转换过程：用虚地址中的虚页号去与快表中虚页号字段的内容相比较，与哪个表项中的虚页号相同，则可以取出该表项中的实页号，并与页内地址拼接出主存实际地址。这一过程可以很快完成，类似于高速缓；中存储器的运行原理。当在快表中找不到该虚页号时，就要到主存中经慢表找出该虚页号对应的实页号，在得到一个主存实际地址的同时用该虚页号和实页号替换快表的一个表项的内容，以反映这次操作的形势。知识点解析：暂无解析7、有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈(即C第一个且D第二个出栈)的次序有哪几个?标准答案：3个：C，D，E，B，A；C，D，B，E，A；C，D，B，A，E。提示：此题考查的知识点是栈的后进先出特点。按题意，C先出，说明A，B已入栈，D出栈再出栈，E可以入栈就出栈，可以有序列C，D，E，B，A。也可以B先出E再入，再出，得序列C，D，B，E，A。还可以B，A都出栈后，E再入栈出栈，得序列C，D，B，A，E。只有这三种情况。知识点解析：暂无解析8、设排序二叉树中结点的结构由三个域构成：数据域data，指向左儿子结点的指针域left，指向右儿子结点的指针域right。设data域为正整数，该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除。标准答案：利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于x，则顺左子树向下查找，直到某结点的值小于等于戈，则该结点及其左子树均应删除。下面设计一查找算法，确定被删除子树的根结点，再设计一删除算法，删除以被删结点为根的子树。typedefstructnode{intdata；structnode*left，*right；}BiTNode，*BSTree；voidDelTree(BSTreer){／／非递归删除以r为根的二叉排序树BSTreeS[]；／／栈，容量足够大，栈中元素是二叉排序树结点的指针BSTreeP；inttop=0；while(r!=null||top>0){while(r!=null){S[++top]=r；r=r一>left；}／／沿左分支向下if(top>0)／／退栈，沿栈顶结点的右子树向下删除，释放被删除结点空间{P=S[top--]；r=p->right；free(P)；}}}／／DelTreevoidDeleteAllx(BSTreeT，intx){／／在二叉排序树T中，删除所有小于等于x的结点BSTreep=T，q；while(T&&T一>data<=X){／／根结点的值小于等于xP=T；T=T一>right；p一>right=null；DelTree(P)；}／／删除二叉树P，删除持续到”根”结点值大于x或T为空树为止if(T){q=T;P=T一>left；while(P&&P一>data>x){／／沿根结点左分支向下，查小于等于x的结点while(P&&p一>data>x){q=p;p=p一>left；}／／q记P的双亲if(P)／／p结点的值小于等于X{q一>left=P一>right；p一>right=null；DelTree(P)；}P=q一>left；／／再查原P的右子树中小于等于X的结点}}}知识点解析：暂无解析9、某模型机的数据通路结构如下图所示。用寄存器传送语句(如PC→MAR)，拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0)，Y(R1)，源和目的操作数地址均采用变址寻址，第1个参数X为源操作数的形式地址，第2个参数为目的操作数的形式地址，分别位于指令的第2个和第3个存储字。(2)数据求反指令COM一一(R0)，采用自减型寄存器间接寻址，结果送回自减后的地址单元。标准答案：(1)MOVX(R0)，Y(R1)指令执行流程中的前3步是完成取指令都有的公操作；接下来的5步是去主存中取源操作数，把取出的数放在暂存器C中；然后的4步是形成目的操作数地址；最后2步完成传送操作。①PC→MAR，Read；取指令②M→MDR→IR③PC+1→PC④PC→MAR，Read；取源操作数形式地址⑤M→MDR→C⑥PC+1→PC⑦C+R0→MAR，Read；形成源操作数有效地址，并取源操作数⑧M→MDR→C；源操作数暂存c中⑨PC→MAR，Read；取目的操作数形式地址⑩M→MDR→DPC+1→PCD+R1→MAR；形成目的操作数有效地址C→MDR；将源操作数送存储器数据寄存器MDR→M，Write；将源操作数写入目的有效地址中(2)COM--(R0)指令执行流程中的前3步是取指令操作；接下来的2步是去主存中取源操作数，把取出的数放在暂存器D中；然后将D的内容取反，写入目的地址中。①PC→MAR，Read；取指令②M→MDR→IR③PC+1→PC④R0一1→R0，R0-1→MAR，Read；修改R0的内容(源和目的操作数地址)⑤M→MDR→D；取出源操作数⑥D→MDR；将源操作数取反⑦MDR→M，Write；写入目的地址中知识点解析：暂无解析10、试分析，在第一级磁盘容错技术和第二级磁盘容错技术中，各采取了哪些容错措施?什么是写后读校验?标准答案：在第一级磁盘容错技术中，包括以下容错措施：(1)双份目录和双份文件分配表。在磁盘上存放的文件目录和文件分配表FAT均为文件管理所用的重要数据结构，所以为之建立备份。(2)在系统每次加电启动时都要对两份目录和两份FAT进行检查，以验证它们的一致性。在第二级磁盘容错技术中，包括以下容错措施：(1)磁盘镜像。在同一磁盘控制器下增设一个完全相同的磁盘驱动器，在每次向文件服务器的主磁盘写入数据后，都要采用写后读校验方式将数据再同样地写到备份磁盘上，使两者具有完全相同的位像图。(2)磁盘双工。将两台磁盘驱动器分别接到两个磁盘控制器上，同样使这两台磁盘机镜像成对，从而在磁盘控制器发生故障时起到数据保护的作用。在磁盘双工时，由于每一个磁盘都有自己的独立通道，故可以同时(并行)地将数据写入磁盘。在读入数据时，可采用分离搜索技术，从响应快的通道上取得数据，因而加快了对数据的读取速度。(3)热修复重定向和写后读校验。两者均用于防止将数据写入有缺陷的盘块中。就热修复重定向而言，系统将一定的磁盘容量作为热修复重定向区，用于存放当发现盘块有缺陷时的待写数据，并对写入该区的所有数据进行登记，方便将来对数据进行访问。而写后读校验则是为了保证所有写入磁盘的数据都能写入到完好的盘块中，故在每次从内存缓冲区向磁盘中写入一个数据块后，应立即从磁盘上读出该数据块并送至另一缓冲区中，再将该缓冲区中内容与原内存缓冲区中在写后仍保留的数据进行比较。若两者一致，便认为此次写入成功，可继续写入下一个盘块；否则，则重写。若重写后两者仍不一致，则认为该盘块有缺陷，此时便将应写入该盘块的数据写入热修复重定向区中，并将该损坏盘块的地址记录在坏盘块表中。知识点解析：暂无解析11、某操作系统的磁盘文件空间共有500块，若用字长为32位的位示图管理磁盘空间，试问：(1)位示图需多少个字?(2)第i字第j位对应的块号是多少?(3)给出申请／归还一块的工作流程。标准答案：(1)位示图占用字数为500÷32=16(向上取整)个字。(2)第i字第j位对应的块号N=32×i+j。(3)申请时自上至下、自左至右扫描位示图跳过为1的位，找到第一个遇到的0位，根据它是第i字第j位算出对应块号，并分配出去。归还时已知块号，块号÷32算出第i字第j位并把位示图相应位清零。知识点解析：暂无解析12、简述字节多路通道、数组选择通道和数组多路通道。标准答案：(1)字节多路通道含有许多非分配型子通道并分别连接在低速、中速I／O设备上，子通道按时间片轮转方式共享，按字节方式进行数据传送。具体而言，当第一个子通道控制其I／O设备完成一字节的交换后，便立即腾出字节多路通道(主通道)给第二个子通道使用；当第二个子通道也交换完一字节后，又把主通道让给第三个子通道使用。以此类推。转轮一周后，重又返回由第一个子通道去使用主通道。(2)数组选择通道只含有一个分配型子通道，一段时间内只能执行一道通道程序、控制一台设备按数组方式进行数据传送。通道被某台设备占用后便一直处于独占状态，直至设备数据传输完毕释放该通道，故通道利用率较低。因此这种方式主要用于连接多台高速设备。(3)数组多路通道是将数组选择通道传输速率高和字节多路通道能使各子通道分时并行操作的优点相结合而形成的一种新通道。其含有多个非分配型子通道并分别连接在高速、中速I／O设备上，子通道按时间片轮转方式共享主通道，按数组方式进行数据传送，因而既具有很高的数据传输速率，又能获得令人满意的通道利用率。知识点解析：暂无解析13、计算机网络是由哪些元素组成的?标准答案：计算机网络由网络软件和网络硬件两大部分组成。网络软件主要包括：网络协议、通信软件、网络操作系统等；网络硬件主要包括网络结点(又称网络单元)和通信链路。知识点解析：暂无解析14、简述移动IP的通信过程。标准答案：移动主机在不同子网间漫游，其数据包的通信过程如下：(1)本地代理和外地代理不停地向网上发送代理广告消息，以声明自己的存在。(2)移动主机收到这些消息，确定自己是在本地网还是在外地网。(3)如果移动主机发现自己仍在本地网，即收到的是本地代理发来的消息，则不启动移动功能。如果是从外地网络重新返回的，则向本地代理发出取消注册的消息，声明自己回到了本地网。(4)当移动主机检测到它移动到外地网时，则获得接管地址(CoA)。(5)然后移动主机向本地代理登记，表明自己已离开本地网，把所获得的接管地址通知本地代理。(6)登记完毕后，所有发给移动主机的数据包被本地代理截获，经本地代理封装后，通过隧道发到外地网络的外地代理FA(第一种CoA地址)或移动主机自身(第二种CoA地址)。第一种情况下，外地代理再把数据包转发给移动主机。此时，数据包在不同子网间传送成功。(7)移动主机发送数据到一般的IP主机时，按正常的IP寻址方法发送，不必通过本地代理。上述工作过程有效地解决了移动主机在子网间漫游通信的问题。但是，却在路由上存在着问题。当移动主机发送数据时，不管它是在本地网络还是在外地网络，它始终保留了它的本地网络地址，当它发送数据包时，可以用通常的IP协议发送。反之，当一般IP主机给移动主机发送数据包时，首先到达移动主机的本地代理(HA)。HA再根据收到的移动主机当前的接管地址CoA(假定为第一种地址)，将数据包发往外地网络，由外地代理最终将数据包发给移动主机，这就出现了路由的“三角问题”。最差的情况是当发送数据包的一般IP主机靠近移动主机所在的外地网络或移动主机已经漫游到发送主机所在的网络时，发送的数据包却仍要先到达移动主机的本地代理，再由本地代理发到外地代理，最后到达移动主机，这不仅增大了传输延迟，同时对一些延迟敏感的业务如音频、视频等造成极大的损害。其次，数据包在网络中运行时间过长，浪费了网络资源，增加了网络负担。知识点解析：暂无解析15、并发请求过程中服务器的处理方案及建立传输连接的过程有哪些?标准答案：解决服务器处理并发请求的方案基本上有两种：一是采用并发服务处理器的方法，二是采用重复服务器的方法。客户与并发服务器建立传输连接的工作过程为：(1)主服务器在固定的端口号上准备接收客户的连接请求：(2)客户向服务器发出连接建立请求：(3)主服务器接收到客户的连接请求后，激活相应的从服务器：(4)主服务器通知客户从服务器的端口号，并关闭与客户的连接：(5)从服务器准备接收客户的连接建立请求：(6)客户向从服务器发送连接建立请求。知识点解析：暂无解析16、利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。标准答案：假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二叉树高度是h，则叶子结点个数最多为2h-1；反之，若有u个叶子结点，则二叉树的高度至少为(log2u)+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log2(n!)的路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log2(n!)。根据斯特林公式，有log2(n!)=O(nlog2n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog2n)。知识点解析：暂无解析设某机有5级中断L0、L1、L2、L3、L4，其中断响应优先次序为L0最高、L1次之、…、L4最低。现在要球将中断处理次序改为L1→L3→L0→L4→L2，试问：17、下表中各级中断处理程序的各中断级屏蔽值如何设置(每级对应一位，该位为“0”表示允许中断，该位为“1”表示中断屏蔽)?标准答案：中断处理程序如下：知识点解析：暂无解析18、若这5级中断同时都发出中断请求，按更改后的次序画出进入各级中断处理程序的过程示意图。标准答案：示意图如下：知识点解析：暂无解析19、网络协议的三个要素是什么?备有什么含义?标准答案：网络协议：为完成网络通信而建立的规则、标准或约定。由以下三个要素组成：(1)语法：即数据与控制信息的结构或格式。(2)语义：即需要发出何种控制信息，完成何种动作以及作出何种响应。(3)同步：即事件实现顺序的详细说明。知识点解析：暂无解析20、物理层要解决什么问题?物理层的主要特点是什么?试给出数据通信系统的模型并说明其主要组成构件的作用。标准答案：(1)物理层考虑的是怎样才能在连接各种计算机的传输媒体上传输数据比特流，而不是指连接计算机的具体的物理设备或具体的传输媒体。(2)现有的网络中物理设备和传输媒体种类繁多，通信手段也有许多不同的方式。物理层的作用正是．要尽可能地屏蔽掉这些差异，使数据链路层感觉不到这些差异，这样数据链路层只需要考虑如何完成本层的协议和服务，而不必考虑网络具体的传输媒体是什么。物理层的重要任务是确定与传输媒体的接口的一些特性。(3)一个数据通信系统可划分为三大部分：源系统(发送端)、传输系统(或传输网络)和目的系统(接收端)。源系统一般包括以下两个部分：①源点：源点设备产生要传输的数据。例如正文输入到PC，产生输出的数字比特流。②发送器：通常源点生成的数据要通过发送器编码后才能在传输系统中进行传输。例如，调制解调器将PC输出的数字比特流转换成能够在电话线上传输的模拟信号。目的系统一般包括以下两部分：①接收器：接收传输系统传送过来的信号，并将其转换为能够被目的设备处理的信息。例如，调制解调器接收来自传输线路上的模拟信号，并将其转换成数字比特流。②终点：终点设备从接收器获取传送过来的信息。知识点解析：暂无解析考研计算机专业基础综合（综合应用题）模拟试卷第4套一、综合应用题(本题共20题，每题1.0分，共20分。)1、OSPF协议采用什么路由算法?有什么特点?标准答案：OSPF是一种基于链路状态的路由协议，需要每个路由器向其同一管理域的所有其他路由器发送链路状态广播信息。在OSPF的链路状态广播中包括所有接口信息、所有的量度和其他一些变量。利用OSPF的路由器首先必须收集有关的链路状态信息，并根据一定的算法计算出到每个结点的最短路径。而基于距离一向量的路由协议仅向其邻接路由器发送有关路由更新信息。与RIP不同，OSPF将一个自治域再划分为区，相应地有两种类型的路由选择方式：当源和目的地在同一区时，采用区内路由选择；当源和目的地在不同区时，则采用区间路由选择。这就大大减少了网络开销，并增加了网络的稳定性。当一个区内的路由器出了故障时并不影响自治域内其他区路由器的正常工作，这也给网络的管理、维护带来方便。知识点解析：暂无解析2、试比较单播、组播和广播三种传输方式的区别。标准答案：(1)单播传输：在发送者和每一接收者之间实现点对点网络连接。如果一个发送者同时给多个接收者传输相同的数据，也必须相应地复制多份相同的数据包。如果有大量主机希望获得数据包的同一副本时，将导致发送者负担沉重、延迟长、网络拥塞，为保证一定的服务质量需增加硬件和带宽。(2)组播传输：在发送者和每一接收者之间实现点对多点网络连接。如果一个发送者同时给多个接收者传输相同的数据，只需复制一份相同的数据包。它提高了数据传送效率，减少了骨干网络出现拥塞的可能性。(3)广播传输：是指在IP子网内广播数据包，所有在子网内部的主机都将收到这些数据包。广播意味着网络向子网每一个主机都投递一份数据包，不论这些主机是否乐于接收该数据包。所以广播的使用范围非常小，只在本地子网内有效，通过路由器和交换机网络设备控制广播传输。知识点解析：暂无解析3、设某计算机有变址寻址、间接寻址和相对寻址等寻址方式。设当前指令的地址码部分为00lAH，正在执行的指令所在地址为1F05H，变址寄存器中的内容为23A0H。(1)当执行取数指令时，如为变址寻址方式，取出的数为多少?(2)如为间接寻址，取出的数为多少?(3)当执行转移指令时，转移地址为多少?标准答案：(1)变址寻址的寻址过程如下：变址寻址工作原理：指令地址码部分给出的地址A和指定的变址寄存器x的内容通过加法器相加，所得的和作为地址从存储器中读出所需的操作数。因此，操作数S：((Rx)+A)=(23AOH+001AH)=(23BAH)=1748H。(2)间接寻址的寻址过程如下：变址寻址工作原理：对于存储器一次问址的情况，需访问两次存储器才能取得数据第一次从存储器读出操作数地址：第二次从该地址中读取操作数。因此，操作数S=((A))=((001AH))=(23AOH)=2600H。(3)转移指令使用相对寻址，其过程如下：转移地址=(PC)+A=1F06H+1H+001AH=1F21H。知识点解析：暂无解析4、从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、一、*、／四种运算，例如：234—34+2*$。标准答案：逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND，对表达式从