1、中级软件设计师下午试题-96 及答案解析(总分：105.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)阅读下列说明和数据流图，回答问题 1 至问题 3。 说明 图书管理系统旨在用计算机对图书进行管理，包括图书的购入、借阅、归还以及注销。管理人员可以查询某位读者、某种图书的借阅情况，还可以对当前图书借阅情况进行一些统计，给出统计表格，以便掌握图书的流通情况。 系统要实现以下四方面的功能：购入新书、读者借书、读者还书以及图书注销。 (1)购入新书：需要为该书编制图书卡片，包括分类目录号、图书流水号(要保证每本书都有唯一的流水号，即使同类图书也是如此)、书名、作者、内容摘要、
2、价格和购书日期等信息，写入图书目录文件中。 (2)读者借书：填写借书单，包括读者号、欲借图书分类目录号，系统首先检查该读者号是否有效，若无效，则拒绝借书，否则进一步检查该读者所借图书是否超过最大限制数，若已达到最大借阅数，则拒绝借书，否则读者可以借出该书，登记图书分类目录号、图书流水号、读者号和借阅日期等，写回到借书文件中去。 (3)读者还书：根据图书流水号，从借书文件中读出和该图书相关的借阅记录，表明还书日期，再写回借书文件中；如果图书逾期未还，则处以相应罚款。 (4)图书注销：将一些过时或无保留价值的图书注销，从图书文件中删除相关记录。 (5)流通查询：管理员可以对图书流通情况进行查询，包
3、括某位读者、某种图书和全局图书，给出流通情况统计表。 以下是经分析得到的数据流图及部分数据字典，有些地方有待填充，假定顶层数据流图是正确的。图 1-1是顶层数据流图，图 1-2 是第 0 层数据流图，图 1-3 是第 1 层数据流图。图 1-1 * 图 1-2 * 图 1-3 * * 数据字典 (1)数据流条目图书管理要求=入库单|借书单|还书单|注销单 入库单=分类目录号+数量+书名+作者+内容摘要+价格+购书日期 借书单=读者号+(d)+借阅日期 还书单=(e)+还书日期 (2)文件说明 文件名：目录文件 组成：分类目录号+书名+作者+内容摘要+价格+入库日期+总数+库存数+(f)1.根据
4、题意，指出数据流图中缺失的数据流(a)的名称，并指出该数据流的起点。（分数：15.00）_二、试题二(总题数：3，分数：15.00)1.根据 E-R 图中给出的词汇，按照“有关模式名(属性，属性，)”的格式，将此 E-R 图转换为 3 个关系模式，指出每个关系模式中的主码和外码，其中模式名根据需要取实体名或联系名。（分数：6.00）_2.创建 Athlete 表时，ANo 使用 CHAR(6)并且唯一，AName 使用 CHAR(20)，ASex 使用 CHAR(1)，ATeam 使用 CHAR(20)。请在下列用于创建表 Athelete 的 SQL 语句空缺处填入正确的内容。 CREATE
5、 TABLE Athlete(ANo CHAR(6) NOT NULL， AName CHAR(20)， ASex CHAR(1)， ATeam CHAR(20) NOT NULL， _);（分数：3.00）填空项 1:_假定 Games 表存储参赛情况，如下的 SQL 语句是委员会用于查询“队名为China的各个运动员各自夺取得的总积分”的不完整语句，请在空缺处填入正确的内容。 SEl3ECT (1) FROM Games WHERE ANo (2) (SELECT ANo FROM (3) WHERE ATeam=“China“) GROUP BY ANo;（分数：6.00）填空项 1:_
6、填空项 1:_填空项 1:_三、试题三(总题数：1，分数：15.00)阅读下列说明和图，回答问题 1 至问题 3。 说明 某大型旅店为了便于管理，欲开发一个客房管理系统。希望实现客房预定、入住登记、帐务结算、退房，以及将服务项目记入客人帐单。 旅客包括散客和团体，散客预定或入住时需要提供姓名、性别、身份证和联系电话，团体则提供团体名称、负责人的姓名、性别、身份证和联系电话，以及团体人数。对于散客，还要提供换房。 旅店还提供了很多服务项目，比如早餐。对每一个入住客人，服务列表记录了住宿期间的各项服务，包括服务类型、日期、数量等。当然，客人也可以不要任何服务。 旅店的客房有一个唯一的房间号，分为不
7、同的类别，不同的房间床位数和价格不同。 为了有效的管理，需要记录每天的客房状态。客房的状态有：空闲、占用、已预定和维修。 客人入住后，客房处于占用状态； 客人退房后，客房处于空闲状态； 客人预定后，客房处于已预定状态； 预定客人入住后，客房处于占用状态； 预定客人取消预定后客房处于空闲状态； 需要维修时客房处于维修状态； 维修完成后客房处于空闲状态。 该系统采用面向对象方法开发，系统中的类以及类之间的关系用 UML 类图表示，图 3-1 是该系统的类图的一部分，图 3-2 描述了客房状态的转变情况。 图 3-1 *图 3-2 *1.请用图 3-1 的属性和方法的名称给出客人类的属性和方法。(注
8、意：团体类中的负责人姓名等与散客的对应属性含义相同，不必区分)（分数：15.00）_四、试题四(总题数：3，分数：15.00)执行指令时，计算页号与页内地址，判断“该页在内存吗”，若在，则进行地址映射过程；若不在内存，则产生缺页中断。当发生缺页中断时，保存当前进程现场，判断“有空闲页面吗”，如有，直接调入所需的页面。若没有，按照某种算法选择一页置换，判断“该页被修改过吗”，如果被修改过，就必须把它写回磁盘以便更新该页在磁盘上的副本；如果该页没有被修改过，那么它在磁盘上的副本已经是最新的了，则不需要写回，调入的所需的页面直接覆盖被淘汰的页。调整页表及内存分配表，恢复被中断进程现场。 补充缺页中断
9、处理流程图 4-1 中的判断(1)(3)。 图 4-1 *（分数：6.00）填空项 1:_填空项 1:_填空项 1:_3.发生缺页时，通常需要进行页面置换，页面置换算法的优劣将会影响虚拟存储系统的性能。常用的页面置换算法有理想页面置换算法(OPT：Optimal)、先进先出页面置换算法(FIFO：First-In First-Out)以及最近最少使用页面置换算法(LRU：Least Recently Used)。 某程序在内存中分配 3 页，初始为空，页面走向为 4、3、2、1、4、3、5、4、3、2、1、5。给出采用先进先出(FIFO)、最近最少使用(LRU)和理想(OPT)页面置换算法所得
10、到的内存中的页面变化序列。 注：缺页标记栏，用表示没有缺页，用表示发生了缺页。 OPT 4 3 2 1 4 3 5 4 3 2 1 5页 1页 2页 3缺页标记FIFO 4 3 2 1 4 3 5 4 3 2 1 5页 1页 2页 3缺页标记LRU 4 3 2 1 4 3 5 4 3 2 1 5页 1页 2页 3缺页标记（分数：6.00）_4.简述 Belady 异常。（分数：3.00）_五、试题五(总题数：1，分数：15.00)阅读下列函数说明和 C 代码，将应填入 (n) 处的字句写上。 说明 若要在 N 个城市之间建立通信网络，只需要 N-1 条线路即可。如何以最低的经济代价建设这个网络
11、，是一个网的最小生成树的问题。现要在 8 个城市间建立通信网络，其问拓扑结构如图 5-1 所示，边表示城市间通信线路，边上标示的是建立该线路的代价。 图 5-1 * 无向图用邻接矩阵存储，元素的值为对应的权值。考虑到邻接矩阵是对称的且对角线上元素均为 0，故压缩存储，只存储上三角元素(不包括对角线)。 现用 Prim 算法生成网络的最小生成树。由网络 G=(V，E)构造最小生成树 T=(U，TE)的 Prim 算法的基本思想是：首先从集合 V 中任取一顶点放入集合 U 中，然后把所有一个顶点在集合 U 里、另一个顶点在集合V-U 里的边中，找出权值最小的边(u，v)，将边加入 TE，并将顶点
12、v 加入集合 U，重复上述操作直到 U=V为止。 函数中使用的预定义符号如下： #define MAX 32768 /*无穷大权，表示顶点间不连通*/ #define MAXVEX 30 /*图中顶点数目的最大值*/ typedef struct int startVex，stopVex; /*边的起点和终点*/ float weight; /*边的权*/ Edge; typedef struct char vexsMAXVEX; /*顶点信息*/ float arcsMAXVEX*(MAXVEX-1)/2; /*邻接矩阵信息，压缩存储*/ int n; /*图的顶点个数*/ Graph; 函
13、数 void PrimMST(Graph*pGraph, Edge mst)int i,j,k,min,vx,vy; float weight，minWeight; Edge edge; for(i=0; ipGraph-n-1；i+) msti.StartVex=0; msti.StopVex=i+1; msti.weight=pGraph-arcsi; for(i=0；i(1)；i+)/*共 n-1 条边*/ minWeight=(float)MAX; min=i; /*从所有边(vx，vy)中选出最短的边*/ for(j=i; jpGraph-n-1; j+) if(mstj.weigh
14、tminWeight) minWeight=(2); min=j； /*mstminl 是最短的边(vx，vy)，将 mstmin加入最小生成树*/ edge=mstmin； mstmin=msti; msti=edge; vx= (3) ;/*vx 为刚加入最小生成树的顶点下标*/ /*调整 msti+1到 mstn-1*/ for(j=i+1；jpGraph-n-1；j+) vy=mstj.StopVex; if( (4) )/*计算(vx，vy)对应的边在压缩矩阵中的下标*/ k=pGraph-n*vy-vy*(vy+1)/2+vx-vy-1； else k=pGraph-n*vx-vx
15、*(vx+1)/2+vy-vx-1; weight= (5) ； if(weightmstj.weight) mstj.weight=weight; mstj.StartVex=vx; （分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_六、试题六(总题数：1，分数：15.00)阅读以下说明和 C+代码，将应填入 (n) 处的字句写上。 说明 现有一个显示系统，要显示的图形有线 Line、矩形 Square，抽象出一个 Shape 类(接口)，有方法显不display()。 需要新增图形 Circle，又已知有类 XXCircle 实现了所需要实现的功能：
16、显示 displayIt()。为了继承自shape 以提供统一接口，又不希望从头开发代码，希望使用 XXCircle。这样将 XXcircle 作为 Circle 的一个属性，即 Circle 的对象包含一个 XXCircle 对象。当一个 Circle 对象被实例化时，它必须实例化一个相应的 XXCircle 对象： Circle 对象收到的做任何事的请求都将转发给这个 XXCircle 对象。通过这种称为 Adapter 模式，Circle 对象就可以通过“让 XXCircle 做实际工作”来表现自己的行为了。图 6-1 显示了各个类间的关系。以下是 C+语言实现，能够正确编译通过。 图
17、6-1 * C+代码 class Shape public： (1) void display()=0; ; class Line：public Shape/省略具体实现 ; class Square：public Shape/省略具体实现 ; class XXCircle public： void displayIt() /省略具体实现 /省略其余方法和属性 ; class Circle：public Shape private： XXCircle *pxc; public： Circle(); void display(); ; Circle：Circle() pxc= (2) ; voi
18、d Circle：display() pxc- (3) ; class Factory public： (4) getshapeInstance(int type)/生成特定类实例 switch(type) case 1：return new Square; case 2：return new Line;case 3 ：return new Circle; default：return NULL; ; void main(int argc，char*argv) if(argc !=2) cout“error parameters!“endl; return; int type=atoi(arg
19、v1); Factory factory； Shape*s=factory. (5) ; if(s=NULL) cout“Error get the instance!“endl; return; s-display(); delete s； return； （分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_七、试题七(总题数：1，分数：15.00)阅读以下函数说明和 Java 代码，将应填入 (n) 处的字句写上。 说明 现有一个显示系统，要显示的图形有线 Line、矩形 Square，抽象出一个 Shape 类(接口)，有方法显示display()。
20、 需要新增图形 Circle，又已知有类 XXCircle 实现了所需要实现的功能：显示 displayIt()。为了继承自shape 以提供统一接口，又不希望从头开发代码，希望使用 XXCircle。这样将 XXCircle 作为 Circle 的一个属性，即 Circle 的对象包含一个 XXCircle 对象。当一个 Circle 对象被实例化时，它必须实例化一个相应的 XXCircle 对象；当 Circle 对象收到的做任何事的请求都将转发给这个 XXCircle 对象。通过这种称为 Adapter 模式，Circle 对象就可以通过“让 XXCircle 做实际工作”来表现自己的行
21、为了。图 7-1 显示了各个类间的关系。以下是 JAVA 语言实现，能够正确编译通过。 图 7-1 * Java 代码 /Shape.java 文件 public interface Shape public (1) void display();/XXCircle.jave 文件 public class XXCircle public void displayIt() /省略具体实现 /Circle.java 文件 public class Circle (2) Shape private XXCircle pcx= (3) ; public void display() pcx.disp
22、layIt()； /Factory.java 文件 public class Factory public (4) getShapeInstance(int type) switch(type) case 1：return new Line()； case 2：return new Square()； case 3：return new Circle()； default：return null； /Main.java 文件 public class Main public static void main(Stringargs) int type=1； Factory factory=new
23、 Factory()； Shape s; s=factory. (5) ； if(s=null) System.out.println(“Error get the instance!“); return； s.display(); return； （分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_中级软件设计师下午试题-96 答案解析(总分：105.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)阅读下列说明和数据流图，回答问题 1 至问题 3。 说明 图书管理系统旨在用计算机对图书进行管理，包括图书的购入、借阅、归还以及注销。管
24、理人员可以查询某位读者、某种图书的借阅情况，还可以对当前图书借阅情况进行一些统计，给出统计表格，以便掌握图书的流通情况。 系统要实现以下四方面的功能：购入新书、读者借书、读者还书以及图书注销。 (1)购入新书：需要为该书编制图书卡片，包括分类目录号、图书流水号(要保证每本书都有唯一的流水号，即使同类图书也是如此)、书名、作者、内容摘要、价格和购书日期等信息，写入图书目录文件中。 (2)读者借书：填写借书单，包括读者号、欲借图书分类目录号，系统首先检查该读者号是否有效，若无效，则拒绝借书，否则进一步检查该读者所借图书是否超过最大限制数，若已达到最大借阅数，则拒绝借书，否则读者可以借出该书，登记图
25、书分类目录号、图书流水号、读者号和借阅日期等，写回到借书文件中去。 (3)读者还书：根据图书流水号，从借书文件中读出和该图书相关的借阅记录，表明还书日期，再写回借书文件中；如果图书逾期未还，则处以相应罚款。 (4)图书注销：将一些过时或无保留价值的图书注销，从图书文件中删除相关记录。 (5)流通查询：管理员可以对图书流通情况进行查询，包括某位读者、某种图书和全局图书，给出流通情况统计表。 以下是经分析得到的数据流图及部分数据字典，有些地方有待填充，假定顶层数据流图是正确的。图 1-1是顶层数据流图，图 1-2 是第 0 层数据流图，图 1-3 是第 1 层数据流图。图 1-1 * 图 1-2
26、* 图 1-3 * * 数据字典 (1)数据流条目图书管理要求=入库单|借书单|还书单|注销单 入库单=分类目录号+数量+书名+作者+内容摘要+价格+购书日期 借书单=读者号+(d)+借阅日期 还书单=(e)+还书日期 (2)文件说明 文件名：目录文件 组成：分类目录号+书名+作者+内容摘要+价格+入库日期+总数+库存数+(f)1.根据题意，指出数据流图中缺失的数据流(a)的名称，并指出该数据流的起点。（分数：15.00）_正确答案：(a)名称：当前日期，起点：系统时钟)解析：加工 2 的输入数据流有“当前日期”和“有效的图书管理要求”。根据平衡原则，加工 2.1 的输入数据流(a)应为“当前
27、日期”，其起点自然是“系统时钟”。_正确答案：(b)读者文件 (c)借书文件)解析：2“读者查询”需要“借书文件”及“读者文件”，而加工 3.3“图书查询”与“读者文件”不相关，因此 b 处应填“读者文件”，c 处应填“借书文件”。_正确答案：(d)分类目录号 (e)图书流水号 (f)图书流水号)解析：根据说明“填写借书单，包括读者号、欲借图书分类目录号”可得，借书单应包括“读者号”和“图书分类号”。故 d 应填“分类目录号”。 还书时是根据“图书流水号”的，因此还书单应包括“图书流水号”。故 e 应填图书流水号。 “目录文件”存储图书的情况，包括分类目录号、图书流水号、书名、作者、内容摘要、
28、价格，可见“目录文件”需要存储图书流水号，而且“一种”书有多个副本，因此 f 应填图书流水号。注意，大括号表示多个数据项。二、试题二(总题数：3，分数：15.00)1.根据 E-R 图中给出的词汇，按照“有关模式名(属性，属性，)”的格式，将此 E-R 图转换为 3 个关系模式，指出每个关系模式中的主码和外码，其中模式名根据需要取实体名或联系名。（分数：6.00）_正确答案：(Athlete(ANo，AName，ASex，Age，ATeam)，主键为 ANo。 Item(INo，IName，ITime，IPlace)，主键为 INo。 Games(ANo，INo，Score，Credit)，主
29、键为(ANo，INo)。)解析：E-R 模型向关系模型的转换应遵循如下原则： 每个实体类型转换成一个关系模式； 一个 1：1 的联系(一对一联系)可转换为一个关系模式，或与任意一端的关系模式合并。若独立转换为一个关系模式，那么两端关系的码及其联系的属性为该关系的属性；若与一端合并，那么将另一端的码及属性的属性合并到该端。 一个 1：n 的联系(一对多联系)可转换为一个关系模式，或与 n 端的关系模式合并。若独立转换为一个关系模式，那么两端关系的码及其联系的属性为该关系的属性，而 n 端的码为关系的码。 一个 n：m 的联系(多对多联系)可转换为一个关系模式，两端关系的码及其联系的属性为该关系的
30、属性，而关系的码为两端实体的码的组合。 三个或三个以上多对多的联系可转换为一个关系模式，诸关系的码及联系的属性为关系的属性，而关系的码为各实体的码的组合。 具有相同码的关系可以合并。 根据上述规则，可得如下关系模式： Athlete(ANo，AName，ASex，Age，ATeam)，主键为 ANo。 Item(INo，IName，ITime，IPlace)，主键为 INo。 Games(ANo，INo，Score，Credit)，主键为(ANo，INo)。2.创建 Athlete 表时，ANo 使用 CHAR(6)并且唯一，AName 使用 CHAR(20)，ASex 使用 CHAR(1)，
31、ATeam 使用 CHAR(20)。请在下列用于创建表 Athelete 的 SQL 语句空缺处填入正确的内容。 CREATE TABLE Athlete(ANo CHAR(6) NOT NULL， AName CHAR(20)， ASex CHAR(1)， ATeam CHAR(20) NOT NULL， _);（分数：3.00）填空项 1:_ （正确答案：PRIMARY KEY ANo）解析：Athlete 表 ANo 是主键，创建表时需要说明主键，故空应填 PRIMARY KEY ANo。假定 Games 表存储参赛情况，如下的 SQL 语句是委员会用于查询“队名为China的各个运动员
32、各自夺取得的总积分”的不完整语句，请在空缺处填入正确的内容。 SEl3ECT (1) FROM Games WHERE ANo (2) (SELECT ANo FROM (3) WHERE ATeam=“China“) GROUP BY ANo;（分数：6.00）填空项 1:_ （正确答案：(1)SUM(Credit)）解析：填空项 1:_ （正确答案：(2)IN）解析：填空项 1:_ （正确答案：(3)Athlete）解析：SELECTALL|DISTINCT目标列表达式，目标列表达式 FROM 表名或视图名，表名或视图名 WHERE条件表达式 GROUP BY列名 1HAVING条件表达式
33、 ORDER BY列名 2ASC|DESC 子句顺序为 SELECT、FROM、WHERE、GROUP BY、HAVING、ORDER BY，但 SELECT 和 FROM 是必须的，HAVING子句只能与 GROUPBY 搭配起来使用。SELECT 子句对应的是关系代数中的投影运算，用来列出查询结果中的属性，其输出可以是列名、表达式、集函数(AVG、COUNT、MAX、MIN、SUM)，DISTINCT 选项可以保证查询的结果集中不存在重复元组；FROM 子句对应的是关系代数中的笛卡儿积，它列出的是表达式求值过程中须扫描的关系；WHERE 予句对应的是关系代数中的选择谓词。 根据题意，空(1
34、)应填 SUM(Credit)，空(2)应填 IN，空(3)应填 Athlete。三、试题三(总题数：1，分数：15.00)阅读下列说明和图，回答问题 1 至问题 3。 说明 某大型旅店为了便于管理，欲开发一个客房管理系统。希望实现客房预定、入住登记、帐务结算、退房，以及将服务项目记入客人帐单。 旅客包括散客和团体，散客预定或入住时需要提供姓名、性别、身份证和联系电话，团体则提供团体名称、负责人的姓名、性别、身份证和联系电话，以及团体人数。对于散客，还要提供换房。 旅店还提供了很多服务项目，比如早餐。对每一个入住客人，服务列表记录了住宿期间的各项服务，包括服务类型、日期、数量等。当然，客人也可
35、以不要任何服务。 旅店的客房有一个唯一的房间号，分为不同的类别，不同的房间床位数和价格不同。 为了有效的管理，需要记录每天的客房状态。客房的状态有：空闲、占用、已预定和维修。 客人入住后，客房处于占用状态； 客人退房后，客房处于空闲状态； 客人预定后，客房处于已预定状态； 预定客人入住后，客房处于占用状态； 预定客人取消预定后客房处于空闲状态； 需要维修时客房处于维修状态； 维修完成后客房处于空闲状态。 该系统采用面向对象方法开发，系统中的类以及类之间的关系用 UML 类图表示，图 3-1 是该系统的类图的一部分，图 3-2 描述了客房状态的转变情况。 图 3-1 *图 3-2 *1.请用图
36、3-1 的属性和方法的名称给出客人类的属性和方法。(注意：团体类中的负责人姓名等与散客的对应属性含义相同，不必区分)（分数：15.00）_正确答案：(属性：姓名、性别、身份证、联系电话 方法：预定、入住、结帐)解析：“客人”类是“散客”类和“团体”类的泛化，具有二者的公共属性和公共方法。比对二者属性及方法得，“客人”类属性有：姓名、性别、身份证、联系电话，方法有：预定、入住、结账。_正确答案：(1)01 (2)1* (3)1 (4)01)解析：散客入住时只改变一个客房状态，而团体入住时则有可能改变多个客房状态；客房状态改变不一定是住宿导致的，客房维修同样改变客房状态。因此(1)处应填 01，(
37、2)处应填 1*。客人可以有多项服务，但只需用一张“服务列表”，当然也可能不需要任何服务；而一张服务列表必然属于而且只输于一个住宿。因此(3)处应填 1，(4)处应填 01。_正确答案：(A：空闲 B：占用 C：入住 D：取消预定)解析：“维修”完成后客房处于“空闲”状态，故状态 A 为“空闲”；客人入住后，客房由“空闲”转为“占用”，故状态 B 为“占用”；状态“已预订”经“入住”转为“占用”，故 C 为“入住”；状态“已预订”经“取消”转为“空闲”，故 D 为“取消”。四、试题四(总题数：3，分数：15.00)执行指令时，计算页号与页内地址，判断“该页在内存吗”，若在，则进行地址映射过程；
38、若不在内存，则产生缺页中断。当发生缺页中断时，保存当前进程现场，判断“有空闲页面吗”，如有，直接调入所需的页面。若没有，按照某种算法选择一页置换，判断“该页被修改过吗”，如果被修改过，就必须把它写回磁盘以便更新该页在磁盘上的副本；如果该页没有被修改过，那么它在磁盘上的副本已经是最新的了，则不需要写回，调入的所需的页面直接覆盖被淘汰的页。调整页表及内存分配表，恢复被中断进程现场。 补充缺页中断处理流程图 4-1 中的判断(1)(3)。 图 4-1 *（分数：6.00）填空项 1:_ （正确答案：(1)该页在内存吗？）解析：填空项 1:_ （正确答案：(2)有空闲页面吗？）解析：填空项 1:_ （
39、正确答案：(3)该页被修改过吗？）解析：根据缺页中断处理的说明，易于判断：(1)该页在内存吗？(2)有空闲页面吗？(3)该页被修改过吗？3.发生缺页时，通常需要进行页面置换，页面置换算法的优劣将会影响虚拟存储系统的性能。常用的页面置换算法有理想页面置换算法(OPT：Optimal)、先进先出页面置换算法(FIFO：First-In First-Out)以及最近最少使用页面置换算法(LRU：Least Recently Used)。 某程序在内存中分配 3 页，初始为空，页面走向为 4、3、2、1、4、3、5、4、3、2、1、5。给出采用先进先出(FIFO)、最近最少使用(LRU)和理想(OPT
40、)页面置换算法所得到的内存中的页面变化序列。 注：缺页标记栏，用表示没有缺页，用表示发生了缺页。 OPT 4 3 2 1 4 3 5 4 3 2 1 5页 1页 2页 3缺页标记FIFO 4 3 2 1 4 3 5 4 3 2 1 5页 1页 2页 3缺页标记LRU 4 3 2 1 4 3 5 4 3 2 1 5页 1页 2页 3缺页标记（分数：6.00）_正确答案：(OPT7 次 OPT 4 3 2 1 4 3 5 4 3 2 1 5页 1 4 3 2 1 1 1 5 5 5 2 1 1页 2 4 3 3 3 3 3 3 3 5 5 5页 3 4 4 4 4 4 4 4 4 4 4缺页标记
41、FIFO9 次 FIFO 4 3 2 1 4 3 5 4 3 2 1 5页 1 4 3 2 1 4 3 5 5 5 2 1 1页 2 4 3 2 1 4 3 3 3 5 2 2页 3 4 3 2 1 4 4 4 3 35 5缺页标记 LRU10 次 LRU 4 3 2 1 4 3 5 4 3 2 1 5页 1 4 3 2 1 4 3 5 4 3 2 1 5页 2 4 3 2 1 4 3 5 4 3 2 1页 3 4 3 2 1 4 3 5 4 3 2缺页标记 )解析：常用页面置换算法有： (a)理想页面置换算法(OPT：Optimal)。选择淘汰不再使用或最远的将来才使用的页。 (b)先进先出页面置换算法(FIFO：FirSt-In First-Out)。选择淘汰主存驻留时间最长的页。 (c)最近最少使用页面置换算法(LRU：Least Recently Used)。选择淘汰离当前时刻最近的一段时间使用得最少的页。 (d)随机算法(Rand)。随机地选择淘汰的页。 (e)最近未使用页面置换算法(NFU：Not Recently Used)。4.简述 Belady 异常。（分数：3.00）_正确答案：(一般来讲，在内存中的物理页面数越多，程序的缺页次数应该越少，但令人吃惊的是，实际情况并
