试题4
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。
【说明】
在并发系统设计中,通过对信号量S的P、V操作实现进程的同步与互斥控制。
P(S):S:=S-1,若S≥0,则执行P操作的进程继续执行:若S<0,则置该进程为阻塞状态,并将其插入阻塞队列。
V(S):S:=S+1,若S>0,则执行V操作的进程继续执行;若S≤0,则从阻塞队列唤醒一个进程,并将其插入就绪队列,然后执行V操作的进程继续执行。
【问题1】
在某并发系统中,有一个发送进程A、一个接收进程B、一个环形缓冲区BUFFER、信号量S1和S2。发送进程不断地产生消息并写入缓冲区BUFFER,接收进程不断地从缓冲区BUFFER取消息。假设发送进程和接收进程可以并发地执行,那么,当缓冲区的容量为N时,如何使用P、V操作才能保证系统的正常工作。发送进程A和接收进程B的工作流程如图4-1所示。请在图4-1中的空(1)~(4)处填入正确的内容。
【问题2】
若系统中有多个发送进程和接收进程,进程间的工作流程如图4-2所示,其中空 (1)~(4)的内容与图4-1相同。发送进程产生消息并顺序地写入环形缓冲区BUFFER,接收者进程顺序地从BUFFER中取消息,且每条消息只能读取一次。为了保证进程间的正常通信,增加了信号量SA和SB。
①请说明信号量SA和SB的物理意义,并在图4-2中的空(5)和空(6)处填入正确的内容。
②请从图4-2的(a)~(1)中选择四个位置正确地插入P(SA)、V(SA)、P(SB)、V(SB)。
【问题3】
设系统中只有进程A和进程B,除了互斥地使用CPU和打印机R外,进程A和B不使用其他资源。另外,进程B的优先级比A高,而进程A先于B准备好。进程A和 B的执行情况如图4-3所示,其中粗实线表示进程在执行中,细实线表示打印机R在使用中(每个进程具有三种状态:运行、就绪和阻塞)。
请分别说明进程A和B在图4-3所示的t1、t2、t3、t4时刻所处的状态;若是阻塞状态,请说明阻塞原因。
试题1
阅读下列说明和数据流图,回答问题1至问题3。
说明
某图书管理系统的主要功能是图书管理和信息查询。对于初次借书的读者,系统自动生成读者号,并与读者基本信息(姓名、单位、地址等)一起写入读者文件。
系统的图书管理功能分为四个方面:购入新书、读者借书、读者还书以及图书注销。
1.购入新书时需要为该书编制入库单。入库单内容包括图书分类目录号、书名、作者、价格、数量和购书日期,将这些信息写入图书目录文件并修改文件中的库存总量(表示到目前为止,购入此种图书的数量)。
2.读者借书时需填写借书单。借书单内容包括读者号和所借图书分类目录号。系统首先检查该读者号是否有效,若无效,则拒绝借书;若有效,则进一步检查该读者已借图书是否超过最大限制数(假设每位读者能同时借阅的书不超过5本),若已达到最大限制数,则拒绝借书;否则允许借书,同时将图书分类目录号、读者号和借阅日期等信息写入借书文件中。
3.读者还书时需填写还书单。系统根据读者号和图书分类目录号,从借书文件中读出与该图书相关的借阅记录,标明还书日期,再写回到借书文件中,若图书逾期,则处以相应的罚款。
4.注销图书时,需填写注销单并修改图书目录文件中的库存总量。
系统的信息查询功能主要包括读者信息查询和图书信息查询。其中读者信息查询可得到读者的基本信息以及读者借阅图书的情况;图书信息查询可得到图书基本信息和图书的借出情况。
图书管理系统的顶层图如图1-1所示;图书管理系统的第0层DFD图如图1-2所示,其中,加工2的细化图如图1-3所示。
数据流图1.1
图1-3 加工2的细化图
【问题1】
数据流图1-2中有两条数据流是错误的,请指出这两条数据流的起点和终点。
【问题2】
数据流图1-3中缺少三条数据流,请指出这三条数据流的起点和终点。
【问题3】
根据系统功能和数据流图填充下列数据字典条目中的(1)和(2):
查询请求信息=【查询读者请求信息|查询图书请求信息】
读者情况;读者号+姓名+所在单位+{借书情况}
管理工作请求单= (1)
入库单= (2)
试题2
阅读下列说明和E-R图,回答问题1至问题3,将解答填入答题纸的对应栏内。
说明
某网上订书系统的E-R图(已消除了不必要的冗余)如图2-1所示(图中没有标出主码)。图中实体的说明如表2-1所示,相关属性说明如表2-2所示。
一个顾客可以在同一天填写多张购书单,每张购书单上可填写多种图书,每种图书可以订购多本,bid相同的图书在同一张购书单上不能出现多次。
注:为简化起见,不考虑信用卡号码泄漏所带来的安全性等问题。
【问题1】
根据E-R图中给出的词汇,按照“关系模式名(属性,属性,…)”的格式,将此 E-R图转换为4个关系模式,并指出每个关系模式中的主码和外码,其中模式名根据需要取实体名或联系名。
【问题2】
创建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,
(1) ,
(2) )
【问题3】
如下的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))
试题3
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。
【说明】
某指纹门禁系统的体系结构如图3-1所示,其主要部件有:主机(MainFrame)、锁控器(LockController)、指纹采集器(FingerReader)和电控锁(Lock)。
(1)系统中的每个电控锁都有一个惟一的编号。锁的状态有两种:“已锁住”和“未
锁住”。
(2)在主机上可以设置每把锁的安全级别以及用户的开锁权限。只有当用户的开锁权限大于或等于锁的安全级别并且锁处于“已锁住”状态时,才能将锁打开。
(3)用户的指纹信息、开锁权限以及锁的安全级别都保存在主机上的数据库中。
(4)用户开锁时,只需按一下指纹采集器。指纹采集器将发送一个中断事件给锁控器,锁控器从指纹采集器读取用户的指纹并将指纹信息发送到主机,主机根据数据库中存储的信息来判断用户是否具有开锁权限,若有且锁当前处于“已锁住”状态,则将锁打开;否则系统报警。
该系统采用面向对象方法开发,系统中的类以及类之间的关系用UML类图表示,图3-2是该系统类图的一部分;系统的动态行为采用UML序列图表示,图3-3是用户成功开锁的序列图。
【问题1】
图3-2是该系统类图的一部分,依据上述说明中给出的术语,给出类Lock的主要属性。
【问题2】
依据上述说明中给出的词语,将图3-3中的(1)~(5)处补充完整。
【问题3】
组装(composition)和聚集(aggregation)是UML中两种非常重要的关系。请说明组装和聚集分别表示什么含义?两者的区别是什么?
13、阅读下列函数说明和c代码,将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
函数int Toplogical(Linded WDipaph G.的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE-网,图中顶点从1~n依次编号,图G的存储结构采用邻接表表示,其数据类型定义如下:
typedefstruct Gnode{ /* 邻接表的表结点类型*/
iht adjvex; /* 邻接顶点编号*/
iht weight; /* 弧上的权值*/
street Gnode *nextarc; /* 指示下一个弧的结点*/
}Gnode;
typedef struct Adjlist{ /* 邻接表的头结点类型*/
char vdata; /*顶点的数据信息*/
struct Gnode *Firstadj; /* 指向邻接表的第一个表结点*/
}Adjlist;
typedef street LinkedWDigraph{ /* 图的类型*/
int n, e; /* 图中顶点个数和边数*/
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)); /* 存储网中各顶点的入度*/
Stack = (int *)malloe((G.n+1)*sizeof(int)); /* 存储入度为0的顶点的编号*/
if(!ve||!indegree || !Stack) exit(0);
for (j = 1;j <= G.n;j++) {
ve[j] = 0; indegree[j]= 0;
}/*for*/
for(j= 1;j<=G.n;j++) { /* 求网中各顶点的入度*/
p = G.head[j].Firstadj;
while (p) {
(1) ; p = p→nextarc;
}/*while*/
}/*for*/
for (j = 1; j <= G.n; j++) /*求网中入度为0的顶点并保存其编号*/
if (!indegree[j]) Stack[++top] =j;
while (top > 0) {
w= (2) ;
printf("%e ", G.head[w].vdata);
p = G.head[w].Firstadj;
while (p) {
(3) ;
if ( !indegree [p→adjvex])
Staek[++top] = p→adjvex;
if( (4) )
ve[p→adjvex] = ve[w] + p→weight;
p = p→nextarc;
}/* while */
}/* while */ return (5) ; }/*Toplogieal*/
阅读以下说明和C++代码,将应填入 (n) 处的字句写在答题纸的对应栏内。
说明
通常情况下,用户可以对应用系统进行配置,并将配置信息保存在配置文件中。应用系统在启动时首先将配置文件加载到内存中,这些内存配置信息应该有且仅有一份。下面的代码应用了单身模式(Singleton)以保证Configure类只能有一个实例。这样, Configure类的使用者无法定义该类的多个实例,否则会产生编译错误。
C++代码
#include<iostream.h>
class Configure{
(1) :
Configure(){} //构造函数
public:
static Configure*Instance();
public:
int GetConf~ureData(){return data;} //获取配置信息
int SetConfigureDate(int m_data)
{data=m_data; return data;} //设置配置信息
private:
static 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=t→GetConfigureData();
//获取配置信息后进行其他工作,此处省略
}
阅读以下说明和Java代码,将应填入 (n) 处的字句写在答题纸的对应栏内。
说明
类Queue表示队列,类中的方法如下表所示。
类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 { // 队列
Node 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.getNext();
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_Next = 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) { // 异常处理类
public EmptyQueueException0 {
System.out.println("队列已空 ! ");
}
}