考研计算机学科专业基础综合-17

1、考研计算机学科专业基础综合 -17（ 总分： 150.00 ，做题时间： 90 分钟 ）一、 单项选择题 （ 总题数： 40，分数： 80.00）1. 栈S最多只能容纳4个元素，现在6个元素按A, B, C, D, E, F的顺序进栈，下列哪一个序列是可能的 出栈序列 （ ）?A EDCBAF BBCEFAD CCBEDAF DADFEBC（分数： 2.00 ）A.B.C. VD.解析：由于栈只能容纳 4个元素，所以一次进栈最多 4个，即ABCD同时在栈中，则EDCBA不可能，E和F 还没有进栈就已经出栈，B中的D元素不可能出栈在 A的后面。D中最后两个元素出栈顺序也有误。2. 有A, B,

2、C, D, E 5个元素按次序入栈，在各种可能的出栈次序中，以元素C, D最先出栈的序列中，下列正确的一组是 （ ） 。ACDBAE CDABEBCDEBA CDBEACCDEAB CDABEDCEBAE CDAEB（分数： 2.00 ）A.B. VC.D.解析：要使得CD作为第一、二个元素出栈，应是A、B、C先入栈，C出栈，D入栈，D出栈；接着就剩下A、 B在栈中，E未入栈，共3个元素，此三者序列为 BAE BEA EBA3. 已知一棵完全二叉树的第 6层（设根为第 1层）有8个叶结点，则完全二叉树的结点个数最多是（ ） 。A39 B52 C111 D119（分数： 2.00 ）A.B.C.

3、 VD.解析：4将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（）。I父子关系兄弟关系山.u的父结点与v的父结点是兄弟关系A. 只有U B .I和U C .I和U D .I、U和山分数： 2.00 ）A.B. VC.D.解析：5. 线索化的二叉树中，某结点 *p 没有孩子的充要条件是 ( ) 。A. p- lchild=NULL B . p- ltag=1 & p- rtag=1C. p- ltag=0 D . p- lchild=NULL & p- Itag = 1(分数： 2.00 )A.B. VC.D.解析：参考线索二叉树

4、的定义。6. 设二叉排序树中关键字由11000的整数构成，现要查找关键字为363的结点，下列关键字序列不可能是在二叉排序树上查找到的序列是 ( ) 。A 2， 252401 ， 398， 330， 344， 397 ， 363 B 924， 220， 911 ， 244， 898， 258， 362， 363C 925 ， 202， 911， 240， 912， 245， 363D2， 399， 387， 219， 266， 382， 381， 278， 363(分数： 2.00 )A.B.C. VD.解析：可以把这四个序列各插入到一个初始为空的二叉排序树中，结果可以发现，C序列形成的不是一条

5、路径，而是有分支的，可见它是不可能在查找过程中访问到的序列。7. 在下列查找的方法中，平均查找长度与结点个数 n 无关的查找方法是 ( ) 。A. 顺序查找B .二分法C.利用二叉搜索树 D .利用哈希(hash)表 (分数： 2.00 )A.B.C.D. V解析：8. 如下所示带权图G,其最小生成树各边权的总和为()。*A14 B19 C21 D26分数： 2.00 )A.C. VD.解析：9将两个长度为N的有序表归并到一个长度为2N的有序表，最少需要比较的次数是（），最多需要比较的次数是 （ ） 。AN， 2N-1 B N-1， 2NC N， 2N D N-1， 2N-1 （分数： 2.0

6、0 ）A. VB.C.D.解析：10. 用直接插入排序方法对下列 4 个表进行 （由小到大 ）的排序，比较次数最少的是 （ ）A 94，32，40， 90， 80，46，21，69 B 21，32，46，40， 80，69，90，94C32，40，21， 46， 69，94，90，80 D90，69，80，46， 21，32，94，40（分数： 2.00 ）A.B.C. VD.解析：11. CPU中决定指令执行顺序的是（）。A. 指令寄存器IR B 程序计数器PCC.程序状态字寄存器 PSWR D主存地址寄存器 MAR（分数： 2.00 ）A.B. VC.D.解析：CPU中用程序计数器PC来跟

7、踪下一条将要执行的指令的地址，即通过程序计数器PC来决定指令执行顺序。12. 一个C语言程序在一台32位机器上运行。程序中定义了三个变量x、y和z，其中x和z是int型，y为 short 型。当 x=127， y=-9 时，执行赋值语句 z=x+y 后， x、 y 和 z 的值分别是 （ ） 。A.x=0000007FH，y=FFF9H， z=00000076HB.x=0000007FH，y=FFF9H， z=FFFF0076HC.x=0000007FH，y=FFF7H， z=FFFF0076HD. x=0000007FH，y=FFF7H， z=00000076HB.分数： 2.00 ）A.C

8、.D. V解析：结合题干及选项可知，int为32位，short为16位；又C语言的整型数据在内存中为补码形式，故x、 y 的机器数写为十六进制为O000007FH、FFF7H；执行 z=x+y 时，由于 x 为 int 型， y 为 short 型，故需将 y 的类型强制转换为 int ，在机器中通过符号位扩 展实现，由于 y 的符号位为 1，故在 y 的前面添加 16个 1，即可将 y 强制转换为 int 型，其十六进制形式 为 FFFFFFF7H；然后执行加法，即 0000007FH+FFFFFFF7H=00000076H最高位的进位1自然丢弃）。故选 D。13. 原码两位乘中，符号位单独

9、处理，参加操作的数是 （ ） 。A. 原码B .补码C.绝对值的原码 D .绝对值的补码（分数： 2.00 ）A.B.C.D. V 解析：原码两位乘中，符号位单独处理，但运算过程中可能需要进行“减被乘数绝对值”的操作，计算机 中减法一般通过补码加法来实现，故原码两位乘运算过程中参加操作的数是绝对值的补码。14. 在Cache和主存构成的两级存储系统中， Cache的存取时间为100ns，主存的存取时间为 1卩s，Cache 访问失败后CPU才开始访存。如果希望Cache主存系统的平均存取时间不超过 Cache存取时间的15%则 Cache的命中率至少应为（）。A. 95% B. 98% C.

10、98.5% D. 99.5%（分数： 2.00 ）A.B.C. VD.解析：设Cache主存系统的平均存取时间为Cache存取时间的1.15倍时Cache命中率为p，则有100+1000X（1 -p）=115，解之得，p=0.985=98.5%。15. 双端口存储器之所以能高速读写是因为 （ ） 。A. 采用了两套独立的存储体B 采用了两套相互独立的读写电路C.采用了新型的器件 D 两套读写电路分时使用存储体（分数： 2.00 ）A.B. VC.C. 解析：双端口存储器采用了两套相互独立的读写电路，两套读写电路可以同时访问共同的存储体，故可以 高速读写。16. 某机主存容量64KB,按字节编址

11、。主存地址 0100H处有一条相对转移指令，指令字长16位，其中，第一个字节为操作码，第二个字节为相对位移量（用补码表示 ） ，则该指令执行结束后，后继指令的地址范围可能是 （ ） 。A. 0000HFFFFH B. 0080H017FHC. 0082H0181H D . 0080H01FFH（分数： 2.00 ）A.B.C. VD.解析：该指令取指结束后，PC值自动加2,即（PC）=0102H;相对位移量用8位补码表示，故其范围为80H7FH,扩展到16位为FF80H- 007FH,与PC值相加就可得后继指令的地址范围为0082H0181H。17. 下列哪个选项不是 RISC的特点（）。A.

12、 只有取数和存数指令访问存储器，其余指令都在寄存器之间进行B. 由使用频率高的简单指令和很有用且不复杂的指令组成C. 使用RISC技术后，指令系统又回到了计算机发展早期的比较简单的情况D. 使用优化的编译程序（分数： 2.00 ）A.B.C. VD.解析：早期的指令系统简单是由设计水平和器件水平决定的，而且RISC技术不是简单地精简了指令系统,而是在合理选择简单指令的基础上采取了很多优化措施，如缩短机器周期，采用流水线技术，使用优化的 编译程序等等，两者不可等同。18. 下列微指令的编码方式中，执行速度最快的是 （ ） 。A. 直接编码B 字段直接编码C.字段间接编码 D 无法判断（分数： 2

13、.00 ）A. VB.C.D.解析：直接编码方式下，微指令操作控制字段中的每一位代表一个微操作命令，微操作命令的发出不需要 通过译码，故执行速度最快。19. 相对于微程序控制器，硬布线控制器的特点是 （ ） 。A. 指令执行速度慢，指令功能的修改和扩展容易B. 指令执行速度慢，指令功能的修改和扩展难C. 指令执行速度快，指令功能的修改和扩展容易D. 指令执行速度快，指令功能的修改和扩展难分数： 2.00 )A.B.C.D. V解析：硬布线控制器采用硬连线逻辑，故一旦构成，除非在物理上进行重新布线，否则指令功能无法修改 和扩展； 微程序控制器采用存储逻辑， 当需要对指令功能进行修改和扩展时， 只

14、要重新设计微代码的码点， 并将其注入控制存储器中即可；但是由于采用存储逻辑，相比硬布线控制器多了从控制存储器中读出码点 的过程，故其执行速度较慢。综合上述分析，可知D 正确。20. 某机采用计数器定时查询方式来进行总线判优控制， 共有 4个主设备竞争总线使用权， 当计数器初值恒 为 10 2 时， 4 个主设备的优先级顺序为 ( ) 。A. 设备0设备1设备2设备3 B .设备2设备1 设备0设备3C.设备2设备3设备0设备1 D .设备2=设备3=设备0=设备1(分数： 2.00 )A.B.C. VD.解析：计数器初值为 102 ，故设备 2的优先级最高，计数器值会递增然后返回到0，故优先级

15、顺序为设备2设备3设备0设备1。21 .下列通道中，以字节为单位进行数据传送的是 ( ) 。A. 字节多路通道 B 选择通道C 数组多路通道 D 以上都是(分数： 2.00 )A. VB.C.D.解析：选择通道和数组多路通道都是以数据块为单位进行数据传送。22. 下列选项中，能引起外部中断的事件是 ( ) 。A. 键盘输入B .除数为0 C .浮点运算下溢 D .访存缺页(分数： 2.00 )A. VB.C.D.解析：浮点数下溢一般做“机器零”处理.不引起中断；除数为0、访存缺页会引出内部中断；只有键盘输入能引起外部中断，故选A。23. 单处理机系统中，可并行的是 ( ) 。I进程与进程H处理

16、机与设备山处理机与通道 W设备与设备A. I、U和山B .I、U和W C.I、山和W D.U、山和W(分数： 2.00 )A.B.C.D. V解析：进程和进程是不能并行的，因为只有一个CPU。24. 下列进程调度算法中，综合考虑进程等待时间和执行时间的是A. 时间片轮转调度算法B 短进程优先调度算法C.先来先服务调度算法D 高响应比优先调度算法（分数：2.00 ）A.B.C.D. V解析：响应比=（等待时间+执行时间”要求服务的时间。25. 某计算机系统中有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是（）。A. 2 B . 3 C . 4 D

17、. 5（分数：2.00 ）A.B.C. VD.解析：每个进程都占有 2台打印机时，发生死锁。26. 在虚拟存储系统中，若进程在内存中占3位（开始时为空），采用先进先岀页面淘汰算法，当执行访问页号序列为1，2, 3，4，1，2，5，1, 2，3，4，5，6时，将产生（）次缺页中断。A. 7 B . 8 C . 9 D . 10（分数:A.B.C.2.00 )27. 拿内存加上外存容量之和与虚拟存储空间相比，其大小关系是 （）A.前者比后者大 B .前者比后者小 C .二者相等D .不一定（分数：2.00 ）A.B.C.D. V解析：虚拟存储空间是由地址的位数决定的，可能比内存加上外存大，也可能小

18、。28. 位示图可用于磁盘空间的管理。设某系统磁盘共有500块，块号从0到499;第0字的第0位表示第0块，第0字的第1位表示第1块，依次类推。若用位示图法管理这 500块的盘空间，当字长为 32位时，第 i个第j位对应的块号是（）。A. 32i+j B . 32i+j-1C 32i+j-32 D 32i+j-32-1（分数： 2.00 ）A. VB.C.D.解析：因为从 0 开始编号，所以选 A。29. 考虑一文件存放在 100 个数据块中，文件控制块、索引块或索引信息都驻留内存。那么，如果 （ ） ，不 需要做任何磁盘 I/O 操作。A. 采用contiguous allocation策略

19、，将最后一个数据块搬到文件头部B. 采用single level indexed allocation策略，将最后一个数据块插入文件头部C. 采用linked allocation策略，将最后一个数据块插入文件头部D. 采用linked allocation策略，将第一个数据块插入文件尾部（分数： 2.00 ）A.B. VC.D.解析：采用索引分配：将最后一个数据块插入文件头部，只需修改索引表就行，不需要移动数据。30. 文件系统中，设立打开文件系统功能调用的基本操作是 （ ） 。A. 把文件信息从辅存读到内存B. 把文件的控制管理信息从辅存读到内存C. 把文件的FAT表信息从辅存读到内存D.

20、 把磁盘的超级块从辅存读到内存（分数： 2.00 ）A.B. VC.D.解析：本题考查文件打开的概念。31. 文件系统采用树形目录结构后，对于不同用户的文件，其文件名 （ ） 。A.应该不同B 由操作系统类型决定C.可以相同也可以不同 D 受系统约束（分数： 2.00 ）A.B.C. VD.解析：树形目录的引入提高了检索的效率， 解决了文件的重名问题， 即允许不同的用户使用相同的文件名 因此，对于不同用户文件而言其文件名既可以相同也可以不同。32. 对于硬盘上存放的信息，物理上读写的最小单位是一个A.二进制B .字节C .物理块D .逻辑记录（分数： 2.00 ）A.B.C. VD.解析：硬盘

21、的读取是以块为单位的。33.IEEE的802委员会已经标准化了很多种类的LAN其中无线LAN标准是（）A. IEEE802.3 B. IEEE802.5C. IEEE802.11 D . IEEES02.17（分数： 2.00 ）A.B.C. VD.解析：IEEE802.11是无线LAN的标准。34. 有一条无噪声的8KHz信道，每个信号包含8级，每秒采样24K次，那么可以获得的最大传输速率是 （）A. 24Kbps B. 32Kbps C . 48Khps D. 72Kbps（分数： 2.00 ）A.B.C. VD.解析：无噪声的信号应该满足尼奎斯特定理，即最大数据传输率=2Hlog2V（位

22、/秒）。将题目中的数据带入，得到答案是48kHz。注意题目中给出的每秒采样 24kHz是无意义的，因为超过了 2H,所以D是错误答案。35. 下图为一个modem勺调制图，那么当它要发送115200bps的数据时，需要达到（）波特率。*A. 115200bpsB. 57600bpsC. 28800bpsD. 230400bps（分数： 2.00 ）A.B. VC.D.解析：如题的调制图所示，信道上一个信号可以有四种变化，即可以表示2bit 的数据。那么为了达到115200bps的数据率，只要 57600bps的波特率就可以了。36. 在 Internet 的几种路由协议中， （ ） 采用了链路

23、状态路由算法。A. RIP B. BGP C. OSF， F D. NAT(分数： 2.00 )A.B.B. VD.解析：OSPF开放的最短路径优先)内部网关路由协议采用了链路状态路由算法。37. 个3200bit上的TCP报文传到IP层，数据链路层可以发送的最长数据帧中的数据部分只有1200bitIP 层需要向数据链路层发送 ( ) 。A3200bit B 3400bit C 5400bit D 3680bit(分数： 2.00 )A.B.C.B. V解析：在题目给出的情况中，必须要对IP包进行分片，需要分 3200/ 1200=3片。那么共需要添加 3个IP首部，每个IP首部的长度是160

24、bit ,那么总共需要发送 3200+160X3=3680bit数据。38. 某公司获得了一个 IP 地址段，在不分子网的情况下， 最多可以容纳 65534 个主机，那么这个地址属于 ( )。A. A类地址B . B类地址C . C类地址D . D类地址(分数： 2.00 )A.B. VC.D.解析：B类地址的主机号的长度是 16位，再去点全“ 0”和全“1”两个地址，还可以分配65534个主机。39. 在 TCP/IP 模型中，主机采用 ( ) 标识，运行在主机上的应用程序采用 ( ) 标识A.端口号，主机地址 B .主机地址，IP地址CIP 地址，主机地址 DIP 地址，端口号(分数： 2

25、.00 )A.B.C.D. V解析：在 TCPIP 模型中， IP 地址用来标识主机，使用 IP 地址来完成数据包的路由。而端口号则存在于 传输层的头部中，用来标识主机上的不同进程。40. 下面( ) 协议中，客户端和服务器之间采用面向无连接的协议进行通信。AFTP BSMTP CTELNET DDHCP分数： 2.00 )A.B.C.B. V解析：DHCP采用UDP来发送数据，所以 D是采用面向无连接的协议的。二、 综合应用题 ( 总题数： 7，分数： 70.00)41. 在平衡二叉树中的每个结点上增设一个 Lsize 域，其值为它的左子树中的结点个数加 1，试写一个时间 复杂度为 O(lo

26、g n) 的算法，确定树中第 k 个结点的位置。分数： 10.00 )正确答案：(A二叉排序树中第k个结点，即为二叉排序树中序序列中顺序号为k的结点，根结点的Lsize域中存放的是根结点的顺序号。要确定二叉排序树中第k个结点，先需将k与根结点的顺序号进行比较，若相等，则找到；若 k 小于根结点的顺序号， k 继续与根的左孩子结点的顺序号比较，依次类推。 (注意， 右孩子结点的顺序号等于根结点的顺序号与右孩子结点的 Lsize 域值之和。 ) 由于查找过程中不超过树的高 度，故其算法复杂度为 O(log n) 。typedef struct Nodeint key:struct Node* lc

27、hild,*rchild:int LsizeBSNode;BSNode* Locate(BSNode* T,int k)int j,i=0;BSNode* p=T;while(p)j=i+p- Lsize;if(j=k) return p;/找到if(j k) p=p- lchild;elsei+=p- Lsize;p=P-rchild;return NULL:)解析：如下图所示的AOE网，求：*(分数： 15.00 )(1) . 每项活动 ai 的最早开始时间 e(ai) 和最迟开始时间 1(ai )。(分数：3.75 ) 正确答案： ( 所有事件的最早发生时间如下：Ve(1)=0Ve(2)

28、=5Ve(3)=6Ve(4)=maxve(2)+3 ， ve(3)+6=12Ve(5)=maxve(3)+3 ， ve(4)+3=15Ve(6)=ve(4)+4=16Ve(7)=ve(5)+1=16Ve(8)=ve(5)+4=19Ve(9)=maxve(7)+5 ， ve(8)+2)=21Ve(10)=maxve(6)+4 ， ve(9)+2=23 所有事件的最晚发生时间如下： Vl(10)=23Vl(9)=vl(10)-2=21Vl(8)=vl(9)-2=19Vl(7)=vl(9)-5=16Vl(6)=vl(10)-4=19Vl(5)=minvl(7)-1， vl(8)-4=15Vl(4)=

29、minvl(6)-4， vl(5)-3)=12Vl(3)=minvl(4)-6， vl(5)-3=6Vl(2)=vl(4)-3=9Vl(1)=minvl(2)-5， vl(3)-6=0因此，所有活动 Ai的 e( ) ， l( )，d（ ） 如下：Al:e(1)=ve(1)=0 ，l(1)=vl(2)-5=4， d(1)=4A2:e(2)=ve(1)=0 ，l(2)=vl(3)-6=0， d(2)=OA3:e(3)=ve(2)=5，l(3)=vl(4)-3=8， d(3)=3A4:e(4)=ve(3)=6，l(4)=vl(4)-6=6， d(4)=0A5:e(5)=ve(3)=6，l(5)=v

30、l(5)-3=12， d(5)=6A6:e(6)=ve(4)=12，l(6)=vl(5)-3=12， d(6)=0A7:e(7)=ve(4)=12 ，l(7)=vl(6)-4=15， d(7)=3A8:e(8)=ve(5)=15，l(8)=vl(7)-1=15， d(8)=0A9:e(9)=ve(5)=15，l(9)=vl(8)-4=15， d(9)=0A11:e(11)=ve(7)=19， l(11)=vl(9)-2=19， d(10)=0A10:e(12)=ve(8)=16， l(12)=vl(10)-4=19， d(10)=3A10:e(13)=ve(9)=21， l(13)=vl(10

31、)-2=21， d(10)=0)解析：（2）. 完成此工程最少需要多少天 （设边上权值为天数 ）? （分数： 3.75 ） 正确答案： （ 完成此工程最少需要 23 天。） 解析：（3）. 哪些是关键活动 ?（分数： 3.75 ）正确答案：（从以上计算可知，关键活动为a2, a4, a6, a8, a9, a10, all, a13。这些活动构成两条关键路径即： a2， a4， a6， a8， a10， a13 和 a2， a4， a6， a9， a11 ， a13。 ）解析：（4）. 是否存在某项活动，当其提高速度后能使整个工程缩短工期?（分数： 3.75 ） 正确答案： （存在 a2， a

32、4， a6， a 1 3活动，当其提高速度后能使整个工程缩短工期 ）解析：某32位机（机器字长32位）的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令，平均每 条指令需要5个机器周期，其中3个周期必须访问内存，内存读写需一个机器周期，假定CPU在 95%的时间内持续执行“背景程序”，且这段时间内不执行 I/O 指令。现该外设需要把一个非常大的数据块传送到 内存。分数： 11.00 ）(1) .如果采用程序I/O方式，每传送一 32位字宽的数据需要 CPU执行2条指令。请计算最大数据传输率(单 位：字 / 秒)。(分数： 5.50 )正确答案：(1)数据块非常大，可认为其执行时

33、间远远大于1s，故可用其1s内的最大数据传输率来近似表示其整个传输过程中的最大数据传输率， (2) 同。CPU每秒执行100条指令，且95%的时间内持续执行背景程序，故1s内CPU可用来进行I/O传送的指令条数为100X(1 -95%)=5(条)最大数据传输率为5/2=2.5( 字/秒)解析：(2) .如果采用DMA方式，在DMA与 CPU出现总线访问冲突时，CPU优先。请计算最大数据传输率(单位：字 /秒)。(分数：5.50) 正确答案：(CPU每秒内共有(10 0X5=)500个机器周期，其中执行“背景程序”时有(100 X95%X3=)285 个 机器周期必须访问内存， 由于DMA与 C

34、PU访存冲突时，CPU优先，故DMA空制器只能在余下的500-285=215 个机器周期内访存；又内存读写需要一个机器周期，故采用DMA专输方式时，1s内可读写内存215次，即最大数据传输率为215字/ 秒。 )解析：42. 下图是某模型机CPU的组成框图。设该CPL采用同步控制逻辑，分取指周期、取第一操作数周期，取第 二操作数周期、执行周期四个机器周期，每个机器周期有T。、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADD R0 (R1)完成功能(R0)+(R1) -R0*分数： 10.00 ) 正确答案： ( 各机器周期的微操作命令及节拍安排如下。(1) 取指周期T:P

35、Ct总线t MA冷主存，微操作命令形成部件发读信号到主存:M(MAR戸MDR微操作命令形成部件发+1信号到PCT2：MDFT总线t IR，OP(IR)t微操作命令形成部件(2) 取第一操作数周期T0：R0t总线t firstT1:T2:(3) 取第二操作数周期T0：R1t总线t mat主存，微操作命令形成部件发读信号到主存T1:M(MAR)tMDRT2：MDFT总线t second(4) 执行周期T0：FIRSTt 总线tyT1：微操作命令形成部件发 Add信号到ALU, (Y)+(SECONDTALITZT2：Z t总线t R0)解析：43. 设有一缓冲池P, P中含有10个可用缓冲区，一个

36、输入进程将外部数据读入P，另有一个输出进程将 P中数据取出并输出 (如下图所示 )。若进程每次操作均以一个缓冲区为单位，试用记录型信号量写出两个进程的同步算法，要求写岀信号量的设置。 输入进程输岀进程L:读入数据L:从一满缓冲区中取岀数据 将数据写入一空缓冲区将数据输岀GOTO L GOTO L（分数：7.00 ） 正确答案：（设置信号量 mutex, empty, full 初值，mutex=1 , empty=10, full=0（2）设置Wflit , signal操作如下。输入进程输岀进程L:读入数据 L : wait（full）wait（empty） wait（mutex）wait（

37、mutex） 从一满缓冲区中取出数据将数据写入一空缓冲区signal（mutex）signal（mutex） signal（empty） signal（full）将数据输出）解析：页号页框(Page Frame)号有效位（存在位）0101H1102254H1请求分页管理系统中，假设某进程的页表内容如下表所示。页面大小为4KB, 次内存的访问时间是 100ns, 一次快表仃LB）的访问时间是10ns，处理一次缺页的平均 时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为 2，采用最近最少使用置换算法（LRU） 和局部淘汰策略。假设：TLB初始为空；地址转换时先访问TLB,若T

38、LB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到 产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H 25A5H,请问：（分数：8.00 ）（1）.依次访问上述三个虚地址，各需多少时间？给出计算过程。（分数：4.00 ） 正确答案：（根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解岀来。页面大小为4KB,即212，则得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的页号P如下（十六进制的一位数字转换成 4位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号）：2362H:P=2,访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns ,共计 10ns+100ns+100ns=210ns。1565H:P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，合成物理地址后访问主存 100ns，共计 10ns+100ns+108ns+100np 108ns。25A5H:P=2,访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计 10ns+100ns=110n