2016年上半年（下午）《软件设计师》真题

2016年上半年（下午）软件设计师真题注意：图片可根据实际需要调整大小卷面总分：6分答题时间：240分钟试卷题量：6题练习次数：0次 问答题 （共6题，共6分）1.某软件系统中，已设计并实现了用于显示地址信息的类Address（如图5-1所示），现要求提供基于Dutch语言的地址信息显示接口。为了实现该要求并考虑到以后可能还会出现新的语言的接口，决定采用适配器（Adapter）模式实现该要求，得到如图5-1所示的类图。图5-1适配器模式类图【C+代码】#includeiostreamusing namespace std;class Addresspublic:void stree（）/*实现代码省略*/void zip（）/*实现代码省略*/void city（）/*实现代码省略*/其他成员省略;class DutchAddresspublic:virtual void straat（）=0;virtual void postcode（）=0;virtual void plaats（）=0;/其他成员省略;class DutchAddressAdapter:public DutchAddressprivate:（1）;public:DutchAddressAdapter(Address*addr)address=addr;void straat（）（2）;void postcode（）（3）;void plaat（）（4）;/其他成员省略;void testDutch(DutchAddress*addr)addr-straat（）;addr-postcode（）;addr-plaats（）;int main（）Address*addr=new Address（）;（5）;coutn The DutchAddressnendl;testDutch(addrAdapter);return 0; 正确答案： 本题解析： （1）Address*address; （2）address-street();（3）address-zip();（4）address-city();（5）DutchAddress*addrAdapter=new DutchAddressAdaptor(addr);本题考查的是面向对象程序设计，结合设计模式。本题涉及的设计模式是适配器。对于代码填空，可以参照类图和代码上下文补充。首先理清类与类之间的继承关系，再根据上下文填写。对于第（1）空，DutchAddressAdapter继承了DutchAddress方法，根据下面的同名构造函数可知，该类定义了一个名叫address的参数，而根据代码上下文可以，address的类型为Address。本空应该填写Address*address。第（2）（3）（4）空是接口转换的具体实现，而在DutchAddressAdapter涉及的方法，可以从类图中找到，分别是straat()，postcode()，plaats()，适配器的目的是接口转换，即用这些方法分别展现原有Address中的street()、zip()、city()方法，因此这3个空分别填写address-street()、address-zip()、address-city()。对于第（5）空，根据上下文最终调用testDutch方法的对象是addrAdapter，而此处是将原有的Address对象addr转换为接口对象，因此此处填写DutchAddress*addrAdapter=new DutchAddressAdapter(addr)。 2.某会议中心提供举办会议的场地设施和各种设备，供公司与各类组织机构租用。场地包括一个大型报告厅、一个小型报告厅以及诸多会议室。这些报告厅和会议室可提供的设备有投影仪、白板、视频播放/回放设备、计算机等。为了加强管理，该中心欲开发一会议预订系统，系统的主要功能如下。（1）检查可用性。客户提交预订请求后，检查预订表，判定所申请的场地是否在申请日期内可用；如果不可用，返回不可用信息。（2）临时预订。会议中心管理员收到客户预定请求的通知之后，提交确认。系统生成新临时预订存入预订表，并对新客户创建一条客户信息记录加以保存。根据客户记录给客户发送临时预订确认信息和支付定金要求。（3）分配设施与设备。根据临时预订或变更预定的设备和设施需求，分配所需设备（均能满足用户要求）和设施，更新相应的表和预订表。（4）确认预订。管理员收到客户支付定金的通知后，检查确认，更新预订表，根据客户记录给客户发送预订确认信息。（5）变更预订。客户还可以在支付余款前提交变更预订请求，对变更的预订请求检查可用性，如果可用，分配设施和设备；如果不可用，返回不可用信息。管理员确认变更后，根据客户记录给客户发送确认信息。（6）要求付款。管理员从预订表中查询距预订的会议时间两周内的预定，根据客户记录给满足条件的客户发送支付余款要求。（7）支付余款。管理员收到客户余款支付的通知后，检查确认，更新预订表中的已支付余款信息。现采用结构化方法对会议预定系统进行分析与设计，获得如图1-1所示的上下文数据流图和图1-2所示的0层数据流图（不完整）。图1-1上下文数据流图图1-2 0层数据流图【问题1】（2分）使用说明中的词语，给出图1-1中的实体E1E2的名称。【问题2】（4分）使用说明中的词语，给出图1-2中的数据存储D1D4的名称。【问题3】（6分）根据说明和图中术语，补充图1-2之中缺失的数据流及其起点和终点。【问题4】（3分）如果发送给客户的确认信息是通过Email系统向客户信息中的电子邮件地址进行发送的，那么需要对图1-1和1-2进行哪些修改？用150字以内文字加以说明。 正确答案： 本题解析： 【问题1】 E1：客户E2：管理员【问题2】D1：预定表D2：客户信息记录表D3：设施表（场地表或场地设施表）D4：设备表注：D3、D4可互换【问题3】【问题4】图1-1中：增加外部实体“第三方Email系统”，将临时预订/预订/变更确认信息终点均修改至“第三方Email系统”。图1-2中：增加外部实体“第三方Email系统”，增加加工“发送邮件”，将临时预订/预订/变更确认信息终点均修改至“发送邮件”加工，并增加从D2到“发送邮件”加工的数据流“电子邮件地址”，再从发送邮件加工引出数据流临时预订/预订/变更确认信息终点为第三方Email系统。本题考查数据流图（DFD）应用于采用结构化方法进行系统分析与设计，是比较传统的题目，要求考生细心分析题目中所描述的内容。DFD是一种便于用户理解、分析系统数据流程的图形化建模工具，是系统逻辑模型的重要组成部分。【问题1】本题要求找到图1-1中实体对应关系，从题干描述，可以找到两个实体，客户和会议中心管理员，由“客户提交预订请求后，检查预订表，判定所申请的场地是否在申请日期内可用；如果不可用，返回不可用信息。”提交预定申请并且接收不可用信息的是客户，因此E1为客户；“会议中心管理员收到客户预定请求的通知之后，提交确认”接收预定请求的通知，并且提交确认的是会议中心管理员，因此E2为管理员。【问题2】本题要求找到图1-2中存储对应关系。由“客户提交预订请求后，检查预订表，判定所申请的场地是否在申请日期内可用；如果不可用，返回不可用信息。”可知此处有预订表存储，与1检查可用性交互，因此D1为预订表。由“系统生成新临时预订存入预订表，并对新客户创建一条客户信息记录加以保存”，此处与2临时预定有交互的是预订表和保存客户信息记录的存储，预订表已确定为D1，因此D2为存储客户信息记录的文件，可命名为客户记录、客户表、客户信息记录表等形式。由“根据临时预订或变更预定的设备和设施需求，分配所需设备（均能满足用户要求）和设施，更新相应的表和预订表”，此处与3分配设施与设备相关的存储由预订表，设施和设备相应的表，因此D3、D4为设施表、设备表，二者可互换。【问题3】本题要求找到图1-2中缺失的数据流。对于缺失数据流的查找，一般首先根据父图与子图平衡的原则查找，再根据题干说明查找，一般来说题干中的说明都可以在图中找到对应的数据流。根据子图与父图平衡原则：图1-1由付款凭据数据流，而在1-2中对应由已支付定金凭据，是对父图数据流的拆分，因此此处缺失已支付余款凭据，起点为E1客户，终点为7支付余款。图1-1有系统到客户的预定确认信息，而1-2中没有，因此此处缺失数据流预定确认信息，起点是4确认预定，终点是E1客户。根据题干描述查找：根据“（4）确认预订。管理员收到客户支付定金的通知后，检查确认，更新预订表，根据客户记录给客户发送预订确认信息”，对于4确认预定加工，有输出到管理员的客户支付定金通知，输出到预订表更新支付确认，输出到客户，发送预定确认信息（上面已补充此数据流），此时缺少根据客户记录，即起点为客户表的输入数据流-客户记录。对于5变更预定、6要求付款，都需要根据客户记录发送消息，因此都缺失起点为客户表的客户记录数据流，同时，对于6要求付款加工还需要“管理员从预订表中查询距预订的会议时间两周内的预订”，此处还缺少查询预订结果的返回，即起点为D1预订表的“距预订的会议时间两周内的预订”数据流。【问题4】图1-1中：增加外部实体“第三方Email系统”，将临时预订/预订/变更确认信息终点均修改至“第三方Email系统”。图1-2中：增加外部实体“第三方Email系统”，增加加工“发送邮件”，将临时预订/预订/变更确认信息终点均修改至“发送邮件”加工，并增加从D2到“发送邮件”加工的数据流“电子邮件地址”，再从发送邮件加工引出数据流，临时预订/预订/变更确认信息终点为第三方Email系统。如下图所示： 3.某销售公司当前的销售业务为商城实体店销售。现该公司拟开展网络销售业务，需要开发一个信息化管理系统。请根据公司现有业务及需求完成该系统的数据库设计。【需求描述】（1）记录公司所有员工的信息。员工信息包括工号、身份证号、姓名、性别、出生日期和电话，并只登记一部电话。（2）记录所有商品的信息。商品信息包括商品名称、生产厂家、销售价格和商品介绍。系统内部用商品条码唯一区别每种商品。（3）记录所有顾客的信息。顾客信息包括顾客姓名、身份证号、登录名、登录密码、和电话号码。一位顾客只能提供一个电话号码。系统自动生成唯一的顾客编号。（4）顾客登录系统之后，在网上商城购买商品。顾客可将选购的商品置入虚拟的购物车内，购物车可长期存放顾客选购的所有商品。顾客可在购物车内选择商品、修改商品数量后生成网购订单。订单生成后，由顾客选择系统提供的备选第三方支付平台进行电子支付，支付成功后系统需要记录唯一的支付凭证编号，然后由商城根据订单进行线下配送。（5）所有的配送商品均由仓库统一出库。为方便顾客，允许每位顾客在系统中提供多组收货地址、收货人及联系电话。一份订单所含的多个商品可能由多名分拣员根据商品所在仓库信息从仓库中进行分拣操作，分拣后的商品交由配送员根据配送单上的收货地址进行配送。（6）新设计的系统要求记录实体店的每笔销售信息，包括营业员、顾客、所售商品及其数量。【概念模型设计】根据需求阶段收集的信息，设计的实体联系图（不完整）如图所示。【逻辑结构设计】根据概念模型设计阶段完成的实体联系图，得出如下关系模式（不完整）：员工（工号，身份证号，姓名，性别，出生日期，电话）商品（商品条码，商品名称，生产厂家，销售价格，商品介绍，（a）顾客（顾客编号，姓名，身份证号，登录名，登录密码，电话）收货地点（收货ID，顾客编号，收货地址，收货人，联系电话）购物车（顾客编号，商品条码，商品数量）订单（订单ID，顾客编号，商品条码，商品数量，（b）分检（分拣ID，分拣员工号，（c），分拣时间）配送（配送ID，分拣ID，配送员工号，收货ID，配送时间，签收时间，签收快照）销售（销售ID，营业员工号，顾客编号，商品条码，商品数量）【问题1】（4分）补充图中的“配送“联系所关联的对象及联系类型。【问题2】（6分）补充逻辑结构设计中的（a）、（b）和（c）三处空缺。【问题3】（5分）对于实体店销售，若要增加送货上门服务，由营业员在系统中下订单，与网购的订单进行后续的统一管理。请根据该需求，对图进行补充，并修改订单关系模式。 正确答案： 本题解析： 【问题1】 补充内容如图中虚线所示：【问题2】（a）所在仓库（b）支付凭证（c）订单ID，商品条码【问题3】补充内容如图中虚线所示：关系模式：订单（订单ID，顾客编号（FK），商品条码（FK），商品数量，销售ID（FK），支付凭证）。注：用FK标注外键。本题考查数据库概念结构设计和逻辑结构设计。此类题目要求考生认真阅读题目中的需求描述，配合已给出的E-R图，理解概念结构设计中设计者对实体及联系的划分和组织方法，结合需求描述完成E-R图中空缺部分，并使用E-R图向关系模式的转换方法，完成逻辑结构设计。【问题1】根据所给E-R图，结合需求描述，购物车作为顾客和商品之间的联系，而订单由顾客从购物车中选择商品生成，因此将购物车这一联系当作实体，与订单实体产生联系。将联系当作实体参与另一联系，称为聚合，通常当后一联系与此联系相关时，采用这种设计方法。顾客可以从购物车中生成多个订单，一个订单只能从一个购物车里提取商品，属于一对多联系。根据需求描述中的“分拣后的商品交由配送员根据配送单上的收货地址进行配送。”可以知道，配送是与分拣联系相关的联系，同样的，将分拣联系进行聚合，参与配送联系，同时参与配送联系的还有配送员和地点，为多对多对多联系，语义为配送员根据分拣结构按照收货地点进行配送，与需求相符。【问题2】本小题考核E-R图向关系模式的转换。由于E-R图中没有画出实体及联系的属性，需要根据需求描述进行补充。根据需求中的“一种商品只能放在一个仓库中”和“一份订单所含的多个商品可能由多名分拣员根据商品的所在仓库信息从仓库中进行分拣操作”，可以确定“所在仓库”作为商品实体的属性，转入商品关系中。订单关系由E-R图中的订单实体和一对多联系网站合并而成，取一方的主码，即购物车这一联系的主码，为参与该联系的实体的主码商品条码和顾客编号，加上网购联系的属性数量，并入到订单实体转成的关系模式中。订单ID为订单实体的标识符，订单实体的其他属性需要通过需求描述中获取。根据需求“订单生成后，由顾客选择系统提供的备选第三方支付平台进行电子支付，支付成功后系统需要记录唯一的支付凭证编号”，支付凭证编号应为订单的属性，转入订单关系中。E-R图中的分拣联系为分拣员与订单之间的多对多联系，转换成独立的分拣关系模式，应包含分拣员实体的标识符分拣员工号和订单实体的标识符订单ID，“一份订单所含的多个商品可能由多名分拣员根据商品所在仓库信息从仓库中进行分拣操作”，需要补充商品条码号加以区分，及分拣联系的属性分拣时间。【问题3】实体店的订单是营业员根据销售结果生成的，将销售联系聚合成实体，与订单产生联系。一笔销售对应一个订单，一个订单对应一笔销售，为一对一联系。转换为关系模式时，将此联系归入订单关系，即取销售的标识符销售ID加入到订单关系模式中。 4.某软件公司欲设计实现一个虚拟世界仿真系统。系统中的虚拟世界用于模拟现实世界中的不同环境（由用户设置并创建），用户通过操作仿真系统中的12个机器人来探索虚拟世界。机器人维护着两个变量b1和b2，用来保存从虚拟世界中读取的字符。该系统的主要功能描述如下：（1）机器人探索虚拟世界（RunRobots）。用户使用编辑器（Editor）编写文件以设置想要模拟的环境，将文件导入系统（LoadFile）从而在仿真系统中建立虚拟世界（SetupWorld）。机器人在虚拟世界中的行为也在文件中进行定义，建立机器人的探索行为程序（SetupProgram）。机器人在虚拟世界中探索时（RunProgram），有2种运行模式：自动控制（Run）：事先编排好机器人的动作序列（指令（Instruction），执行指令，使机器人可以连续动作。若干条指令构成机器人的指令集（InstructionSet）。单步控制（Step）：自动控制方式的一种特殊形式，只执行指定指令中的一个动作。（2）手动控制机器人（ManipulateRobots）。选定1个机器人后（SelectRobot），可以采用手动方式控制它。手动控制有4种方式：Move：机器人朝着正前方移动一个交叉点。Left：机器人原地沿逆时针方向旋转90度。Read：机器人读取其所在位置的字符，并将这个字符的值赋给b1；如果这个位置上没有字符，则不改变b1的当前值。Write：将b1中的字符写入机器人当前所在的位置，如果这个位置上已经有字符，该字符的值将会被b1的值替代。如果这时b1没有值，即在执行Write动作之前没有执行过任何Read动作，那么需要提示用户相应的错误信息（ShowErrors）。手动控制与单步控制的区别在于，单步控制时执行的是指令中的动作，只有一种控制方式，即执行下个动作；而手动控制时有4种动作。现采用面向对象方法设计并实现该仿真系统，得到如图3-1所示的用例图和图3-2所示的初始类图。图3-2中的类“Interpreter”和“Parser”用于解析描述虚拟世界的文件以及机器人行为文件中的指令集。图3-1用例图图3-2初始类图【问题1】（6分）根据说明中的描述，给出图3-1中U1U6所对应的用例名。【问题2】（4分）图3-1中用例U1U6分别与哪个（哪些）用例之间有关系，是何种关系？【问题3】（5分）根据说明中的描述，给出图3-2中C1C5所对应的类名。 正确答案： 本题解析： 【问题1】 U1/U2：Run、StepU3：WriteU4/U5/U6：Move、Left、Read【问题2】U1和U2和RunProgram有泛化关系。U3，U4，U5，U6和Manipulate Robots有泛化关系。【问题3】C1：World/虚拟世界C2：RobotsC3：InstructionC4：InstructionSetC5：Errors本题考查的是面向对象UML建模内容，涉及到用例图和类图。在本题中部分信息隐含，有一定难度，需要认真阅读并理解题干说明。【问题1】问题1要求补充U1U6用例名，答案可根据题干说明和图示关系判断，较为容易，具体分析过程如下：（1）对于U1、U2用例与Run Program相关，从题干说明“机器人在虚拟世界中探索时（RunProgram），有2种运行模式：自动控制（Run）单步控制（Step）”，因此可以判断U1、U2分别为Run和Step用例，二者位置可以互换。（2）从题干说明“手动控制机器人（ManipulateRobots）。选定1个机器人后（SelectRobot），可以采用手动方式控制它。手动控制有4种方式：Move：Left：Read：Write：”可以看到与ManipulateRobots相关的用例有Move，Left，Read，Write，又根据Write的说明“即在执行Write动作之前没有执行过任何Read动作，那么需要提示用户相应的错误信息（ShowErrors）”可以看到，与ShowErrors相关的用例是Write，即U3为Write。剩余U4、U5、U6分别为Move、Left、Read，三者位置可以互换。【问题2】判断用例之间的关系。用例之间的关系有三种：泛化、扩展和包含。包含关系：其中这个提取出来的公共用例称为抽象用例，而把原始用例称为基本用例或基础用例系。当可以从两个或两个以上的用例中提取公共行为时，应该使用包含关系来表示它们。扩展关系：如果一个用例明显地混合了两种或两种以上的不同场景，即根据情况可能发生多种分支，则可以将这个用例分为一个基本用例和一个或多个扩展用例，这样使描述可能更加清晰。泛化关系：当多个用例共同拥有一种类似的结构和行为的时候，可以将它们的共性抽象成为父用例，其他的用例作为泛化关系中的子用例。在用例的泛化关系中，子用例是父用例的一种特殊形式，子用例继承了父用例所有的结构、行为和关系。（1）RunProgram有两种运行模式，即Run和Step分别是RunProgram的一种，二者与RunProgram是特殊/一般的关系，RunProgram与U1、U2是泛化关系。（2）同理，Move、Left、Read、Write分别是手动控制的四种方式之一，因此，这四者与Manipulate Robots是特殊/一般的关系，即Manipulate Robots与U3、U4、U5、U6是泛化关系。【问题3】问题3由于部分信息隐含，所以难度较大。（1）首先根据类图，存在2组部分与整体的关系，分别是C3-C4，C1-C2，其中多重度关系：C4包含1n个C3，C1包含12个C2，且C1和C4都与Interpreter、Parser有关。（2）根据说明“类“Interpreter”和“Parser”用于解析描述虚拟世界的文件以及机器人行为文件中的指令集”，因此C1、C4分别是虚拟世界的文件和机器人行为文件中的指令集，后者题干给出为Instruction Set。其中满足1n多重度的应该为指令Instruction和InstructionSet，因此，C3为Instruction，C4为InstructionSet。C1是虚拟世界的文件，可以写作World（题干中虚拟世界只描述为World）。对于C2与World有12的多重度关系，根据题干说明，只有“用户通过操作仿真系统中的12个机器人来探索虚拟世界”符合要求，因此C2为机器人（Robot/Robots）。（3）剩下C5与World相关，根据题干描述“用户使用编辑器（Editor）编写文件以设置想要模拟的环境，将文件导入系统（LoadFile）从而在仿真系统中建立虚拟世界（SetupWorld）”，因此建立虚拟世界需要编辑器编辑文件，并将文件导入仿真系统，因此C5为仿真系统。 5.某软件系统中，已设计并实现了用于显示地址信息的类Address（如图6-1所示），现要求提供基于Dutch语言的地址信息显示接口。为了实现该要求并考虑到以后可能还会出现新的语言的接口，决定采用适配器（Adapter）模式实现该要求，得到如图6-1所示的类图。图6-1适配器模式类图【Java代码】import java.util.*;Class Addresspublic void street（）/实现代码省略public void zip（）/实现代码省略public void city（）/实现代码省略/其他成员省略;class DutchAddresspublic void straat（）/实现代码省略public void postcode（）/实现代码省略public void plaats（）/实现代码省略/其他成员省略;class DutchAddressAdapter extends DutchAddressprivate（1）;public DutchAddressAdapter(Address addr)address=addr;public void straat（）（2）;public void postcode（）（3）;public void plaats（）（4）;/其他成员省略;class Testpublic static void main(Stringargs)Address addr=new Address（）;（5）;System.out.println(n The DutchAddressn);testDutch(addrAdapter);Static void?testDutch(DutchAddress addr)addr.straat（）;addr.postcode（）;addr.plaats（）; 正确答案： 本题解析： （1）Address address; （2）address.street();（3）address.zip();（4）address.city();（5）DutchAddress addrAdapter=new DutchAddressAdapter(addr);本题考查的是面向对象程序设计，结合设计模式。本题涉及的设计模式是适配器。对于代码填空，可以参照类图和代码上下文补充。首先理清类与类之间的继承关系，再根据上下文填写。对于第（1）空，DutchAddressAdapter继承了DutchAddress方法，根据下面的同名构造函数可知，该类定义了一个名叫address的参数，而根据代码上下文可以，address的类型为Address。本空应该填写Address?address；第（2）（3）（4）空是接口转换的具体实现，而在DutchAddressAdapter涉及的方法，可以从类图中找到，分别是straat()，postcode()，plaats()，适配器的目的是接口转换，即用这些方法分别展现原有Address中的street()、zip()、city()方法，因此这3个空分别填写address.street()、address.zip()、address.city()。对于第（5）空，根据上下文最终调用testDutch方法的对象是addrAdapter，而此处是将原有的Address对象addr转换为接口对象，因此此处填写DutchAddress addrAdapter=new?DutchAddressAdapter(addr)。 6.在一块电路板的上下两端分别有n个接线柱。根据电路设计，用(i,(i)表示将上端接线柱i与下端接线柱(i)相连，称其为该电路板上的第i条连线。如图4-1所示的(i)排列为8,7,4,2,5,1,9,3,10,6。对于任何1ijn，第i条连线和第j条连线相交的充要条件是(i)(j)。图4-1电路布线示意在制作电路板时，要求将这n条连线分布到若干绝缘层上，在同一层上的连线不相交。现在要确定将哪些连线安排在一层上，使得该层上有尽可能多的连线，即确定连线集Nets=(i,(i)，1in的最大不相交子集。【分析问题】记N(i,j)=t|(t,(t)Nets,ti,(t)j。N(i,j)的最大不相交子集为MNS(i,j)，size(i,j)=|MNS(i,j)|。经分析，该问题具有最优子结构性质。对规模为n的电路布线问题，可以构造如下递归式：【C代码】下面是算法的C语言实现。（1）变量说明sizeij：上下端分别有i个和j个接线柱的电路板的第一层最大不相交连接数pii：(i)，下标从1开始（2）C程序#includestdlib.h#includestdio.h#define?N?10/*问题规模*/int m=0；/*记录最大连接集合中的接线柱*/void maxNum(int pi,int sizeN+1N+1,int n)/*求最大不相交连接数*/int i,j;for(j=0;jpi1;j+)size1j=0;/*当j(1)时*/for(j=pi1;j=n;j+)（1）;/*当j=(1)时*/for(i=2;in;i+)for(j=0;jpii;j+)（2）;/*当jpii时*/for(j=pii;j=n；j+)/*当j=ci时,考虑两种情况*/sizeij=sizei-1j=sizei-1pii-1+1?sizei-1j:sizei-1pii-1+1;/*最大连接数*/sizenn=sizen-1n=sizen-1pin-1+1?sizen-1n:sizen-1pin-1+1;/*构造最大不相交连接集合，neti表示最大不相交子集中第i条连线的上端接线柱的序号*/void constructSet（int pi,int sizeN+1N+1,int n,int netn）int i,j=n;m=0；for(i=n;i1;i-)/*从后往前*/if(sizeij!=sizei-1j)/*(i,pii)是最大不相交子集的一条连线*/（3）;/*将i记录到数组net中，连接线数自增1*/j=pii-1;/*更新扩展连线柱区间*/if(j=pi1)netm+=1;/*当i=1时*/【问题1】（6分）根据以上说明和C代码，填充C代码中的空（1）（3）。【问题2】（6分）据题干说明和以上C代码，算法采用了（4）算法设计策略。函数maxNum和constructSet的时间复杂度分别为（5）和（6）（用O表示）。【问题3】（3分）若连接排列为8,7,4,2,5,1,9,3,10,6，即如图4-1所示，则最大不相交连接数为（7），包含的连线为（8）（用(i,(i)的形式给出）。 正确答案： 本题解析： 【问题1】 （1）size1j=1（2）sizeij=sizei-1j（3）netm+=i;【问题2】（4）动态规划算法（5）O(n2)（6）O(n)【问题3】（7）4（8）（3，（3），（5，（5），（7，（7），（9，（9）或：（3，4），（5，5），（7，9），（9，10）本题是算法设计题，涉及的算法策略是动态规划法。【问题1】本题要求补充代码，主要参照代码注释、题干的算法思路和递归式即可得到。对于第（1）空，有注释“当j=(1)时”，此时属于i=1的其他情况，找到递归式的条件，所以（1）空填写size1j=1；对于第（2）空，有注释“当j(i)时”，此时属于i1时，j(i)的条件，找到递归式对应条件，所以（2）空填写sizeij=sizei-1j；对于第（3）空，有注释“将i记录到数组net中，连接线数自增1”，将i记录到net数组，即net=i，其中net位置应该时连接线数m，此时为m+，因此（3）空填写netm+=i。本空也可以根据后面的代码推导。【问题2】1、根据题干描述“经分析，该问题具有最优子结构性质。对规模为n的电路布线问题，可以构造如下递归式”，根据最优子结构可判断本题使用的是动态规划法的算法策略。2、根据代码，可以看到maxNum函数有两层嵌套循环，因此时间复杂度为O(n2)。3、根据代码，可以看到constructSet函数只有一层循环结构，因此事件复杂度为O(n)。【问题3】这个是动态规划问题，不相交的平行线。设aij为上端接线柱i与下端接线柱j前的最大不相交子集，则：若i与j不相连，则i与j前的最大不想交子集等于i与j-1前或i-1与j前的最大不相交子集的最大值，即aij=max(aij-1,ai-1j)若i与j相连，则i与j前的最大不想交子集等于i-1与j-1前的最大不想交子集加1，即aij=ai-1j-1+1题目的意思就是要求出，没有交叉的这种连线的数量达到最大的情况。此时，有4条这样的线不会交叉，所以是大不相交子集连接数为4。如果你能找到5条这样不交叉的线，则是5。就这个意思。由此可得，最大不相交连接数为4，包含的连接线为：（3，（3），（5，（5），（7，（7），（9，（9）