即212，则得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的页号P如下（十六进制的一位数字转换成4位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号）：
2362H：P=2，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。
1565H：P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，访问快表10ns，合成物理地址后访问主存100ns，共计10ns+100ns+108ns+10ns+100ns=100 000 220ns。
25A5H：P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns+100ns=110ns。
(2) 当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。 47．解答：
⑴CIDR中的子网号可以全0或全1，但主机号不能全0或全1。
因此若将IP地址空间202.118.1.0/24划分为2个子网，且每个局域网需分配的IP地址个数不少于120个，子网号至少要占用一位。
由 2-2<120<2-2可知，主机号至少要占用7位。
由于源IP地址空间的网络前缀为24位，因此 主机号位数+子网号位数=8 。 综上可得主机号位数为7，子网号位数为1。
因此子网的划分结果为：子网1：202.118.1.0/25，子网2：202.118.1.128/25。
地址分配方案：子网1分配给局域网1，子网2分配给局域网2，或子网1分配给局域网2，子网2分配给局域网1。
⑵由于局域网1和局域网2分别与路由器R1的E1、E2接口直接相连，因此在R1的路由表中，目的网络为局域网1的转发路径是直接通过接口E1转发，目的网络为局域网2的转发路径是直接通过接口E1转发。由于局域网1、2的网络前缀均为25位，因此它们的子网掩码均为255.255.255.128。
根据题意，R1专门为域名服务器设定了一个特定的路由表项，因此该路由表项中的子网掩码应为255.255.255.255。对应的下一跳转发地址是202.118.2.2，转发接口是L0。
根据题意，到互联网的路由实质上相当于一个默认路由，默认路由一般写作0/0，即目的地址为0.0.0.0，子网掩码为0.0.0.0。对应的下一跳转发地址是202.118.2.2，转发接口是L0。
综上可得到路由器R1的路由表为：
（若子网1分配给局域网1，子网2分配给局域网2）
目的网络IP地址 202.118.1.0 202.118.1.128 202.118.3.2 0.0.0.0 子网掩码 255.255.255.128 255.255.255.128 255.255.255.255 0.0.0.0 下一跳IP地址 — — 202.118.2.2 202.118.2.2 接口 E1 E2 L0 L0 6
7
（若子网1分配给局域网2，子网2分配给局域网1）
目的网络IP地址 202.118.1.128 202.118.1.0 202.118.3.2 0.0.0.0 子网掩码 255.255.255.128 255.255.255.128 255.255.255.255 0.0.0.0 下一跳IP地址 — — 202.118.2.2 202.118.2.2 接口 E1 E2 L0 L0 ⑶局域网1和局域网2的地址可以聚合为202.118.1.0/24，而对于路由器R2来说，通往局域网1和2的
转发路径都是从L0接口转发，因此采用路由聚合技术后，路由器R2到局域网1和局域网2的路由为：
目的网络IP地址 202.118.1.0 子网掩码 255.255.255.0 下一跳IP地址 202.118.2.1 接口 L0 2009年全国硕士研究生入学统一考试
计算机学科专业基础综合试题——选择题部分解析
一、单项选择题
1．考查栈和队列的特点及应用。
C和D直接排除，缓冲区的特点需要先进先出，若用栈，则先进入缓冲区的数据则要排队到最后才能打印，不符题意，所以只有队列符合题意。 2．考查栈的最大递归深度。
时刻注意栈的特点是先进后出。下面是出入栈的详细过程： 序号 1 2 3 4 5 6 7 说明 a入栈 b入栈 b出栈 c入栈 d入栈 d出栈 c出栈 a ab a ac acd ac a b b b bd bdc 栈内 栈外 序号 8 9 10 11 12 13 14 说明 e入栈 f入栈 f出栈 e出栈 a出栈 g入栈 g出栈 g 栈内 ae aef ae a 栈外 bdc bdc bdcf bdcfe bdcfea bdcfea bdcfeag 栈内的最大深度为3，故栈S的容量至少是3。 3．考查二叉树的特殊遍历。
分析遍历后的结点序列，可以看出根结点是在中间被访问的，而且右子树结点在左子树之前，则遍历的方法是RNL。本题考查的遍历方法并不是二叉树遍历的三种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。 4．考查平衡二叉树的定义。
根据平衡二叉树的定义有，任意结点的左右子树高度差的绝对值不超过1。而其余三个答案均可以找到不符合的结点。
5．考查完全二叉树的特点。
完全二叉树比起满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层上有叶结点。第6层有叶结点则完全二叉树的高度可能为6或7，显然树高为7时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了8×2＝16个叶结点，故完全二叉树的结点个数最多为27-1-16=111个结点。6．考查森林和二叉树的转换。
森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。
情形Ⅰ：若结点v是结点u的第二个孩子结点，在转换时，结点v就变成结点u第一个孩子的右孩子，符合要求。
情形Ⅱ：结点u和v是兄弟结点的关系，但二者之中还有一个兄弟结点k，则转换后，结点v就变为结点k的右孩子，而结点k则是结点u的右孩子，符合要求。
情形Ⅲ：结点v的父结点要么是原先的父结点或兄弟结点。若结点u的父结点与v的父结点是兄弟关系，则转换之后，不可能出现结点u是结点v的父结点的父结点。 7．考查无向连通图的特性。
每条边都连接了两个结点，则在计算顶点的度之时，这条边都被计算了两次，故所有顶点的度之和
为边数的两倍，显然必为偶数。而ii和iii则不一定正确，如：对顶点数N≥1无向完全图不存在一个顶点的度为1，并且边数与顶点数的差要大于1。 8．考查m阶B-树的定义。
A、B和C都是B-树的特点，而选项D则是B+树的特点。注意区别B-树和B+树各自的特点。 9．考查小根堆的调整操作。
小顶堆在逻辑上可以用完全二叉树来表示，根据关键序列得到的小顶堆的二叉树形式为下图左图：
插入关键字3时，先将其放在小顶堆的末端，再将该关键字向上进行调整，得到的结果上图右边所示。所以，调整后的小顶堆序列为：3，5，12，8，28，20，15，22，19。 10．考查各排序算法的特点。
解答本题之前要对不同排序算法的特点极为清楚。对于起泡排序和选择排序而言，每一趟过后都能确定一个元素的最终位置，而由题目中所说，前两个元素和后两个元素均不是最小或最大的两个元素并按序排列。答案D中的二路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。插入排序在每趟排序结束后能保证前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特点。 11．考查指令执行过程。
通常完成一条指令可分为取指阶段和执行阶段。在取指阶段通过访问存储器可将指令取出；在执行阶段通过访问存储器可以将操作数取出。这样，虽然指令和数据都是以二进制代码形式存放在存储器中，但CPU可以判断在取指阶段访问存储器取出的二进制代码是指令；在执行阶段访存取出的二进制代码是数据。
12．考查符号位的扩展。
结合题干及选项可知，int为32位，short为16位；又C语言的数据在内存中为补码形式，故x、y的机器数写为0000007FH、FFF7H;
执行z=x+y时，由于x是int型，y为short型，故需将y的类型强制转换为int，在机器中通过符号位扩展实现，由于y的符号位为1，故在y的前面添加16个1，即可将y强制转换为int型，其十六进制形式为FFFFFFF7H;
然后执行加法，即0000007FH+FFFFFFF7H=00000076H，其中最高位的进位1自然丢弃。故选D。 13．考查浮点加法运算。
根据题意，X可记为00, 111; 00, 11101（分号前为阶码，分号后为尾数），Y可记为00, 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，故需进行右规。 规格化，将尾数右移1位，阶码加1，得X+Y为01, 000; 00, 1000，阶码符号位为01，说明发生溢出。
14．考查Cache与主存之间的映射方式。
由于Cache共有16块，采用2路组相联，因此共有8组，0，1，2，...，7。并且主存的某一字块按模8映像到Cache某组的任一字块中，即主存的第0，8，16...字块可以映像到Cache第0组2个字块的任一字块中，而129号单元是位于第4块主存块中，因此将映射到Cache第4组2个字块的任一字块中。
注意：由于在计算机系统结构中和计算机组成原理的某些教材中介绍的组相联跟此处的组相联并不相同，导致部分考生理解错题目。考生应以真题为准，以后再出现类似题目，应以此种解答为标准。 15．考查存储器的扩展。
首先确定ROM的个数，ROM区为4KB，选用2K×8的ROM芯片，需要方式；60KB的RAM区，选用4K×4的RAM芯片，需要16．考查相对寻址。
相对寻址EA=(PC)+A，首先要求的是取指令后PC的值。转移指令由两个字节组成，每取一个字节PC自动加1，因此取指令后PC值为2002H，故EA=(PC)+A=2002H+06H=2008H。 17．考查RISC的特性。
相对于CISC计算机，RISC计算机的特点指令条数少；指令长度固定，指令格式和寻址种类少；只有取数/存数指令访问存储器，其余指令的操作均在寄存器之间进行；CPU中通用寄存器多；大部分指令在一个或者小于一个机器周期内完成；以硬布线逻辑为主，不用或者少用微程序控制。 18．考查流水线中时钟周期的特性。
时钟周期应以最长的执行时间为准，否则用时长的流水段的功能将不能正确完成。 19．考查硬布线控制器的特点。
硬布线控制器的速度取决于电路延迟，所以速度快；微程序控制器采用了存储程序原理，每条指令都要访控存，所以速度慢。硬布线控制器采用专门的逻辑电路实现，修改和扩展困难。 20．考查总线的基本概念。
总线带宽是指单位时间内总线上可传输数据的位数，通常用每秒钟传送信息的字节数来衡量，单位可用字节/秒（Bps）表示。根据题意可知，在2*1/10MHz秒内传输了4B，所以4B*10MHz/2=20MB/S。 21．考查Cache的命中率。
命中率=Cache命中的次数/所有访问次数，有了这个公式这道题就很容易看出，要注意的一点是看清题，题中说明的是缺失50次，而不是命中50次，仔细审题是做对题的第一步。 22．考查中断的分类。
选项中能引起外部中断的只能是输入设备键盘。 23．考查并行性的限定。
单处理机系统中只有一条指令流水线，一个多功能的操作部件，每个时钟周期只能完成一条指令，故进程与进程显然不可以并行。 24．考查几种基本的调度算法概念。
高响应比优先调度算法，同时考虑每个进程的等待时间和需要的执行时间，从中选出响应比最高的进程
投入执行。响应比R定义如下：
响应比R = (等待时间+执行时间) / 执行时间
4K?8?2片，采用字扩展
2K?860K?8?30片，采用字和位同时扩展方式。
4K?425．考查死锁的条件。
这种题用到组合数学中鸽巢原理的思想，考虑最极端情况，因为每个进程最多需要3台打印机，如果每个进程已经占有了两个打印机，那么只要还有多的打印机，那么总能满足达到3台的条件，所以，将8台打印机分给K个进程，每个进程有2台打印机，这个情况就是极端情况，K为4。
2009至2019年计算机考研408历年真题及解析
