全国计算机技与软件专业技术资格水平考试

《全国计算机技与软件专业技术资格水平考试》由会员分享，可在线阅读，更多相关《全国计算机技与软件专业技术资格水平考试（16页珍藏版）》请在装配图网上搜索。

1、全国计算机技术与软件专业技术资格（水平）考试2009 年下半年软件设计师下午试卷（考试时间 14: 0016: 30共 150 分钟）请按下述要求正确填写答题纸1. 在答题纸的指定位置填写你所在的省、自治区、直辖市、计划单列市的名称。2. 在答题纸的指定位置填写准考证号、出生年月日和姓名。3. 答题纸上除填写上述内容外只能写解答。4. 本试卷共 7 道题，试题一至试题四是必答题，试题五至试题七选答1 道。每题 15 分，满分 75 分。5. 解答时字迹务必清楚，字迹不清时，将不评分。6. 仿照下面例题，将解答写在答题纸的对应栏内。例题2009 年下半年全国计算机技术与软件专业技术资格 （水平）

2、考试日期是（1）月（ 2）日。因为正确的解答是 “ 11 月 14 日”，故在答题纸的对应栏内写上 “11”和“14”（参看下表）。例题解答栏（1）11（2）14试题一（共15 分）阅读以下说明和数据流图，回答问题 1至问题 4，将解答填入答题纸的对应栏内。【说明】现准备为某银行开发一个信用卡管理系统CCMS ，该系统的基本功能为：1. 信用卡申请。 非信用卡客户填写信用卡申请表， 说明所要申请的信用卡类型及申请者的基本信息，提交 CCMS 。如果信用卡申请被银行接受， CCMS 将记录该客户的基本信息，并发送确认函给该客户，告知客户信用卡的有效期及信贷限额；否则该客户将会收到一封拒绝函。非信

3、用卡客户收到确认函后成为信用卡客户。2. 信用卡激活。信用卡客户向 CCMS 提交激活请求，用信用卡号和密码激活该信用卡。激活操作结束后， CCMS 将激活通知发送给客户， 告知客户其信用卡是否被成功激活。3. 信用卡客户信息管理。信用卡客户的个人信息可以在CCMS 中进行在线管理。每位信用卡客户可以在线查询和修改个人信息。4. 交易信息查询。信用卡客户使用信用卡进行的每一笔交易都会记录在CCMS 中。信用卡客户可以通过CCMS 查询并核实其交易信息（包括信用卡交易记录及交易额）。图 1-1 和图 1-2分别给出了该系统的顶层数据流图和0层数据流图的初稿。【问题 1】（ 3 分）根据【说明 】

4、，将图 1-1中的 E1E3 填充完整。【问题 2】（ 3 分）图 1-1 中缺少三条数据流， 根据【说明 】，分别指出这三条数据流的起点和终点。（注：数据流的起点和终点均采用图中的符号和描述）【问题 3】（ 5 分）图 1-2 中有两条数据流是错误的，请指出这两条数据流的名称，并改正。（注：数据流的起点和终点均采用图中的符号和描述）【问题 4】（ 4 分）根据【说明 】，将图 1-2中 P1P4 的处理名称填充完整。拒绝函E1确认函P0信用卡申请信息查询 /修改个人信息信用卡管理系统 CCMSE3激活通知交易记录查询请求信用卡申请验证结果E2个人信息图 1-1 顶层数据流图交易信息交易记录查

5、询请求查询 /修改个人信息个人信息E2激活通知拒绝函信用卡申请表E1确认函P1P2P3激活请求P4信用卡申请信息E3信用卡申请验证结果图 1-20 层数据流图试题二（共15 分）阅读下列说明，回答问题1至问题 3，将解答填入答题纸的对应栏内。【说明】某公司拟开发一多用户电子邮件客户端系统，部分功能的初步需求分析结果如下：（ 1）邮件客户端系统支持多个用户，用户信息主要包括用户名和用户密码，且系统中的用户名不可重复。（ 2）邮件帐号信息包括邮件地址及其相应的密码，一个用户可以拥有多个邮件地址（如 user1）。（ 3）一个用户可拥有一个地址薄，地址簿信息包括联系人编号、姓名、电话、单位地址、邮件

6、地址 1、邮件地址 2、邮件地址 3 等信息。地址薄中一个联系人只能属于一个用户，且联系人编号唯一标识一个联系人。（ 4）一个邮件帐号可以含有多封邮件，一封邮件可以含有多个附件。邮件主要包括邮件号、发件人地址、收件人地址、邮件状态、邮件主题、邮件内容、发送时间、接收时间。其中，邮件号在整个系统内唯一标识一封邮件，邮件状态有已接收、待发送、已发送和已删除 4 种，分别表示邮件是属于收件箱、发件箱、已发送箱和废件箱。一封邮件可以发送给多个用户。附件信息主要包括附件号、附件文件名、附件大小。一个附件只属于一封邮件，附件号仅在一封邮件内唯一。【问题 1】（ 5 分）根据以上说明设计的E-R 图如图 2

7、-1 所示，请指出地址簿与用户、电子邮件帐号与邮件、邮件与附件之间的联系类型。地址簿邮件帐号包含邮件( 2)( 3)( 1)m( 4)拥有 1拥有 2属于11( 5)用户附件图 2-1 电子邮件客户端系统E-R 图【问题 2】（ 4 分）该邮件客户端系统的主要关系模式如下，请填补( a) ( c) 的空缺部分。用户 ( 用户名，用户密码 )地址簿 ( (a)，联系人编号，姓名，电话，单位地址，邮件地址1，邮件地址 2，邮件地址 3)邮件帐号（邮件地址，邮件密码，用户名）邮件 ( (b)，收件人地址，邮件状态，邮件主题，邮件内容，发送时间，接收时间 )附件 (c)，附件号，附件文件名，附件大小)

8、【问题 3】（ 6 分）（ 1）请指出 【问题 2】中给出的地址簿、邮件和附件关系模式的主键，如果关系模式存在外键请指出。（ 2）附件属于弱实体吗？请用50 字以内的文字说明原因。试题三（共15 分）阅读下列说明和UML 图，回答问题1 至问题 4，将解答填入答题纸的对应栏内。【说明】某企业为了方便员工用餐，为餐厅开发了一个订餐系统（System），企业员工可通过企业内联网使用该系统。COS： Cafeteria Ordering企业的任何员工都可以查看菜单和今日特价。系统的顾客是注册到系统的员工，可以订餐（如果未登录，需先登录） 、注册工资支付、预约规律的订餐，在特殊情况下可以覆盖预订。餐厅

9、员工是特殊顾客，可以进行备餐、生成付费请求和请求送餐，其中对于注册工资支付的顾客生成付费请求并发送给工资系统。菜单管理员是餐厅特定员工，可以管理菜单。送餐员可以打印送餐说明，记录送餐信息（如送餐时间）以及记录收费（对于没有注册工资支付的顾客，由送餐员收取现金后记录）。顾客订餐过程如下：1. 顾客请求查看菜单；2. 系统显示菜单和今日特价；3. 顾客选菜；4. 系统显示订单和价格；5. 顾客确认订单；6. 系统显示可送餐时间；7. 顾客指定送餐时间、地点和支付方式；8. 系统确认接受订单， 然后发送 Email 给顾客以确认订餐， 同时发送相关订餐信息通知给餐厅员工。系统采用面向对象方法开发，使

10、用UML 进行建模。系统的顶层用例图和一次订餐的活动图初稿分别如图 3-1 和图 3-2 所示。【问题 1】（ 2 分）根据【说明】 中的描述，给出图3-1中 A1 和 A2 所对应的参与者。【问题 2】（ 8 分）根据【说明】 中的描述，给出图3-1中缺少的四个用例及其所对应的参与者。【问题 3】（ 4 分）根据【说明】 中的描述，给出图3-2中（ 1）（ 4）处对应的活动名称或图形符号。【问题 4】（ 1 分）指出图 3-1 中员工和顾客之间是什么关系，并解释该关系的内涵。图 3-1COS 系统顶层用例图（ 1）（ 2）（3）（4）图 3-2一次订餐的活动图试题四（共15 分）阅读下列说明

11、，回答问题1 至问题 2，将解答填入答题纸的对应栏内。【说明】0-1 背包问题可以描述为：有 n 个物品，对 i = 1, 2, , n，第 i 个物品价值为 vi，重量为 w i（ vi 和 wi 为非负数），背包容量为 W （ W 为非负数），选择其中一些物品装入背包，n使 装入 背包 物品 的总 价值 最大 ，即 maxvi xi ， 且 总重 量不 超过 背包 容量 ， 即i1n0,1 ，xi=0 表示第 i 个物品不放入背包， xi=1 表示第 i 个物品wi xi W ，其中， xii 1放入背包。【问题 1】（ 8 分）用回溯法求解此0-1 背包问题，请填充下面伪代码中（1）（

12、4）处空缺。回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了 BOUND( v,w,k,W ) 函数，其中 v、 w 、k 和 W 分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后， 对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值

13、，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。下面给出0-1 背包问题的回溯算法伪代码。函数参数说明如下:W ：背包容量； n：物品个数； w：重量数组； v：价值数组； fw ：获得最大价值时背包的重量； fp：背包获得的最大价值； X ：问题的最优解。变量说明如下：cw：当前的背包重量； cp：当前获得的价值； k：当前考虑的物品编号； Y ：当前已获得的部分解。BKNAP( W,n,w,v,fw,fp,X )1 cw cp 02 （1）3 fp -14 while true5while k n and cw + wk W do6（2）7cp cp+ vk8Yk 19k k

14、+ 110if k n then11if fp cp then12fp cp13fw cw14k n15X Y16else Y(k) 017while BOUND(cp,cw,k,W) fp do18while k 0and Y(k) 1 do19（ 3）20if k = 0 then return21Yk 022cw cw - wk23cp cp- vk24（ 4）【问题 2】（ 7 分）考虑表 4-1 的实例，假设有3 个物品，背包容量为22。图 4-1 中是根据上述算法构造的搜索树，其中结点的编号表示了搜索树生成的顺序，边上的数字1/0 分别表示选择/不选择对应物品。除了根结点之外，每个

15、左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品（ 5），获得的价值为（ 6）。表 4-10-1 背包问题实例物品1物品2物品3重量151010价值301817单位价值21.81.7110对物品 1的选择15352530010对物品 2的选择10341.961781801对物品 3的选择30420735图 4-1表 4-1 实例的搜索树对于表 4-1 的实例，若采用穷举法搜索整个解空间，则搜索树的结点数为（ 7），而用了上述回溯法，搜索树的结点数为（8） 。从下列的3 道试题（试题五至试题七）

16、中任选1 道解答。如果解答的试题数超过1 道，则题号小的1 道解答有效。试题五（共15 分）阅读下列说明和 C+代码，将应填入 （ n） 处的字句写在答题纸的对应栏内。【说明】现欲构造一文件 /目录树，采用组合（ Composite）设计模式来设计，得到的类图如 5-1 所示：图 5-1 类图【 C+代码】#include #include #include using namespace std;class AbstractFile protected :string name;/ 文件或目录名称public:void printName()cout name;virtual void ad

17、dChild(AbstractFile*file)=0;virtual void removeChild(AbstractFile *file)=0;virtual list *getChildren()=0;/ 打印文件或目录名称/ 给一个目录增加子目录或文件/ 删除一个目录的子目录或文件/ 获得一个目录的子目录或文件;class File : public AbstractFile public :File(string name) （ 1） = name; void addChild(AbstractFile*file) return ; void removeChild(Abstrac

18、tFile *file) return ; （ 2）getChildren() return（3） ; ;class Folder :public AbstractFile private :list childList;/ 存储子目录或文件public :Folder(string name) （ 4）= name; void addChild(AbstractFile *file) childList.push_back(file); void removeChild(AbstractFile *file) childList.remove(file);list *getChildren(

19、) return（ 5） ; ;void main() / 构造一个树形的文件 /目录结构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-addChil

20、d(windowsFolder); compositeFolder-addChild(file);试题六（共15 分）阅读下列说明和 Java 代码，将应填入 （ n） 处的字句写在答题纸的对应栏内。【说明】现欲构造一文件 /目录树，采用组合（ Composite）设计模式来设计，得到的类图如 6-1 所示：图 6-1 类图【 Java 代码】import java.util.ArrayList;import java.util.List;（ 1） class AbstractFile protected String name;public void printName()System.ou

21、t.println(name); public abstract boolean addChild(AbstractFile file); public abstract boolean removeChild(AbstractFile file); public abstract List getChildren();class File extends AbstractFile public File(String name) this.name = name; public boolean addChild(AbstractFile file) return false; public

22、boolean removeChild(AbstractFile file) return false; public List getChildren() return（ 2） ; class Folder extends AbstractFile private List childList;public Folder(String name) this.name = name;this.childList = new ArrayList();public boolean addChild(AbstractFile file) return childList.add(file); pub

23、lic boolean removeChild(AbstractFile file) return childList.remove(file); public（ 3） getChildren() return（ 4） ; public class Client public static void main(String args) / 构造一个树形的文件 /目录结构AbstractFile rootFolder = new Folder(c:);AbstractFile compositeFolder = new Folder(composite); AbstractFile window

24、sFolder = new Folder(windows); AbstractFile file = new File(TestComposite.java); rootFolder.addChild(compositeFolder); rootFolder.addChild(windowsFolder); compositeFolder.addChild(file);/ 打印目录文件树printTree(rootFolder);private static void printTree(AbstractFile ifile) ifile.printName();List children =

25、 ifile.getChildren();if(children = null)return;for (AbstractFile file:children) （5） ;该程序运行后输出结果为:c:compositeTestComposite.javaWindows试题七（共15 分）阅读以下说明和C 程序，将应填入（ n）处的字句写在答题纸的对应栏内。【说明】现有 n（ n 1000 ）节火车车厢，顺序编号为1,2,3,.,n，按编号连续依次从A 方向的铁轨驶入，从B 方向铁轨驶出，一旦车厢进入车站（Station）就不能再回到A 方向的铁轨上；一旦车厢驶入B 方向铁轨就不能再回到车站，如图

26、7-1 所示，其中Station 为栈结构，初始为空且最多能停放1000 节车厢。1,3,2,51,2,3,4,54图 7-1车站示意图下面的C 程序判断能否从B 方向驶出预先指定的车厢序列，程序中使用了栈类型STACK , 关于栈基本操作的函数原型说明如下：void InitStack ( STACK *s ) ：初始化栈。void Push ( STACK *s , int e):将一个整数压栈，栈中元素数目增1。void Pop ( STACK *s ) ：栈顶元素出栈，栈中元素数目减1。int Top ( STACK s ) ：返回非空栈的栈顶元素值，栈中元素数目不变。int IsEm

27、pty ( STACK s ) ：若是空栈则返回1，否则返回0。【C 程序】#include/* 此处为栈类型及其基本操作的定义，省略*/int main( )STACK station;int state1000;int n;/*int begin, i, j, maxNo;printf( 请输入车厢数：scanf(%d,&n);/*);车厢数 */maxNo 为 A 端正待入栈的车厢编号*/printf( 请输入需要判断的车厢编号序列（以空格分隔）： );if (n 1)return -1;for (i = 0; in; i+)/*读入需要 驶出 的车厢编号序列, 存入数组state */

28、scanf(%d,&statei);（ 1） ; /* 初始化栈 */ maxNo = 1;for(i = 0; i n; )/* 检查输出序列中的每个车厢号statei 是否能从栈中获取*/if ( （ 2） ) /* 当栈不为空时*/if (statei = Top(station) /* 栈顶车厢号等于被检查车厢号 */ printf(%d , Top(station);Pop(&station);i+;elseif (（3） )printf(errorn);return 1;else begin =（ 4） ;for(j = begin+1; j=statei; j+) Push(&station, j);else /* 当栈为空时 */begin = maxNo;for(j = begin; j=statei; j+)Push(&station, j);maxNo =（5） ;printf(OK);return 0;