2009~2023软件设计师下午试卷.pdf

软件设计师下午试卷 2009 年2023 年 计算机技术与软件专业技术资格（水平）考试 2009 年上半年 软件设计师 下午试卷 1 全国计算机技术与软件专业技术资格（水平）考试全国计算机技术与软件专业技术资格（水平）考试 2009 年上半年年上半年 软件设计师软件设计师 下下午试卷午试卷 （考试时间 14:0016:30 共 150 分钟）请按下述要求正确填写答题卡请按下述要求正确填写答题卡 1.在答题纸的指定位置填写你所在的省、自治区、直辖市、计划单列市的名称。2.在答题纸的指定位置填写准考证号、出生年月日和姓名。3.答题纸上除填写上述内容外只能写解答。4.本试卷共 7 道题，试题一至试题四是必答题，试题五至试题七选答 1 道。每题 15 分，满分 75 分。5.解答时字迹务必清楚，字迹不清时，将不评分。6.仿照下面的例题，将解答写在答题纸的对应栏内。例题 2009 年上半年全国计算机技术与软件专业技术资格（水平）考试日期是（1）月（2）日。因为正确的解答是“5 月 23 日”，故在答题纸的对应栏内写上“5”和“23”（参看下表）。例题 解答栏（1）5（2）23 2 2009 年上半年 软件设计师 下午试卷 试题一试题一（共（共 15 分）分）阅读下列说明，回答问题 1 和问题 2，将解答填入答题纸的对应栏内。【说明】假设某大型商业企业由商品配送中心和连锁超市组成，其中商品配送中心包括采购、财务、配送等部门。为实现高效管理，设计了商品配送中心信息管理系统，其主要功能描述如下：（1）系统接收由连锁超市提出的供货请求，并将其记录到供货请求记录文件。（2）在接到供货请求后，从商品库存记录文件中进行商品库存信息查询。如果库存满足供货请求，则给配送处理发送配送通知；否则，向采购部门发出缺货通知。（3）配送处理接到配送通知后，查询供货请求记录文件，更新商品库存记录文件，并向配送部门发送配送单，在配送货品的同时记录配送信息至商品配送记录文件。（4）采购部门接到缺货通知后，与供货商洽谈，进行商品采购处理，合格商品入库，并记录采购清单至采购清单记录文件、向配送处理发出配送通知，同时通知财务部门给供货商支付货款。该系统采用结构化方法进行开发，得到待修改的数据流图如下图所示。2009 年上半年 软件设计师 下午试卷 3【问题 1】（8 分）使用说明中的词语，给出上图中外部实体 E1 至 E4 的名称和数据存储 D1 至 D4 的名称。【问题 2】（7 分）以上数据流图中存在四处错误数据流，请指出各自的起点和终点；若将上述四条错误数据流删除，为保证数据流图的正确性，应补充三条数据流，请给出所补充数据流的起点和终点。（起点和终点请采用上述数据流图中的符号或名称）4 2009 年上半年 软件设计师 下午试卷 试题二试题二（共（共 15 分）分）阅读下列说明，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。【说明】某集团公司拥有多个大型连锁商场，公司需要构建一个数据库系统以方便管理其业务运作活动。【需求分析结果】（1）商场需要记录的信息包括商场编号（编号唯一），商场名称，地址和联系电话。某商场信息如下表所示。商场信息表 （2）每个商场包含有不同的部门，部门需要记录的信息包括部门编号（集团公司分配），部门名称，位置分布和联系电话。某商场的部门信息如下表所示。部门信息表 2009 年上半年 软件设计师 下午试卷 5（3）每个部门雇用多名员工处理日常事务，每名员工只能隶属于一个部门（新进员工在培训期不隶属于任何部门）。员工需要记录的信息包括员工编号（集团公司分配），姓名，岗位，电话号码和工资。员工信息如下表所示。员工信息表 （4）每个部门的员工中有一名是经理，每个经理只能管理一个部门，系统需要记录每个经理的任职时间。【概念模型设计】根据需求阶段收集的信息，设计的实体联系图（不完整）如图 2-1 所示。图 2-1 实体联系图 【逻辑结构设计】根据概念模型设计阶段完成的实体联系图，得出如下关系模式（不完整）：商场（商场编号，商场名称，地址，联系电话）部门（部门编号，部门名称，位置分布，联系电话，（a）员工（员工编号，员工姓名，岗位，电话号码，工资，（b）经理（c），任职时间）6 2009 年上半年 软件设计师 下午试卷 【问题 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 年上半年 软件设计师 下午试卷 7 试题三试题三（共（共 15 分）分）阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。【说明】某银行计划开发一个自动存提款机模拟系统（ATM System）。系统通过读卡器（CardReader）读取 ATM 卡；系统与客户（Customer）的交互由客户控制台（Customer-Console）实现；银行操作员（Operator）可控制系统的启动（System Startup）和停止（System Shutdown）；系统通过网络和银行系统（Bank）实现通信。当读卡器判断用户已将 ATM 卡插入后，创建会话（Session）。会话开始后，读卡器进行读卡，并要求客户输入个人验证码（PIN）。系统将卡号和个人验证码信息送到银行系统进行验证。验证通过后，客户可从菜单选择如下事务（Transaction）：1从 ATM 卡账户取款（Withdraw）；2向 ATM 卡账户存款（Deposit）；3进行转账（Transfer）；4查询（Inquire）ATM 卡账户信息；一次会话可以包含多个事务，每个事务处理也会将卡号和个人验证码信息送到银行系统进行验证。若个人验证码错误，则转个人验证码错误处理（Invalid PIN Process）。每个事务完成后，客户可选择继续上述事务或退卡。选择退卡时，系统弹出 ATM 卡，会话结束。系统采用面向对象方法开发，使用 UML 进行建模。系统的顶层用例图如图 3-1 所示，一次会话的序列图（不考虑验证）如图 3-2 所示。8 2009 年上半年 软件设计师 下午试卷 2009 年上半年 软件设计师 下午试卷 9 【问题 1】（7 分）根据说明中的描述，给出图 3-1 中 A1 和 A2 所对应的参与者，U1 至 U3 所对应的用例，以及该图中空 （1）所对应的关系。（U1 至 U3 的可选用例包括：Session、Transaction、Insert Card、Invalid PIN Process 和 Transfer）【问题 2】（6 分）根据说明中的描述，使用消息名称列表中的英文名称，给出图 3-2 中 69 对应的消息。【问题 3】（2 分）解释图 3-1 中用例 U3 和用例 Withdraw、Deposit 等四个用例之间的关系及其内涵。10 2009 年上半年 软件设计师 下午试卷 试题四试题四（共（共 15 分）分）阅读下列说明，回答问题 1 和问题 2，将解答填入答题纸的对应栏内。【说明】现需在某城市中选择一个社区建一个大型超市，使该城市的其它社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其他各顶点的最短路径之和最小。算法首先需要求出每个顶点到其它任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其它各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。本题采用 Floyd-Warshall 算法求解任意两个顶点之间的最短路径。已知图的顶点集合为=1,2,，=为权重矩阵。设()为从顶点到顶点的一条最短路径的权重。当 k=0 时，不存在中间顶点，因此(0)=；当 0 时，该最短路径上所有的中间顶点均属于集合1,2,。若中间顶点包括顶点，则()=(1)+(1)；若中间顶点不包括顶点，则()=(1)。于是得到如下递归式()=min(1),(1)+(1)=0 0 因为对于任意路径，所有的中间顶点都在集合1,2,内，因此矩阵()=()给出了任意两个顶点之间的最短路径，即对所有,()表示顶点到顶点的最短路径。下面是求解该问题的伪代码，伪代码中的主要变量说明如下：W：权重矩阵 n：图的顶点个数 SP：最短路径权重之和数组，SPi表示顶点 i 到其它各顶点的最短路径权重之和，i 从 1 到 n min_SP：最小的最短路径权重之和 min_v：具有最小的最短路径权重之和的顶点 i：循环控制变量 j：循环控制变量 k：循环控制变量 2009 年上半年 软件设计师 下午试卷 11 【问题 1】（12 分）根据说明和伪代码，填充伪代码中的空（1）（6）。【问题 2】（3 分）问题 1 中伪代码的时间复杂度为 （7）（用 符号表示）。12 2009 年上半年 软件设计师 下午试卷 试题试题五（共五（共 15 分）分）阅读下列说明和 C 函数代码，将应填入 （n）处的字句写在答题纸的对应栏内。【说明】对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个节点，且每个节点仅访问一次的过程。函数 InOrder()借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储，节点类型定义如下：typedef struct BtNode ElemType data;/*节点的数据域，ElemType 的具体定义省略*/struct BtNode*lchild,*rchild;/*节点的左、右孩子指针域*/BtNode,*BTree;在函数 InOrder()中，用栈暂存二叉树中各个节点的指针，并将栈表示为不含头节点的单向链表（简称链栈），其节点类型定义如下：typedef struct StNode /*链栈的节点类型*/BTree elem;/*栈中的元素是指向二叉链表节点的指针*/struct StNode*link;StNode;假设从栈顶到栈底的元素为 en、en-1、e1，则不含头节点的链栈示意图如图 5-1 所示。2009 年上半年 软件设计师 下午试卷 13【C 函数】int InOrder(BTree root)/*实现二叉树的非递归中序遍历*/BTree ptr;/*ptr 用于指向二叉树中的节点*/StNode*q;/*q 暂存链栈中新创建或待删除的节点指针*/StNode*stacktop=NULL;/*初始化空栈的栈顶指针 stacktop*/ptr=root;/*ptr 指向二叉树的根节点*/while(1)|stacktop!=NULL)while(ptr!=NULL)q=(StNode*)malloc(sizeof(StNode);if(q=NULL)return-1;q-elem=ptr;(2);stacktop=q;/*stacktop 指向新的栈顶*/ptr=(3);/*进入左子树*/q=stacktop;(4);/*栈顶元素出栈*/visit(q);/*visit 是访问节点的函数，其具体定义省略*/ptr=(5);/*进入右子树*/free(q);/*释放原栈顶元素的节点空间*/return 0;/*InOrder*/14 2009 年上半年 软件设计师 下午试卷 试题试题六（共六（共 15 分）分）阅读下列说明和 C+代码，将应填入 （n）处的字句写在答题纸的对应栏内。【说明】现欲实现一个图像浏览系统，要求该系统能够显示 BMP、JPEG 和 GIF 三种格式的文件，并且能够在 Windows 和 Linux 两种操作系统上运行。系统首先将 BMP、JPEG 和 GIF三种格式的文件解析为像素矩阵，然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，采用桥接（Bridge）设计模式进行设计，所得类图如下图所示 采用该设计模式的原因在于：系统解析 BMP、GIF 与 JPEG 文件的代码仅与文件格式相关，而在屏幕上显示像素矩阵的代码则仅与操作系统相关。【C+代码】class Matrix /各种格式的文件最终都转化为像素矩阵/此处代码省略;class ImageImp public:virtual void doPaint(Matrix m)=0;/显示像素矩阵 m;2009 年上半年 软件设计师 下午试卷 15 class WinImp:public ImageImp public:void doPaint(Matrix m)/*调用 Windows 系统的绘制函数绘制像素矩阵*/;class LinuxImp:public ImageImp public:void doPaint(Matrix m)/*调用 Linux 系统的绘制函数绘制像素矩阵*/;class Image public:void setImp(ImageImp*imp)(1)=imp;virtual void parseFile(string fileName)=0;protected:(2)*imp;class BMP:public Image public:void parseFile(string fileName)/此处解析 BMP 文件获得一个像素矩阵对象 m (3);/显示像素矩阵 m ;class GIF:public Image /此处代码省略;16 2009 年上半年 软件设计师 下午试卷 class JPEG:public Image /此处代码省略;void main()/在 Windows 操作系统上查看 demo.bmp 图像文件 Image*image1=(4);ImageImp*imageImp1=(5);(6);image1-parseFile(demo.bmp);现假设该系统需要支持 10 种格式的图像文件和 5 种操作系统，不考虑类 Matrix，若采用桥接设计模式则至少需要设计 （7）个类。2009 年上半年 软件设计师 下午试卷 17 试题试题七（共七（共 15 分）分）阅读下列说明和 Java 代码，将应填入 （n）处的字句写在答题纸的对应栏内。【说明】现欲实现一个图像浏览系统，要求该系统能够显示 BMP、JPEG 和 GIF 三种格式的文件，并且能够在 Windows 和 Linux 两种操作系统上运行。系统首先将 BMP、JPEG 和 GIF三种格式的文件解析为像素矩阵，然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，采用桥接（Bridge）设计模式进行设计所得类图如下图所示 采用该设计模式的原因在于：系统解析 BMP、GIF 与 JPEG 文件的代码仅与文件格式相关，而在屏幕上显示像素矩阵的代码则仅与操作系统相关。【Java 代码】class Matrix /各种格式的文件最终都被转化为像素矩阵/此处代码省略 abstract class ImageImp public abstract void doPaint(Matrix m);/显示像素矩阵 m 18 2009 年上半年 软件设计师 下午试卷 class WinImp extends ImageImp public void doPaint(Matrix m)/*调用 Windows 系统的绘制函数绘制像素矩阵*/class LinuxImp extends ImageImp public void doPaint(Matrix m)/*调用 Linux 系统的绘制函数绘制像素矩阵*/abstract class Image public void setImp(ImageImp imp)(1)=imp;public abstract void parseFile(String fileName);protected (2)imp;class BMP extends Image public void parseFile(String fileName)/此处解析 BMP 文件并获得一个像素矩阵对象 m (3);/显示像素矩阵 m class GIF extends Image /此处代码省略 class JPEG extends Image /此处代码省略 2009 年上半年 软件设计师 下午试卷 19 public class javaMain public static void main(String args)/在 windows 操作系统上查看 demo.bmp 图像文件 Image image1=(4);ImageImp imageImp1=(5);(6);Image1.parseFile(demo.bmp);现假设该系统需要支持 10 种格式的图像文件和 5 种操作系统，不考虑类 Matrix，若采用桥接设计模式则至少需要设计 （7）个类。2009 年下半年 软件设计师 下午试卷 21 全国计算机技术与软件专业技术资格（水平）考试全国计算机技术与软件专业技术资格（水平）考试 2009 年下半年年下半年 软件设计师软件设计师 下下午试卷午试卷 （考试时间 14:0016:30 共 150 分钟）请按下述要求正确填写答题卡请按下述要求正确填写答题卡 1.在答题纸的指定位置填写你所在的省、自治区、直辖市、计划单列市的名称。2.在答题纸的指定位置填写准考证号、出生年月日和姓名。3.答题纸上除填写上述内容外只能写解答。4.本试卷共 7 道题，试题一至试题四是必答题，试题五至试题七选答 1 道。每题 15 分，满分 75 分。5.解答时字迹务必清楚，字迹不清时，将不评分。6.仿照下面的例题，将解答写在答题纸的对应栏内。例题 2009 年下半年全国计算机技术与软件专业技术资格（水平）考试日期是（1）月（2）日。因为正确的解答是“11 月 14 日”，故在答题纸的对应栏内写上“11”和“14”（参看下表）。例题 解答栏（1）11（2）14 22 2009 年下半年 软件设计师 下午试卷 试题一试题一（共（共 15 分）分）阅读下列说明和数据流图，回答问题 1 至问题 4，将解答填入答题纸的对应栏内。【说明】现准备为某银行开发一个信用卡管理系统 CCMS，该系统的基本功能为：（1）信用卡申请。非信用卡客户填写信用卡申请表，说明所要申请的信用卡类型及申请者的基本信息，提交 CCMS。如果信用卡申请被银行接受，CCMS 将记录该客户的基本信息，并发送确认函给该客户，告知客户信用卡的有效期及信贷限额；否则该客户将会收到一封拒绝函。非信用卡客户收到确认函后成为信用卡客户。（2）信用卡激活。信用卡客户向 CCMS 提交激活请求，用信用卡号和密码激活该信用卡。激活操作结束后，CCMS 将激活通知发送给客户，告知客户其信用卡是否被成功激活。（3）信用卡客户信息管理。信用卡客户的个人信息可以在 CCMS 中进行在线管理。每位信用卡客户可以在线查询和修改个人信息。（4）交易信息查询。信用卡客户使用信用卡进行的每一笔交易都会记录在 CCMS 中。信用卡客户可以通过 CCMS 查询并核实其交易信息（包括信用卡交易记录及交易额）。下图 1-1 和 1-2 分别给出了该系统的顶层数据流图和 0 层数据流图的初稿。图 1-1 顶层数据流图 2009 年下半年 软件设计师 下午试卷 23 图 1-2 0 层数据流图【问题 1】（3 分）根据说明，将图 1-1 中的 E1E3 填充完整。【问题 2】（3 分）图 1-1 中缺少三条数据流，根据说明，分别指出这三条数据流的起点和终点。（注：数据流的起点和终点均采用图中的符号和描述）【问题 3】（5 分）图 1-2 中有两条数据流是错误的，请指出这两条数据流的名称，并改正。（注：数据流的起点和终点均采用图中的符号和描述）【问题 4】（4 分）根据说明，将图 1-2 中 P1P4 的处理名称填充完整。24 2009 年下半年 软件设计师 下午试卷 试题二试题二（共（共 15 分）分）阅读下列说明，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。【说明】某公司拟开发一多用户电子邮件客户端系统，部分功能的初步需求分析结果如下：【需求分析结果】（1）邮件客户端系统支持多个用户，用户信息主要包括用户名和用户密码，且系统中的用户名不可重复。（2）邮件帐号信息包括邮件地址及其相应的密码，一个用户可以拥有多个邮件地址（如user1）。（3）一个用户可拥有一个地址薄，地址簿信息包括联系人编号、姓名、电话、单位、地址、邮件地址 1、邮件地址 2、邮件地址 3 等信息。地址薄中一个联系人只能属于一个用户，且联系人编号唯一标识一个联系人。（4）一个邮件帐号可以含有多封邮件，一封邮件可以含有多个附件。邮件主要包括邮件号、发件人地址、收件人地址、邮件状态、邮件主题、邮件内容、发送时间、接收时间。其中，邮件号在整个系统内唯一标识一封邮件，邮件状态有己接收、待发送、已发送和已删除 4 种，分别表示邮件是属于收件箱、发件箱、己发送箱和废件箱。一封邮件可以发送给多个用户。附件信息主要包括附件号、附件文件名、附件大小。一个附件只属于一封邮件，附件号仅在一封邮件内唯一。【概念模型设计】根据需求阶段收集的信息，设计的实体联系图（不完整）如图 2-1 所示。图 2-1 电子邮件客户端系统 E-R 图 2009 年下半年 软件设计师 下午试卷 25【逻辑结构设计】根据概念模型设计阶段完成的实体联系图，得出如下关系模式（不完整）：用户（用户名，用户密码）地址簿（a），联系人编号，姓名，电话，单位地址，邮件地址 1，邮件地址 2，邮件地址 3）邮件帐号（邮件地址，邮件密码，用户名）邮件（b），收件人地址，邮件状态，邮件主题，邮件内容，发送时间，接收时间）附件（c），附件号，附件文件名，附件大小）【问题 1】（5 分）根据以上说明设计的 E-R 图如图 2-1 所示，请指出地址簿与用户、电子邮件帐号与邮件、邮件与附件之间的联系类型。【问题 2】（4 分）根据实体联系图，将关系模式中的空（a）（c）补充完整 【问题 3】（6 分）（1）请指出问题 2 中给出的地址簿、邮件和附件关系模式的主键，如果关系模式存在外键请指出。（2）附件属于弱实体吗？请用 50 字以内的文字说明原因。26 2009 年下半年 软件设计师 下午试卷 试题三试题三（共（共 15 分）分）阅读下列说明和 UML 图，回答问题 1 至问题 4，将解答填入答题纸的对应栏内。【说明】某企业为了方便员工用餐，为餐厅开发了一个订餐系统（COS：Cafeteria Ordering System），企业员工可通过企业内联网使用该系统。企业的任何员工都可以查看菜单和今日特价。系统的顾客是注册到系统的员工，可以订餐（如果未登录，需先登录）、注册工资支付、预约规律的订餐，在特殊情况下可以覆盖预订。餐厅员工是特殊顾客，可以进行备餐、生成付费请求和请求送餐，其中对于注册工资支付的顾客生成付费请求并发送给工资系统。菜单管理员是餐厅特定员工，可以管理菜单。送餐员可以打印送餐说明，记录送餐信息（如送餐时间）以及记录收费（对于没有注册工资支付的顾客，由送餐员收取现金后记录）。顾客订餐过程如下：1顾客请求查看菜单；2系统显示菜单和今日特价；3顾客选菜；4系统显示订单和价格；5顾客确认订单；6系统显示可送餐时间；7顾客指定送餐时间、地点和支付方式；8系统确认接受订单，然后发送 E-mail 给顾客以确认订餐，同时发送相关订餐信息通知给餐厅员工。系统采用面向对象方法开发，使用 UML 进行建模。系统的顶层用例图和一次订餐的活动图初稿分别如图 3-1 和图 3-2 所示。2009 年下半年 软件设计师 下午试卷 27 图 3-1 COS 系统顶层用例图 图 3-2 一次订餐的活动图 28 2009 年下半年 软件设计师 下午试卷 【问题 1】（2 分）根据说明中的描述，给出图 3-1 中 A1 和 A2 所对应的参与者。【问题 2】（8 分）根据说明中的描述，给出图 3-1 中缺少的四个用例及其所对应的参与者。【问题 3】（4 分）根据说明中的描述，给出图 3-2 中（1）（4）处对应的活动名称或图形符号。【问题 4】（1 分）指出图 3-1 中员工和顾客之间是什么关系，并解释该关系的内涵。2009 年下半年 软件设计师 下午试卷 29 试题四试题四（共（共 15 分）分）阅读下列说明和伪代码，回答问题 1 和问题 2，将解答填入答题纸的对应栏内。【说明】0-1 背包问题可以描述为：有个物品，对=1,2,，第个物品价值为，重量为（和为非负数），背包容量为（为非负数），选择其中一些物品装入背包，使装入背包物品的总价值最大，即=1，且总重量不超过背包容量，即=1，其中，0,1，=0 表示第个物品不放入背包，=1 表示第个物品放入背包。用回溯法求解此 0-1 背包问题，请填充下面伪代码中（1）（4）处空缺。回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点己经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判 断并 剪枝 那些即 使扩 展了 也不 能得到 最优 解的 结点。现在 假设 已经 设计 了BOUND(,)函数，其中、和分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。下面给出 0-1 背包问题的回溯算法伪代码。函数参数说明如下：W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。变量说明如下：cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。30 2009 年下半年 软件设计师 下午试卷 【问题 1】（8 分）根据说明和伪代码，填充伪代码中的空（1）（4）。2009 年下半年 软件设计师 下午试卷 31【问题 2】（7 分）考虑下表所示的实例，假设有 3 个物品，背包容量为 22。下图是根据上述算法构造的搜索树，其中结点的编号表示了搜索树生成的顺序，边上的数字 1/0 分别表示选择/不选择对应物品。除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品 （5），获得的价值为 （6）。对于上述实例，若采用穷举法搜索整个解空间，则搜索树的结点数为 （7），而用了上述回溯法，搜索树的结点数为 （8）。32 2009 年下半年 软件设计师 下午试卷 试题试题五（共五（共 15 分）分）阅读下列说明和 C+代码，将应填入 （n）处的字句写在答题纸的对应栏内。【说明】现欲构造一文件/目录树，采用组合（Composite）设计模式来设计，得到的类图如下图所示：2009 年下半年 软件设计师 下午试卷 33【C+代码】#include#include#include using namespace std;class AbstractFile protected:string name;/文件或目录名称 public:void printName()cout name;/给一个目录增加子目录或文件 virtual void addChild(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(AbstractFile*file)return;(2)*getChildren()return (3);34 2009 年下半年 软件设计师 下午试卷 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()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-addChild(windowsFolder);compositeFolder-addChild(file);2009 年下半年 软件设计师 下午试卷 35 试题六试题六（共（共 15 分）分）阅读下列说明和 Java 代码，将应填入 （n）处的字句写在答题纸的对应栏内。【说明】现欲构造一文件/目录树，采用组合（Composite）设计模式来设计，得到的类图如下图所示：【Java 代码】import java.util.ArrayList;import java.util.List;36 2009 年下半年 软件设计师 下午试卷 (1)class AbstractFile protected String name;public void printName()System.out.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 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);public boolean removeChild(AbstractFile file)return childList.remove(file);public (3)getChildren()return (4);2009 年下半年 软件设计师 下午试卷 37 public class Client public static void main(String args)/创造一个树形的文件/目录结构 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.addChild(windowsFolder);compositeFolder.addChild(file);/打印目录文件数 printTree(rootFolder);private static void printTree(AbstractFile ifile)ifile.printName();List children=ifile.getChildren();if(Children=null)return;for(AbstractFile file:Children)(5);该程序运行后输出结果为：c:composite TestCompsite.java Windows 38 2009 年下半年 软件设计师 下午试卷 试题试题七（共七（共 15 分）分）阅读以下说明和 C 程序，将应填入 （n）处的字句写在答题纸的对应栏内。【说明】先有 n（n 1000）节火车车厢，顺序编号为 1，2，3，n，按编号连续依次从 A方向的铁轨驶入，从 B 方向铁轨驶出，一旦车厢进入车站（Station）就不能再回到 A 方向的铁轨上；一旦车厢驶入 B 方向铁轨就不能再回到车站，如下图所示，其中 Station 为栈结构，初始为空且最多能停放 1000 节车厢。下面的 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 2009 年下半年 软件设计师 下午试卷 39【C 程序】#include /*此处为栈类型及其基本操作的定义，省略*/int main()STACK station;int state1000;int n;/*车厢数*/int begin,i,j,maxNo;/*maxNo 为 A 端正待入栈的车厢编号*/printf(请输入车厢数：);scanf(%d,&n);printf(请输入需要判断的车厢编号序列（以空格分隔）：);if(n 1)return-1;/*读入需要驶出的车厢编号序列，存入数组 state*/for(i=0;i n;i+)scanf(%