1、2009年下半年软件水平考试(中级)软件设计师下午(应用技术)试题真题试卷及答案与解析 一、必答题(共 4道大题,每道大题 15分) 1 阅读以下说明和数据流图,回答问题 1至问题 4,将解答填入答题纸的对应栏内。 【说明】 现准备为某银行开发一个信用卡管理系统 CCMS,该系统的基本功能为: 1信用卡申请。非信用卡客户填写信用卡申请表,说明所要申请的信用卡类型及申请者的基本信息,提交 ccMs。如果信用卡申请被银行接受, CCMS将记录该客户的基本信息,并发送确认函给该客户,告知客户信用卡的有效期及信贷限额;否则该客户将会收到一封拒绝函。非信用卡客户收到确认函后成为信用卡客户。 2信用卡激活
2、。信用卡客户向 (3CMS提交激活请求,用信用卡号和密码激活该信用卡。激活操作结束后, CCMS将激活通知发送给客户,告知客户其信用卡是否被成功激活。 3信用卡客户信息管理。信用卡客户的个人信息可以在 (3CMS中进行在线管理。每位信用卡客户可以在线查询和修改个人信息。 4交易信息查询。信用卡客户使用信用卡进行的每一笔交易都会记录在 CCMS中。信用卡客户可以通过 CCMS查询并核实其交易信息 (包括信用卡交易记录及交易额 )。图 61和图 62分别给出了该系统的顶层数据流图和 O层数据流图的初稿。 1 根据【说明】,将图 61中的 E1一 E3填充完整。 2 图 61中缺少三条数据流,根据【
3、说明】,分别指出这三条数据流的起点和终点。 (注:数据流的起点和终点均采用图中的符号和描述 ) 3 图 62中有两条数据流是错误的,请指出这两条数据流的名称,并改正。(注:数据流的起点和终点均采用图中的符号和描述 ) 4 根据【说明】,将图 62中 Pl P4的处理名称填充完整。5 阅读下列说明,回答问题 1至问题 3,将解答填入 答题纸的对应栏内。 【说明】 某公司拟开发一多用户电子邮件客户端系统,部分功能的初步需求分析结果如下: (1)邮件客户端系统支持多个用户,用户信息主要包括用户名和用户密码,且系统中的用户名不可重复。 (2)邮件账号信息包括邮件地址及其相应的密码,一个用户可以拥有多个
4、邮件地址 (如 userl123 com)。 (3)一个用户可拥有一个地址薄,地址簿信息包括联系人编号、姓名、电话、单位地址、邮件地址 1、邮件地址2、邮件地址 3等信息。地址薄中一个联系人只能属于一个用户,且联系人编号唯一标识一个联系人。 (4)一个邮 件账号可以含有多封邮件,一封邮件可以含有多个附件。邮件主要包括邮件号、发件人地址、收件人地址、邮件状态、邮件主题、邮件内容、发送时间、接收时间。其中,邮件号在整个系统内唯一标识一封邮件,邮件状态有已接收、待发送、已发送和已删除 4种,分别表示邮件是属于收件箱、发件箱、已发送箱和废件箱。一封邮件可以发送给多个用户。附件信息主要包括附件号、附件文
5、件名、附件大小。一个附件只属于一封邮件,附件号仅在一封邮件内唯一。 5 根据以上说明设计的 ER图如图 63所示,请指出地址簿与用户、电子邮件账号与邮件、邮件与附 件之间的联系类型。 6 该邮件客户端系统的主要关系模式如下,请填补 (a) (c)的空缺部分。用户 (用户名,用户密码 ) 地址簿( (a) ,联系人编号,姓名,电话,单位地址,邮件地址 1,邮件地址 2,邮件地址3)邮件账号 (邮件地址,邮件密码,用户名 )邮件 ( (b) ,收件人地址,邮件状态,邮件主题,邮件内容,发送时间,接收时间 )附件 ( (c) ,附件号,附件文件名,附件大小 ) 7 (1)请指出 问题 2中给出的地址
6、簿、邮件和附件关系模式的主键,如果关系模式存在外键请指出。 (2)附件属于弱实体吗 ?请用 50字以内的文字说明原因。 8 阅读下列说明和 uML图,回答问题 l至问题 4,将解答填入答题纸的对应栏内。【说明】某企业为了方便员工用餐,为餐厅开发了一个订餐系统 (COS: Cafeteria Ordering system),企业员工可通过企业内联网使用该系统。企业的任何员工都可以查看菜单和今日特价。系统的顾客是注册到系统的员工,可以订餐 (如果未登录,需先登录 )、注册工资支付、预约规律的订餐,在特殊情况下可以覆盖预订。餐厅员工是特殊顾客,可以进行备餐、生成付费请求和请求送餐,其中对于注册工资
7、支付的顾客生成付费请 求并发送给工资系统。菜单管理员是餐厅特定员工,可以管理菜单。送餐员可以打印送餐说明,记录送餐信息 (如送餐时间 )以及记录收费 (对于没有注册工资支付的顾客,由送餐员收取现金后记录 )。顾客订餐过程如下: 1顾客请求查看菜单; 2系统显示菜单和今日特价; 3顾客选菜; 4系统显示订单和价格; 5顾客确认订单; 6系统显示可送餐时间; 7顾客指定送餐时间、地点和支付方式; 8-系统确认接受订单,然后发送 Email给顾客以确认订餐,同时发送相关订餐信息通知给餐厅员工。系统采用面向对象方法开发,使用 UML进行建模。系统 的顶层用例图和一次订餐的活动图初稿分别如图 64和图
8、55所示。8 根据【说明】中的描述,给出图 64中 A1和 A2所对应的参与者。 9 根据【说明】中的描述,给出图 64中缺少的四个用例及其所对应的参与者。 10 根据【说明】中的描述,给出图 65中 (1)一 (4)处对应的活动名称或图形符号。 11 指出图 64中员工和顾客之间是什么关系,并解释该关系的内涵。 12 阅读下列说明,回答问题 1至问题 2,将解答填入答题纸的对应栏内。 【说明】 01背包问题可以描述为:有 n个物品,对 i=l, 2, , n,第 i个物品价值为 vi,重量为 wi(vi和 wi为非负数 ),背包容量为 w(W为非负数 ),选择其中一些物品装入背包,使装入背包
9、物品的总价值最大,即 ,且总重量不超过背包容量,即 ,其中, xi O, 1, xi=0表示第 i个物品不放入背包, xi=1表示第 i个物品放入背包。 12 用回溯法求解此 01背包问题,请填充下面伪代码中 (1) (4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点 ,若扩展该结点已经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了 BOuND(v, w, k, W)函数,其中 v、 w、
10、k和 w分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。下面给出 01背包 问题的回溯算法伪代码。 函数参数说明如下: w:背包容量; n:物品个数; w:重量数组; v:价值数组;fw:获得最大价值时背包的重量; fp:背包获得的最大价值; X:问题的最优解。 变量说明如下: cw:当前的背包重量; cp:当前获得的价值; k:当前考虑的物品编号; Y:当前已获得的部分解。
11、 BKNAP(W, n, w, v, fw, fp, X) 1 cwcp0 2 (1) 3 fpl 4 while true 5 while kn and cw+wkw d。 6 (2) 7 cpc p+vk 8 Ykl 9 kk+1 10 if kn then 11 if fpaddChild(compositeFolder); rootFolder-addChild (windowsFolder);compositeFolder-addChiid(file); ) 15 阅读下列说明和 Java代码,将应填入 (n) 处的字句写在答题纸的对应栏内。【说明】现欲构造一文件目录树,采用组合 (
12、Composite)设计模式来设计,得到的类图如 68所示: 【 Java代码】 import JavA util ArrayList; import JavA util List; (1)class AbstractFileprotected String name; public void printName()System out println(name); public abstract boolean addChild(AbstractFile file); public abstract boolean removeChild(AbstractFile file); public
13、 abstract ListgetChildren ; class File extends AbstractFilepublic File(String name)(this name=name; public boolean addChild(AbstractFile file)return false; public boolean removeChild(AbstractFile file)return false; public ListgetChildren()return (2) ; )clasS Folder extends AbstractFileprivate Listch
14、ildList; public Folder(String name)thiS name=name; this childList=new ArrayList; public boolean addChild(AbstractFile file)return childList add(file); public boolean removeChild(AbstractFile file)return childList remove(file); public (3)getChildren()return (4) ; )public class Clientpublic static voi
15、d main(Stringargs)构造一个树形的文件目录结构AbstractFile rootFolder=new Folder(“C: ”); AbstractFile compositeFolder=new Folder(”composite”); AbstractFile windowsFolder=new Folder(”windows”);AbstractFile file=new File(”TestComposite java”); rootFOlder addChild (compositeFolder); rootFolder addChiid(windowsFolder)
16、;compositeFolder addChild(file);打印目录文件树printTree(rootFolder); private static void printTree(AbstractFile ifile)ifile PrIntName(); Listchildren: ifile getChildren ();if(chiidren=null)return; for(AbstractFile file: children)(5) ; 该程序运行后输出结果为: C: compositeTestComposite javaWindows 16 阅读以下说明和 C程序,将应填入 (
17、n) 处的字句写在答题纸的对应栏内。【说明】现有 n(n 下面的 c程序判断能否从 B方向驶出预先指定的车厢序列,程序中使用了栈类型 sTACK,关于栈基本操作的函数原型说明如下: void InitStack(STACK*s):初始化栈。 void Push(STACK*s, int e):将一个整数压栈,栈 中元素数目增 1。 void Pop(STACK*S):栈顶元素出栈,栈中元素数目减 1。 int Top(STACK s):返回非空栈的栈顶元素值,栈中元素数目不变。 int IsEmpty(STACK s):若是空栈则返回1,否则返回 0。【 C程序】 #include *此处为栈
18、类型及其基本操作的定义,省略 * int main()STACK station; int state1000; int n; *车厢数 * int begin, i,j,maxNo; *maxNo为 A端正待入栈的车厢编号 * printf(”请输入车厢数: ”);scanf(“ d”, n); printf(“请输入需要判断的车厢编号序列 (以空格分隔 ): ”); if(n 2009年下半年软件水平考试(中级)软件设计师下午(应用技术)试题真题试卷答案与解析 一、必答题(共 4道大题,每道大题 15分) 1 【正确答案】 E1:非信用卡客户 E2:信用卡客户 E3:银行 【试题解析】 由
19、于题干中已经提到信用卡申请的步骤,即非信用卡客户添写申请表提交给 CCMS,如果信用申请被银行接受,则返回确认函,否则返回拒绝函。因此可以确定 E1为非信用卡客户 。同理信用卡信息管理的步骤为信用卡客户可以在线在 CCMS 信用卡管理系统中查询修改个人信息,由此可得出 E2为信用卡客户。根据信用卡申请中 ccMs 向银行发送信用卡申请信息可知 E3为银行。 2 【正确答案】 【试题解析】 需要补充的三条数据流为: (1)Po到 E2,因为 Po 信用卡客户可以向 POCCMS 提交激活请求, (2)E1到 P0,根据信用卡申请的步骤,可知 E1非信用卡客户允许填写信用卡申请表,并提交 POCC
20、MS。 (3)P0 到 E2,根据信用卡客户管理。 POCCMs 需要返回给 E2信用卡客户修改后 的信息。 3 【正确答案】 错误的数据流:信用卡申请表,激活请求更改为【试题解析】 根据题干可得出非信用卡客户 E1向 CCMS 提出信用卡申请,故信用卡申请数据流应为 E1P4 ,激活请求是 P0 信用卡客户可以向 Po(EMS 发出的,所以激活请求数据流应为 E2P3 。 4 【正确答案】 P1:交易信息查询 P2:信用卡客户信息管理 P3:信用卡激活P4:信用卡申请 【试题解析】 由题干 4交易信息查询说明的具体步骤可知 P1 的处理名称为交易信息查询。同里由题干 3信用卡客户信息管理的步
21、骤可知 P2 的处理名称 为信用卡客户信息管理。相同方法可得出 P3、 P4。 5 【正确答案】 (1)1 (2)1 (3)m或 n或 * (4)1 (5)m或 n或 * 【试题解析】 此类题目要求考生认真阅读题目对现实问题的描述,经过分类、聚集和概括等方法从中确定实体及其联系。题目己经给出了几个实体,需要根据需求描述给出实体问的联系。 问题 l:由 “一个用户可拥有一个地址簿 ”可知地址簿和用户是 1: 1的关系,根据题干捕述 “一个电子邮件账号可以含有多封邮件 ”可知电子邮件账号与邮件的关系是 1: n。由题干 “一封邮件可以含有多个附件 ”可知邮件与附件为 1: n 的关系。 问题 2:
22、地址簿的属性信息中,联系人编号不会重复,可作为地址簿的主键属性,邮件的属性信息中,缺少发件人地址属性以及邮件账号属性,另外邮件号属性不会重复,可作为邮件的主键属性。附件中缺少邮件号属性。完整的关系模式如下: 地址簿 (用户名,联系人编号,姓名,电话,单位地址,邮件地址 1,邮件地址 2,邮件地址 3) 邮件账号 (邮件地址,邮件密码,用户名 ) 邮件 (邮件号,发件人地址,邮件账号,收件人地址,邮件状态,邮件主题,邮件内容,发送时问,接收时问 ) 附件 (邮件号,附件号,附件文件名,附 件大小 ) 问题 3: 地址簿的属性信息中联系人编号不会重复,可作为主键属性,用户名来自用户关系属性信息,所
23、以作为外键。同理邮件属性信息中邮件号不会重复作为主键,邮件账号来自邮件账号关系,作为外键。附件中邮件号和附件号不会重复,均可作为主键,外键是邮件号,来自邮件的属性信息。附件属性是邮件内容的一部分,也就是说附件是否存在是以邮件是否存在为前提的。 6 【正确答案】 (1)用户名 (2)邮件号,发件人地址,邮件账号 (3)邮件号 7 【正确答案】 (1) (2)附件属于弱实体。附件中邮件号和附件号不 会重复,均可作为主键,外键是邮件号,来自邮件的属性信息。附件属性是邮件内容的一部分,也就是说附件是否存在是以邮件是否存在为前提的。 8 【正确答案】 Al:工资系统 A2:菜单管理员 【试题解析】 问题
24、 1:识别参与者时,考查与系统交互的人员和外部系统。本题中, Al 和 A2所对应的参与者为工资系统和菜单管理员。 9 【正确答案】 10 【正确答案】 11 【正确答案】 泛化关系。 泛化关系内涵:泛化关系是一般元素和具体元素之间的一种分类关系。具体元素与一般元素完全一致,但包含一些额外的信 息。在允许使用一般元素的场合,可在实际生活中发现有许多东西具有相同的特征。例如,猫和狗都是动物。对象也可以具有共同的特征,我们可以使用它们所属类之间的泛化关系来阐明这些共同特征。 12 【正确答案】 (1)k1(2)cwcw+wk(3)kk -1(4)kk+l 13 【正确答案】 (5)2与 3(6)
25、35(7) 15(8) 8 【试题解析】 本题实质上是一个 0-1背包问题,该问题最优化的目标函数是maxvixi (xi=0, 1);约束函数是: pixiM (xi=0, 1)。 0-1背包问题可用动态规划策略求得最优解,求解的递归式为其中, nvij表示由前 i项物品组合且价格不超过 i的背包的总价值。问题最终要求的背包的总价值为 nvnM,根据上述递归式,可以很容易以自底向上的方式编写伪代码。 问题 1中伪代码的第 1行到第12行计算数组 nv的元素值,第 1行到第 4行计算 i为 0或者 j为 0时 nvi的值,对应递归式的第一种情况;第 7行和第 8行计算当 j 二、选答题(共 3
26、道大题,每道大题 15分) 从下列 3道试题中任选 1道解答,如果解答的试题数超过 1道,则仅题号小的 1道题解答有效。 14 【正确答案】 (1)this一 name(2)list*(3)NULL(4)this-name(5)&childList 【试题解析】 Composite模式定义:将对象以树型结构组织起来,以达成 “部分一整体 ”的层次结构,使得客户端对单个对象和组合对象的使用具有一致性。Composite比较容易理解,想到 Composite就应该想到树形结构图。组合体内这些对象都有共同接口,当组合体一个对象的方法被调用执行时, Composite将遍历(Iterator)整个树
27、形结构,寻找同样包含这个方法的对象并实现调用执行。AbstractFile为一个抽象文件类,其作用主要是实现对文件或者文件夹的抽象。文件类 File继承自 AbstractFile。 File(stringname)为 File类的一个属性,用于获取文件名称。 Addchild方法用来给一个目录增加子目录或文件。 Removechild 方法用于删除一个目录的子目录或文件。 Getchildren 方法用于获取一个目录或文件,所以返回值类型应该是一个列表形式的 AbstractFile,但文件本身不包括子目录,故返回 NULL。 Fold 类表示一个文件夹,属性 Fold.er用于获取文件夹名
28、称,Getchildren 方法返回值应为 List型的 AbstractFile对象指针。 15 【正确答案】 (1)Abstract(2)null(3)List(4)childList(5)printTree(file) 【试题解析】 Composite模式定义:将对象以树型结构组织起来,以达成 “部分 -整体 ”的层次结构,使得客户端对单个对象和组合对象的使用具有一致性。Composite比较容易理解,想到 Composite就应该想到树型结构图 。组合体内这些对象都有共同接口,当组合体一个对象的方法被调用执行时, Composite将遍历(Iterator)整个树形结构,寻找同样包含这
29、个方法的对象并实现调用执行。AbstractFile为一个抽象文件类,其作用主要是实现对文件或者文件夹的抽象。文件类 File继承自 AbstractFile。 File(stringname)为 File类的一个属性,用于获取文件名称。 Add-child方法用来给一个目录增加子目录或文件。 Removechild 方法用于删除一个目录的子目录或文件。 Getchildren 方法用于 获取一个目录或文件,所以返回值类型应该是一个列表形式的 AbstractFile,但文件本身不包括子目录,故返回 NUIJIJ。 Fold 类表示一个文件夹,属性 Folder用于获取文件夹名称,Getchi
30、ldren 方法返回值应为 List型的 AbstractFile对象指针。 16 【正确答案】 (1)InitStack(&station)(2)IsEmpty(station)(3)stateitop(starion)(4)top(station)(5)j 【试题解析】 从本题来看,程序首先要求用户 输入车厢数,然后初始化栈,给出的操作原型 voidInitStack=(STACK*s)用于初始化栈,而 Main 函数已经定义Stackstation,故应填 Init-Stack(&station)。根据输入 n的值遍历栈,当栈不为空时,需要添加判断函数 IsEmpty(sTACKs),如栈顶车厢号等于被检查车厢号时,则输出车厢号;如栈顶车厢号小于被检查车厢号时,输出错误。根据函数原型,填 stateitop(station),当栈顶车厢号大于被检查车厢号时,开始压栈。栈是只能通过访问它的一端来实现数据存储和检 索的一种线性数据结构。换句话说,栈的修改是按先进后出的原则进行的。因此,栈又称为先进后出的线性表。对栈来说,进行插入和删除操作的一端称为栈顶,另一端称为栈底。不包含数据元素的栈称为空栈。