计算机等级考试软件设计2009年下午试题

2009年上半年软件设计师下午试卷第1页（共15页）全国计算机技术与软件专业技术资格（水平）考试2009年上半年软件设计师下午试卷（考试时间14:00～16:30共150分钟）请按下述要求正确填写答题纸1.在答题纸的指定位置填写你所在的省、自治区、直辖市、计划单列市的名称。2.在答题纸的指定位置填写准考证号、出生年月日和姓名。3.答题纸上除填写上述内容外只能写解答。4.本试卷共7道题，试题一至试题四是必答题，试题五至试题七选答1道。每题15分，满分75分。5.解答时字迹务必清楚，字迹不清时，将不评分。6.仿照下面例题，将解答写在答题纸的对应栏内。例题2009年上半年全国计算机技术与软件专业技术资格（水平）考试日期是（1）月（2）日。因为正确的解答是“5月23日”，故在答题纸的对应栏内写上“5”和“23”（参看下表）。例题解答栏（1）5（2）232009年上半年软件设计师下午试卷第2页（共15页）试题一（共15分）阅读下列说明，回答问题1和问题2，将解答填入答题纸的对应栏内。【说明】假设某大型商业企业由商品配送中心和连锁超市组成，其中商品配送中心包括采购、财务、配送等部门。为实现高效管理，设计了商品配送中心信息管理系统，其主要功能描述如下：1.系统接收由连锁超市提出的供货请求，并将其记录到供货请求记录文件。2.在接到供货请求后，从商品库存记录文件中进行商品库存信息查询。如果库存满足供货请求，则给配送处理发送配送通知；否则，向采购部门发出缺货通知。3.配送处理接到配送通知后，查询供货请求记录文件，更新商品库存记录文件，并向配送部门发送配送单，在配送货品的同时记录配送信息至商品配送记录文件。4.采购部门接到缺货通知后，与供货商洽谈，进行商品采购处理，合格商品入库，并记录采购清单至采购清单记录文件、向配送处理发出配送通知，同时通知财务部门给供货商支付货款。该系统采用结构化方法进行开发，得到待修改的数据流图（如图1-1所示）。供货请求处理采购处理D2D3D1D4E3E2E1配送通知配送单供货请求供货请求采购清单入库信息付款通知缺货通知E4库存信息配送处理配送信息配送通知供货请求信息库存更改信息付款通知配送信息图1-1数据流图【问题1】（8分）使用【说明】中的词语，给出图1-1中外部实体E1至E4的名称和数据存储D1至D4的名称。试题一至试题四是必答题2009年上半年软件设计师下午试卷第3页（共15页）【问题2】（7分）图1-1中存在四处错误数据流，请指出各自的起点和终点；若将上述四条错误数据流删除，为保证数据流图的正确性，应补充三条数据流，请给出所补充数据流的起点和终点。（起点和终点请采用数据流图1-1中的符号或名称）错误数据流起点终点补充的数据流起点终点2009年上半年软件设计师下午试卷第4页（共15页）试题二（共15分）阅读下列说明，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某集团公司拥有多个大型连锁商场，公司需要构建一个数据库系统以方便管理其业务运作活动。【需求分析结果】1.商场需要记录的信息包括商场编号（编号唯一），商场名称，地址和联系电话。某商场信息如表2-1所示。表2-1商场信息表商场编号商场名称地址联系电话PS2101淮海商场淮海中路918号021-64158818PS2902西大街商场西大街时代盛典大厦‎029-87283220PS2903东大街商场碑林区东大街239号‎029-87450287PS2901长安商场雁塔区长安中路38号029-852649532.每个商场包含有不同的部门，部门需要记录的信息包括部门编号（集团公司分配），部门名称，位置分布和联系电话。某商场的部门信息如表2-2所示。表2-2部门信息表部门编号部门名称位置分布联系电话DT002财务部商场大楼六层82504342DT007后勤部商场地下副一层82504347DT021安保部商场地下副一层82504358DT005人事部商场大楼六层82504446DT001管理部商场裙楼三层825046683.每个部门雇用多名员工处理日常事务，每名员工只能隶属于一个部门（新进员工在培训期不隶属于任何部门）。员工需要记录的信息包括员工编号（集团公司分配），姓名，岗位，电话号码和工资。员工信息如表2-3所示。表2-3员工信息表员工编号姓名岗位电话号码工资XA3310周超理货员136092576381500.00SH1075刘飞防损员134772934871500.00XA0048江雪花广播员152345678931428.00BJ3123张正华部门主管133456984321876.004.每个部门的员工中有一名是经理，每个经理只能管理一个部门，系统需要记录每个经理的任职时间。2009年上半年软件设计师下午试卷第5页（共15页）【概念模型设计】根据需求阶段收集的信息，设计的实体联系图和关系模式（不完整）如下：图2-1实体联系图【关系模式设计】商场（商场编号，商场名称，地址，联系电话）部门（部门编号，部门名称，位置分布，联系电话，（a））员工（员工编号，员工姓名，岗位，电话号码，工资，（b））经理（（c），任职时间）【问题1】（6分）根据问题描述，补充四个联系，完善图2-1的实体联系图。联系名可用联系1、联系2、联系3和联系4代替，联系的类型分为1:1、1:n和m:n。【问题2】（6分）根据实体联系图，将关系模式中的空（a）~（c）补充完整，并分别给出部门、员工和经理关系模式的主键和外键。【问题3】（3分）为了使商场有紧急事务时能联系到轮休的员工，要求每位员工必须且只能登记一位紧急联系人的姓名和联系电话，不同的员工可以登记相同的紧急联系人。则在图2-1中还需添加的实体是（1），该实体和图2-1中的员工存在（2）联系（填写联系类型）。给出该实体的关系模式。商场部门经理员工2009年上半年软件设计师下午试卷第6页（共15页）试题三（共15分）阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某银行计划开发一个自动存提款机模拟系统（ATMSystem）。系统通过读卡器（CardReader）读取ATM卡；系统与客户（Customer）的交互由客户控制台（CustomerConsole）实现；银行操作员（Operator）可控制系统的启动（SystemStartup）和停止（SystemShutdown）；系统通过网络和银行系统（Bank）实现通信。当读卡器判断用户已将ATM卡插入后，创建会话（Session）。会话开始后，读卡器进行读卡，并要求客户输入个人验证码（PIN）。系统将卡号和个人验证码信息送到银行系统进行验证。验证通过后，客户可从菜单选择如下事务（Transaction）：1.从ATM卡账户取款（Withdraw）；2.向ATM卡账户存款（Deposit）；3.进行转账（Transfer）；4.查询（Inquire）ATM卡账户信息。一次会话可以包含多个事务，每个事务处理也会将卡号和个人验证码信息送到银行系统进行验证。若个人验证码错误，则转个人验证码错误处理（InvalidPINProcess）。每个事务完成后，客户可选择继续上述事务或退卡。选择退卡时，系统弹出ATM卡，会话结束。系统采用面向对象方法开发，使用UML进行建模。系统的顶层用例图如图3-1所示，一次会话的序列图（不考虑验证）如图3-2所示。消息名称参见表3-1。表3-1可能的消息名称列表名称说明名称说明cardInserted()ATM卡已插入performTransaction()执行事务performSession()执行会话readCard()读卡readPIN()读取个人验证码PIN个人验证码信息creat(atm,this,card,pin)为当前会话创建事务create(this)为当前ATM创建会话cardATM卡信息doAgain执行下一个事务ejectCard()弹出ATM卡【问题1】（7分）根据【说明】中的描述，给出图3-1中A1和A2所对应的参与者，U1至U3所对应的用例，以及该图中空（1）所对应的关系。（U1至U3的可选用例包括：Session、Transaction、InsertCard、InvalidPINProcess和Transfer）【问题2】（6分）根据【说明】中的描述，使用表3-1中的英文名称，给出图3-2中6～9对应的消息。【问题3】（2分）解释图3-1中用例U3和用例Withdraw、Deposit等四个用例之间的关系及其内涵。2009年上半年软件设计师下午试卷第7页（共15页）图3-1ATM系统顶层用例图图3-2一次会话的序列图（无验证消息）2009年上半年软件设计师下午试卷第8页（共15页）试题四（共15分）阅读下列说明，回答问题1和问题2，将解答填入答题纸的对应栏内。【说明】现需在某城市中选择一个社区建一个大型超市，使该城市的其它社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其它各顶点的最短路径之和最小。算法首先需要求出每个顶点到其它任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其它各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。【问题1】（12分）本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径。已知图G的顶点集合为{1,2,...,}Vn，*{}ijnnWw为权重矩阵。设()kijd为从顶点i到顶点j的一条最短路径的权重。当0k时，不存在中间顶点，因此(0)ijijdw；当0k时，该最短路径上所有的中间顶点均属于集合{1,2,...,}k。若中间顶点包括顶点k，则()(1)(1)kkkijikkjddd；若中间顶点不包括顶点k，则()(1)kkijijdd。于是得到如下递归式。()(1)(1)(1)0min(,)0ijkkkkijijikkjwkddddk因为对于任意路径，所有的中间顶点都在集合{1,2,...,}n内，因此矩阵()()*{}nnijnnDd给出了任意两个顶点之间的最短路径，即对所有,ijV，()nijd表示顶点i到顶点j的最短路径。下面是求解该问题的伪代码，请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下：W：权重矩阵n：图的顶点个数SP：最短路径权重之和数组，SP[i]表示顶点i到其它各顶点的最短路径权重之和，i从1到nmin_SP：最小的最短路径权重之和min_v：具有最小的最短路径权重之和的顶点i：循环控制变量2009年上半年软件设计师下午试卷第9页（共15页）j：循环控制变量k：循环控制变量LOCATE-SHOPPINGMALL(W,n)1D(0)=W2for（1）3fori=1ton4forj=1ton5if(1)(1)(1)kkkijikkjddd6（2）7else8（3）9fori=1ton10SP[i]=011forj=1ton12（4）13min_SP=SP[1]14（5）15fori=2ton16ifmin_SPSP[i]17min_SP=SP[i]18min_v=i19return（6）【问题2】（3分）【问题1】中伪代码的时间复杂度为（7）（用Ο符号表示）。2009年上半年软件设计师下午试卷第10页（共15页）试题五（共15分）阅读下列说明和C函数代码，将应填入（n）处的字句写在答题纸的对应栏内。【说明】对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数InOrder()借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储，结点类型定义如下：typedefstructBtNode{ElemTypedata;/*结点的数据域，ElemType的具体定义省略*/structBtN