问答题[问题3]（4 分） 组装（Composition）和聚集（Aggregation）是UML 中两种非常重要的关系。请说明组装和聚集分别表示什么含义？两者的区别是什么？

问答题[说明]某医院的门诊管理系统实现了为患者提供挂号、处方药品收费的功能。具体的需求及设计如下：1．医院医师具有编号、姓名、科室、职称、出诊类型和出诊费用，其中出诊类型分为专家门诊和普通门诊，与医师职称无关；各个医师可以具有不同的出诊费用，与职称和出诊类型无关。2．患者首先在门诊挂号处挂号，选择科室和医师，根据选择的医师缴纳挂号费(医师出诊费)。收银员为患者生成挂号单，如表2．1所示，其中，就诊类型为医师的出诊类型。3．患者在医师处就诊后，凭借挂号单和医师手写处方到门诊药房交费买药。收银员根据就诊号和医师处方中开列的药品信息，查询药品库(如表2-2所示)，并生成门诊处方单(如表2-3所示1。4．由于药品价格会发生变化，因此，门诊管理系统必须记录处方单上药品的单价。根据需求阶段收集的信息，设计的实体联系图和关系模式(不完整)如图2-1所示。(1)实体联系图(2)关系模式挂号单(就诊号，病患姓名，医师编号，时间，(5))收银员(编号，姓名，级别)医师(编号，姓名，科室，职称，出诊类型，出诊费用)门诊处方((6)，收银员，时间)处方明细(就诊号，(7))药品库(药品编码，药品名称，(8))

问答题试题四（15分）阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。[说明]在并发系统设计中，通过对信号量S的P、V操作实现进程的同步与互斥控制。P(S)：S:=S-1，若S≥0，则执行P操作的进程继续执行；若S0，则执行V操作的进程继续执行；若S≤0，则从阻塞队列唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续执行。

问答题[问题3](3分) 考虑实例n＝10，C＝10，各个货物的体积为{4，2，7，3，5，4，2，3，6，2}。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为____(9)____和____(10)____。考虑一般的情况，这两种求解策略能否确保得到最优解?____(11)____(能或否)

问答题【程序】下面是一段求最大值的程序，其中datalist是数据表，n是datalist的长度。intGetMax(intn，intdatalist[])intk=0；for(intj=1；j＜n；j++)if(datalist[j]＞datalist[k])k=j；returnk；【控制流图】

问答题[说明] 以下C程序实现了将字符串转化为浮点数的功能。例如字符串“1234567”转化为浮点数1234567；字符串“100.02035”转化为浮点数100.02035；字符串“-100.02035”转化为浮点数-100.02035。程序中的部分变量的含义如表9-5。 {{B}}表9-5{{/B}} 变量名 含　义 　　　intpart 　　　字符串转化为浮点数后的整数部分 　　　doublepart 　　　字符串转化为浮点数后的小数部分 　　　kdouble 　　　记录小数部分的阶次 　　　resoult 　　　字符串转化为浮点数后的结果 　　　psign 　　　字符串转化为浮点数后的符号标识 [C程序] double StrToDouble(char*s) { char hexch[]="0123456789"; int i,j,psign=1; DWORD n,k,intpart=0; double doublepart=0,kdouble,resoult; char ch; if (*s=='.' { {{U}} (1) {{/U}}; {{U}} (2) {{/U}}; } char*s1=s,*temp=NULL; temp=strrchr ( s1,'.' ); if (!temp) { k=1; intpart=0; for (i=strlen (s); i＞0;i--) { ch=s[i-1]; if (ch＞0x3f) ch n=0; for (j=0; j＜10; j++) if ( ch==hexch[j]) n=j; intpart+= (n*k); k*=10; } } else { s1=temp+1; kdouble=0.1; doublepart=0; for ({{U}}(3) {{/U}}) { ch=s1[i-1]; if (ch＞0x3f) ch n=0; for (j=0; j＜10; j++ ) if (ch==hexch[j]) n=j; doublepart+= (n*kdouble); {{U}} (4) {{/U}}; } *temp=NULL; k=1; intpart=0; for ({{U}}(5) {{/U}};) { ch=s[i-1]; if (ch＞0x3f) ch n=0; for (j=0; j＜10; j++) if (ch==hexch[j]) n=j; intpart+= (n*k); k*=10; }//end else } {{U}} (6) {{/U}}; return resoult; }

问答题【说明】一个图书馆信息管理系统的分析与建模。下面是某图书馆的有关介绍。图书馆雇有若干管理员，各自具有编码、姓名等属性。管理员可上岗，也可下岗。图书馆中备有若干图书，每本图书有书号、书名、出版社、价格等属性。图书馆不定期地购买并注册新图书供读者借阅，也可将报废的旧书注销以停止借阅。图书馆可为众多读者提供服务。每个读者在借阅之前需注册姓名、性别、地址、Email等内容。读者可在终端上查询。每个读者最多可同时借阅5本书。每本图书借期为30天；若有一本书超期，则不可再借其他图书。一本书超期一天罚款0.1元。若一本书超期3个月不归还，则发布通告。若读者的图书丢失，在罚款处理之前不能借书，每本报失的图书罚款该书价的2倍。注册新读者不受限制；在注销读者之前，该读者必须归还所有借阅的图书，或者报失并接受罚款。【用例图】【协作图】1.【问题1】在需求分析阶段，采用UML的用例图描述系统功能需求，如图1-6所示。指出图1-6中(1)(2)、(3)、(4)分别是哪个用例?

问答题[问题2] 收费部门业务活动数据库的部分关系模式设计如下，请根据说明补充完整，并给出其主键。 A．员工( (1) 、姓名、 (2) 、 (3) ) B．队别(队别标志号、队名、 (1) 、 (2) )

问答题下列给定程序中，函数fun()的功能是：对N名学生的学习成绩，按从高到低的顺序找出前m(m≤10)名学生来，并将这些学生数据存放在一个动态分配的连续存储区中，此存储区的首地址作为函数值返回。注意：部分源程序给出如下。请勿改动主函数main和其他函数中的任何内容，仅在函数fun()的横线上填入所编写的若干表达式或语句。试题程序：#include＜stdio.h＞#include＜malloc.h＞#include＜string.h＞#include＜conio.h＞#defineN10typedefstructss{charnum[10]；intorder；}STU；STU*fun(STUa[]，intm){STUb[N]，*tt；inti，j，k；{{U}}(1){{/U}}；for(i=0；i＜N；i++)b[i]=a[i]；for(k=0；k＜m；k++){for(i=j=0；i＜N；i++)if({{U}}(2){{/U}})j=i；tt[k]=b[j]；b[j].order=0；}return{{U}}(3){{/U}}；}outresult(STUa[]，FILE*pf){inti；for(i=0；i＜N；i++)fprintf(pf，"No=%sMark=%d/n"，a[i].num，a[i].order)；fprintf(pf，"/n/n")；}main(){STU[N]={{"A01"，80}，{"A02"，79}，{"A03"，66}，{"A04"，82}，{"A05"，87}，{"A06"，93}，{"A07"，78}，{"A08"，60}，{"A09"，85}，{"A10"，73}}；STU*p_order；inti，m；clrscr()；printf("***TheOrigialdata***/n")；outresult(a，stdout)；printf("/nGivethenumeberofthestudentswhohavebetterscore：")；scanf("%d"，&m)；while(m＞10){printf("/nGivethenumberofthestudetswhohavebetterscore：")；scanf("%d"，&m)；}p_order=fun(a，m)；printf("***THERESULT***/n")；printf("***Thetopstudents***/n")；for(i=0；i＜m；i++)printf("%s%d/n"，p_order[i].num，p_order[i].order)；free(p_order)；}

问答题阅读下列说明、流程图和算法，将应填入{{U}}(n){{/U}}处的字句写在答题纸的对应栏内。【说明】下面的流程图1—5用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：【流程图】【算法说明】将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数血p(intA[]，intlow，inthigh)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数voidsort(intA[]，ihtL；intH)的功能是实现数组A中元素的递增排序。【算法】voidsort(intA[]，int1，intH){if(L＜H){k=p(A,L,R)：//p()返回基准数在数组A中的下标sort({{U}}(4){{/U}})；//小于基准数的元素排序sort({{U}}(5){{/U}})；//大于基准数的元素排序}}

问答题【说明】构造最优二叉查找树。 具有n个结点的有序序列a1, a2, …, an存在于数组元素a[1]、a[2], …, a[n]之中, a[0]未被使用。结点a1, a2, …, an-1, an的查找成功的概率p1, p2, …, pn-1, pn存在于数组元素 p[1]、p[2], …, p[n—1]、p[n]之中, p[0]未用。另外, 查找失败的概率q0, q1, …, qn-1, qn存在于数组元素q[0]、p[1], …, q[n-1]、q[n]之中。算法计算的序列ai+1, ai+2,…, aj-1, aj的最优二叉查找树Tij的代价Cij存在于数组元素c[i][j]之中, Tij的根结点的序号rij存在于r[i][j]之中, 它的权值存在于w[i][j]之中。为了便于内存的动态分配, 统统使用一维数组取代二维数组。 const float MAXNUM=99999. 0; //尽可能大的浮点数 template＜{{U}} (1) {{/U}}＞ void OPtimal_Binary_Search_Tree(float p[], float q[], Type a[], int n) { float *C, *W; c={{U}} (2) {{/U}}; w={{U}} (3) {{/U}}; int *r; r=new int[(n+1)*(n+1)]; for(i=0; i＜=n; i++) { c[i*(n+1)+i]=0. 0; // 即：c[i][i]=0.0, 用一维数组表示 w[i*(n+1)+i]=q[i]; // 即：w[i][i]=q[i], 用一维数组表示 } int i, j, k, m, length; // m表示根结点的下标或序号, 范围为0～n float minimum; for(length=1; length＜=n; length++) //处理的序列长度由1到n for(i=0; i＜=n-length; i++){ //i为二叉查找树Tij的起始序号 j=i + length; //j为二叉查找树Tij的终止序号。如：处理序列a1a2a3时, //相应的二叉查找树为T03, i=0, 而j=3 w[i*(n+1)+j]={{U}} (4) {{/U}}; minimum =MAXMUM; for(k=i+1; k＜=j; k++) //考察以ai+1、ai+2, …, ai为根的情况 if({{U}} (5) {{/U}}＜minimum) { minimum=c[i*(n+1)+k-1]+c[k*(n+1)+j];m=k; } c[i*(n+1)+j]=w[i*(n+1)+j]+c[i*(n+1)+m-1]+c[m*(n+1)+j]; r[i*(n+1)+j]=m; // r[i][j]=m } } //构造好的最优二叉查找树的根结点的序号在r[0][n]中

问答题试题六(15分)阅读以下说明和Java代码，将应填入（n）处的字句写在答题纸的对应栏内。[说明]某绘图系统存在Point、Line、Square三种图元，它们具有Shape接口，图元的类图关系如图6-1所示。现要将Circle图元加入此绘图系统以实现功能扩充。已知某第三方库已经提供了XCircle类，且完全满足系统新增的Circle图元所需的功能，但XCircle不是由Shape派生而来，它提供的接口不能被系统直接使用。代码6-1既使用了XCircle又遵循了Shape规定的接口，既避免了从头开发一个新的Circle类，又可以不修改绘图系统中已经定义的接口。代码6-2根据用户指定的参数生成特定的图元实例，并对之进行显示操作。绘图系统定义的接口与XCircle提供的显示接口及其功能如下表所示：[图6-1]

问答题【说明】下面是某租车信息管理系统的介绍：该车库中备有若干车辆，每辆车有车号、车牌、车名、价格等属性。车库不定期地购买并注册新车供用户借用，也可将报废的旧车注销以停止租用。车库可为众多用户提供服务。每个用户在借车之前需注册姓名、地址等内容。每个用户最多可同时借3辆车。每辆车借期7天：若有一辆车超期，则不可再借其他车。一辆车超期一天罚款250元。若一辆车超期3周不归还，则发布通告。若用户借的车丢失，在罚款处理之前不能借车，每辆报失的车罚款该车目前市价(包括折旧)的1.2倍。注册新用户不受限制；而注销用户之前，该用户必须归还所有借的车，或者报失并接受罚款。【状态图1】【状态图2】1.【问题1】分析车辆的状态和事件，指出图2-1中的(1)、(2)、(3)、(4)分别是什么?

问答题一般的树结构常采用孩子-兄弟表示法表示，即用二叉链表作为树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如，如图(a)所示的树的孩子一兄弟表示如图(b)所示。函数LevelTraVerse()的功能是对给定树进行层序遍历。例如，当对图(a)中的树进行层序遍历时，结点的访问次序为DBAEFPC。对树进行层序遍历时使用了队列结构，实现队列基本操作的函数原型如表所示。实现队列基本操作的函数原型表函数原型说明VoidInitQueue(Queue*Q)初始化队列BoolIsEmpty(QueueQ)判断队列是否为空，若是则返回TRUE，否则返回FALSEVoidEnQueue(Queue*Q，TreeNodep)元素入队列VoidDeQueue(Queue*Q，TreeNode*p)元素出队列Bool、Status类型定义如下：typedefenum{FALSE=0,TRUE=1}Bool;typedefenum{OVERFLOW=-2,UNDERFLOW=-1,ERROR=0,OK=1}Status;树的二叉链表结点定义如下：typedefstructNode{chardata;structNode*firstchiid,*nextbrother;}Node,*TreeNode;[函数代码]StatusLevelTraverse(TreeNoderoot){/*层序遍历树，树采用孩子-兄弟表示法，root是树根结点的指针*/QueuetemQ;TreeNodeptr,brotherptr;if(!root)returnERROR;InitQueue(＆tempQ);{{U}}{{U}}{{/U}}{{/U}};brotherptr=root-＞nextbrother;while(brotherptr){EnQueue(＆tempQ,brotherptr);{{U}}{{U}}{{/U}}{{/U}};}/*end-while*/while({{U}}{{U}}{{/U}}{{/U}}){{{U}}{{U}}{{/U}}{{/U}};printf(”%c/t”,ptr-＞data);if({{U}}{{U}}{{/U}}{{/U}})continue;{{U}}{{U}}{{/U}}{{/U}};brotherptr=ptr-＞firstchild-＞nextbrother;while(brotherptr){EnQueue(＆tempQ,brotherptr);{{U}}{{U}}{{/U}}{{/U}};}/*end-while*/}/*end-while*/returnOK;}/*LevelTraverse*/

问答题【说明】 函数DeleteNode (Bitree *r, int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为： typedef struct Tnode{ int data； /*结点的键值*/ struct Tnode *Lchild, *Rchild； /*指向左、右子树的指针*/ }*Bitree： 在二叉查找树上删除一个结点时，要考虑3种情况： ①若待删除的结点p是叶子结点，则直接删除该结点； ②若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点p； ③若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，结点s必属于上述①、②情况之一。 【函数】 int DeleteNode (Bitree *r，int e) { Bitree p=*r,pp，s，c； while ({{U}} (1) {{/U}}){ /*从树根结点出发查找键值为e的结点*/ pp=p; if(e＜p-＞data) p=p-＞Lchild； else p=p-＞Rchild； } if(!P) return-1； /*查找失败*/ if(p-＞Lchild } p-＞data=s-＞data； p=s； } /*处理情况①、②*/ if {{U}}({{U}} (4) {{/U}}) {{/U}}c=p-＞Lchild； else c=p-＞Rchild； if(p==*r) *r=c； else if {{U}}({{U}} (5) {{/U}}) {{/U}}pp-＞Lchild=c； else pp-＞Rchild=c； free (p)； return 0； }

问答题【说明】 下面的程序先构造Point类，再顺序构造Ball类。由于在类Ball中不能直接存取类Point中的xCoordinate及yCoordinate属性值，Ball中的toString方法调用Point类中的toStrinS方法输出中心点的值。在MovingBsll类的toString方法中，super.toString调用父类Ball的toString方法输出类Ball中声明的属性值。 【Java代码】 //Point.java文件 public class Point{ private double xCoordinate; private double yCoordinate； public Point(){} public Point(double x,double y){ xCoordinate=x; yCoordinate=y; } public String toStrthg(){ return"("+Double.toString(xCoordinate)+"," +Double.toString(yCoordinate)+")"; } //other methods } //Ball.java文件 public class Ball{ private{{U}} (1) {{/U}};//中心点 private double radius;//半径 private String color;//颜色 public Ball(){} public Ball(double xValue, double yValue, double r){ //具有中心点及其半径的构造方法 center={{U}} (2) {{/U}};//调用类Point中的构造方法 radius=r; } public Ball(double xValue, double yValue, double r, String c){ //具有中心点、半径和颜色的构造方法 {{U}} (3) {{/U}};//调用3个参数的构造方法 color=c; } public String toString(){ return "A ball with center"+center.toString() +",radius "+Double.toString(radius)+",color"+color; } //other methods } class MovingBall{{U}} (4) {{/U}}{ private double speed; public MovingBall(){} public MoyingBall(double xValue, double yValue, double r, String c, double s){ 　{{U}} (5) {{/U}};//调用父类Ball中具有4个参数的构造方法 speed=s; } public String toString(){ return super.toString()+",speed"+Double.toString(speed); } //other methods } public class test{ public static void main(String args[]){ MovingBall mb=new MovingBall(10,20,40,"green",25); System.out.println(mb); } }

问答题【说明】 以下C++程序的功能是计算三角形、矩形和正方形的面积并输出。程序由4个类组成：类 Triangle、Rectangle和Square分别表示三角形、矩形和正方形：抽象类Figure提供了一个纯虚函数getAxea()，作为计算上述3种图形面积的通用接口。 【C++代码】 #include＜iostream＞ #include＜cmath＞ using namespace std; class Figure public: virtual double getArea()=0;//纯虚函数 ; class Rectangle ： (1) protected: double height; double width; public: Rectangle() Rectangle(double height, double width) this-＞height=height; this-＞width=width; double getArea() return (2) ; ;class Square： (3) public: Square(double width) 　 (4) ; ; class Triangle： (5) private: double la,lb,lc;public: Triangle(double la,double lb,double lc) this-＞la=la;this-＞1b=1b;this-＞lc=lc; double getArea() double s=(la+lb+lc)/2.0; return sqrt(s*(s-la)*(s-lb)*(s-lc)); int main() Figure *figures[3]=new Triangle(2,3,3),new Rectangle(5,8), new Square(5); for(int i=0;i＜3;i++) cout＜＜"figures["＜＜i＜＜"]area="＜＜(figures[i])-＞getArea()＜＜endl; return 0;

问答题 阅读以下说明和流程图，回答问题1和问题2。 【说明】 某供销系统接受顾客的订货单，当库存中某配件的数量小于订购量或库存量低于一定数量时，向供应商发出采购单；当某配件的库存量大于或等于定购粮食，或者收到供应商的送货单并更新了库存后，向顾客发出提货单。该系统还可随时向总经理提供销售和库存情况表。该供销系统的分层数据流图中部分数据流和文件的组成如下： 文件 配件库存＝配件号+配件名+规格+数量+允许的最低库存量 数据流 订货单＝配件号+配件名+规格+数量+顾客名+地址 提货单＝订货单+金额 采购单＝配件号+配件名+规格+数量+供应商名+地址 送货单＝配件号+配件名+规格+数量+金额 假定顶层图(如图6所示)是正确的，“供应商”文件已由其他系统生成。

问答题[说明]一般的树结构常采用孩子—兄弟表示法表示，即用二叉链表做树的存储结构，链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。例如，如图1-15(a)所示树的孩子—兄弟表示如图1-15(b)所示。函数LevelTraverse()的功能是对给定树进行层序遍历。例如，对如图1-15所示的树进行层序遍历时，节点的访问次序为DBAEFPC。对树进行层序遍历时使用了队列结构，实现队列基本操作的函数原型如表1-11所示。Bool、Status类型定义如下：树的二叉链表节点定义如下：{{B}}表1-11实现队列基本操作的函数原型表{{/B}}{{B}}函数原型{{/B}}{{B}}说明{{/B}}voidInitQueue(Queue*Q)初始化队列BoolIsEmpty(QueueQ)判断队列是否为空，若是则返回true，否则返回falsevoidEnQueue(Queue*Q,TreeNodep)元素入队列voidDeQueue(Queue*Q,TreeNode*p)元素出队列[C函数程序]

问答题某大型商场内安装了多个简易的纸巾售卖机，自动出售2元钱一包的纸巾，且每次仅售出一包纸巾。纸巾售卖机的状态图如图1所示。图1纸巾售卖机状态图采用状态(State)模式来实现该纸巾售卖机，得到如图2所示的类图。其中类State为抽象类，定义了投币、退币、出纸巾等方法接口。类SoldState、SoldOutState、NoQuarterState和HasQuarterState分别对应图1中纸巾售卖机的4种状态：售出纸巾、纸巾售完、没有投币、有2元钱。图2用类图[C++代码]#include＜iostream＞usingnamespacestd;//以下为类的定义部分classTissueMachine;//类的提前引用classSrate{public:virtualvoidinsertQuarter()=0;//投币virtualvoidejectQuarter()=0;//退币virtualvoidturnCrank()=0;//按“出纸巾”按钮virtualvoiddispense()=0;//出纸巾}；/*类SoldOutState、NoQuarterState、HasQuarterState、SoldState的定义省略，每个类中均定义了私有数据成员TissueMachine*tissueMachine;*/ClassTissueMachine{private:{{U}}{{U}}{{/U}}{{/U}}*soldOutState,*noQuarterState,*hasQuarterState,*soldState,*State;intcount;//纸巾数public:TissueMachine(intnumbers);voidSetState(State*state);State*getHasQuarterState();State*getNoQuarterState();State*getSoldState();State*getSoldoutState();intgetCount();//其余代码省略};//以下为类的实现部分voidNoQuarterState::insertQuarter(){tissueMachine-＞setState({{U}}{{U}}{{/U}}{{/U}});}voidHasQuarterstate::ejectQuarter(){tissueMachine-＞setState({{U}}{{U}}{{/U}}{{/U}});}voidSoldState::dispense(){if(tissueMachine-＞getCount()＞0){tissueMachine-＞setState({{U}}{{U}}{{/U}}{{/U}});}else{tissueMachine-＞setState({{U}}{{U}}{{/U}}{{/U}});}}//其余代码省略