2007年下半年软件设计师下午试卷

考试总分：7分

考试类型：模拟试题

作答时间：60分钟

已答人数：967

试卷答案：有

试卷介绍： 2007年下半年软件设计师下午试卷

开始答题

试卷预览

1. 试题一（共15分）阅读以下说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】某高校欲开发一个成绩管理系统，记录并管理所有选修课程的学生的平时成绩和考试成绩，其主要功能描述如下：1.每门课程都有3到6个单元构成，每个单元结束后会进行一次测试，其成绩作为这门课程的平时成绩。课程结束后进行期末考试，其成绩作为这门课程的考试成绩。2.学生的平时成绩和考试成绩均由每门课程的主讲教师上传给成绩管理系统。3.在记录学生成绩之前，系统需要验证这些成绩是否有效。首先，根据学生信息文件来确认该学生是否选修这门课程，若没有，那么这些成绩是无效的；如果他的确选修了这门课程，再根据课程信息文件和课程单元信息文件来验证平时成绩是否与这门课程所包含的单元相对应，如果是，那么这些成绩是有效的，否则无效。4.对于有效成绩，系统将其保存在课程成绩文件中。对于无效成绩，系统会单独将其保存在无效成绩文件中，并将详细情况提交给教务处。在教务处没有给出具体处理意见之前，系统不会处理这些成绩。5.若一门课程的所有有效的平时成绩和考试成绩都已经被系统记录，系统会发送课程完成通知给教务处，告知该门课程的成绩已经齐全。教务处根据需要，请求系统生成相应的成绩列表，用来提交考试委员会审查。6.在生成成绩列表之前，系统会生成一份成绩报告给主讲教师，以便核对是否存在错误。主讲教师须将核对之后的成绩报告返还系统。7.根据主讲教师核对后的成绩报告，系统生成相应的成绩列表，递交考试委员会进行审查。考试委员会在审查之后，上交一份成绩审查结果给系统。对于所有通过审查的成绩，系统将会生成最终的成绩单，并通知每个选课学生。现采用结构化方法对这个系统进行分析与设计，得到如图1-1所示的顶层数据流图和图1-2所示的0层数据流图。图1-1顶层数据流图图1-20层数据流图【问题1】（4分）使用说明中的词语，给出图1-1中的外部实体E1~E4的名称。【问题2】（3分）使用说明中的词语，给出图1-2中的数据存储D1~D5的名称。【问题3】（6分）数据流图1-2缺少了三条数据流，根据说明及数据流图1-1提供的信息，分别指出这三条数据流的起点和终点。起点终点【问题4】（2分）数据流图是在系统分析与总体设计阶段宏观地描述系统功能需求的重要图形化工具，程序流程图也是软件开发过程中比较常用的图形化工具。简要说明程序流程图的适用场合与作用。[15分]

2. 试题三（共15分）阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】已知某唱片播放器不仅可以播放唱片，而且可以连接电脑并把电脑中的歌曲刻录到唱片上（同步歌曲）。连接电脑的过程中还可自动完成充电。关于唱片，还有以下描述信息：1．每首歌曲的描述信息包括：歌曲的名字、谱写这首歌曲的艺术家以及演奏这首歌曲的艺术家。只有两首歌曲的这三部分信息完全相同时，才认为它们是同一首歌曲。艺术家可能是一名歌手或一支由2名或2名以上的歌手所组成的乐队。一名歌手可以不属于任何乐队，也可以属于一个或多个乐队。2．每张唱片由多条音轨构成；一条音轨中只包含一首歌曲或为空，一首歌曲可分布在多条音轨上；同一首歌曲在一张唱片中最多只能出现一次。3.每条音轨都有一个开始位置和持续时间。一张唱片上音轨的次序是非常重要的，因此对于任意一条音轨，播放器需要准确地知道，它的下一条音轨和上一条音轨是什么（如果存在的话）。根据上述描述，采用面向对象方法对其进行分析与设计，得到了如表3-1所示的类列表、如图3-1所示的初始类图以及如图3-2所示的描述播放器行为的UML状态图。图3-2播放器行为UML状态图【问题1】（3分）根据说明中的描述，使用表3-1给出的类的名称，给出图3-1中的A~F所对应的类。【问题2】（6分）根据说明中的描述，给出图3-1中（1）~（6）处的多重度。【问题3】（4分）图3-1中缺少了一条关联，请指出这条关联两端所对应的类以及每一端的多重度。类多重度【问题4】（2分）根据图3-2所示的播放器行为UML状态图，给出从“关闭”状态到“播放”状态所经过的最短事件序列（假设电池一开始就是有电的）。[15分]

3. 试题五（共15分）阅读以下说明和C代码，将应填入（n）处的字句写在答题纸的对应栏内。【说明】在一个简化的绘图程序中，支持的图形种类有点(point)和圆(circle)，在设计过程中采用面向对象思想，认为所有的点和圆都是一种图形(shape)，并定义了类型shape_t、point_t和circle_t分别表示基本图形、点和圆，并且点和圆具有基本图形的所有特征。[C代码]typedefenum{point,circle}shape_type;/*程序中的两种图形：点和圆*/typedefstruct{/*基本的图形类型*/shape_typetype;/*图形种类标识：点或者圆*/void(*destroy)();/*销毁图形操作的函数指针*/void(*draw)();/*绘制图形操作的函数指针*/}shape_t;typedefstruct{shape_tcommon;intx;inty;}point_t;/*定义点类型，x、y为点坐标*/voiddestroyPoint(point_t*this){free(this);printf("Pointdestoryed!\n");}/*销毁点对象*/voiddrawPoint(point_t*this){printf("P(%d,%d)",this->x,this->y);}/*绘制点对象*/shape_t*createPoint(va_list*ap){/*创建点对象，并设置其属性*/point_t*p_point;if((p_point=(point_t*)malloc(sizeof(point_t)))==NULL)returnNULL;p_point->common.type=point;p_point->common.destroy=destroyPoint;p_point->common.draw=drawPoint;p_point->x=va_arg(*ap,int);/*设置点的横坐标*/p_point->y=va_arg(*ap,int);/*设置点的纵坐标*/return(shape_t*)p_point;/*返回点对象指针*/}typedefstruct{/*定义圆类型*/shape_tcommon;point_t*center;/*圆心点*/intradius;/*圆半径*/}circle_t;voiddestroyCircle(circle_t*this){free(（1）);free(this);printf("Circledestoryed!\n");}voiddrawCircle(circle_t*this){printf("C(");（2）.draw(this->center);/*绘制圆心*/printf(",%d)",this->radius);}shape_t*createCircle(va_list*ap){/*创建一个圆，并设置其属性*/circle_t*p_circle;if((p_circle=(circle_t*)malloc(sizeof(circle_t)))==NULL)returnNULL;p_circle->common.type=circle;p_circle->common.destroy=destroyCircle;p_circle->common.draw=drawCircle;（3）=createPoint(ap);/*设置圆心*/p_circle->radius=va_arg(*ap,int);/*设置圆半径*/returnp_circle;}shape_t*createShape(shape_typest,...){/*创建某一种具体的图形*/va_listap;/*可变参数列表*/shape_t*p_shape=NULL;（4）(ap,st);if(st==point)p_shape=createPoint(&ap);/*创建点对象*/if(st==circle)p_shape=createCircle(&ap);/*创建圆对象*/va_end(ap);returnp_shape;}intmain(){inti;/*循环控制变量，用于循环计数*/shape_t*shapes[2];/*图形指针数组，存储图形的地址*/shapes[0]=createShape(point,2,3);/*横坐标为2，纵坐标为3*/shapes[1]=createShape(circle,20,40,10);/*圆心坐标(20,40)，半径为10*/for(i=0;idraw(shapes[i]);printf("\n");}/*绘制数组中图形*/for(i=1;i>=0;i--)shapes[i]->destroy(shapes[i]);/*销毁数组中图形*/return0;}[运行结果]P(2,3)（5）Circledestoryed!Pointdestoryed![15分]

4. 试题六（共15分）阅读下列说明和C++代码，将应填入（n）处的字句写在答题纸的对应栏内。【说明】已知某企业的采购审批是分级进行的，即根据采购金额的不同由不同层次的主管人员来审批，主任可以审批5万元以下（不包括5万元）的采购单，副董事长可以审批5万元至10万元（不包括10万元）的采购单，董事长可以审批10万元至50万元（不包括50万元）的采购单，50万元及以上的采购单就需要开会讨论决定。采用责任链设计模式（ChainofResponsibility）对上述过程进行设计后得到的类图如图6-1所示。图6-1设计类图[C++代码]#include#includeusingnamespacestd;classPurchaseRequest{public:doubleAmount;//一个采购的金额intNumber;//采购单编号stringPurpose;//采购目的};classApprover{//审批者类public:Approver(){successor=NULL;}virtualvoidProcessRequest(PurchaseRequestaRequest){if(successor!=NULL){successor->（1）;}}voidSetSuccessor(Approver*aSuccesssor){successor=aSuccesssor;}private:（2）successor;};classCongress:publicApprover{public:voidProcessRequest(PurchaseRequestaRequest){if(aRequest.Amount>=500000){/*决定是否审批的代码省略*/}else（3）ProcessRequest(aRequest);}};classDirector:publicApprover{public:voidProcessRequest(PurchaseRequestaRequest){/*此处代码省略*/}};classPresident:publicApprover{public:voidProcessRequest(PurchaseRequestaRequest){/*此处代码省略*/}};classVicePresident:publicApprover{public:voidProcessRequest(PurchaseRequestaRequest){/*此处代码省略*/}};voidmain(){CongressMeeting;VicePresidentSam;DirectorLarry;PresidentTammy;//构造责任链Meeting.SetSuccessor(NULL);Sam.SetSuccessor(（4）);Tammy.SetSuccessor(（5）);Larry.SetSuccessor(（6）);PurchaseRequestaRequest;//构造一采购审批请求cin>>aRequest.Amount;//输入采购请求的金额（7）.ProcessRequest(aRequest);//开始审批return;}[15分]

5. 试题七（共15分）阅读下列说明和Java代码，将应填入（n）处的字句写在答题纸的对应栏内。【说明】已知某企业的采购审批是分级进行的，即根据采购金额的不同由不同层次的主管人员来审批，主任可以审批5万元以下（不包括5万元）的采购单，副董事长可以审批5万元至10万元（不包括10万元）的采购单，董事长可以审批10万元至50万元（不包括50万元）的采购单，50万元及以上的采购单就需要开会讨论决定。采用责任链设计模式（ChainofResponsibility）对上述过程进行设计后得到的类图如图7-1所示。图7-1设计类图[Java代码]classPurchaseRequest{publicdoubleAmount;//一个采购的金额publicintNumber;//采购单编号publicStringPurpose;//采购目的};classApprover{//审批者类publicApprover(){successor=null;}publicvoidProcessRequest(PurchaseRequestaRequest){if(successor!=null){successor.（1）;}}publicvoidSetSuccessor(ApproveraSuccesssor){successor=aSuccesssor;}private（2）successor;};classCongressextendsApprover{publicvoidProcessRequest(PurchaseRequestaRequest){if(aRequest.Amount>=500000){/*决定是否审批的代码省略*/}else（3）.ProcessRequest(aRequest);}};classDirectorextendsApprover{publicvoidProcessRequest(PurchaseRequestaRequest){/*此处代码省略*/}};classPresidentextendsApprover{publicvoidProcessRequest(PurchaseRequestaRequest){/*此处代码省略*/}};classVicePresidentextendsApprover{publicvoidProcessRequest(PurchaseRequestaRequest){/*此处代码省略*/}};publicclassrs{publicstaticvoidmain(String[]args)throwsIOException{CongressMeeting=newCongress();VicePresidentSam=newVicePresident();DirectorLarry=newDirector();PresidentTammy=newPresident();//构造责任链Meeting.SetSuccessor(null);Sam.SetSuccessor(（4）);Tammy.SetSuccessor(（5）);Larry.SetSuccessor(（6）);//构造一采购审批请求PurchaseRequestaRequest=newPurchaseRequest();BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));aRequest.Amount=Double.parseDouble(br.readLine());（7）.ProcessRequest(aRequest);//开始审批return;}}[15分]

6. 试题二（15分）阅读下列说明，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】某汽车维修站拟开发一套小型汽车维修管理系统，对车辆的维修情况进行管理。1．对于新客户及车辆，汽车维修管理系统首先登记客户信息，包括：客户编号、客户名称、客户性质（个人、单位）、折扣率、联系人、联系电话等信息；还要记录客户的车辆信息，包括：车牌号、车型、颜色等信息。一个客户至少有一台车。客户及车辆信息如表2-1所示。表2-1客户及车辆信息客户编号GS0051客户名称××公司客户性质单位折扣率95%联系人杨浩东联系电话82638779车牌号颜色车型车辆类别**0765白色帕萨特微型车2．记录维修车辆的故障信息。包括：维修类型（普通、加急）、作业分类（大、中、小修）、结算方式（自付、三包、索赔）等信息。维修厂的员工分为：维修员和业务员。车辆维修首先委托给业务员。业务员对车辆进行检查和故障分析后，与客户磋商，确定故障现象，生成维修委托书。如表2-2所示。表2-2维修委托书No.20070702003登记日期：2007-07-02车牌号**0765客户编号GS0051维修类型普通作业分类中修结算方式自付进厂时间2007070211:09业务员张小江业务员编号012预计完工时间故障描述车头损坏，水箱漏水3．维修车间根据维修委托书和车辆的故障现象，在已有的维修项目中选择并确定一个或多个具体维修项目，安排相关的维修工及工时，生成维修派工单。维修派工单如表2-3所示。表2-3维修派工单No.20070702003维修项目编号维修项目工时维修员编号维修员工种012维修车头5.00012机修012维修车头2.00023漆工015水箱焊接补漏1.00006焊工017更换车灯1.00012机修4．客户车辆在车间修理完毕后，根据维修项目单价和维修派工单中的工时计算车辆此次维修的总费用，记录在委托书中。根据需求阶段收集的信息，设计的实体联系图（图2-1）和关系模式（不完整）如下所示。图2-1中业务员和维修工是员工的子实体。【概念结构设计】图2-1实体联系图【逻辑结构设计】客户((5)，折扣率，联系人，联系电话)车辆(车牌号，客户编号，车型，颜色，车辆类别)委托书((6)，维修类型，作业分类，结算方式，进厂时间，预计完工时间，登记日期，故障描述，总费用)维修项目(维修项目编号，维修项目，单价)派工单((7)，工时)员工((8)，工种，员工类型，级别)【问题1】（4分）根据问题描述，填写图2-1中(1)～(4)处联系的类型。联系类型分为一对一、一对多和多对多三种，分别使用1:1，1:n或1:*，m:n或*:*表示。【问题2】（4分）补充图2-1中的联系并指明其联系类型。联系名可为：联系1，联系2，…。【问题3】（4分）根据图2-1和说明，将逻辑结构设计阶段生成的关系模式中的空(5)～(8)补充完整。【问题4】（3分）根据问题描述，写出客户、委托书和派工单这三个关系的主键。[15分]

A(1)～(4)处联系的类型。联系类型分为一对一、一对多和多对多三种，分别使用1:1，1:n或1:*，m:n或*:*表示。【问题2】（4分）补充图2-1中的联系并指明其联系类型。联系名可为：联系1，联系2，…。【问题3】（4分）根据图2-1和说明，将逻辑结构设计阶段生成的关系模式中的空(5)～(8)补充完整。【问题4】（3分）根据问题描述，写出客户、委托书和派工单这三个关系的主键。[15分]

7. 试题四(共15分)阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某机器上需要处理n个作业job1,job2,…,jobn，其中：(1)每个作业jobi(1≤i≤n)的编号为i，jobi有一个收益值p[i]和最后期限值d[i]；(2)机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；(3)job1～jobn的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；(4)如果作业jobi在其期限之内完成，则获得收益p[i]；如果在其期限之后完成，则没有收益。为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图4-1是基于贪心策略求解该问题的流程图。(1)整型数组J[]有n个存储单元，变量k表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤…≤d[J[k]]。(2)为了方便于在数组J中加入作业，增加一个虚拟作业job0，并令d[0]=0，J[0]=0。(3)算法大致思想：先将作业job1的编号1放入J[1]，然后，依次对每个作业jobi(2≤i≤n)进行判定，看其能否插入到数组J中，若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列，否则不插入。jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。(4)流程图中的主要变量说明如下：i：循环控制变量，表示作业的编号；k：表示在期限内完成的作业数；r：若jobi能插入数组J，则其在数组J中的位置为r+1；q：循环控制变量，用于移动数组J中的元素。图4-1贪心策略流程图【问题1】（9分）请填充图4-1中的空缺(1)、(2)和(3)处。【问题2】(4分)假设有6个作业job1,job2,…,job6；完成作业的收益数组p=(p[1],p[2],p[3],p[4],p[5],p[6])=(90,80,50,30,20,10)；每个作业的处理期限数组d=(d[1],d[2],d[3],d[4],d[5],d[6])=(1,2,1,3,4,3)。请应用试题中描述的贪心策略算法，给出在期限之内处理的作业编号序列(4)（按作业处理的顺序给出），得到的总收益为(5)。【问题3】(2分)对于本题的作业处理问题，用图4-1的贪心算法策略，能否求得最高收益？(6)。用贪心算法求解任意给定问题时，是否一定能得到最优解？(7)。[15分]

A(1)每个作业jobi(1≤i≤n)的编号为i，jobi有一个收益值p[i]和最后期限值d[i]；

B(2)机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；

C(3)job1～jobn的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；

D(4)如果作业jobi在其期限之内完成，则获得收益p[i]；如果在其期限之后完成，则没有收益。为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图4-1是基于贪心策略求解该问题的流程图。(1)整型数组J[]有n个存储单元，变量k表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤…≤d[J[k]]。(2)为了方便于在数组J中加入作业，增加一个虚拟作业job0，并令d[0]=0，J[0]=0。(3)算法大致思想：先将作业job1的编号1放入J[1]，然后，依次对每个作业jobi(2≤i≤n)进行判定，看其能否插入到数组J中，若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列，否则不插入。jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。(4)流程图中的主要变量说明如下：i：循环控制变量，表示作业的编号；k：表示在期限内完成的作业数；r：若jobi能插入数组J，则其在数组J中的位置为r+1；q：循环控制变量，用于移动数组J中的元素。图4-1贪心策略流程图【问题1】（9分）请填充图4-1中的空缺(1)、(2)和(3)处。【问题2】(4分)假设有6个作业job1,job2,…,job6；完成作业的收益数组p=(p[1],p[2],p[3],p[4],p[5],p[6])=(90,80,50,30,20,10)；每个作业的处理期限数组d=(d[1],d[2],d[3],d[4],d[5],d[6])=(1,2,1,3,4,3)。请应用试题中描述的贪心策略算法，给出在期限之内处理的作业编号序列(4)（按作业处理的顺序给出），得到的总收益为

E(5)。【问题3】(2分)对于本题的作业处理问题，用图4-1的贪心算法策略，能否求得最高收益？

F(6)。用贪心算法求解任意给定问题时，是否一定能得到最优解？

G(7)。[15分]

2007年下半年 软件设计师 下午试卷

试卷预览

2007年下半年软件设计师下午试卷