2014考研计算机真题及答案解析(详细)

1、2014年全国硕士研究生入学统一考试年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机科学与技术学科联考计算机学科专业基础综合试题计算机学科专业基础综合试题一、单项选择题：第一、单项选择题：第140小题，每小题小题，每小题2分，共分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。分。下列每题给出的四个选项中，只有一个选项最符合试题要求。1下列程序段的时间复杂度是（）。count=0;for(k=1;k=n;k*=2)for(j=1;j=n;j+)count+;AO(log2n)BO(n)CO(nlog2n)DO(n2)2假设栈初始为空，将中缀表达式a/b+(c*d-e

2、*f)/g转化为等价后缀表达式的过程中，当扫描到f时，栈中的元素依次是（）。A+(*-B+(-*C/+(*-*D/+-*3循环队列存放在一组数组A0.M-1中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素，初始时为空。下列判断队空和队满的条件中，正确的是（）。A队空：end1=end2；队满：end1=(end2+1)modMB队空：end1=end2；队满：end2=(end1+1)mod(M-1)C队空：end2=(end1+1)modM；队满：end1=(end2+1)modMD队空：end1=(end2+1)m

3、odM；队满：end2=(end1+1)mod(M-1)4若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是（）。Ae、cBe、aCd、cDb、a5将森林F转化为对应的二叉树T，F中叶结点的个数等于（）。AT中叶结点的个数BT中度为1的结点个数CT中左孩子指针为空的结点个数DT中右孩子指针为空的结点个数65个字符有如下4种编码方案，不是前缀编码的是（）。A01,0000,0001,001,1B011,000,001,010,1C000,001,010,011,100D0,100,110,1110,11007对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（）。A3,1,2

4、,4,5,6B3,1,2,4,6,5C3,1,4,2,5,6D3,1,4,2,6,58用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（）。A存储效率B散列函数C装填（装载）因子D平均查找长度9在一棵具有15个关键字的4阶B树中，含有关键词的结点个数最多是（）。A5B6C10D1510用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量（间隔）可能是（）。A2B3C4D511下列选项中，不可能是快速排序第2趟排序结果的是（）。A2,3,5,4,6,7,9B2,7,5,6,4,

5、3,9C3,2,5,4,7,6,9D4,2,3,5,7,6,912程序P在机器M上的执行时间是20秒，编译优化后，P执行的指令数减少到原来的70%，而CPI增加到原来的1.2倍，则P在M上的执行时间是（）。A8.4秒B11.7秒C14.0秒D16.8秒13若x=103,y=-25，则下列表达式采用8位定点补码运算实现时，会发生溢出的是（）。Ax+yB-x+yCx-yD-x-y14float型数据通常采用IEEE754单精度浮点格式表示。假定两个float型变量x和y分别存放在32位寄存器f1和f2中，若(f1)=CC900000H,(f2)=B0C00000H,则x和y之间的关系为（）。Axy

6、且符号相同Bxy且符号相同Dxy且符号不同15某容量为256MB的存储器由若干84M位DRAM芯片构成，该DRAM芯片的地址引脚和数据引脚总数是（）。A19B22C30D3616采用指令Cache和数据Cache分离的主要目的是（）。A降低Cache的缺失损失B提高Cache的命中率C降低CPU平均访问时间D减少指令流水线资源冲突17某计算机有16个通用寄存器，采用32位定长指令字，操作码字段（含寻址方式位）为8位，Store指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式。若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store指令中偏移量的取值范围是（）。A-327

7、68+32767B-32767+32768C-65536+65535D-65535+6553618某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微指令，各指令对应的微程序平均由4条微指令组成，采用断定法（下址字段法）确定下条微指令地址，则微指令中下址字段的位数至少是（）。A5B6C8D919某同步总线采用数据总线和地址总线复用方式，其中地址/数据线有32根，总线时钟频率为66MHz，每个时钟周期传送两次数据（上升沿和下降沿各传送一次数据），该总线的最大数据传输率（总线带宽）是（）。A132MB/sB264MB/sC528MB/sD1056MB/s20一次总线事务中，主设备

8、只需给出一个首地址，从设备就能从首地址开始的若干连续单元读出或写入多个数据。这种总线事务方式称为（）。A并行传输B串行传输C突发传输D同步传输21下列有关I/O接口的叙述中，错误的是（）。A状态端口和控制端口可以合用同一个寄存器BI/O接口中CPU可访问的寄存器称为I/O端口C采用独立编址方式时，I/O端口地址和主存地址可能相同D采用统一编址方式时，CPU不能用访存指令访问I/O端口22若某设备中断请求的响应和处理时间为100ns，每400ns发出一次中断请求，中断响应所允许的最长延迟时间为50ns，则该设备持续工作过程中，CPU用于该设备的I/O时间占整个CPU时间的百分比至少是（）。A12

9、.5%B25%C37.5%D50%23下列调度算法中，不可能导致饥饿现象的是（）。A时间片轮转B静态优先数调度C非抢占式短作业优先D抢占式短作业优先24某系统有n台互斥使用的同类设备，三个并发进程分别需要3、4、5台设备。可确保系统不发生死锁的设备数n最小为（）。A9B10C11D1225下列指令中，不能在用户态执行的是（）。Atrap指令B跳转指令C压栈指令D关中断指令26一个进程的读磁盘操作完成后，操作系统针对该进程必做的是（）。A修改进程状态为就绪态B降低进程优先级C为进程分配用户内存空间D增加进程的时间片大小27现有一个容量为10GB的磁盘分区，磁盘空间以簇（Cluster）为单位进行

10、分配，簇的大?j4KB，若采用位图法管理该分区的空闲空间，即用一位（bit）标识一个簇是否被分配，则存放该位图所需簇的个数为（）。A80B320C80KD320K28下列措施中，能加快虚实地址转换的是（）。I增大快表（TLB）容量II让页表常驻内存III增大交换区（Swap）A仅IB仅IIC仅I、IID仅II、III29在一个文件被用户进程首次打开的过程中，操作系统需做的是（）。A将文件内容读到内存中B将文件控制块读到内存中C修改文件控制块中的读写权限D将文件的数据缓冲区首指针返回给用户进程30在页式虚拟存储管理系统中，采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分

11、配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady异常现象的是（）。ILRU算法IIFIFO算法IIIOPT算法A仅IIB仅I、IIC仅I、IIID仅II、III31下列关于管道（Pipe）通信的叙述中，正确的是（）。A一个管道可实现双向数据传输B管道的容量仅受磁盘容量大小限制C进程对管道进行读操作和写操作都可能被阻塞D一个管道只能有一个读进程或一个写进程对其操作32下列选项中，属于多级页表优点的是（）。A加快地址变换速度B减少缺页中断次数C减少页表项所占字节数D减少页表所占的连续内存空间33在OSI参考模型中，直接为会话层提供服务的是（）。A应用层B表示层C传输层D网络层34

12、某以太网拓扑及交换机当前转发表如下图所示。主机00-e1-d5-00-23-a1向主机00-e1-d5-00-23-c1发送1个数据帧，主机00-e1-d5-00-23-c1收到该帧后，向主机00-e1-d5-00-23-a1发送1个确认帧，交换机对这两个帧的转发端口分别是（）。交换机00-e1-d5-00-23-a100-e1-d5-00-23-b100-e1-d5-00-23-c1目的地址00-e1-d5-00-23-b1端口2123A3和1B2,3和1C2,3和1,2D1,2,3和135下列因素中，不会影响信道数据传输速率的是（）。A信噪比B频率带宽C调制速率D信号传播速度36主机甲与主

13、机乙之间使用后退N帧协议（GBN）传输数据，甲的发送窗口尺寸为1000，数据帧长为1000字节，信道带宽为100Mbps,乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认。若甲乙之间的单向传播时延是50ns，则甲可以达到的最大平均数据传输速率约为（）。A10MbpsB20MbpsC80MbpsD100Mbps37站点A、B、C通过CDMA共享链路，A、B、C的码片序列（chippingsequence）分别是（1，1，1，1）、（1，-1，1，-1）和（1，1，-1，-1）。若C从链路上收到的序列是（2，0，2，0，0，-2，0，-2，0，2，0，2），则C收到A发送的数据是（）。

14、A000B101C110D11138主机甲和主机乙已建立了TCP连接，甲始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB的确认段。若甲在t时刻发生超时时拥塞窗口为8KB，则从t时刻起，不再发生超时的情况下，经过10个RTT后，甲的发送窗口是（）。A10KBB12KBC14KBD15KB39下列关于UDP协议的叙述中，正确的是（）。I.提供无连接服务II.提供复用/分用服务III.通过差错校验，保障可靠数据传输A仅IB仅I、IIC仅II、IIIDI、II、III40使用浏览器访问某大学Web网站主页时，不可能使用到的协议是（）。APPPBA

15、RPCUDPDSMTP二、综合应用题：综合应用题：4147小题，共小题，共70分。请将答案写在答题纸指定位置上。分。请将答案写在答题纸指定位置上。41（13分）二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为：leftweightright其中叶节点的weight域保存该节点的非负权值。设root为指向T的根节点的指针，请设计求T的WPL的算法。要求：（1）给出算法的基本设计思想；（2）使用C或C+语言，给出二叉树结点的数据类型定义；（3）根据设计思想，采用C或C+语言描述算法，关键之处给出注释。42（10分）某网络中的路由器

16、运行OSPF路由协议，题42表是路由器R1维护的主要链路状态信息（LSI），题42图是根据题42表及R1的接口名构造出来的网络拓扑。题42表R1所维护的LSIR1的LSIR2的LSIR3的LSIR4的LSI备注RouterID10.1.1.110.1.1.210.1.1.510.1.1.6标识路由器的IP地址Link1ID10.1.1.210.1.1.110.1.1.610.1.1.5所连路由器的RouterIDIP10.1.1.110.1.1.210.1.1.510.1.1.6Link1的本地IP地址Metric3366Link1的费用Link2ID10.1.1.510.1.1.610.1.

17、1.110.1.1.2所连路由器的RouterIDIP10.1.1.910.1.1.1310.1.1.1010.1.1.14Link2的本地IP地址Metric2424Link2的费用Net1Prefix192.1.1.0/24192.1.6.0/24192.1.5.0/24192.1.7.0/24直连网络Net1的网络前缀Metric1111到达直连网络Net1的费用题42图R1构造的网络拓扑请回答下列问题。（1）本题中的网络科抽象为数据结构中的哪种逻辑结构？（2）针对题42表中的内容，设计合理的链式存储结构，以保存题42表中的链路状态信息（LSI）。要求给出链式存储结构的数据类型定义，并画

18、出对应题42表的链式存储结构示意图（示意图中可仅以ID标识结点）（3）按照迪杰斯特拉（Dijkstra）算法的策略，依次给出R1到达题42图中子网192.1.x.x的最短路径及费用。43（9分）请根据题42描述的网络，继续回答下列问题。（1）假设路由表的结构如下表所示，请给出题42图中R1的路由表，要求包括到达题42图192.1.1.0/24192.1.6.0/24192.1.5.0/24192.1.7.0/241E0L010.1.1.1R1R3R2R4L110.1.1.910.1.1.1010.1.1.510.1.1.610.1.1.1310.1.1.1410.1.1.21234611?51

19、92.1.x.x的路由，且路由表中的路由项尽可能少。目的网络下一条接口（2）当主机192.1.1.130向主机192.1.7.211发送一个TTL=64的IP分组时，R1通过哪个接口转发该IP分组？主机192.1.7.211收到的IP分组的TTL是多少？（3）若R1增加一条Metric为10的链路连接Internet，则题42表中R1的LSI需要增加哪些信息？44（12分）某程序中有如下循环代码段P：“for(i=0;iN;i+)sum+=Ai;”，假设编译时变量sum和i分别分配在寄存器R1和R2中，常量N在寄存器R6中，数组A的首地址在寄存器R3中。程序段P起始地址为08048100H,对

20、应的汇编代码和机器代码如题44表所示。题44表编号地址机器代码汇编代码注释108048100H00022080Hloop:sllR4,R2,2(R2)lchild=NULL/返回该叶子结点的带权路径长度elsereturn(WPL(root-lchild,d+1)+WPL(root-rchild,d+1);/*返回左右子树中全部叶结点的带权路径长度之和*/【答案二】?1）算法的设计思想：（4分）若借用非叶结点的weight域保存其孩子结点中weight域值的和，则树的WPL等于树中所有非叶结点weight域值之和。采用后序遍历策略，在遍历二叉树T时递归计算每个非叶结点的weight域的值，则树

21、T的WPL等于根结点左子树的WPL+右子树的WPL+根结点中weight域的值。（2）算法中使用的二叉树结点的数据类型定义同【答案一】。（2分）（3）算法实现：（7分）intWPL(BTnode*root)/基于递归的后序遍历算法实现intw_l,w_r;if(root-lchild=NULLelsew_l=WPL(root-lchild);/计算左子树的WPLw_r=WPL(root-rchild);/计算右子树的WPLroot-weight=root-lchild-weight+root-rchild-weight;/填写非叶结点的weight域return(w_l+w_r+root-we

22、ight);/返回WPL值【评分说明】若考生给出能够满足题目要求的其他算法（包括用非递归的遍历方式实现的算法），且正确，可同样给分。参考答案中只给出了使用C语言的版本，使用C+语言正确实现的算法同样给分。若对算法的基本设计思想和主要数据结构的描述不十分清晰，但在算法实现中能够清晰反映出算法思想且正确，参照的标准给分。若考生给出的二叉树结点的数据类型定义及算法实现中，使用的是除整型之外的其他数值类型，可视同使用整型类型。若考生给出的答案中算法主要设计思想或算法实现中部分正确，可酌情给分。42【答案要点】（1）本题中的网络可抽象为图结构。（1分）【评分说明】只要考生的答案中给出与图的含义相似的描述

23、，例如“网状结构”，“非线性结构”等，同样给分。（2）链式存储结构的数据类型定义如下：（3分）typedefstructLinkNodeunsignedintID;/所连路由器的RouterIDunsignedintIP;/本地IP地址LinkNode;/Link的结构typedefstructNetNodeunsighedintPrefix;/IP前段unsighedintMask;/掩码NetNode;/Net的结构typedefstructArcNodeintFlag;/当Flag=1时，表示Link；当Flag=2时，表示NetunionLinkNodeLnode;NetNodeNno

24、de;LinkORNet;/用union定义Link结点和Net结点unsighedintMetric;/费用structArcNode*Next;/用于指向下一个弧结点的指针ArcNode;/弧结点的结构typedefstructHNodeunsighedintRouterID;/路由器的RouterIDArcNode*LN_link;/用于指向弧结点的指针structHNode*Next;/用于指向下一个表头结点的指针HNode;/表头结点的结构对应题42表的链式存储结构示意图如下。（2分）【评分说明】若考生给出的答案是将链表中的表头结点保存在一个一维数组中（即采用邻接表形式），同样给分。

25、若考生给出的答案中，弧结点没有使用union定义，而是采用两种不同的结构分别表示Link和Net，同样在表头结点中定义了两个指针，分别指向由这两种类型的结点构成的两个链表，同样给分。考生所给的答案的弧结点中，可以在单独定义的域中保存各直连网络IP地址的前缀长度，也可以与网络地址保存在同一个域中。数据类型定义中，只要采用了可行的链式存储结构，并保存了题目中所给的LSI信息，例如将网络抽象为一类结点，写出含8个表头结点的链式存储结构，均可参照的标准给分。考生给出的答案中，图示部分应与其数据类型定义部分一致，图示只要能够体现链式存储结构及题42图中的网络连接关系（可以不给出结点内的细节信息），即可给

26、分。若解答不完全正确，酌情给分。?3）迪杰斯特拉（Dijkstra）算法得出的最短路径及费用。目的网络最短路径代价（费用）步骤1192.1.1.0/24直接到达1步骤2192.1.5.0/24R1R3192.1.5.0/243步骤3192.1.6.0/24R1R2192.1.6.0/244步骤4192.1.7.0/24R1R2R4192.1.7.0/248【评分说明】若考生给出的各条最短路径的结果部分正确，可酌情给分。若考生给出的从R1到达子网192.1.x.x的最短路径及代价正确，但不完全符合代价不减的次序，可酌情给分。43【答案要点】（1）子网192.1.6.0/24和192.1.7.0/

27、24在R1的路由表中可聚合为一个子网192.1.6.0/23。于是得到R1的路由表如下：（6分）解析：本题考察路由表的构造和路由聚合，除了192.1.1.0/24这个网络与是R1直接连接的，到达其他的网络都需要路由器之间的转发，一般是可以将每个目的网络都加到R1的路由表中的，但是题目要求使路由表中的路由项尽可能地少，于是对于剩下的三个网络我们有必要要对它们采取路由聚合，通过合并某些网络构造一个新的网络这样就减少了路由项，那么要把哪些网络聚合在一起呢，这就要将这三个网络的网络地址的第三个字段转成二进制：192.1.00000101.0192.1.00000110.0192.1.00000111.

28、0通过比较发现后两个网络前缀的前23位正好一样，且可以和第一个网络区别开来，这样就可以把后两个网络合并成一个网络，网络标识为23位，这样发给192.1.6.0/24和192.1.7.0/24的分组都可以通过路由器R2进行交付。当然最极端的情况是将这三个网络全部聚合，网络标识22位，下一跳10.1.1.10，接口是L1也可，只是这样做会无形中增加了开销。【评分说明】每正确解答1个路由项，给2分，共6分。路由项解答不完全正确或者路由项多于3条，可酌情给分。（2）R1通过L0接口转发该IP分组（1分）；主机收到的IP分组的TTL是61（1分）。解析：本题考查TTL的有关知识，这两个主机分别来自网络1

29、92.1.1.0和192.1.7.0，根据第一问构造的路由表可知，要到达网络192.1.7.0的分组都经过L0接口转发；在转发途中经过三个路由器，故TTL减3.（3）R1的LSI需要增加一条直连网络，网络前缀Prefix为“0.0.0.0/0”,Metric为10。（1分）解析：本题考察的是默认路由的概念，默认路由是一种特殊的静态路由,指的是当路由表中与包的目的地址之间没有匹配的表项时路由器能够做出的选择.如果没有默认路由器,那么目的地址在路由表中没有匹配表项的包将被丢弃.默认路由在某些时候非常有效,当存在末梢网络时,默认路由会大大简化路由器的配置,减轻管理员的工作负担,提高网络性能.因为只增

30、加了一条直连网络，并不知道此网络的网络ID，而且除了R1中到达其他网络都有转发的接口，所以增加此默认路由会减少检索工作。目的网络下一跳接口192.1.1.0/24E0192.1.5.0/2410.1.1.10L1192.1.6.0/2310.1.1.2L0?A?6B$?考生只要回答：增加前缀Prefix为“0.0.0.0/0”,Metric为10，同样给分。44【答案要点】（1）字节；（2分）解析：由题可知每条指令的长度为32位，占4个字节，而从表中我们得知相邻的两条指令的地址相差4个单位，所以存储器编址单位是字节。（2）32位；（2分）解析：R2里面存放的是数组元素的下标i，将R2中的内容左

31、移两位，相当于乘以4，然后加上R3当中存放的数组的首地址，得到元素所在的地址，然后每循环一次，R2中内容自增1。因为计算机按字节编址，每计算一次移动4个位置，故每个数组元素占4个字节，即32位。（3）-6；（1分）指令bne所在地址为08048114H，转移目标地址为08048100H，因为08048100H=08048100H+4+（-6）4；（1分）所以，指令bne的转移目标地址计算公式为（PC）+4+OFFSET4。（1分）解析：由指令bne的机器代码1446FFFAH加上OFFSET的字段位数很容易知道OFFSET=FFFAH，值为-6(这里的偏移量6是以4个字节为单位)；指令bne所

32、在地址为08048114H，执行完bne指令之后，PC的内容加1（这里的1是4个字节的单位），gotoloop转移目标地址为08048100H，于是08048100H=08048114H+4+(-6)*4；所以，指令bne的转移目标地址计算公式为：（PC）+4+OFFSET4。（4）第2、3、4、6条指令会因为数据相关而发生阻塞；（3分）第6条指令会发生控制冒险；（1分）当前循环的第5条指令虽然与下次循环的第1条指令存在数据相关，但题干告诉我们第6条指令会引起3个时钟周期的阻塞，这样就延迟了下一条指令对R2的访问，因而消除了该数据相关。（1分）解析：1从44表中的注释我们可以看到第2条指令有赖

33、于第1条指令的结果（R4），第3条指令有赖于第2条指令的结果（R4）,第4条指令有赖于第3条指令的结果（R5），第6条指令有赖于第5条指令的结果（R2）；2控制冒险也称为控制相关，见组原笔记P180，控制相关冲突是由转移指令引起的，当执行转移指令时，依据转移条件的产生结果，可能顺序执行下一条指令；也可能转移到新的目标地址取指令，从而使流水线发送断流。3程序的指令流水示意图如下：1141312111098765432指令1指令1指令6指令5指令4指令3指令2IFIDEXEMEMWBIFIDEXEMEMWBIFIDEXEMEMWBIFIDEXEMEMWBIFIDEXEMEMWBIFIDEXEMEM

34、WBIFIDEXEMEMWB三个时钟周期的阻塞从图中我们可以看出正因为有了这三个时钟周期的阻塞，延迟了下一条指令对R2的访问，所以不会出现阻塞。【评分说明】对于第1问，若考生回答：因为指令1和2、2和3、3和4、5和6发生数据相关，因而发生阻塞的指令为第2、3、4、6条指令，同样给3分。答对3个以上给3分，部分正确酌情给分。45【答案要点】（1）由于（R6）=1000，故（R2）=1000；（1分）解析：因为R2里面存放的是循环变量i，而R6里面存放的是循环的边界1000，故当循环执行结束后，i=1000，即R2的内容是1000；（2）指令Cache数据区的容量512B32B16；（1分）99

35、.98%（过程见解析）；（2分）解析：此题没有什么难度，可以认为Cache每一行就是一个独立的块，由于每块大小应和主存块大小一致，故所得。因为程序段共有6条指令，占24字节，小于一个主存块的大小（32B），故所有指令都在同一个主存块中，起始地址为08048100H。当读取第一个指令时，Cache不命中，将P所在的主存块调入Cache中的某一行，以后每次读取指令，Cache都命中，所以在1000次循环当中只出现了一次指令访问缺失，所以Cache的命中率为：（10006-1）/（10006）=99.98%【评分说明】若考生给出正确的命中率，而未说明原因和过程，给1分。若命中率计算错误，但解题思路正

36、确，可酌情给分。（3）P执行的过程中，指令4（或addR1,R1,R5）的执行可能发生溢出异常；（2分）load指令（指令3）的执行可能会产生缺页异常。因为load指令需要读取数组A的内容，当数组A不在主存时发生缺页异常。（1分）；对于数组A的访问，需要读磁盘一次，读TLB1001次（过程见解析）；解析：1因为指令4实际上对应的是sum+=Ai这一过程，这样有可能因为所得的结果超出了寄存器R1所能表示的最大的数而发生溢出异常；而其余的指令的运算都是涉及地址的运算或者是循环变量的自增（对于自增运算，只要R6和R2位数一致，就不可能溢出）是不会出现溢出的；2load指令需要访问数组A中的元素Ai，

37、当数组A不在主存当中时就发生缺页异常。3当第一次执行load指令时，因为数组A尚未调入主存，此时TLB访问失效，并且产生缺页，需要从磁盘上读取数组A，因为数组A所在的页在同一个磁盘扇区中，所以在不考虑页面置换的情况下，只需要读磁盘1次，（2分）并且读取磁盘结束后，并将快表中的内容更新；缺页异常处理结束后，重新执行load指令，load指令的随后1000次执行中，每次都能在TLB中命中，所以无需访问内存页表和磁盘，故P在1000次循环执行的过程中，对于数组A，共需读取TLB1001次。（2分）【评分说明】对于第1问，若答案中除指令4外还包含其他运算类指令（即指令1、2、5），则给1分，其他情况，

38、则给0分。对于第2问，只要回答“load指令”即可得分。对于第3问，若答案中给出的读TLB的次数为1002，同样给分。若直接给出正确的TLB及磁盘的访问次数，而未说明原因，给3分。若给出的TLB及磁盘的访问次数不正确，但解题思路正确，可酌情给分。46【答案要点】（1）下列是连续分配的磁盘块使用情况。122930199200现在需要将一条记录插入到文件F中，作为其第30条记录，也就是插入到第29条记录的后面。这需要向前移动文件的前29条记录。移动后如下图，其中灰底的磁盘块存储的是插入的记录。1233031200201向前移动文件的前29条记录，每条记录需先读一次，然后写到其前一块磁盘块中，共需2

39、92=58次。然后需要将新记录写到腾出的那个磁盘块中，作为该文件的第30条记录。故总共需要58+1=59次。由于文件的起始位置前移了一个磁盘块，同时文件也增加了一条记录，因此F的文件控制块中的文件的起始位置和文件的大小会发生改变。（2）下列是链接分配的磁盘块使用情况。现在需要将一条记录插入到文件F中，作为其第30条记录，也就是插入到第29条记录的后面。插入后效果如下图。这就需要先找到第29条文件记录的磁盘块，然后获得第30条文件记录的磁盘块地址（需读磁盘29次）。再为该记录分配一个空闲磁盘块，将该记录以及第30条文件记录的磁盘块地址写入其中，再将该块写入磁盘（需写磁盘1次）。最后还需要修改第29块的链接指针，指向新的插入块，并将第29块写回磁盘（需写磁盘1次）。故共需要29+1+1=31次。由于每个磁盘块大小为1KB，其中4个字节存放链接指针，因此用于存放文件的空间为