《2009年计算机408统考真题解析.pdf》由会员分享，可在线阅读，更多相关《2009年计算机408统考真题解析.pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2009年计算机学科专业基础综合试题参考答案一、单项选择题1.B 9.A 17.A 25.C 33.B 1.解析：缓冲区的概念出现在操作系统的设备管理中，其特点是先进先出。缓冲区的作用是解决主机与打印机之间速度不匹配的问题，而不应改变打印数据的顺序。若用栈，先进入缓冲区的数据则要排队到最后才能打印，显然不符题意，故选B。2.解析：由千队列的特点是先进先出，即栈S的出栈顺序就是队Q的出队顺序。故本题只需注意栈的特点是先进后出。出入栈的详细过程见下表。2.10.18.26.34.3.11.19.27.35.BDBBA DCDCC CBAAB 4.12.20.28.36.5.13.21.29.37.
2、6.14.22.30.38.7.15.23.31.39.ADDBC BCAAD CDDAD 8.16.24.32.40.DCDAA 序号说明栈内栈外序号说明栈内栈外1 a入栈A 8 e入栈ae bdc 2 b入栈Ab 9 f入栈aef bdc 3 b出栈A b 10 f出栈ae bdcf 4 c入栈Ac b 11 e出栈a bdcfe 5 d入栈Acd b 12 a出栈bdcfea 6 d出栈Ac bd 13 g入栈g bdcfea 7 c出栈A bdc 14 g出栈bdcfeag 栈内的最大深度为3,故栈S的容量至少是3。【另解】元素的出栈顺序是b,d,c,f,e,a,g,可推出进栈出栈顺序
3、为Push(S,a),Push(S,b),Pop(S,b),Push(S,c),Push(S,d),Pop(S,d),Pop(S,c),Push(S,e),Push(S,f),Pop(S,f),Pop(S,e),Pop(S,a),Push(S,g),Pop(S,g)。假设初始所需容量为o,每做一次Push进行一次+1操作，每做一次Pop进行一次-1操作，记录容量的最大值为3,所以选C。3.解析：分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即遍历的方式是RNL。本题考查的遍历方法并不是二叉树的3种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。4.解析：根据
4、平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过1。而其余3个选项均可以找到不符合该条件的结点。在做题过程中，如果答案不太明显，可以把每个非叶结点的平衡因子都写出来再进行判断。5.解析：完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层 之上是个满二叉树，并且只有最后两层有叶结点。第6层有叶结点则完全二叉树的高度可能为 6或7,显然树高为 7时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层 缺失了8x2=16个叶结点，故完全 二叉树的结点个数最多为(27-1)-16=111个结点。6.解析：森林与二叉树的转换规则 为“左孩子右兄弟”。在最后生成的
5、二叉树中，父子关系在对应森林关系中 可能是兄弟关系或原本就是父子关系。情形I:若结点v是结点u的第二个孩子结点，在转换时，结点v就变成结点u第一个孩子的右孩子，符合要求。情形II:结点 u 和v 是兄弟结点的关系，但二者之中还有一个兄弟结点k,则转换后，结点v就变为结点K的右孩子，而结点k则是结点u的右孩子，符合要求。喜。嘉II 情形III:若结点u的父结点与v的父结点是兄弟关系，则转换后，结点u和v分别在两者最左父结点的两棵子树中，不可能出现在同一条路径中。分图III【逆向法】由题意可知 u 是 v的父结点的父结点，如下图所示有 4种情况：根据树与二叉树的转换规则，将这4种情况转换成树种结点
6、的关系。(1)在原来的树中 u是v的父结点的父结点；(2)在树中u是v的父结点；(3)在树中u是v的父结点的兄弟；(4)在树中u与v是兄弟关系。由此可知 I 和II正确。7.解析：每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次（出度和入度），故所有顶点的度之和为边数的两倍，I正确。n个顶点、n-l条边可以构成无向连通图，比如树，II错误。顶点数 为N(Nl)的无向完全图中不存在度为 1的顶点，III错误。8.解析：选项A、B和C都是 B-树的特点，而选项D则是 B+树的特点。注意区别 B-树和B+树各自的特点。9.解析：根据关键字序列得到的小顶堆的二叉树形式如下图所示。19
7、15 15 15 22 22 22(I)插入关键字 3 时，先将其放在小顶堆的末端，如图(2)所示。再将该关键字向上进行调整，得到的结果如图(3)所示。所以，调整后的小顶堆序列为 3,5,12,8,28,20,15,22,19。10.解析：解答本题需要对各种排序算法的特点极为清楚。对于冒泡排序和选择排序，每一趟都能确定一个元素的最终位置，而题目中，前 2 个元素和后 2 个元素均不是最小或最大的 2 个元素并按序排列。选项 D 中的 2 路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。插入排序在每趟排序后能确定前面的若干元素是有序的，而此时第二趟排序
8、后，序列的前三个元素是有序的，符合其特征。11.解析：虽然指令和数据都是以二进制形式存放在存储器中，但CPU可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，在执行阶段取出的是数据。本题容易误选A,需要清楚的是，CPU只有在确定取出的是指令之后，才会将其操作码送去译码，因此，不可能依据译码的结果来区分指令和数据。12.解析：C语言中的整型数据为补码形式，int为32位，short为 16 位，故x、y转换成十六进制为0000007FH、FFF7H。执行 z=x+y 时，由于 x是 int型，y 为 short型，需将短字长数据转换成长字长数据，称之为“符号扩展”。由于
9、y 的符号位为 1,故在y 的前面添加 16 个 1,即可将y 上升为 int型，其十六进制形式为 FFFFFFF7H。最后执行加法，即 0000007FH+FFFFFFF7H=00000076H,其中最高位的进位 1 自然丢弃。故选D。【排除法】对于x的值，4个选项都一样，无须计算；z=x+y=127-9=118 O,前 4个字节必然全o,排除BC;只需算出y=-9 的值即可，其十六进制形式为 FFF7H,排除 A。【提示】解题时，应先排除明显错误的选项，然后再推敲剩下的选项。13.解析：X的浮点数格式为 00,111;00,11101(分号前为阶码，分号后为尾数），Y 的浮点数格式为00,
10、101;00,10100。然后根据浮点数的加法步骤进行运算。第一步：对阶。X、Y 阶码相减，即 00,111-00,101=00,111+11,0111=00,010,可知 X的阶码比 Y 的价码大 2(这一步可直接目测）。根据小阶向大阶看齐的原则，将Y 的阶码加 2,尾数右移2 位，将Y 变为 00,111;00,00101。第二步：尾数相加。即 00,11101+00,00101=01,00010,尾数相加结果符号位为 01,故需右规。第三步：规格化。将尾数右移l位，阶码加 1,得 X+Y 为 01,000;00,10001。第四步：判溢出。阶码符号位为 01,说明发生溢出。本题容易误选选
11、项B、c,这是因为选项B、C本身并没有计算错误，只是它们不是最终结果，选项 B少了第3步和 第4步，选项C少了第4步。【偷懒法】本题也可以直接用数学知识对原数进行计算，然后将计算的结果 转换成浮点数的格式。X+Y=29/32x27+5/8x25=29/32x 27+5/32x27=(29/32+5/32)x27=34/32x27=17/32x少，阶码用补码表示，数值位 3位，最大只能表示7,即X+Y的结果的阶码8超出了该浮点数的表示范围，故溢出。“你在做题时想到过这种方法吗？”14.解析：由于Cache共有16块，采用 2路组相联，因此 共分为8组，组号为0,1,2,，7。主存的某一字块按模8
12、映射到Cache某组的任一字块中，即主存的 第0,8,16,字块可以映射到Cache第0组的任一字块中。每个 主存块大小为32字节，故129号单元位于第4块 主存块（注意是从0开始），因此 将映射到Cache第4组的任一字块中。15.解析：首先确定 ROM的个数，ROM区为4KB,选用 2Kx8位的ROM芯片，需要4Kx8=2Kx8 2片，60Kx8 采用字扩展方式；RAM区为60KB,选用 4Kx4位的 RAM芯片，需要=30片，采用字4Kx4 和位同时扩展方式。16.解析：相对寻址EA=(PC)+A,首先要求的是取指令后PC的值。转移指令由两个字节组成，每取一个字节 PC值自动加1,因此取
13、指令后PC值为2000H+2H=2002H,故EA=(PC)+A=2002H+06H=2008H。【易错点】本题易误选A或B。选项A没有考虑PC值的自动更新，选项B虽然考虑了PC值要自动更新，但没有注意到该转移指令是一条两字节指令，PC值仅仅+I而不是+2。17.解析：相对千CISC,RISC的特点是指令条数少；指令长度固定，指令格式和 寻址种类少；只有取数I存数指令访问存储器，其余指令的操作均在寄存器之间进行；CPU中通用寄存器多；大部分指令在一个或者小于一个机器周期内完成；以硬布线逻辑为主，不用或者少用微程序控制。选项B、C、D都是RISC的特点，选项A是错误的，因为RISC的速度快，所以
14、普遍采用硬布线控制器，而非微程序控制器。18.解析：流水线的时钟周期应以最长的执行时间为准，否则用时长的流水段的功能将不能正确完成。19.解析：微程序控制器采用了“存储程序”的原理，每条机器指令对应一个微程序，因此修改和扩充容易，灵活性好，但每条指令的执行都要访问控制存储器，所以速度慢。硬布线控制器采用专门的逻辑电路实现，其速度主要取决于逻辑电路的延迟，因此速度快，但修改和扩展困难，灵活性差。20.解析：总线带宽是指单位时间内总线上传输数据的位数，通常用每秒钟传送信息的字节数来衡量，单位Bis。由题意可知，在1个总线周期(=2个时钟周期）内传输了4字节信息，时钟周期=1110MHz=O.ls,
15、故总线带宽为4B/(2xO.Is)=4B/(0.2x10-6s)=20MB/s。21.解析：命中率=Cache命中次数I总访问次数。需要注意的是看清题，题中说明的是缺失50次，而不是命中 50次，仔细审题是做对题的第一步。22.解析：外部中断指的是CPU执行指令以外的事件产生的中断，通常是指来自CPU与内存以外的中断。A中键盘输入属于外部事件，每次键盘输入CPU都需要执行中断以读入输入数据，所以能引起外部中断。B 中除数为0属于异常，也就是内中断，发生在CPU内部。C中浮点运算下溢将按机器零处理，不会产生中断。而D访存缺页属于CPU执行指令时产生的中断，也不属于外部中断。所以能产生外部中断的只
16、能是输入设备键盘。23.解析：在单处理机系统（不包含多核的情况）中，同一时刻只能有一个进程占用处理机，因此进程之间不能并行执行。通道是独立于CPU的控制输入输出的设备，两者可以并行，显然，设备与设备之间也是可以并行的。24.解析：在高响应比优先调度算法中，选出响应比最高的进程投入执行，响应比R定义如下：响应比R=(等待时间执行时间）执行时间。它综合考虑 了每个进程的等待时间和执行时间，对于同时到达的长进程和短进程，短进程会优先执行，以提高系统吞吐量；而长进程的响应比可以随等待时间的增加而提高，不会产生进程无法调度的情况。25.解析：这种题用到组合数学中鸽巢原理的思想。考虑最极端情况，因为每个进
17、程最多需要3台打印机，如果每个进程已经占有了2台打印机，那么只要还有多的打印机，总能满足一个进程达到3台的条件，然后顺利执行，所以将 8台打印机分给K个进程，每个进程有2台打印机，这个情况就是极端情况，K为4。26.解析：每个进程都拥有自己独立的进程空间，若一个进程在运行时 所产生的地址在其地址空间之外，则发生地址越界，因此需要进行界地址保护，即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断。27.解析：分段存储管理的逻辑地址分为段号和位移量两部分，段内位移的最大值就是最大段长。地址长度为32位，段号占8位，则位移量占32-8=24位，故最大段长为224B
18、。28.解析：文件的物理结构包括连续、链式、索引三种，其中链式结构不能 实现随机访问，连续结构的文件不易于扩展。因此随机访问且易于扩展是索引结构的特性。29.解析：SCAN算法类似电梯的工作原理。首先，当磁头从105道向序号增加的方向移动时，便会按照从小到大的顺序服务 所有大于105的磁道号(110,170,180,195);往回移动时又会按照从大到小的顺序进行服务(68,45,35,12)。30.解析：为了实现“按名存取”，在文件系统中为每个文件设置用于描述和控制文件的数据结构，称之为文件控制块(FCB)。在文件控制块中，通常包含以下三类信息，即基本信息、存取控制信息及使用信息。31.解析：
19、建立符号链 接时，引用计数值直接复制；建立硬链接时，引用计数值加1。删除文件时，删除操作 对于符号链接是不可见的，这并不影响文件系统，当以后再通过符号链接访问时，发现文件 不存在，直接删除符号链接；但对于硬链接则不可以直接删除，引用计数值减1,若值不为O,则不能删除此文件，因为还有其他硬链接指向此文件。当建立F2时，Fl和F2的引用计数值都为1。当再建立F3时，Fl和F3的引用计数值就都变成了 2。当后来删除Fl时，F3的引用计数值为2-1=1,F2的引用计数值一直不变。32.解析：设备管理具有设备独立性的特点，操作系统以系统调用方式来请求某类设备时，使用的是逻辑设备名。而在程序实际执行时，将
20、逻辑设备名 转换为对应的物理 设备名。33.解析：传输层提供应用进程间的逻辑通信（通过端口号），即端到端的通信。而数据链路层负责相邻结点之间的通信，这个结点包括了交换机和路由器等数据通信 设备，这些设备 不能称为端系统。网络层负责主机到主机的逻辑通信。因此选B。34.解析：采用 4个相位，每个相位有4种幅度的QAM调制方法，每个信 号可以有16种变化，传输4bit的数据。根据奈奎斯特定理，信息的最大传输速率为2x3kx4=24kbps。35.解析：在后退N帧协议中，当 接收方检测到某个帧出错后，则简单地丢弃该帧及其后所有的后续帧，发送方超时后需重传该数据帧及其后续的所有帧。这里应注意，连续AR
21、Q协议中，接收方一般采用累积确认的方式，即接收方 对按序到达的最后一个分组发送确认，因此本题中收到3的确认帧就表示编号为0,1,2,3的帧已接收，而此时发送方未收到1号帧的确认只能代表确认帧在返回的过程中丢失了，而不代表 1号帧未到达 接收方。因此需要重传的帧为编号是4,5,6,7的帧。3 6.解析：交换机实质上是一个多端口网桥，工作在数据链路层，数据链路层 使用物理地址进行转发，而转发到目的地通常是使用 目的地址。因此POU地址是目的物理地址。37.解析：若最短帧长减少，而数据传输速率不变，则 需要 使冲突域的最大距离变 短来实现碰撞窗口的减少。碰撞窗口是指网络中收发结点间的往返时延，因此假
22、设需要减少的最小距离为S,则可以得到如下公式（注意单位的 转换）：减少的往返时延减少的发送时延，即 2xs/(2xl08)=800/(lxl09)。即，由千帧长减少而缩短的发送时延，应等于由于距离减少而缩短的 传播时延的 2倍。可得s=80,即最远的两个站点之间的距离最少需要减少 80m。【注意】CSM幻CD的碰撞窗口=2倍传播时延，报文发送时间碰撞窗口。38.解析：返回的确认序列号是接收 端期待收到对方下一个报文段数据部分的第一个字节的序号，因此乙在正确接收到两个段后，返回给甲的确认序列号是200+300+500=1 000。39.解析：在发生超时后，慢开始门限ssthresh变为16KB/
23、2=8KB,拥塞窗口变为1 KB。在接下来的3个RTT内，执行慢开始算法，拥塞窗口大小依次为2KB、4KB、8KB,由千慢开始门限ssthresh为8KB,因此之后转而执行拥塞避免算法，即拥塞窗口开始“加法增大”。因此第4个RTT结束后，拥塞窗口的大小为9KB。40.解析：对于FTP文件传输，为了保证可靠性，选择TCP协议，排除C、D。FTP的控制信息是带外传送的，也即FTP使用了一个分离的控制连接来传送命令，故选A。二、综合应用题41.解答：该方法不一定能（或不能）求得最短路径。(4 分）举例说明：(6分）图(1)中，设初始顶点为1,目标顶点为4,欲求从顶点1到顶点4之间的最短路径，显然这两
24、点之间的最短路径长度为2。利用给定方法求得的路径长度为3,但这条路径并不是这两点之间的最短路径。图(2)中，设初始顶点为1,目标顶点为3,欲求从顶点1到顶点3之间的最短路径。利用给定的方法，无法求出顶点1到顶点3的路径。二二(I)(2)【评分说明】CD若考生回答“能求得最短路径”，无论给出何种证明，均不给分。考生只要举出类似上述的一个反例说明“不能求得最短路径”或答案中体现了“局部最优不等于全局最优”的思想，均可给6分；若举例说明不完全正确，可酌情给分。42.解答：1)算法的基本设计思想：问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第k个结点的位置。算法的基本设计思想：定
25、义两个指针变量p和q,初始时均指向头结点的下一个结点（链表的第一个结点）。p指针沿链表移动，当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。2)算法的详细实现步骤：CD count=O,p和q指向链表表头结点的下一个结点；若p为空，转;若count等于k,则q指向下一个结点；否则，count=count+1;p指向下一个结点，转；若count等于k,则查找成功，输出该结点的data域的值，返回1;否则，说明K值超过了线性表的长度，查找失败，返回 0;算法结束。3)算法实现：typedef in
26、t Elem.Type;typedef struct LNodeElemType.data;struct Lnode*link;链表数据的类型定义II链表结点的结构定义结点数据结点链接指针)*LinkList;in七Search k(LinkList list,int k)查找链表list倒数第k个结点，并输出该结点data域的值LinkList p=list-link,q=lis七一link;/指针p、q指示第一个结点int countO;.while(p!=NULL if(countlink;p=p-link;./while if(countdata;return l;/Search_k
27、II遍历链表直到最后一个结点计数，若countk只移动p之后让p、q同步移动II查找失败返回0否则打印并返回1提示：算法程序题，如果能够写出数据结构类型定义，正确的算法思想都会至少给一半以上分 数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。【评分说明】若所给出的算法采用一遍扫描方式就能得到正确结果，可给满分 15分；若采用两遍或多遍扫描才能得到正确结果的，最高给10分；若采用递归算法得到正确结果的，最高给10分；若实现算法的空间复杂度过高（使用了大小与K有关的辅助数组），但结果正确，最高给10分；若实现的算法的空间复杂度过高（使用了大小与K有关的辅助数组），但结果正确，最高
28、给10分。若在算法基本思想描述和算法步骤描述中因文字表达没有非常清晰地反映出算法的思路，但在算法实现中能够清晰看出算法思想和步骤且正确，按照O的标准给分。若考生的答案中算法基本思想描述、算法步骤描述或算法实现中部分正确，可酌情给分。43.解答：1)按题意，外设每秒传送0.5MB,中断时每次传送4B。中断方式下，CPU每次用于数据传送的时钟周期 为5x18+5x2=100。(2分）为达到外设0.5MB/s的数据传输率，外设每秒申请的中断 次数为0.5MB/4B=125000。(1分）ls内用于中断的开销为lOOx125000=12500000=12.5M个时钟周期。(1分）CPU用于外设1/0的
29、时间占整个CPU时间的百分比为12.5M/500M=2.5%。(1分）2)当外设数据传输率提高到5MB/s时，改用DMA方式传送，每次DMA传送5000B,ls内需产生的DMA次数为5MB/5000B=1000。(1分）CPU用于DMA处理的总开销为lOOOx 500=500000=0.5M个时钟周期。(1分）CPU用于外设1/0的时间占整个CPU时间的百分比为0.5M/500M=0.1%。(1分）【评分说明】如果考生只给出正确的计算结果，未给出计算过程，每个给2分。44.解答：题干己给出取值和译码阶段每个节拍的功能和有效控制信号，我们应以弄清楚取指阶段中数据通路的信息流动作为突破口，读懂每个
30、节拍的功能和有效控制信号。然后应用到解题思路中，包括划分执行步骤、确定完成的功能、需要的控制信号。先分析题干中提供的示例（本部分解题时不做要求）：取 指令的功能是根据PC的内容所指主存 地址，取出 指令代码，经过MDR,最终送至IR。这部分和后面的指令执行阶段的取 操作数、存运算结果的方法是相通的。Cl:(PC)-MAR 在读 写存储器前，必须先将地址（这里为(PC)送至M凡。C2:M(MAR尸MDR,(PC)+1-PC 读 写的数据必须经过MDR,指令 取出后PC自增1。C3:(MDR)-IR 然后将读到MDR中指令代码送至IR进行后续操作。指令ADD(Rl),RO的操作数一个在主存中，一个
31、在寄存器 中，运算结果在主存中。根据指令功能，要读出 Rl的内容所指 的 主存单元，必须先将Rl的内容送至MAR,即(Rl)-M凡L而读出的数据必须经过MDR,即 M(M凡l)-MDR。因此，将Rl的内容所指主存单元的数据读出到MDR的节拍安排如下：C5:(Rl)-MAR C6:M(MAR尸MDRALU一端是寄存器A,MDR或RO中 必须有一个先写入A中，如MDR。C7:(MDR)-A 然后执行加法操作，并将结果送入寄存器AC。CS:(A)+(RO)-AC 之后将加法 结果写回到Rl的内容所指主存单元，注意MAR中的内容没有改变。C9:(AC)-MDR ClO:(MDR)-M(MAR)有效控制
32、信号的安排并不难，只需看数据是流入还是流出，如流入寄存器X就 是Xin,流出 寄存器X就是Xout。还需注意其他特殊控制信号，如PC+1、Add等。千是得到参考答案如下：时钟功能有效控制信号cs MAR-(Rl)RI out,MARin C6 MDR-M(MAR)MemR,MDRinE C7 A-(MDR)MDRout,Ain cs AC-(A)+(RO)ROout,Add,ACin C9 MDR一(AC)ACout,MDRin CIO M(MAR)-(MDR)MDRoutE,MemW 本题答案不唯一，如果在C6 执行M(MAR)-MDR的同时，完成(RO)-A(即选择将(RO)写入A),并不
33、会发生总线冲突，这种方案可节省l个 节拍，见下表。时钟功能有效控制信号cs MAR-(Rl)Rlout,MARin C6 MDR一M(MAR),A-(RO)MemR,MDRinE,ROout,Ain C7 AC-(MDR)+(A)MDRout,Add,ACin C8 MDR-(AC)ACout,MDRin C9 M(MAR)气(MDR)MDRoutE,MemW 45.解答：互斥资源：缓冲区只能互斥访问，因此设置互斥信号噩mutex。同步问题：P1、P2因为奇数的放置与取用而同步，设同步信号量odd;P1、P3因为偶数的放置与取用而同步，设置同步信号量even;P1、P2、P3因为共享缓冲区，设
34、同步信号量empty,初值为N。程序如下：semaphore mutex=l;semaphore odd=O,even=O;semaphore empty=N;main()cobegin Process Pl()while(True)x=produce();P(empty);P(mutex);Put();V(mutex);if(x%2=0)V(even);else V(odd);Process P2()while(True)P(odd);P(mu七ex);getodd();V(mutex);V(empty);countodd();Process P3()while(True)coend 46.
35、解答：P(even);P(mutext);geteven();V(mutex);V(empty);counteven();II生成一个数II判断缓冲区是否有空单元缓冲区是否被占用II释放缓冲区如果是偶数，向P3发出信号II如果是奇数，向P2发出信号II收到Pl发来的信号，已产生一个奇数缓冲区是否被占用II释放缓冲区II向Pl发信号，多出一个空单元II收到Pl发来的信号，已产生一个偶数II缓冲区是否被占用II释放缓冲区向Pl发信号，多出一个空单元1)根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB,即i2,则得到页内位移占虚地址的低12位，页号占剩余高位。
36、可得三个虚地址的页号P如下（十六进制的一位数字转换成4位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号）：2362H:P=2,访问快表lOns,因初始为空，访问页表lOOns得到页框号，合成物理地址后访问主存lOOns,共计lOns+lOOns+lOOns=2 lOns。1565H:P=1,访问快表lOns,落空，访问页表lOOns落空，进行缺页中断处理108ns,访问快表lOns,合成物理地址后访问主存lOOns,共计lOns+lOOns+108ns+1 Ons+lOOns=100000220 ns。25A5H:P=2,访问快表，因第一次访问已将该页号放入快表，因此花费lOns便
37、可合成物理地址，访问主存lOOns,共计lOns+lOOns=l lOns。2)当访问虚地址1565H时，产生缺页中断，合法驻留集为2,必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0 号页面，因此 1565H 的对应页框号为101H。由此可得1565H的物理地址为101565H。47.解答：1)CIDR 中的子网号可以全0或 全1,但主机号不能全0或全l。因此若将IP地址空间202.118.1.0/24划分为2个子网，且每个局域网需分配的IP地址个 数不少于120个，子网号至少要占用一位。由26-2 120 27-2 可知，主机号至少要占用7 位。由于源IP地址空间的网络前缀为24 位
38、，因此 主机号位数子网号位数=8。综上可得主机号位数为7,子网号位数为1。因此子网的划分结果为子网1:202.118.1.0/25,子网2:202.118.1.128/25。地址 分配方案：子网1分配给局域网1,子网2分配给局域网2;或子网1分配给局域网2,子网2分配给局域网l。2)由于局域网1和局域网2分别与路由器Rl的El、E2 接口直接相连，因此在Rl的路由表中，目的网络为局域网l的 转发路径是直接通过接口El转发的，目的网络为局域网2 的 转发路径是直接通过接口El转发的。由于局域网l、2 的网络前缀均为25 位，因此它们的子网掩码均为255.255.255.128。Rl专门为域名服务
39、器设定了一个特定的 路由表项，因此该路由表项中的 子网掩码应为255.255.255.255(只有和全l的子网掩码相与才能完全保证和目的IP地址一样，从而选择该特定路由）。对应的下一跳转发地址是202.118.2.2,转发接口是LO。Rl到互联网的路由实质上相当于一个默认路由，默认路由一般写为0/0,即目的地址为0.0.0.0,子网掩码为0.0.0.0。对应的下一跳转发地址是202.118.2.2,转发接口是LO。综上可得到路由器Rl的路由表如下。若子网1分配给局域网1,子网2分配给局域网2,见下表。目的网络IP地址子网掩码下一跳IP地址接口202.118.1.0 255.255.255.12
40、8 El 202.1 I 8.1.128 255.255.255.128 E2 202.118.3.2 255.255.255.255 202.118.2.2 LO 0.0.0.0 0.0.0.0 202.118.2.2 LO 若子网1分配给局域网2,子网2分配给局域网1,见下表。目的网络IP地址子网掩码下一跳IP地址接口202.118.1.128 255.255.255.128 El 202.118.1.0 255.255.255.128 E2 202.118.3.2 255.255.255.255 202.118.2.2 LO 0.0.0.0 0.0.0.0 202.118.2.2 LO 3)局域网1和局域网2的地址可以聚合为202.118.1.0/24,而对于路由器R2来说，通往局域网l和局域网2的转发路径都是从LO接口转发，因此采用路由聚合技术后，路由器R2到局域网1和局域网2的路由，见下表。目的网络IP地址202.118.1.0 子网s掩码255.255.255.0 下一跳IP地址202.118.2.1 接口LO