2014年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解

一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是符合题目要求的。

1下列程常段的时间复杂度是（　　）

A．O（log₂n）

B．O（n）

C．O（nlog₂n）

D．O（n²）

【答案】C

【解析】外部循环的退出条件是k＞n，而对于k，每次循环都执行k＝k*2，所以循环次数为log₂n；内部循环的退出条件是j＞n，对于j，每次循环都执行j＝j＋1，所以每次循环次数为n次。所以此程序段的时间复杂度为O（nlog₂n），即选C。

2假设栈初始为空，将中缀表达式a/b＋（c*d－e*f）/g转换为等价后缀表达式的过程中，当扫描到f时，栈中的元素依次是（　　）

A．＋（*－

B．＋（－*

C．/＋（*－*

D．/＋－*

【答案】B

【解析】中缀表达式转后缀表达式遵循以下原则：

（1）遇到操作数，直接输出；

（2）栈为空时，遇到运算符，入栈；

（3）遇到左括号，将其入栈；

（4）遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出；

（5）遇到其他运算符‘＋’、‘－’、‘*'、‘/’时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈；

（6）最终将栈中的元素依次出栈，输出。

所以扫描到‘/’，入栈；扫描到‘＋’，由于‘＋’优先级比‘/’低，所以将‘/’弹出，‘＋’入栈；扫描到‘*’，优先级比‘＋’高，入栈；扫描到‘（’，入栈；扫描到‘－’，将栈中优先级更高的‘*’弹出，‘－’入栈；扫描到‘*’，优先级比‘－’高，入栈。所以扫描到f的时候，栈中元素为：＋（－*。

3循环两列放在一维数组A[0…M－1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（　　）

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）modM

B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod（M－1）

C．队空：end2＝＝（end1＋1）modM；队满：end1＝＝（end2＋1）modM

D．队空：end1＝＝（end2＋1）modM；队满：end2＝＝（end1＋1）mod（M－1）

【答案】A

【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。

4若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是（　　）

A．e，c

B．e，a

C．d，c

D．b，a

【答案】D

【解析】此二叉树的中序遍历序列为：debxac，由于节点x左右孩子都为空，所有进行中序线索化时，它的左右孩子指针分别指向它的中序遍历序列的直接前驱结点b和直接后继结点a，所以选D。

5将森林F转换为对应的二叉树T，F中叶结点的个数等于（　　）

A．T中叶结点的个数

B．T中度为1的结点个数

C．T中左孩子指针为空的结点个数

D．T中右孩子指针为空的结点个数

【答案】C

【解析】森林转化为对应的二叉树是‘孩子-兄弟’存储的，即左孩子指针指向当前节点的孩子节点，右孩子指针指向当前节点的兄弟节点，所以在T中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以选C。

65个字符有如下4种编码方案，不是前缀编码的是（　　）

A．01，0000，0001，001，1

B．011，000，001，010，1

C．000，001，010，011，100

D．0，100，110，1110，1100

【答案】D

【解析】在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。约定左分支表示字符‘0’，右分支表示字符‘1’，则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。D选项中，编码110是编码1100的前缀，故不符合前缀编码的定义。

7对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（　　）

A．3，1，2，4，5，6

B．3，1，2，4，6，5

C．3，1，4，2，5，6

D．3，1，4，2，6，5

【答案】D

【解析】拓扑排序方法如下:

（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它；

（2）从图中删去该顶点，并且删去从该顶点发出的全部有向边；

（3）重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。

对于此有向图进行拓扑排序所有序列为：3，1，4，6，2，5和3，1，4，2，6，5。所以选D。

8用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（　　）

A．存储效率

B．数列函数

C．装填（装载）因子

D．平均查找长度

【答案】D

【解析】哈希方法冲突会使在查找冲突的关键字时，还要根据冲突处理办法多次比较关键字，则直接影响了平均查找长度。

9在一棵具有15个关键字的4阶B树中，含关键字的结点数最多是（　　）

A．5

B．6

C．10

D．15

【答案】D

【解析】m阶B树非根结点含关键字个数j有：⌈m/2⌉－1＜＝j＜＝m－1。4阶B树非根结点含关键字1～3个，所以要使关键字结点数量最多，那么每个结点只有一个关键字，一共有15个关键字那么最多有15个含有关键字的结点。

10用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9，1，4，13，7，8，20，23，15，则该趟排序采用的增量（间隔）可能是（　　）

A．2

B．3

C．4

D．5

【答案】B

【解析】对于A，增量为2，那么9，4，7，20，15是一组，而它们是无序的，所以A错误；对于C，增量为4，那么9，7，15是一组，而它们是无序的，所以C错误；对于D，增量为5，那么9，8是一组，降序，1，20是一组，而它们是升序，所以D也错误。对于B，分为3组：9，13，20；1，7，23；4，8，15都是升序有序，所以B正确。

11下列选项中，不可能是快速排序第2趟排序结果的是（　　）

A．2，3，5，4，6，7，9

B．2，7，5，6，4，3，9

C．3，2，5，4，7，6，9

D．4，2，3，5，7，6，9

【答案】C

【解析】对于快速排序，每一趟都会使一个元素位于有序时的位置，而有序序列为2，3，4，5，6，7，9，与C进行对比，只有9位于它有序的时候的位置，显然不是第二趟快速排序的结果。

12程序P在机器M上的执行时间是20秒，编译优化后，P执行的指令数减少到原来的70%，而CPI增加到原来的1.2倍，则P在M上的执行时间是（　　）

A．8.4秒

B．11.7秒

C．14秒

D．16.8秒

【答案】D

【解析】20*0.7*1.2＝16.8

13若x＝103，y＝－25，则下列表达式采用8位定点补码运算实现时，会发生溢出的是（　　）

A．x＋y

B．－x＋y

C．x－y

D．－x－y

【答案】C

【解析】8位定点补码能表示的数的范围为：－128～127。A结果为78，B结果为－128，D结果为－78都在此范围内，只有C结果128超过了8位定点补码能表示的数的范围，会发生溢出。

14float型整数据常用IEEE754单精度浮点格式表示，假设两个float型变量x和y分别在32为寄存器f₁和f₂中，若（f₁）＝CC900000H，（f₂）＝B0C00000H，则x和y之间的关系为：（　　）

A．x＜y且符号相同

B．x＜y且符号不同

C．x＞y且符号相同

D．x＞y且符号不同

【答案】A

【解析】两个数对应的IEEE754的标准形式为；

将IEEE754单精度形式的二进制转化为浮点数公式为V＝（－1）^s*2^（E-Bias）*M

由于f1，f2的符号位都是1，所以f1，f2符号相同，而阶码上f1＞f2，所以f1＞f2，所以f1的绝对值比f2大，而他们都是负数，所以f1＜f2，所以选A。

15某容量为256M的存储器，由若干4M*8位的DRAM芯片构成，该DRAM芯片的地址引脚和数据引脚总数是：（　　）

A．19

B．22

C．30

D．36

【答案】A

【解析】DRAM地址线复用，4M为2的22次方，因此除2为11根，数据线8根。因此地址引脚和数据引脚总数为19根。

16采用指令Cache与数据Cache分离的主要目的是（　　）

A．减低Cache的缺失损失

B．提高Cache的命中率

C．减低CPU平均访问时间

D．减少指令流水线资源冲突

【答案】D

【解析】指令流水线不会断流，预取过来的都是指令。

17某计算机有16个通用寄存器，采用32位定长指令字操作码字段（含寻址方式位）为8位，Store指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式，若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store指令中偏移量的取值范围是（　　）

A．－32768～＋32767

B．－32767～＋32768

C．－65536～＋65535

D．－65535～＋65536

【答案】A

【解析】寄存器个数16＝2^4，偏移量有32－8－4－4＝16位

指令编址方式如下所示：

16位补码取值范围为－32768～＋32767，所以偏移量取值范围为－32768～＋32767。

18某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微程序，各指令对应的微程序平均由4条微指令组成，采用断定法（下址字段法）确定下条微指令的地址，则微指令中下址字段的位数至少是：（　　）

A．5

B．6

C．8

D．9

【答案】C

【解析】32*4＋2＝130，2⁷＝128＜130＜2⁸＝256，所以至少需要8位才能表示完130个地址。

19某同步总线采用数据线和地址线复用方式。其中地址数据线有8根，总线时钟频率为66MHZ，每个时钟同期传送两次数据。（上升沿和下降沿各传送一次数据）该总线的最大数据传输率是（总线带宽）：（　　）

A．132MB/S

B．264MB/S

C．528MB/S

D．1056MB/S

【答案】C

【解析】总线带宽＝总线工作频率×（总线宽度/8），由于地址线与数据线复用，所以在两次数据传输过程中总线上数据一共传输了8次，那么总线带宽为66*8＝528，所以选C。

20一次总线事物中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元格读出或写入的个数，这种总线事务方式称为（　　）

A．并行传输

B．串行传输

C．突发

D．同步

【答案】C

【解析】猝发数据传输方式：在一个总线周期内传输存储地址连续的多个数据字的总线传输方式。

21下列有关I/O接口的叙述中错误的是：（　　）

A．状态端口和控制端口可以合用同一寄存器

B．I/O接口中CPU可访问寄存器，称为I/O端口

C．采用独立编址方式时，I/O端口地址和主存地址可能相同

D．采用统一编址方式时，CPU不能用访存指令访问I/O端口

【答案】D

【解析】采用统一编码方式，存储器和I/O端口共用统一的地址空间，不需要专用的I/O指令，任何对存储器数据进行操作的指令都可用于I/O端口的数据操作。所以D错误。

22某设备中断请求的相应和处理时间为100ns，每400ns发出一次中断请求，中断相应所容许的最长延迟时间为50ns，则在该设备持续工作过程中CPU用于该设备的I/O时间占整个CPU时间百分比至少是（　　）

A．12.5%

B．25%

C．37.5%

D．50%

【答案】B

【解析】每400ns响应一次中断并且用100ns进行处理，所以该设备的I/O时间占用CPU时间百分比为100/400＝25%，中断响应容许的延迟时间对此没有影响，属于干扰条件。

23下列调整中，不可能导致饥饿现象的是（　　）

A．时间片转移

B．静态优先及调度

C．非抢占式作业优先

D．抢占式短作业优先

【答案】A

【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU使用时间，不会产生饥饿的现象，其余三个都会产生饥饿。

24某系统有n台互斥使用的同类设备，3个并发进程需要3，4，5台设备，可确保系统不发生死锁的设备数n最小为（　　）

A．9

B．10

C．11

D．12

【答案】B

【解析】2＋3＋4＋1＝10。

25下列指令中，不能在用户态执行的是（　　）

A．trap指令

B．跳转指令

C．后栈指令

D．关中断指令

【答案】D

【解析】关中断指令必须在和心态才能执行，trap指令可以在用户态下执行，执行了就转到和心态，跳转与退栈指令都是可以在用户态下执行的指令。

26一个进程的读磁区操作完成后，操作系统针对该进程必做的是（　　）

A．修改进程状态为就绪态

B．降低进程优先级

C．进程分配用户内存空间

D．增加进程的时间片大小

【答案】A

【解析】进程等待的I/O操作完成便会从等待状态转移到就绪状态。

27现有容量为10GB的磁盘分区，磁盘空间以簇（cluster）为单位进行分配，簇的大小为4KB，若采用位图法管理该分区的空闲空间，即用一位（bit）标识一个簇是否被分配，则存放该位图所需簇的个数为（　　）

A．80

B．320

C．80K

D．320K

【答案】A

【解析】磁盘的簇的个数为：10GB/4KB＝2.5*2²⁰个，而一个簇的位示图能管理的簇的个数为：4KB*8＝32K，所以需要簇的个数为2.5*2²⁰/32K ＝80个。

28下列措施中，能加快虚实地址转换的是1增大快表（TLB）2让页表常驻内存3增大交换区（　　）

A．仅1

B．仅2

C．仅1，2

D．仅2，3

【答案】C

【解析】加大快表能增加快表的命中率，即减少了访问内存的次数；让页表常驻内存能够使CPU不用访问内存找页表，从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响

29在一个文件被用户进程首次打开的过程中，操作系统需做的是（　　）

A．将文件内容读到内存中

B．将文件控制块读到内存中

C．修改文件控制块中的读写权限

D．将文件的数据缓冲区首指针返回给用户进程

【答案】B

【解析】概念

30在页式存储管理系统中，采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady异常现象的是（　　）

Ⅰ．LRU算法

Ⅱ．FIFO算法

Ⅲ．OPT算法

A．仅Ⅱ

B．Ⅰ、Ⅱ

C．Ⅰ、Ⅲ

D．Ⅱ、Ⅲ

【答案】A

【解析】Belady现象只有FIFO算法才会出现。

31下列关于管道（Pipe）通信的叙述中，正确的是（　　）

A．一个管道可实现双向数据传输

B．管道的容量仅受磁盘容量大小限制

C．进程对管道进行读操作和写操作都可以被阻塞

D．一个管道只能有一个读写进程或一个写进程对其操作

【答案】C

【解析】只有写进程才能对管道写入数据，读进程对管道进行读取数据，只能半双工通信，即某一时刻只能单向传输。管道为空，则读操作被堵塞，而如果有写操作对管道进行写的话那就要堵塞了。那么C正确。

32下列选项中，属于多级页表优点的是（　　）

A．加快地址变换速度

B．减少缺页中断次数

C．减少页表项所占字节数

D．减少页表所占的连续内存空间

【答案】D

【解析】多级页表避免了把所有的页表一直保存在内存中。

33在OSI参考模型中，直接为会话层提供服务的是（　　）

A．应用层

B．表示层

C．传输层

D．网络层

【答案】C

【解析】OSI参考模型中，下层直接为上层提供服务，而会话层的下层为传输层。

34某以太网拓扑及交换机当前转发表如下图所示，主机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发送一个确认帧，交换机对这两个帧的转发端口分别是（　　）

A．{3}和{1}

B．{2，3}和{1}

C．{2，3}和{1，2}

D．{1，2，3}和{1}

【答案】B

【解析】第一次交换机没有00-e1-d5-00-23-c1的信息，只能选择从其他端口全部发送，同时记录这个数据报源MAC地址的信息00-e1-d5-00-23-a1，确认帧发送时已经有00-e1-d5-00-23-a1的信息了所以只用从1端口转发。

35下列因素中，不会影响信道数据传输速率的是（　　）

A．信噪比

B．频率宽带

C．调制速率

D．信号传播速度

【答案】D

【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。

36主机甲与主机乙之间使用后退N帧协议（GBN）传输数据，甲的发送窗口尺寸为1000，数据帧长为1000字节，信道宽带为100Mbps，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间的单向传播延迟是50ms，则甲可以达到的最大平均数据传输速率约为（　　）

A．10 Mbps

B．20 Mbps

C．80 Mbps

D．100 Mbps

【答案】C

【解析】1000B*1000/（50*2ms）＝10MB＝80Mbps。

37站点A、B、C通过CDMA共享链路，A、B、C的码片序列（chipping sequence）分别是（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发送的数据是（　　）

A．000

B．101

C．110

D．111

【答案】B

【解析】用A的码片与信息做内积运算。

38主机甲和乙已建立了TCP连接，甲始终以MSS＝1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB的确认段。若甲在t时刻发生超时时拥塞窗口为8KB，则从t时刻起，不再发生超时的情况下，经过10个RTT后，甲的发送窗口是（　　）

A．10KB

B．12KB

C．14KB

D．15KB

【答案】A

【解析】发送窗口是接受窗口和拥塞窗口的最小值，这里接收窗口总是10KB。拥塞窗口到那个时候是大于10KB的，取最小值。

39下列关于UDP协议的叙述中，正确的是（　　）

Ⅰ．提供无连接服务

Ⅱ．提供复用/分用服务

Ⅲ．通过差错校验，保障可靠数据传输

A．仅Ⅰ

B．仅Ⅰ、Ⅱ

C．仅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

【答案】B

【解析】UDP无连接创建，提供多路复用服务。虽然有差错检验，但是不能保证可靠数据传输，所以Ⅲ错误。

40使用浏览器访问某大学Web网站主页时，不可能使用的协议是（　　）

A．PPP

B．ARP

C．UDP

D．SMTP

【答案】D

【解析】SMTP是简单邮件传输协议，访问主页时并不涉及邮件相关协议。

二、综合应用题：41～47小题，共70分。

41（10分）二叉树的带权路径长度（WP1）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T，采用二叉链表存储，节点结构为：

其中叶节点的weight域保存该结点的非负权值。设root为指向T的根节点的指针，设计求T的WP1的算法。要求：

（1）给出算法的基本设计思想；

（2）使用C或C＋＋语言，给出二叉树结点的数据类型定义；

（3）根据设计思想，采用C或C＋＋语言描述算法，关键之处给出注释。

答：（1）算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。

（2）typedef struct BiNode

（3）具体算法实现如下：

42（10分）某网络中的路由器运行OSPF路由协议，题42表是路由器R1维护的主要链路状态信息（LSI），题42图是根据题42表及R1的接口名构造出来的网络拓扑。

题42表　R1所维护的LSI

题42图　R1构造的网络拓扑

请回答下列问题。

本题中的网络可抽象为数据结构中的哪种逻辑结构？

针对题42表中的内容，设计合理的链式存储结构，以保存题42表中的链路状态信息（LSI）。要求给出链式存储结构的数据类型定义，并画出对应题42表的链式存储结构示意图（示意图中可仅以ID标识节点）。

按照迪杰斯特拉（Dijikstra）算法的策略，依次给出R1到达题42图中子网192.1.x.x的最短路径及费用。

答：（1）图

（2）使用图的邻接表存储结构进行存储，数据类型定义如下：

链式存储结构示意图如下图所示：

（3）目标网络192.1.1.0/24记为N1，192.1.5.0/24记为N2，192.1.6.0/24记为N3，192.1.7.0/24记为N4，使用dijkstra算法找最短路径步骤如下表所示：

所以R1到达子网192.1.1.0/24最短路径为：R1->子网，费用为1；

R1到达子网192.1.6.0/24的最短路径为：R1->R2->子网，费用为3；

R1到达子网192.1.5.0/24的最短路径为：R1->R3->子网，费用为4；

R1到达子网192.1.7.0/24的最短路径为R1->R2->R4->子网，费用为8。

43（9分）请根据题42描述的网络，继续回答下列问题。

（1）假设路由表结构如下表所示，请给出题42图中R1的路由表，要求包括到达题42图中子网192.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需要增加哪些信息？

答：（1）

（2）通过接口L0转发该IP分组，由于要经过R1，R2，R4三个路由器，所以主机192.1.7.211收到的IP分组的TTL为64－3＝61。

（3）只需要在R1的LSI中增加一项信息，prefix＝目的internet，Metric＝10。

44（11分）某程序中有如下循环代码段p：

假设编译时变量sum和i分别分配在寄存器R1和R2中。常量N在寄存器R6中，数组A的首地址在寄存器R3中，程序段P起始地址为0804 8100H，对应的汇编代码和机器代码如题44表所示

执行上述代码的计算机M采用32位定长指令字，其中分支指令Bne采用如下格式，

Op为操作码：Rs和Rd为寄存器编号：OFFSET为偏移量，用补码表示。请回答下列问题，并说明理由。

（1）M的存储器编址单位是什么？

（2）已知sll指令实现左移功能，数组A中每个元素占多少位？

（3）题44表中bne指令的OFFSET字段的值是多少？已知bne指令采用相对寻址方式，当前PC内容为bne指令地址，通过分析题44表中指令地址和bne指令内容，推断出bne指令的转移目标地址计算公式。

（4）若M采用如下“按序发射、按序完成”的5级指令流水线：IF（取指）、ID（译码及取数）、EXE（执行）、MEM（访存）、WB（写回寄存器），且硬件不采取任何转发措施，分支指令的执行均引起3个时钟周期阻塞，则P中哪些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令1的执行不会因为与指令5的数据相关而发生阻塞？

答：（1）由题可知，指令为32为即4个字节，而程序执行时是以4为间隔逐条取指令的，故可知M的存储器是采用字节编址。

（2）32位，因为sll中实现左移，而（R2）＜＜2→R4即左移两位就是乘以4，所以是4*8＝32位。

（3）由Bne的指令格式可知其OFFSET为指令的后16位，而Bne的机器码码为1446 FFFAH，所以Bne的OFFSET为FFFAH即－6。

由题可知Bne采用相对寻址方式，故有效地址EA＝（PC）＋A＝（PC）＋OFFSET，而PC的值为当前Bne指令的地址即（PC）＝08048114H，而取完Bne指令后，（PC）＋4→PC，故（PC）＝0804 8118H。而要跳转到指令1的地址08048100H，两者相差了18H也就是24个字节，而OFFSET是－6，故转移目标地址计算公式为（PC）＋OFFSET*（24/6）＝（PC）＋OFFSET*4。

（4）由指令序列可知，指令1需写R4而指令2需读R4，故指令2会因为数据相关而发生阻塞，同理指令3、指令4也会因为数据相关而发生阻塞；而指令6为分支指令，故其存在控制冒险。因为分支指令会有3个时钟周期的阻塞，故指令1的执行不会因为指令5的数据相关而发生阻塞。

45（10分）假设对于44题中的计算机M和程序P的机器代码，M采用页式虚拟存储管理。P开始执行时，（R1）＝（R2）＝0，（R6）＝1000，其机器代码已调入主存但不在Cache中；数组A未调入主存，其所有数组元素在同一页，并存储在磁盘同一个扇区，请回答下列问题，并说明理由。

（1）P执行结束时，R2的内容是多少？

（2）M的指令Cache和数据Cache分离，若Cache共有16行，Cache和主存交换的块大小为32字节，则其数据区的容量是多少？若仅考虑程序段P的执行，则指令Cache的命中率为多少？

（3）P在执行过程中，哪条指令的执行可能发生溢出异常？哪条指令的执行可能产生缺页异常？对于数组A的访问，需要读磁和TLB至少各多少次？

答：（1）R2是保存变量i的内容，当P执行完即i＜N不满足，故i＝N＝（R6）＝1000。

（2）Cache共有16行，每行大小为32B，而本段指令大小为6*4B＝24B，故指令占一行Cache，所以数据Cache的大小为15*32B＝160B。

由题可知N＝1000，故循环了1000次，所以共执行了1000*6＝6000条指令，而只有第一次循环执行指令1时指令不在Cache中，故指令Cache命中率＝（6000－1）/6000＝99.9%。

（3）指令4有可能发生溢出，该指令是统计数组A[0]～A[i]的和，而数组A的各元素的值未知，故该指令是可能发生溢出的。

第一次执行指令2时需要访问数组A，而数组A未在内存中，故会发生缺页异常。由题可知数组A的所有元素在同一页，并存储在磁盘同一个扇区，故经过一次便将该页调入内存，所以以后访问便不会发生缺页中断，故只需读一次磁盘，999次TLB。

46（9分）文件F由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F中，作为其第30条记录，请回答下列问题，并说明理由。

（1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件F的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？F的文件控制区内容会有哪些改变？

（2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要访问多少存储块？若每个存储块大小为1KB，其中4个字节存放指针，则该系统支撑文件的最大长度是多少？

答：（1）因为要最少访问，所以选择将前29块前移一个存储块单元，然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出，再访问目标存储块将数据写入，所以最少需要访问29*2＋1＝59块存储块。F的文件区的文件长度加1，起始块号减1。

（2）采用链接方式则需要顺序访问前29块存储块，然后将新纪录的存储块插入链中即可，把新的块存入磁盘要1次访存，然后修改第29块的链接地址存回磁盘又一次访存。一共就是29＋1＋1＝31次。4个字节的指针的地址范围为2³²。所以此系统支撑文件的最大长度为2³²*（1KB－4B）＝4080GB。

47（11分）系统中有多个生产者进程和消费者进程，共享用一个可以存1000个产品的缓冲区（初始为空），当缓冲区为未满时，生产者进程可以放入一件其生产的产品，否则等待；当缓冲区为未空时，消费者进程可以取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品，请用信号量P，V（wait，signed）操作实现进程间的互斥和同步，要求写出完整的过程；并指出所用信号量的含义和初值

答：设置5个信号量，

empty：表示缓冲区是否为空，初值为1000；

full：表示缓冲区是否为满，初值为0；

mutex1：生产者之间的互斥信号，初值为1；

mutex2：消费者之间的互斥信号，初值为1；

available：当前消费者能否访问缓冲区，初值为1；

定义变量in，out分别为生产者和消费者进程所要使用的指针，指向下一个可用的缓冲区单元，MaxNum＝1000为缓冲区的大小，count标志当前消费者已经取的产品的数量，初值为0。

生产者进程：

消费者进程