1、2004年下半年软件水平考试（中级）软件设计师下午（应用技术）试题真题试卷及答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 阅读下列说明和数据流图，回答问题 1至问题 3。说明 某图书管理系统的主要功能是图书管理和信息查询。对于初次借书的读者，系统自动生成读者号，并与读者基本信息 (姓名、单位、地址等 )一起写入读者文件。 系统的图书管理功能分为四个方面：购入新书、读者借书、读者还书以及图书注销。 1购入新书时需要为该书编制入库单。入库单内容包括图书分类目录号、书名、作者、价格、数量和购书日期，将这 些信息写入图书目录文件并修改文件中的库存总量 (表示到目前为止，购入此种图书的数
2、量 )。 2读者借书时需填写借书单。借书单内容包括读者号和所借图书分类目录号。系统首先检查该读者号是否有效，若无效，则拒绝借书；若有效，则进一步检查该读者已借图书是否超过最大限制数 (假设每位读者能同时借阅的书不超过 5本 )，若已达到最大限制数，则拒绝借书；否则允许借书，同时将图书分类目录号、读者号和借阅日期等信息写入借书文件中。 3读者还书时需填写还书单。系统根据读者号和图书分类目录号，从借书文件中读出与该图书相关的借阅记录，标明 还书日期，再写回到借书文件中，若图书逾期，则处以相应的罚款。 4注销图书时，需填写注销单并修改图书目录文件中的库存总量。 系统的信息查询功能主要包括读者信息查询
3、和图书信息查询。其中读者信息查询可得到读者的基本信息以及读者借阅图书的情况；图书信息查询可得到图书基本信息和图书的借出情况。 图书管理系统的顶层图如图 1-1所示；图书管理系统的第 0层 DFD图如图1-2所示，其中，加工 2的细化图如图 1-3所示。1 数据流图 1-2中有两条数据流是错误的，请指出这两条数据流的起点和终点。 2 数据流图 1-3中 缺少三条数据流，请指出这三条数据流的起点和终点。 3 根据系统功能和数据流图填充下列数据字典条目中的 (1)和 (2)： 查询请求信息 =【查询读者请求信息 |查询图书请求信息】 读者情况；读者号 +姓名 +所在单位 +借书情况 管理工作请求单
4、=(1) 入库单 =(2) 4 阅读下列说明和 E-R图，回答问题 1至问题 3，将解答填入答题纸的对应栏内。说明 某网上订书系统的 E-R图 (已消除了不必要的冗余 )如图 2-1所示 (图中没有标出主码 )。图中实体的说明如表 2-1所示，相关属性说明如 表 2-2所示。一个顾客可以在同一天填写多张购书单，每张购书单上可填写多种图书，每种图书可以订购多本， bid相同的图书在同一张购书单上不能出现多次。 注：为简化起见，不考虑信用卡号码泄漏所带来的安全性等问题。4 根据 E-R图中给出的词汇，按照 “关系模式名 (属性，属性， )” 的格式，将此 E-R图转换为 4个关系模式，并指出每个关
5、系模式中的主码和外码，其中模式名根据需要取实体名或联系名。 5 创建 Customers表时， cid使用 INTEGER数据类型， cnarne使用 CHAR(80)数据类型， address使用 CHAR(200)数据类型， cardnum使用 CHAR(16)数据类型并且要求此列值惟一。请在下列用于创建表 Customers的 SQL语句空缺处填入正确的内容。 CREATE TABLE Customers(cid INTEGER NOT NULL， cname CHAR(80)NOT NULL， address CHAR(200)， cardnum CHAR(16)NOT NULL， (
6、1)， (2) 6 如下的 SQL语句是书店用于查询 “所有订购了 bid为 123-456图书的用户订购其他图书的情况 ”的不完整语句，请在空缺处填入正确的内容。 Select bid From Orderlist A Where not exists(Select*from Orders B where A.ordemum=B.ordemum and B.cid (3) (Select cid from Ordcrlist C,Orders D where (4) bid=123-456 and (5)=D.ordemum) 7 阅读下列说明和图，回答问题 1至问题 3，将解答填入答题纸的
7、对应栏内。【说明】 某指纹门禁系统的体系结构如图 3-1所示，其主要部件有：主机(MainFrame)、锁控器 (LockController)、指纹采集器 (FingerReader)和电控锁 (Lock)。 (1)系统中的每个电控锁都有一个惟一的编号。锁的状态有两种： “已锁住 ”和 “未锁住 ”。 (2)在主机上可以设置每把锁的安全级别以及用户的开锁权限。只有当用户的开锁权限大于或等于锁的安全级别并且锁处于 “已锁住 ”状态时，才能将锁 打开。 (3)用户的指纹信息、开锁权限以及锁的安全级别都保存在主机上的数据库中。 (4)用户开锁时，只需按一下指纹采集器。指纹采集器将发送一个中断事件给
8、锁控器，锁控器从指纹采集器读取用户的指纹并将指纹信息发送到主机，主机根据数据库中存储的信息来判断用户是否具有开锁权限，若有且锁当前处于 “已锁住 ”状态，则将锁打开；否则系统报警。 该系统采用面向对象方法开发，系统中的类以及类之间的关系用 UML类图表示，图 3-2是该系统类图的一部分；系统的动态行为采用 UML序列图表示，图 3-3是用户成功开锁的序列图。7 图 3-2是该系统类图的一部分，依据上述说明中给出的术语，给出类 Lock的主要属性。 8 依据上述说明中给出的词语，将图 3-3中的 (1) (5)处补充完整。 9 组装 (composition)和聚集 (aggregation)是
9、 UML中两种非常重要的关系。请说明组装和聚集分别表示什么含义 ?两者的区别是什么 ? 10 阅读下列说明和图，回答问题 1至问题 3，将解答填入答题纸的对应栏内。 【说明】 在并发系统设计中，通过对信号量 S的 P、 V操作实现进程的同步与互斥控制。 P(S):S:=S-1，若 S0，则执行 P操作的进程继续执行：若 S 0，则置该进程为阻塞状态，并将其插入阻塞队列。 V(S):S:=S+1，若 S 0，则执行 V操作的进程继续执行；若 S0，则从阻塞队列唤醒一个进程，并将其插入就绪队列，然后执行 V操作的进程继续执行。 10 在某并发系统中，有一个发送进程 A、一个接收进程 B、一个环形缓
10、冲区BUFFER、信号量 S1和 S2。发送进程不断地产生消息并写入缓冲区 BUFFER，接收进程不断地从缓冲区 BUFFER取消息。假设发送进程和接收进程可以并发地执行，那么，当缓冲区的容量为 N时，如何 使用 P、 V操作才能保证系统的正常工作。发送进程 A和接收进程 B的工作流程如图 4-1所示。请在图 4-1中的空 (1) (4)处填入正确的内容。 11 若系统中有多个发送进程和接收进程，进程间的工作流程如图 4-2所示，其中空 (1) (4)的内容与图 4-1相同。发送进程产生消息并顺序地写入环形缓冲区BUFFER，接收者进程顺序地从 BUFFER中取消息，且每条消息只能读取一次。为
11、了保证进程间的正常通信，增加了信号量 SA和 SB。 请说明信号量 SA和 SB的物理意义，并在图 4-2中的空 (5)和空 (6)处填入正确的内容。 请从图 4-2的 (a) (1)中选择四个位置正确地插入 P(SA)、 V(SA)、 P(SB)、V(SB)。 12 设系统中只有进程 A和进程 B，除了互斥地使用 CPU和打印机 R外，进程 A和 B不使用其他资源。另外，进程 B的优先级比 A高，而进程 A先于 B准备好。进程 A和 B的执行情况如图 4-3所示，其中粗实线表示进程在执行中，细实线表示打印机 R在使用中 (每个进程具有三种状态：运行、就绪和阻塞 )。请分别说明进程 A和 B在
12、图 4-3所示的 t1、 t2、 t3、 t4时刻所处的状态；若是阻塞状态，请说明阻塞原因。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 13 阅读下列函数说明和 c代码，将应填入 (n)处的字句写在答题纸的对应栏内。【说明】 函数 int Toplogical(Linded WDipaph G)的功能是对图 G中的顶点进行拓扑排序，并返回关键路径的长度。其中图 G表示一个具有 n个顶点的 AOE-网，图中顶点从 1 n依次编号，图 G的存储结构采用邻接表表示，其数据类型定义如下： typedefs
13、truct Gnode /* 邻 接表的表结点类型 */ iht adjvex; /* 邻接顶点编号 */ iht weight; /* 弧上的权值 */ street Gnode *nextarc; /* 指示下一个弧的结点 */ Gnode; typedef struct Adjlist /* 邻接表的头结点类型 */ char vdata; /*顶点的数据信息 */ struct Gnode *Firstadj; /* 指向邻接表的第一个表结点 */ Adjlist; typedef street LinkedWDigraph /* 图的类 型 */ int n, e; /* 图中顶点个
14、数和边数 */ struct Adjlist *head; /*指向图中第一个顶点的邻接表的头结点 */ LinkedWDigraph; 例如，某AOE-网如图 5-1所示，其邻接表存储结构如图 5-2所示。【函数】 iht Toplogical(LinkedWDigraph G) Gnode *p; intj, w, top = 0; iht *Stack, *ye, *indegree; ye = (int *)malloe(G.n+1) * sizeof(int); indegree = (int *)malloc(G.n+1)*sizeof(int); /* 存储网中各顶点的入度 */
15、 Stack = (int *)malloe(G.n+1)*sizeof(int); /* 存储入度为0的顶点的编号 */ if(!ve|!indegree | !Stack) exit(0); for (j = 1;j = G.n;j+) vej = 0; indegreej= 0; /*for*/ for(j= 1;j 14 阅读以下说 明和 C+代码，将应填入 (n)处的字句写在答题纸的对应栏内。 说明 通常情况下，用户可以对应用系统进行配置，并将配置信息保存在配置文件中。应用系统在启动时首先将配置文件加载到内存中，这些内存配置信息应该有且仅有一份。下面的代码应用了单身模式 (Singl
16、eton)以保证 Configure类只能有一个实例。这样， Configure类的使用者无法定义该类的多个实例，否则会产生编译错误。 C+代码 #include iostream h class Configure (1)： Configure() /构造函数 public： static Configure*Instance()； public： int GetConfureData()return data； /获取配置信息 int SetConfigureDate(int m_data) data=m_data； return data； /设置配置信息 private： static
17、 Configure*_instance； int data； /配置信息 ； (2)=NULL； Configure*Configure Instance() if(_instance NULL) _instance=(3); /加载配置文件并设置内存配置信息，此处省略 return (4)； void main()( Configure*t=NULL； t=(5)； int d=tGetConfigureData() ； /获取配置信息后进行其他工作，此处省略 15 阅读以下说明和 Java代码，将应填入 (n)处的字句写在答题纸的对应栏内。说明 类 Queue表示队列，类中的方法如下表所
18、示。类 Node表示队列中的元素；类 EmptyQueueException 给出了队列操作中的异常处理操作。 Java 代码 public class TestMain / 主类 public static void main(String args) Queue q = new Queue(); q.enqueue(“first!“); q.enqueue(“second!“); q.enqueue(“third!“); (1) while(true) System.out.println(q. dequeue(); catch(2) ( public class Queue / 队列 N
19、ode m_FirstNode; public Queue() m_FirstNode = null; public boolean isEmpty() if(m_FirstNode = null) return true; else return false; public void enqueue(Object newNode) / 入队操作 Node next = m_FirstNode; if(next=null) m_FirstNode = new Node(newNode); else while(next.getNext() != null) next = next.getNex
20、t(); next.setNext(new Node(newNode); public Object dequeue() (3) / 出队操作 Object node; if (isEmpty() (4); / 队列为空，抛出异常 else node = m_FirstNode.getObject(); m_FirstNode = m_FirstNode.getNext(); return node;public class Node / 队列中的元素 Object m_Data; Node m_Next; public Node(Object data) m_Data = data; m_N
21、ext = null; public Node(Object data, Node next) m_Data = data; m_Next = next; public void setObject(Object data) m_Data = data; public Object getObject0 return m_Data; public void setNext(Node next) m_Next = next; public Node getNext() return m_Next; public class EmptyQueueException extends (5) / 异常
22、处理类 public EmptyQueueException0 System.out.println(“队 列已空 ! “); 2004年下半年软件水平考试（中级）软件设计师下午（应用技术）试题真题试卷答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 【正确答案】 起点：读者文件 终点：登记读者信息或 3 起点：处理查询请求或 2 终点：读者文件 【试题解析】 本题考查的是数据流图方面的基础知识。对这种类型问题求解的关键是要仔细阅读题目，注意解题技巧，从一些常规的入口作为突破口，即利用分层数据流图数据流的平衡原则 (即父图和子图 (加工图 )的一致性 )来解题。 (子图是其父图 中
23、某一部分内部的细节图 (加工图 )，它们的输入 /输出数据流应该保持一致。子图也是如此，在上一级中有几个数据流，他的子图也一定有同样的数据流。 )而且它们的输送方向是一致的 (也就是说如果原图有 3条进的数据流 2条出的，子图同样也是 )。 比较数据流图 1-1和数据流图 1-2可以得到，图书管理系统的所有输入流和输出流都是正确的，所以可以初步判断是图 1-2中从加工 2到读者文件的数据流和从读者文件到加工 3的数据流是错误的，再分析题目说明： “对于初次借书的读者，系统自动生成读者号，并与读者基本信息 (姓名、单位、地址等 )一起写 入读者文件 ”，此段说明表示加工 3应该向读者文件中写入数
24、据，从 “系统首先检查该读者号是否有效，若无效，则拒绝借书 ”可以得出加工 2从读者文件中读取数据。另外，从数据流图 1-3可以看出数据流图是从读者文件到读者查询加工。所以错误的数据流是加工 2到读者文件和从读者文件到加工 3。 2 【正确答案】 起点：图书目录文件 终点：图书信息查询或 2.2 起点：借书文件 终点：读者信息查询或 2.1 起点；借书文件 终点：图书信息查询或 2.2 【试题解析】 读者信息查询可得到读者的基本信息以及读者借阅 图书的情况；图书信息查询可得到图书基本信息和图书的借出情况。读者基本信息存储在读者文件中，而读者借阅图书的信息存储在借书文件中，图书的基本信息存储在图
25、书目录文件中，而图书借阅情况则需要通过借书文件获得，所以，应该有从借书文件到加工 2.1和加工 2.2，以及从图书目录文件到加工 2.2的三条数据流。 3 【正确答案】 (1)【入库单 |借书单 |还书单 |注销单】 (2)分类目录号 +书名 +作者 +价格 +数量 +购书日期 【试题解析】 根据题目说明，管理工作主要分为购入新书、读者借书、读者还书以及图书注销，而每一项 管理工作都需要填写相应的单据，所以，管理工作请求单 =【入库单 |借书单 |换书单 |注销单】，入库单的内容包括图书分类目录号、书名、作者、价格、数量和购书日期，因此，入库单 =图书分类目录号 +书名 +作者 +价格 +数量
26、 +购书日期。 4 【正确答案】 Customers(cid， cname， adderss， cardnum)，主键： cid Orders(ordemum,orderdate,cid)，主键： ordemum外键： cid Books(bid,title,author,qty_in_stock,year_publicshed,price)，主键： bid Orderlist(bid， ordemum， qty,ship_date)，其中 bid和 ortlemum是主键，也是键码 注：以上四个关系模式和每个模式中的属性可按任意次序书写。 【试题解析】 本题考查的是数据库方面的知识。 问题
27、1：题干已经指明转换为 4个关系模式，根据 ER图和说明可以得出：Books、 Customers 和 orders 为三个关系模式，由于一个客户可以填写多张购书单，而一张购书单仅仅属于一个客户，所以， PlaceOrder不需要单独 成为一个关系模式，而购书单和书之间是多对多的关系，所以， OrderList 需要单独一个关系模式。因此关系模式和其主键及外键如下： 1 Customers(cid， cname， adderss， cardnum) 主键为： cid 2 Orders(ordemum， orderdate， Cid) 主键为： ordemum；外键为： cid 3 Books(
28、bid， title， author， qty_in_stock， year_publicshed， price) 主键为： bid 4 Orderlist(bid， ordemum， qty， ship_date) 主键为： (bid， ordemum)，外键为 bid、 ordemum 5 【正确答案】 (1)PRIMARY KEY(cid) (2)UNIQUE(cardnum) 注： (1)和 (2)的次序可以颠倒。 【试题解析】 根据题意分析，对于关系模式 Customers的主键为 cid，而cardnum列值惟一，因此，应分别在空缺处填入 Primary Key cid 和 UNI
29、QUE carclnum。 填写后完整的 SQL语句如下： CREATE TABLE Customers(cid INTEGERNOTNULL， crlame CHAR(80)NOTNULL， address CHAR(200)， cardnum CHAR(16)NOTNULL， Primary Key cid， UNIQUE cardnum ) 6 【正确答案】 (1)not in (2)C (3)C.ordemum 【试题解析】 根据题意分析，最内层的 SQL 语句查找订购了 123-456的客户cid， ordemum只出现在 Orderlist和 order 中，所以 (5)中应填写
30、C.ordemum， (4)中应该填写 C，而要求寻找这些用户还订购哪些其他书籍，所以 (3)中应填写 in。 填写后完整的 SQL语句如下： Select bid From Orderlist A Where not exists(Select*fromOrdersB where A.ordernum=B.ordernym and B cid in (Select cid from Orderlist C， Orders D where C bid=123-456 and C.ordemum =D.ordemum) 7 【正确答案】 锁的编号、安全级别、锁的当前状态 【试题解析】 本题是一道
31、使用面向对象方法进行系统开发的题目，主要考查利用UML 的类图和序列图进行面向对象的分析。 类图是面向对象系统的建模中最常见的图。类图显示了一组类、接口、协作以及它们之间的关系。类图用于对系 统静态设计视图建模。在图形上，类图是顶点和弧的集合。在类图中通常包含：类、接口、协作、依赖、泛化和关联关系。类图还可以含有包或者子系统，二者都用于把模型元素聚集成更大的组块。 当对系统的静态设计视图建模时，通常以下述 3种方式之一使用类图。 对系统的词汇建模。对系统的词汇建模涉及做出这样的决定：哪些抽象是考虑中的系统的一部分，哪些抽象处于系统边界之外。用类图详细描述这些抽象和它们的职责。 对简单的协作建模
32、。协作是一些共同工作的类、接口和其他元素的群体，该群体提供的一些合作行为强于所有这些 元素的行为之和。 对逻辑数据库模式建模。将模式看作为数据库的概念设计的蓝图。在很多领域中，要在关系数据库或面向对象数据库中存储永久信息。可以用类图对这些数据库的模式建模。 序列图是场景的图形化表示，描述了以时间顺序组织的对象之间的交互活动。序列图有两个特征： 序列图有对象生命线。对象生命线是一条垂直的虚线，表示一个对象在一段时间内存在。在交互图中出现的大多数对象存在于整个交互过程中，所以这些对象全都排列在图的顶部，其生命线从图的顶部画到图的底部。但对象也可以在交互过程中创建，它们的 生命线从接收到构造型为 c
33、reate的消息时开始。对象也可以在交互过程中撤销，它们的生命线在接收到构造型为 destroy。 y的消息时结束(并且给出一个大 x的标记表明生命的结束 )。 序列图有控制焦点。控制焦点是一个瘦高的矩形，表示一个对象执行一个动作所经历的时间段，既可以是直接执行，也可以是通过下级过程执行。矩形的顶部表示动作的开始，底部表示动作的结束 (可以由一个返回消息来标记 )。还可以通过将另一个控制焦点放在它的父控制焦点的右边来显示 (由循环、自身操作调用或从另一个对象的回调所引起的 )控制焦点的嵌 套 (其嵌套深度可以任意 )。如果想特别精确地表示控制焦点在哪里，也可以在对象的方法被实际执行 (并且控制
34、还没传给另一个对象 )期间，将那段矩形区域阴影化。 问题 1：图 3-2给出了一个不完整的类图，已经完成了面向对象分析中的认定类，下一步的工作是定义类的内部信息，本题主要考查如何从问题域中抽象出类的属性。由于已经确定了类，寻找类的属性就相对容易了。 类 Lock 是本系统中的一个关键类，与它的属性相关的描述有： “系统中的每个电控锁都有一个惟一的编号 ”、 “锁的状态有两种 ”、 “在主机上可以设置每把锁的安全级别 ”。 “锁的编号 ”、 “锁的状态 ”以及 “锁的安全级别 ”都是用来说明 Lock 的属性及特性的，也是类 Lock 的关键属性。 8 【正确答案】 (1)中断事件 (2)读取用
35、户指纹 (3)读取用户开锁权限 (4)读取锁的安全级别 (5)判断用户是否有权限开锁或用户是否可以开锁 【试题解析】 序列图显示了一组对象和由这组对象发送和接收的消息。创建序列图时，首先应确定要建模的内容。它是针对一个用例的基本活动过程吗 ?一个候选过程 ?还是基本活动过程与一个或多个候选过程的组合 ?本题中并没有给出用例图 ，但是题目的说明已经指出了图 3-3所示的序列图的建模内容：用户成功开锁的活动。 用户开锁的过程在说明中的 (4)给出。序列图是按照时间顺序组织的对象之间的交互活动，因此需要将这些活动按照时间顺序排序，并记录下参与每个活动的对象。 用户开锁的激发事件是：用户按下指纹采集器
36、。 发送 “中断事件 ”；指纹采集器 锁控器。 读取用户指纹；锁控器 指纹采集器。 请求开锁；锁控器 主机。 读取锁的状态；主机 锁。 读取用户的开锁权限；主机 用户。 读取锁的安全级别； 主机 锁。 判断用户是否能够开锁：主机 主机。 通知能够开锁；主机 锁控器。 将锁打开；锁控器 锁。 9 【正确答案】 组装和聚集都表示实例之间的整体 /部分关系。组装是聚集的一种形式。 聚集是概念性的，只是区分整体与部分。 组装具有很强的归属关系，而且整体与部分的对象生存周期是一致的。 或者回答：如果没有成分对象，组装对象也不存在；在任何时候，每个给定的成分对象只能是组装对象的组成部分。 【试题解析】 在
37、面向对象的建模中，有 3种特别重要的关系：依赖，它表示类之间的使用关系； 泛化，它把一般类连接到它的特殊类；关联，它表示对象之间的结构关系。 聚集是一种特殊的关联。聚集完全是概念性的，只不过要区分所谓的整体与部分。聚集既没有改变整体与部分之间跨越关联的导航含义，也不链接整体和部分的生存周期。组装是聚集一种形式，它具有强的拥有关系，而且整体与部分具有相同的生存周期。在组装中，一个对象在一个时间内只能是一个组装的一部分：整体负责对它的各个部分的处置，这意味着组装必须管理它的部分的创建与撤销。 10 【正确答案】 (1)P(S1) (2)V(S2) (3)P(S2) (4)V(S1) 【试题解析】
38、本题考查的是并发系统的同步与互斥控制。 在并发系统中，同时存在的多个进程在执行速度上是相对独立的，它们以各自的运行速度向前推进。但是，由于多个并发进程或者共享系统资源，或者合作完成某项任务，所以它们之间常常存在着相互制约或彼此依赖的关系，进程之间的这种制约和依赖关系可以归结为两种基本形式：同步和互斥。 一般来说，一个进程相对于另一个进程的运行速度是不确定的，也就是说进程是在异步环境下运行的，每个进程都有各自独立的、不可预知的速度向前推进。但是相互合 作的进程需要在某些确定点上协调它们的工作，当一个进程到达了这些点后，除非另一进程已经完成了某些操作，否则就不得不停下来等待这些操作结束。这就是进程
39、间的同步。 在多道程序系统中，各进程可以共享各类资源，但有些资源一次只能供一个进程使用，称为临界资源 (critical resource， CR)，如打印机、公共变量、内存工作区、表格等。临界区 (critical section， CS)是进程中对临界资源实施操作的那段程序。 在多道程序系统中，一般都使用 P、 V操作原语通过信号量实现进程的同步和互斥。信号量 是一种特殊的变量，它具有以下特性： 信号量是一个整型变量。 每一个信号量表示一种系统资源的状况，其值表示资源当前可用的数量。 每一个信号量都对应一个空或非空的等待队列，该队列就是信号量所表示的资源的等待队列。 对信号量只能实施 P、
40、 V操作，只有 P、 V操作才能改变其值。 P操作的功能是：当进程执行 P操作时，首先将信号量 S减一，其结果为：若 S0，则该进程继续运行；若 S 0，则阻塞该进程，并把它插入道信号量 S 的等待队列中。 V操作的功能是：当进程执行 V操作时，首先将信号量 S 加 1，其结果是：若 S 0，则该进程继续执行；如果 So，则释放 S 信号量等待队列中队首的等待进程，解除其阻塞状态，而调用 V操作的当前进程继续执行。 P、 V操作是一对操作，若有对信号量的 P操作，必定有对该信号量的 V操作，这样才能保证资源被合理地分配和释放。 问题 1：缓冲区 BUFFER是临界资源，信号量 S1表示缓冲区中
41、空闲单元的数目，初值为 N，信号量 S2表示缓冲区中消息的数目，初值为 0。 显然，发送进程海产生一条消息，将消耗一个空闲的缓冲区单元，所以将消息送入缓冲区时应先执 行一个 P(S1)，写入消息后执行一个 V(S2)。当接收进程执行时，若缓冲区中有消息，则可读取，然后将释放一个空闲单元，所以接收进程进入其临界区后先执行一个 P(S2)，读取消息后执行一个 V(S1)。 11 【正确答案】 表示允许同时对缓冲区进行写操作的进程数量 表示允许同时对缓冲区进行读操作的进程数量 P(SA)插入位置 (b)， V(SA)插入位置 (f)， P(SB)插入位置 (h)， V(SB)插入位置 (k)。 解法
42、 2： 表示允许同时对缓冲区进行读操作的进程数量 表示允许同时对缓冲区进行写操作的进程数量 P(SB)插入位置 (b)， V(SB)插入位置 (f)， P(SA)插入位置 (h)， V(SA)插入位置 (k)。 【试题解析】 当系统中有多个发送进程和接收进程时，对缓冲区的写操作应互斥地进行，并且发送进程对下标 i的修改要顺序地进行：同时，要保证每个消息只能被读取 1次，对缓冲区的读操作也要互斥地进行，并且接收进程对下标 j的修改要顺序地进行。因此，信号量 SA和 SB用于对缓冲区的写、读操作进行互斥控制。 12 【正确答案】 【试题解析】 从题目中给出的进程 A和 B 的执行情况可知，由于进程
43、 A先就绪，所以进程 A先开始执行，当进程 A使用打印机 R时，就释放 CPU。在进程 A释放 CPU期间，进程 B 准备就绪而 CPU空闲，所以进程 B 开始执行。在 t1 时刻，进程 A在等待打印机 R工作结束，所以处于阻塞状态，而进程 B显然在运行状态。在 t2 时刻，进程 A仍然在等待打印机 R工作结束，所以处于阻塞状态，而进程 B则由于需要使用临界声源 R而进入阻塞状态。在 t3 时刻，进程 A处于运行状态，而进程 B 则由于等待打印机 R工作结束而处于阻塞状态。当进程 B 使用完打印机 R后，由于其优先级高于进程 A，所以将 CPU分配给进程 B 而使得进程 A转入就绪状态。因此在
44、 t4 时刻，进程 B 在运行而进程 A处于就绪状态。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 13 【正确答案】 (1)indegree【 padjvex 】 +，及其等价形式 (2)Stack【 top-】，及其等价形式 (3)indegree【 padjvex 】 -，及其等价形式 (4)ve【 w】 +pweight ve【 padjvex 】，及其等价形式 (5)ve【 w】，及其等价形式 【试题解析】 本题考查的是数据结构 中拓扑排序和求关键路径问题的算法。 在AOE 网中，入度为
45、0的顶点为源点，出度为 0的顶点为汇点。从源点到汇点的路径中，长度最长的路径称为关键路径。表示事件的顶点存在最早、最晚发生时间。若以顶点 v1表示源点、顶点 vn表示汇点，则汇点的最早发生时间和最晚发生时间是一致的，并且等于关键路径的长度。 设顶点 vj的最早发生时间用 ve(j)表示，则 ve(j)是指从源点 v1到 vj的最长路径长度 (时间 )。这个时间决定了所有从 vj发出的弧所表示的活动能够开工的最早时间。 ve(j)计算方法为 其中， T 是所有到达顶点 j的弧的集合； dut( i， j )是弧 i， j上的权值； n是网中的顶点数 (即汇点的序号 )，如下图所示。 显然，上式是
46、一个从源点开始的递推公式。ve(j)的计算必须在 vj的所有前驱顶点的最早发生时间全部求出后才能进行。这样必须对 AOE 网进行拓扑排序，然后按拓扑有序序列逐个求出各项点事件的最早发生时间。 拓扑排序是将有向无环图中所有顶点排成一个线性序列的过程，并且该序列满足：若在有向图中从顶点 vi到 vj有一条路径，则在该线性序列中，顶点 vi必然在顶点 vj之前。 题目中给出的是 AOE(Activity On Edge network)网，是一种赋权的有向无环图。 对 AOE 网进行拓扑排序的方法如下： 在 AOE 网中选择一个入度为 0(没有前驱 )的顶点且输出它。 从网中删除该顶点及其与该顶点有
47、关的所有边。 重复上述两步，直至网中不存在入度为 0的顶点为止。 在拓扑排序过程中，有可能同时存在多个入度为 0的顶点，函数中用顺序栈 Stack暂存入度为0且没有进入拓扑序列的顶点。 进行拓扑排序之前，应先求出网中每个顶点的入度并存入数组 indegree中，从而，将 “从网中删除该顶点及其与该顶点有关的所有边 ”的操作转换为 “相关顶点的入度减一 ”，一旦发现某个顶点的入度变为 0，就将其编号压入堆栈。从而将选择入度为 0的顶点转化为从 Stack 中弹出栈顶元素所代表的顶点。 题目中顶点从 1开始编号，顶点 vi的编号为 i，以下代码用于求网中各个顶点的入度。 for(j=1； j G.
48、n;j+) /*求网中各顶点的入度 */ p=G.head【 j】 .Firstadj； while(p) (1) ； p=pnextarc ； /*while*/ /*for*/ 在有向图中，若以 v2为尾的弧有 v2， v4且权值为 30、 v2， v6且权 值为 50，则其的邻接表表示形式如下图所示。 因此，扫描顶点 v2的邻接表可以将邻接于 v2的所有顶点的入度加 10 所以，空 (1)处应填入 “indegree【 pmdjvex 】 +”或其等价形式。 以下代码实现拓扑排序并求解各个顶点时事件的最早发生时间。 while(top 0) w= (2) ； printf(“%c” ， G.head【 w】 .vdata)； p=G.head【 w】 .Firstadj； while(p) (3) ； if(!indegreepadjvex) Stack【 +top】 =padjvex ； if( (4) ) ve【 padjvex 】 =ve【 w】 +pweight ； p=pnextarc ； /*while*/ /*while*/ 由于入度为 0的顶点由栈中弹出，而且根据w 在后续代码中所起的作用，可知空 (2)处应填入 “Stack【 top-】 ”。然后将邻接到顶点 w 的各个顶点 (padjvex
