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

2012年下半年（下午）软件设计师真题注意：图片可根据实际需要调整大小卷面总分：6分答题时间：240分钟试卷题量：6题练习次数：0次 问答题 （共6题，共6分）1.某城市的各国家公园周边建造了许多供游客租用的小木屋和营地，为此，该城市设置了一个中心售票处和若干个区域售票处。游客若想租用小木屋或营地，必须前往中心售票处进行预定并用现金支付全额费用。所有的预定操作全部由售票处的工作人员手工完成。现欲开发一信息系统，实现小木屋和营地的预定及管理功能，以取代手工操作。该系统的主要功能描述如下：1管理预定申请。游客可以前往任何一个售票处提出预定申请。系统对来自各个售票处的预定申请进行统一管理。2预定。预定操作包含登记游客预定信息、计算租赁费用、付费等步骤。3支付管理。游客付费时可以选择现金和信用卡付款两种方式。使用信用卡支付可以享受3%的折扣，现金支付没有折扣。4游客取消预定。预定成功之后，游客可以在任何时间取消预定，但需支付赔偿金，剩余部分则退还给游客。赔偿金的计算规则是，在预定入住时间之前的48小时内取消，支付租赁费用10%的赔偿金；在预定入住时间之后取消，则支付租赁费用50%的赔偿金。5自动取消预定。如果遇到恶劣天气（如暴雨、山洪等），系统会自动取消所有的预定，发布取消预定消息，全额退款。6信息查询。售票处工作人员查询小木屋和营地的预定情况和使用情况，以判断是否能够批准游客的预定申请。现采用面向对象方法开发上述系统，得到如表3-1所示的用例列表和表3-2所示的类列表。对应的用例图和类图分别如图3-1和3-2所示。表3-1表3-2类列表图3-1用例图【问题1】（6分）根据说明中的描述与表3-1，给出图3-1中UC1UC6处所对应的用例名称。【问题2】(7分)根据说明中的描述与表3-2，给出图3-2中C1C7处所对应的类名。【问题3】（2分）对于某些需求量非常大的小木屋或营地，说明中功能4的赔偿金计算规则，不足以弥补取消预定所带来的损失。如果要根据预定的时段以及所预定场地的需求量，设计不同层次的赔偿金计算规则，需要对图3-2进行怎样的修改？（请用文字说明） 正确答案： 本题解析： 【问题1】 UC1:CheckAvailability?UC2:MakeReservationUC3:GetDiscount?UC4:MangeCashPaymentUC5:ManageCrCardPayment UC6:CalcuateRefund注：4和5可以互换【问题2】C1 NationaIPark C2:RateC3:TicketingOfficer C4:PaymentC5:Discount C6:CasbPaymentC7:CreditCardPayment注：6和7可以互换【问题3】解答1：增加一个新的类该类与类Reservationltem之间有关联关系。或解答2：修改Rate类使其具有计算赔偿金的功能。回答出其中一种修改方式即可。本题考查用例图和类图。涉及到用例之间的关系、类之间的关系等问题。【问题1】本题要我们补充完整用例图，这是考试中常考的知识点。在题目的描述中，其实已经给出了本题中相关的用例，我们只需要通过阅读题目的描述，理解清楚这些用例之间的关系，然后结合用例图就可以完成这个问题。在用例图中，只有一个参与者，就是售票处工作人员，通过题目的描述，我们不难知道，他应该与自动取消预订、游客取消预定、管理预定申请和信息查询这些用例有直接关系，因此可以知道用例UC2是预定用例（MakeReservation）。而从用例图中可以看出，UC1与信息查询和管理预定申请都是一种包含关系，说明用例UC1是预定和管理预定申请这两个用例必须都经历的一种行为，因此可以知道此用例是信息查询（CheckAvailability）。而UC3是支付管理的包含用例，根据题目的描述不难知道，在每次付款时，都要首先计算付款折扣，因此，支付管理用例肯定包含了计算付款折扣这个用例，因此UC3就是计算付款折扣（GetDiscount）。而支付方式有现金支付和信用卡支付两种方式，这两种方式与支付管理是一种泛化关系，因此可以UC4和UC5分别是现金支付（MangeCashPayment）和信用卡支付（ManageCrCardPayment），当然，他们俩的位置可以互换。另外，从用例图不难看出，UC6是游客取消预定和系统自动取消预定用例所包含的用例，而这两个用例都必须包含的部分是计算机赔偿金，因此UC6是计算取消预定的赔偿金（CalcuateRefund）。【问题2】本题要我们补充完整类图，也是考试中常考的知识点。题目中给出了相关的类，要我们根据题目的描述并结合类图来完成。C1与类预定申请内容是一种组合关系，而其内容其实就是供游客租用的小木屋和营地以及它们的价格等信息，再结合类图可知，C1应该是国家公园。而从类图可以看出，C2聚合而成预定申请内容类，那么根据前面的分析，不难知道C2是租凭费用类。而从类图不难看出，C6和C7是继承与C4，而从题目的分析中，只有付款、现金支付、信用卡支付存在这种继承关系，因此可以确定C4是付款，而C6和C7分别对应现金支付和信用卡支付。位置可以互换。这样就剩下C3和C5没有确定，而没有确定的类还有售票处和付款折扣。其中C3与预定申请有关，根据题目描述，预定申请是要提交给售票处的，因此可以确定C3就是售票处，而付款的时候有个付款折扣信息，因此C5就是付款折扣。【问题3】问题3主要是要设计赔偿金计算规则，要实现这个功能，可以添加一个类来实现，这类要与类Reservationltem之间有关联关系，也可以在原来的类中实现，如果是这样，就应该是类Rate中实现，因为这个类实现的是租凭费用，且这个类与Reservationltem之间是一种聚合的关联关系。 2.现欲开发一个软件系统，要求能够同时支持多种不同的数据库，为此采用抽象工厂模式设计该系统。以SQL Server和Access两种数据库以及系统中的数据库表Department为例，其类图如图5-1所示。图5-1类图【C+代码】#includeiostreamusing namespace std;class Department/*代码省略*/；class IDepartmentpublic:(1)=0；(2)=0；class SqlserverDepartment:(3)public:void Insert(Department*department)coutInsert a record into Department in SQL Server!n;其余代码省略Department GetDepartment(int id)/*代码省略*/；class AccessDepartment:(4)public:void Insert(Department*department)coutInsert a record into Department in ACCESS!n；其余代码省略Department GetDepartment(int id)/*代码省略*/；(5)public:(6)=0；class SqlServerFactory:public IFactorypublic:IDepartment*CreateDepartment（）return new SqlserverDepartment（）;其余代码省略；class AccessFactory:public IFactorypublic:IDepartment*CreateDepartment（）return new AccessDepartment（）;其余代码省略； 正确答案： 本题解析： (1)virtual void Insert(Departmet*department) (2)virlual Department GetDepartment(int id)(3)public IDepartment(4)public IDepartmcnt(5)class Ifactory(6)virtual IDcpartment*CreateDepartment()本题考查基本面向对象设计模式的运用能力。抽象工厂设计模式主要是提供一个创建一系列相关或相互依赖对象的接口，而无需指定它们具体的类。从题目给出的类图可知SqlserverDepartment和AccessDepartment继承于Idepartment。而从第（1）和第（2）空处的程序语句可以知道，这里是定义纯虚函数，而类Idepartment一个抽象类，而在这里需要定义一个什么样的纯虚函数，就需要根据SqlserverDepartment和AccessDepartment类的内容来了解。在这两个类里面都有Insert和GetDepartment这两个函数，因此在Idepartment类中定义的纯虚函数就是这两个函数，因此第（1）空应该填virtual void Insert(Departmet*department)，而第（2）空应该填virlual Department GetDepartment(int id)。第（3）空和第（4）空是一样的，因为类SqlserverDepartment和AccessDepartment都是继承抽象类Idepartment，而一般情况下的继承方式都是public，所以这两空的答案都是public Idepartment。从第（5）空出现的位置，不难知道这里是定义一个类，结合前后程序，可以知道这里定义的类是Ifactory，这是一个抽象类，因此该空的答案为class Ifactory。第（6）空是定义抽象类Ifactory的纯虚函数，从后面的程序可以看出，需要定义的纯虚函数是CreateDepartment，因此第（6）空的答案是virtual IDcpartment*CreateDepartment()。 3.某电子商务系统采用以数据库为中心的集成方式改进购物车的功能，详细需求如下：（1）加入购物车。顾客浏览商品，点击加入购物车，根据商品标识从商品表中读取商品信息，并更新购物车表。（2）浏览购物车。顾客提交浏览购物车请求后，显示出购物车表中的商品信息。（3）提交订单。顾客点击提交订单请求，后台计算购物车表中商品的总价（包括运费）加入订单表，将购物车表中的商品状态改为待付款，显示订单详情。若商家改变价格，则刷新后可看到更改后的价格。（4）改变价格。商家查看订购自家商品的订单信息，根据特殊优惠条件修改价格，更新订单表中的商品价格。（5）付款。顾客点击付款后，系统先根据顾客表中关联的支付账户，将转账请求（验证码、价格等）提交给支付系统（如信用卡系统）进行转账；然后根据转账结果返回支付状态并更改购物车表中商品的状态。（6）物流跟踪。商家发货后，需按订单标识添加物流标识（物流公司、运单号）；然后可根据顾客或商家的标识以及订单标识，查询订单表中的物流标识，并从相应物流系统查询物流信息。（7）生成报表。根据管理员和商家设置的报表选项，从订单表、商品表以及商品分类表中读取数据，调用第三方服务Crystal Reports生成相关报表。（8）维护信息。管理员维护（增、删、改、查）顾客表、商品分类表和商品表中的信息。现采用结构化方法实现上述需求，在系统分析阶段得到如图1-1所示的顶层数据流图和图1-2所示的0层数据流图。图1-1顶层数据流图【问题1】(4分)使用说明中的词语，给出图1-1中的实体E1E4的名称。【问题2】(4分)使用说明中的词语，给出图1-2中的数据存储D1D4的名称。【问题】(4分)图1-2中缺失了数据流，请用说明或图1-2中的词语，给出其起点和终点。【问题4】（3分）根据说明，给出数据流“转账请求”、“顾客订单物流查询请求”和“商家订单物流查询请求”的各组成数据项。 正确答案： 本题解析： 【问题1】 E1：商家E2：支付系统E3：物流系统E4：CrystaI Reports或第三方服务【问题2】D1:订单表D2：商品表D3：商品分类表D4：购物车表【问题3】图1-2中缺少的数据流：【问题4】转账请求=验证码+价格+账号信息顾客订单物流查询请求=顾客标识+订单标识商家订单物流查询请求=商家标识+订单标识该题以电子商务的购物车系统为载体来考核考生对数据流图知识点的把握。从题目的问答形式上来看，和往年差不多，仍然是要求补充外部实体、补充数据存储、补充缺失数据流等。解答这类问题，有以下两个原则：（1）紧扣试题的系统说明部分，数据流图与系统说明有着严格的对应关系，系统说明部分的每一句话都能对应到图中，解题时可以一句一句地对照着图来分析。（2）数据的平衡原则，这一点在解题过程中也是至关重要的。数据平衡原则有两方面的意思：一方面是分层数据流图中父子图之间的数据流平衡原则；另一方面是每张数据流图中输入与输出数据流的平衡原则。【问题1】外部实体一般是人、组织或者外部系统。在本题中，根据顶层数据流图中购物车与E1的两天数据流，再结合题目的描述“商家发货后，需按订单标识添加物流标识（物流公司、运单号）；然后可根据顾客或商家的标识以及订单标识，查询订单表中的物流标识，并从相应物流系统查询物流信息”，可知E1就是商家。同理，根据说明中的“将转账请求（验证码、价格等）提交给支付系统（如信用卡系统）进行转账；然后根据转账结果返回支付状态”，再结合顶层数据流图可以知道E2是支付系统。根据说明中的“从相应物流系统查询物流信息”，再结合顶层数据流图中E3与购物车之间的数据流信息，可以知道E3是物流系统。根据说明中（7）的描述，再结合顶层图中E4与购物车系统的数据流可以知道E4是Crystal Reports（或第三方服务）。【问题2】数据存储一般是说明中所牵涉到的某某文件或某某表。在本题中，描述中有描述过的数据存储有：顾客表、订单表、商品表、商品分类表和购物车表。由图0层数据流图可知，D1与付款、提交订单、物流跟踪、改变价格等处理有关，可知D1是订单表。由描述“顾客浏览商品，点击加入购物车，根据商品标识从商品表中读取商品信息，并更新购物车表”，再结合0层数据流可知D2是商品表，另外，根据描述“管理员维护（增、删、改、查）顾客表、商品分类表和商品表中的信息”，再结合0层数据流可知D2和D3应该对应商品表和商品分类表，而D2是商品表，因此D3就是商品分类表。同理可以知道D4就是购物车表。【问题3】本题要求我们找出0层数据流图中缺失的数据流，是一类常考的知识点，对应这类题目的求解，我们要充分利用数据的平衡原则，仔细阅读题目给出的描述。根据说明中（5）的描述，我们不难知道，在付款这个加工时，要更改购物车表中商品的状态，很显然这个过程在0层数据流图中并没有体现出来，因此缺少了一条从付款到购物车表的数据流。另外，在付款时，系统先要根据顾客表中关联的支付账户，将转账请求提交给支付系统进行转账，那么就应该有一条从顾客表到付款的数据流。根据说明中（3）的描述，我们不难知道，在顾客点击提交订单请求，后台将要计算购物车表中商品的总价，那么就需要从购物车表中获取商品的价格信息，因此就有一条从购物车表到提交订单的数据流，而显然在0层数据流图中并没有体现出来这样一条数据流，因此缺少了一条从购物车表到提交订单的数据流。根据说明中（7）的描述，可以知道从订单表、商品表以及商品分类表都有到生成报表加工的数据流。从0层数据流图中来看，显然还缺少从订单表到生成报表的数据流。【问题4】数据项也称为数据元素，是最小的数据组成单位，也就是不可再分的数据单位。如学号、姓名等。在题目中，对于转账请求，已经给出了其包含了验证码、价格，另外根据常识，我们知道还应该有账号信息。而顾客订单物流查询请求应包含顾客标识和订单标识。商家订单物流查询请求应包含商家标识和订单标识这些数据项，而且一个商家可能有多个订单，因此订单标识也有多个。 4.某会议策划公司为了方便客户，便于开展和管理各项业务活动，需要构建一个基于网络的会议预定系统。【需求分析】1会议策划公司设有受理部、策划部和其他部门。部门信息包括部门号、部门名称、部门主管、电话和邮箱号。每个部门有多名员工处理部门的日常事务，每名员工只能在一个部门工作。每个部门有一名主管负责管理本部门的事务和人员。2员工信息包括员工号、姓名、部门号、职位、联系方式和工资；其中，职位包括主管、业务员、策划员等。业务员负责受理会议申请。若申请符合公司规定，则置受理标志并填写业务员的员工号。策划部主管为已受理的会议申请制定策划任务，包括策划内容、参与人数、要求完成时间等。一个已受理的会议申请对应一个策划任务，一个策划任务只对应一个已受理的会议申请，但个策划任务可由多名策划员参与执行，且一名策划员可以参与多项策划任务。3客户信息包括客户号、单位名称、通信地址、所属省份、联系人、联系电话、银行账号。其中，一个客户号唯一标识一个客户。一个客户可以提交多个会议申请，但一个会议申请对应唯一的一个客户号，4会议申请信息包括申请号、开会日期、会议地点、持续天数、会议人数、预算费用、会议类型、酒店要求、会议室要求、客房类型、客房数、联系人、联系方式、受理标志和业务员的员工号等。客房类型有豪华套房、普通套房、标准间、三人间等，且申请号和客房类型决定客房数。【概念模型设计】根据需求阶段收集的信息，设计的实体联系图和关系模式（不完整）如下：【关系模式设计】部门（部门号，部门名称，主管，电话，邮箱号）员工（员工号，姓名，（a），联系方式，工资）客户（客户号，单位名称，通信地址，所属省份，联系人，联系电话，银行账号）会议申请（b），开会日期，会议地点，持续天数，会议人数，预算费用，会议类型，酒店要求，会议室要求，客房数，联系人，联系方式，受理标志，员工号）策划任务（c），策划内容，参与人数，要求完成时间）执行策划（d），实际完成时间）【问题1】（5分）根据问题描述，补充五个联系、联系的类型，完善图2-1的实体联系图。【问题2】（7分）根据实体联系图，将关系模式中的空（a）（d）补充完整（1个空缺处可能有多个数据项）。对会议申请、策划任务和执行策划关系模式，用下划线和#分别指出各关系模式的主键和外键。【问题3】（3分）请说明关系模式“会议申请”存在的问题及解决方案。 正确答案： 本题解析： 【问题2】（a）部门号，职位（b）申请号，客房类型，客户号（c）申请号，员工号（d）申请号，员工号关系模式为：会议申请（申请号，客房类型，客户号#，开会日期，会议地点，持续天数，会议人数，预算费用，会议类型，酒店要求，会议室要求，客房数，联系人，联系方式，受理标志，员工号#）策划任务（申请号#，员工号#，策划内容，参与人数，要求完成时间）执行策划（申请号#，员工号#，实际完成时间）【问题3】会议申请存在数据冗余及数据修改的不一致性问题，应该将关系模式分解为如下两个模式：会议申请1（申请号，客户号，开会日期，会议地点，持续天数，会议人数，预算费用，会议类型，酒店要求，会议室要求，联系人，联系方式，受理标志，员工号）会议申请2（申请号，客房类型，客房数）。本题考查数据库相关知识，涉及的知识点包括：ER模型、关系模式、主键、范式。【问题1】问题1考查考生对ER模型的理解。本题主要考查根据题目描述补充完整ER图。在解答本问题时，需要注意将题目描述与已给出的图进行对照分析。在题目中有“业务员负责受理会议申请。”，这说明业务员与会议申请之间有联系，联系的名称可直接取题目中的“受理”一词。同时，由于题目中有“若申请符合公司规定，则置受理标志并填写业务员的员工号”，这说明一个申请只由一个员工受理，但一个员工却可以受理多项业务，也就是说业务员与会议申请之间是1:n的关系。与此同时，通过常识加题目描述，可以意识到一个问题：对于会议申请只表明了受理人员，而谁来提出申请，并未直接说明。纵观系统全局，可以看出会议是由客户申请的。所以客户也与会议申请有联系，这种联系类型也是1:n。从“一个已受理的会议申请对应一个策划任务，一个策划任务只对应一个已受理的会议申请，但个策划任务可由多名策划员参与执行，且名策划员可以参与多项策划任务。”可以得知，策划任务与策划员之间存在“执行”的联系，而且这种联系是n:m的。从“每个部门有多名员工处理部门的日常事务，每名员工只能在一个部门工作。”可以看出，部门与员工之间存在联系，联系类型是1：n。从“每个部门有一名主管负责管理本部门的事务和人员。”可以看出，主管这个角色与部门之间存在联系，由于每个部门只有1名主管，而1名主管也只能负责1个部门的工作，所以他们之间的联系是1：1的。【问题2】当完成问题1的分析之后，问题2就很好解决了。其解题步骤的第一个环节，应是看题目已经给出的信息。例如，第（a）空要求补充员工关系，而题目中已经说明“员工信息包括员工号、姓名、部门号、职位、联系方式和工资”，此时，只要把缺失的“部门号，职位”填入即可。但有时，这一招并不能完全解决问题，例如第（b）空，从题目的描述“会议申请信息包括申请号、开会日期、会议地点、持续天数、会议人数、预算费用、会议类型、酒店要求、会议室要求、客房类型、客房数、联系人、联系方式、受理标志和业务员的员工号等。”可以得知，关系模式缺了申请号与客房类型，但补充这些是否足矣？不行，还缺了属性，即客户号，因为问题1中，已经分析了系统业务逻辑，应是由客户提出申请，所以需要记录客户号。接下来分析会议申请的主键与外键。在会议申请这个关系模式中，由于存在“客房类型有豪华套房、普通套房、标准间、三人间等，且申请号和客房类型决定客房数。”的情况，所以有函数依赖：（申请号，客户类型）-客户数。同时其它所有属性都依赖于（申请号，客户类型）。所以（申请号，客户类型）是本关系模式的主键。而会议申请中的客户号是相对于客户关系的外键，员工号是相对于员工关系的外键。（c）与（d）的内容补充，也需要进行分析才能得出结论，正是由于从题目中有“个已受理的会议申请对应一个策划任务，一个策划任务只对应一个已受理的会议申请，但个策划任务可由多名策划员参与执行，且名策划员可以参与多项策划任务。”，这说明“策划任务”与“执行策划”都与会议申请有关，所以这两个关系中，也需要有申请号。在策划任务关系模式中申请号能确定员工号（因为策划部主管为已受理的会议申请制定策划任务，所以有确定的关系），也能确定策划内容，参与人数，要求完成时间。所以申请号是主键。同时，由于申请号与员工号在其它关系中充当主键，所以他们也是外键。在执行策划关系中，由于“个策划任务可由多名策划员参与执行，且一名策划员可以参与多项策划任务”，所以必须要（申请号，员工号）这个组合属性才能充当主键。同时这两个属性也是外键。【问题3】问题3要求分析关系模式“会议申请”存在的问题及解决方案。分析关系模式的问题，往往需要从关系模式的规范程度入手，规范程度不高的模式，可能出现：插入异常、修改异常、删除异常、数据冗余等问题。在问题2的分析中，已经提到了会议申请关系的主键是：（申请号，客户类型）。但同时存在：申请号-开会日期、申请号-会议地点依赖关系，这就导致了部分依赖的产生。这使得数据冗余、修改异常等问题产生。解决的办法就是拆分。把：（申请号，客户类型，客户数）拆分为一个新表，而另一个表中去除客户类型与客户数，将申请号定义为主键。 5.现欲开发一个软件系统，要求能够同时支持多种不同的数据库，为此采用抽象工厂模式设计该系统。以SQL Server和Access两种数据库以及系统中的数据库表Department为例，其类图如图6-1所示。图6-1类图【Java代码】import javAutil.*;class Department/*代码省略*/interface IDepartment(1)；(2)；class SqlserverDepartment(3)public voidInsert(Department department)System.out.println(”Insert a record into Department in SQL Server!);其余代码省略public Department GetDepartment(int id)/*代码省略*/classAccessDepartment(4)public void Insert(Department department)System.out.println(Insert a record into Department in ACCESS!”);其余代码省略public Department GetDepartment(int id)/*代码省略*/(5)(6)；class SqlServerFactory implements IFactorypublic IDepartment CreateDepartment（）retum new SqlserverDepartment（）;其余代码省略class AccessFactory implements IFactorypublic IDepartment CreateDepartment（）return new AccessDepartment（）;其余代码省略 正确答案： 本题解析： (1)void Insert(Department department) (2)Department GetDepartment(int id)(3)implements lDepartment(4)implements IDepartment(5)interface IFactory(6)IDepartment CreateDepartment()本题考查基本面向对象设计模式的运用能力。抽象工厂设计模式主要是提供一个创建一系列相关或相互依赖对象的接口，而无需指定它们具体的类。从题目给出的类图可知SqlserverDepartment和AccessDepartment继承于接口Idepartment。而从第（1）和第（2）空处的程序语句可以知道，这里是定义抽象函数，但在这里需要定义一个什么样的抽象函数，就需要根据SqlserverDepartment和AccessDepartment类的内容来了解。在这两个类里面都有Insert和GetDepartment这两个函数，因此在Idepartment中定义的抽象函数就是这两个函数，因此第（1）空应该填void Insert(Departmet department)，而第（2）空应该填Department GetDepartment(int id)。第（3）空和第（4）空是一样的，因为类SqlserverDepartment和AccessDepartment都是实现接口Idepartment，而实现接口都是用关键字implements，所以这两空的答案都是implements Idepartment。从第（5）空出现的位置，不难知道这里是定义一个接口，结合前后程序，可以知道这里定义的接口是Ifactory，因此该空的答案为interface Ifactory。第（6）空是定义接口Ifactory的抽象函数，从后面的程序可以看出，需要定义的抽象函数是CreateDepartment，因此第（6）空的答案是Idcpartment CreateDepartment()。 6.设有n个货物要装入若干个容量为C的集装箱以便运输，这n个货物的体积分别为S1，S2，Sn，且有siC(1in)。为节省运输成本，用尽可能少的集装箱来装运这n个货物。下面分别采用最先适宜策略和最优适宜策略来求解该问题。最先适宜策略(firstfit)首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。最优适宜策略(bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容量最小的集装箱，使得该箱子装入货物后闲置空间最小。【C代码】下面是这两个算法的C语言核心代码。(1)变量说明n：货物数C：集装箱容量s：数组，长度为n，其中每个元素表示货物的体积，下标从0开始b：数组，长度为n，bi表示第i+1个集装箱当前已经装入货物的体积，下标从0开始i，j：循环变量k：所需的集装箱数min:当前所用的各集装箱装入了第i个货物后的最小剩余容量m:当前所需要的集装箱数temp：临时变量(2)函数firstfitint firstfit（）inti，j；k=0：for(i=0；in；i+)bi=0；for（i=0；in；i+）(1)；while(C-bjsi)j+;(2)；k=k(j+1）k：(j+1)；return k；(3)函数bestfitint bestfit（）int i，j，min，m，temp;k=0；for（i=0；in；i+）bi=0；for(i=0；in；i+）min=C；m=k+1；for(j=0;jk+l；j+)temp=C-bj-si;if(temp0&tempmin)(3)；m=j，(4)；k=k(m+1）k:(m+1)；return k；【问题1】（8分）根据和【C代码】，填充C代码中的空(1)(4)。【问题2】（4分）根据和【C代码】，该问题在最先适宜和最优适宜策略下分别采用了(5)和(6)算法设计策略，时间复杂度分别为(7)和(8)（用O符号表示）。【问题3】（3分）考虑实例n=10，C=10，各个货物的体积为4，2，7，3，5，4，2，3，6，2。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为(9)和(10)。考虑一般的情况，这两种求解策略能否确保得到最优解？(11)（能或否） 正确答案： 本题解析： 【问题1】 (1)j=0(2)bj=bj+si(3)min=temp(4)bm=bm+si【问题2】(5)贪心(6)贪心(7)O(n2)(8)O(n2)【问题3】(9)5(10)4(11)否本题考查最先适宜策略和最优适宜策略。这两种策略在题目的描述中给出了清楚的解析，对于最先适宜策略，其关键是每次将一个货物装入第一个能容纳它的集装箱中；而对于最优适宜策略，则总是把货物装到能容纳它且目前剩余容量最小的集装箱。下面我们来具体分析程序。函数firstfit()是实现最先适宜策略的，从程序不难看出，第（1）空所在的for循环，就是要将n各货物装入到集装箱。根据算法的描述，是依次从第一个集装箱找，找到合适的就装入货物，依次没装入一个货物，都是依次从第一个集装箱找。结合后面的程序不难知道j标识这当前是第几个集装箱。因此每装入一个货物后，要将j清0，标识从头再找，因此第（1）空的答案是j=0。而接下来的while循环，从其条件表达式C-bjsi不难知道，是比较当前集装箱和当前货物的体积大小，如果当前集装箱体积小，则比较下一个集装箱，否则，就应该将货物装入该集装箱，并且调整集装箱剩余体积的大小，在本题中，这个是通过数组b来实现的，因此第（2）空的答案应该为bj=bj+si。第（3）和第（4）空是在函数bestfit()下，这个函数是实现最优适宜策略的。从程序中不难看出，for(j=0;jk+l；j+)就是要在众多的集装箱中找到最合适的集装箱，而第（3）空是条件if(temp0&tempmin)成立时，执行的语句，该条件成立，表示当前找到的集装箱比原来确定的集装箱更合适，而最合适的集装箱的剩余体积存放在min中，因此第3空的答案为min=temp，而循环结束后，就应该找到了合适的集装箱，这时应该将货物存放到集装箱里面，即第（4）空的答案为bm=bm+si。在本题中，不管是采用最先适宜策略，还是最优适宜策略，他们都是根据不同策略选择目前看来最优的情况，这都属于贪心算法的思想。从两个函数不难看出，其时间复杂度是一样的，都是O(n2)。第3个问题，其实是这个题目中最简单的问题，也是算法的一个实际应用。对于这个实例，如果采用最先适宜策略，那么货物4，2，3存放在第一个集装箱，而7，2存放在第二个集装箱，5，4存放在第三个集装箱，3，6存放在第四个集装箱，而2存放在第五个集装箱。如果采用最优适宜策略，那么货物4，2，4存放在第一个集装箱，而7，3存放在第二个集装箱，5，2，3存放在第三个集装箱，6，2存放在第四个集装箱。因为这两种方法都是采用的贪心策略，那么在一般情况下，是不能确保得到最优解的。