1、计算机水平考试中级软件设计师 2009 年下半年下午真题及答案解析(总分：105.00，做题时间：150 分钟)试题一(共 15 分) 阅读以下说明和数据流图，回答问题 1 至问题 4，将解答填入答题纸的对应栏内。 【说明】 现准备为某银行开发一个信用卡管理系统 CCMS，该系统的基本功能为： 1信用卡申请。非信用卡客户填写信用卡申请表，说明所要申请的信用卡类型及申请者的基本信息，提交 CCMS。如果信用卡申请被银行接受，CCMS 将记录该客户的基本信息，并发送确认函给该客户，告知客户信用卡的有效期及信贷限额；否则该客户将会收到一封拒绝函。非信用卡客户收到确认函后成为信用卡客户。 2信用卡激活
2、。信用卡客户向 CCMS 提交激活请求，用信用卡号和密码激活该信用卡。激动操作结束后，CCMS 将激活通知发送给客户，告知客户其信用卡是否被成功激活。 3信用卡客户信息管理。信用卡客户的个人信息可以在 CCMS 中进行在线管理。每位信用卡客户可以在线查询和修改个人信息。 4交易信息查询。信用卡客户使用信用卡进行的每一笔交易都会记录在 CCMS 中。信用卡客户可以通过 CCMS 查询并核实其交易信息（包括信用卡交易记录及交易额）。 （分数：15.00）(1).【问题 1】（3 分） 根据【说明】，将图 1-1 中的 E1-E3 填充完整。（分数：3.75）_(2).【问题 2】（3 分） 图 1
3、-1 中缺少三条数据流，根据【说明】，分别指出这三条数据流的起点和终点。（注：数据流的起点和终点均采用图中的符号和描述）（分数：3.75）_(3).【问题 3】（5 分） 图 1-2 中有两条数据流是错误的，请指出这两条数据流的名称，并改正。（注：数据流的起点和终点均采用图中的符号和描述）（分数：3.75）_(4).【问题 4】（4 分） 根据【说明】，将图 1-2 中 P1-P4 的处理名称填充完整。（分数：3.75）_试题二（共 15 分） 阅读下列说明，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。 【说明】 某公司拟开发一多用户电子邮件客户端系统，部分功能的初步需求分析结果如下
4、： （1）邮件客户端系统支持多个用户，用户信息主要包括用户名和用户密码，且系统中的用户名不可重复。 （2）邮件帐号信息包括邮件地址及其相应的密码，一个用户可以拥有多个邮件地址（如 ）。 （3）一个用户可拥有一个地址簿，地址薄信息包括联系人编号、姓名、电话、单位地址、邮件地址 1、邮件地址 2、邮件地址 3 等信息。地址薄中一个联系人只能属于一个用户，且联系人编号唯一标识一个联系人。 （4）一个邮件帐号可以含有多封邮件，一封邮件可以含有多个附件。邮件主要包括邮件号、发件人地址、收件人地址、邮件状态、邮件主题、邮件内容、发送时间、接收时间。其中，邮件号在整个系统内唯一标识一封邮件，邮件状态有已接收
5、、待发送、已发送和已删除 4 种，分别表示邮件是属于收件箱、发件箱、已发送箱和废件箱。一封邮件可以发送给多个用户。附件信息主要包括附后件号、附件文件名、附件大小。一个附件只属于一封邮件，附件号仅在一封邮件内唯一。（分数：15.00）(1).【问题 1】（5 分） 根据以上说明设计的 E-R 图如图 2-1 所示，请指出地址簿与用户、电子邮件帐号与邮件、邮件与附件之间的联系类型。 （分数：5.00）_(2).【问题 2】（4 分） 该邮件客户端系统的主要关系模式如下，请填补（a）（c）的空缺部分。 用户（用户名，用户密码） 地址簿（ （a） ，联系人编号，姓名，电话，单位地址，邮件地址 1，邮件
6、地址 2，邮件地址 3） 邮件帐号（邮件地址，邮件密码，用户名） 邮件（ （b） ，收件人地址，邮件状态，邮件主题，邮件内容，发送时间，接收时间） 附件（ （c） ，附件号，附件文件名，附件大小）（分数：5.00）_(3).【问题 3】（6 分） （1）请指出【问题 2】中给出的地址簿、邮件和附件关系模式的主键，如果关系模式存在外键请指出。 （2）附件属于弱实体吗？请用 50 字以内的文字说明原因。（分数：5.00）_试题三（共 15 分） 阅读下列说明和 UML 图，回答问题 1 至问题 4，将解答填入答题纸的对应栏内。 【说明】 某企业为了方便员工用餐，为餐厅开发了一个订餐系统（COS：C
7、afeteria Ordering System）,企业员工可通过企业内联网使用该系统。 企业的任何员工都可以查看菜单和今日特价。 系统的顾客是注册到系统的员工，可以订餐（如果未登录，需先登录）、注册工资支付、预约规律的订餐，在特别情况下可以覆盖预订。 餐厅员工是特殊顾客，可以进行备餐、生成付费请求和请求送餐，其中对于注册工资支付的顾客生成付费请求并发送给工资系统。 菜单管理员是餐厅特定员工，可以管理菜单。 送餐员可以打印送餐说明，记录送餐信息（如送餐时间）以及记录收费（对于没有注册工资支付的顾客，由送餐员收取现金后记录）。 顾客订餐过程如下： 1顾客请求查看菜单； 2系统显示菜单和今日特价；
8、 3顾客选菜； 4系统显示订单和价格； 5顾客确认订单； 6系统显示可送餐时间； 7顾客指定送餐时间、地点和支付方式； 8系统确认接受订单，然后发送 Email 给顾客以确认订餐，同时发送相关订餐信息通知给餐厅员工。 系统采用面向对象方法开发，使用 UML 进行建模。系统的顶层用例图和一次订餐的活动图初稿分别如图 3-1 和图 3-2 所示。 图 3-1 COS 系统顶层用例图 （分数：15.00）(1).【问题 1】（2 分） 根据【说明】中的描述，给出图 3-1 中 A1 和 A2 所对应的参与者。（分数：3.75）_(2).【问题 2】（8 分） 根据【说明】中的描述，给出图 3-1 中
9、缺少的四个用例及其所对应的参与者。（分数：3.75）_(3).【问题 3】（4 分） 根据【说明】中的描述，给出图 3-2 中（1）（4）处对应的活动名称或图形符号。（分数：3.75）_(4).【问题 4】（1 分） 指出图 3-1 中员工和顾客之间是什么关系，并解释该关系的内涵。（分数：3.75）_试题四（共 15 分） 阅读下列说明，回答问题 1 至问题 2，将解答填入答题纸的对应栏内。 【说明】 0-1 背包问题可以描述为：有 n 个物品，对 i=1,2,n，第 i 个物品价值为 vi,重量为 wi(vi 和 wi 为非负数），背包容量为 W(W 为非负数)，选择其中一些物品装入背包，使
10、装入背包物品的总价值最大，即 ,且总重量不超过背包容量，即 （分数：15.00）(1).【问题 1】（8 分） 用回溯法求解此 0-1 背包问题，请填充下面伪代码中(1)(4)处空缺。 回溯法是一种系统的搜索方法，在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往假设已经设计了界函数，判断并剪枝那些即扩展了也不能得到最优解的结点。现在假设已经设计了 BOUND（v,w,k,W）函数，其中 v,w,k 和 W 分别表示当前已经获得的价值、当前背包的重量、已经确定
11、是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得最大的价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。 下面给出 0-1 背包问题的回溯法伪代码。 函数参数说明如下： W：背包容量；n:物品个数；w:重量数组；v:价值数组；fw:获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。 变量说明如下： cw:当前的背包重量；cp:当前获得的价值;k:当前考虑的物品编号；Y:当前已获得的部分解。 BKNAP（W,n,w,v,fw,fp,X） 1 cwcp0 2 (1)
12、 3 fp-1 4 while true 5 while kn and cw+wk W do 6 (2) 7 cpcp+vk 8 Yk 1 9 kk+1 10 if kn then 11 if fp_(2).【问题 2】（7 分） 考虑表 4-1 的实例，假设有 3 个物品，背包容量为 22。图 4-1 中是根据上述算法构造的搜索树，其中结点的编号表示了搜索树生成的顺序，边上的数字 1/0 分别表示选择/不选择对应物品，除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择特(5),
13、获得的价值为(6). 表 4-1 0-1 背包问题实例 （分数：7.50）_1. 试题五（共 15 分） 阅读下列说明和 C+代码，将应填入（n）处的字句写在答题纸的对应栏内。【说明】 现欲构造一文/目录树，采用组合(Composite)设计模式来设计，得到的类图如 5-1 所示： 图 5-1 类图 （分数：15.00）_2.试题六（共 15 分） 阅读下列说明和 JAVA 代码，将应填入（n）处的字句写在答题纸的对应栏内。 【说明】 现欲构造一文/目录树，采用组合(Composite)设计模式来设计，得到的类图如 6-1 所示： （分数：15.00）_3.试题七（共 15 分） 阅读以下说明
14、和 C 程序，将应填入 （n） 处的字句写在答题纸的对应栏内。 【说明】 现有 n（n n then 11 if fp_正确答案：(（1）k0,或其等价形式 （2）cwcw+wk , 或其等价形式 （3）kk-1, 或其等价形式 （4）kk+1, 或其等价形式)解析：本题考查的是用回溯法求解 0-1 背包问题。回溯法有两类算法框架：非递归形式和递归形式，本题采用非递归形式表示。理解回溯法的基本思想和这两类算法框架是正确解答本题的根本要求。 回溯法从第一项物品开始考虑是否应该装入背包中，因此当前考虑的物品编号 k 从 1 开始，即 k1。然后逐项往后检查，若能全部放入背包则将该项放入背包，此时背
15、包的重量应该是当前的重量加上当前考虑物品的重量，即 cwcw+wk，当然背包中物品的价值也为当前的价值加上当前考虑物品的价值。若已经考虑完了所有的物品，则得到一个解，判断该解是否为当前最优，若为最优，则将该解的信息放入变量 fp、fw 和X 中。若还没有考虑完所有的物品，意味着有些物品不能放入背包，此时先判断若不将当前的物品放入背包中，则其余物品放入背包是否可能得到比当前最优解更优的解，若得不到则回溯；否则继续考虑其余的物品。(2).【问题 2】（7 分） 考虑表 4-1 的实例，假设有 3 个物品，背包容量为 22。图 4-1 中是根据上述算法构造的搜索树，其中结点的编号表示了搜索树生成的顺
16、序，边上的数字 1/0 分别表示选择/不选择对应物品，除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择特(5),获得的价值为(6). 表 4-1 0-1 背包问题实例 （分数：7.50）_正确答案：(（5）物品 2 和物品 3 （6）35 （7）15 （8）8)解析：根据问题 1 中给出的伪代码运行该实例，可以很容易得到此 0-1 背包问题的最优解，应该选择物品2 和物品 3，此时背包的重量为 10+10=20，获得的价值为 17+18=35。 若采用穷举法搜索整个解空间，即要
17、构造一颗完全二叉树，此时搜索树的结点数应为 24-1=15，而采用了上述回溯法，搜索树的结点数仅为8 个，如上图所示。 本题考查算法设计技术回溯法。 此类题目要求考生掌握基本的算法设计技术，包括分治法、动态规划法、贪心算法、回溯法和分支限界法等，然后结合具体的问题，用对应的算法设计技术来解决问题。1. 试题五（共 15 分） 阅读下列说明和 C+代码，将应填入（n）处的字句写在答题纸的对应栏内。【说明】 现欲构造一文/目录树，采用组合(Composite)设计模式来设计，得到的类图如 5-1 所示： 图 5-1 类图 （分数：15.00）_正确答案：(（1）this-name （2）list*
18、 （3）NULL （4）this-name （5）&childList)解析：2.试题六（共 15 分） 阅读下列说明和 JAVA 代码，将应填入（n）处的字句写在答题纸的对应栏内。 【说明】 现欲构造一文/目录树，采用组合(Composite)设计模式来设计，得到的类图如 6-1 所示： （分数：15.00）_正确答案：(（1）abstract （2）null （3）List （4）childList （5）printTree(file)解析：3.试题七（共 15 分） 阅读以下说明和 C 程序，将应填入 （n） 处的字句写在答题纸的对应栏内。 【说明】 现有 n（n 1000）节火车车厢，顺序编号为 1,2,3,.,n，按编号连续依次从 A 方向的铁轨驶入，从 B 方向铁轨驶出，一旦车厢进入车站（Station）就不能再回到 A 方向的铁轨上；一旦车厢驶入B 方向铁轨就不能再回到车站，如图 7-1 所示，其中 Station 为栈结构，初始为空且最多能停放 1000 节车厢。 （分数：15.00）_正确答案：(（1）InitStack(&station) （2）!IsEmpty(station) （3）stateiTop(station)解析：
