1、中级软件设计师下午试题-109 及答案解析(总分：71.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)说明假设某大型商业企业由商品配送中心和连锁超市组成，其中商品配送中心包括采购、财务、配送等部门。为实现高效管理，设计了商品配送中心信息管理系统，其主要功能描述如下：1系统接收由连锁超市提出的供货请求，并将其记录到供货请求记录文件。2在接到供货请求后，从商品库存记录文件中进行商品库存信息查询。如果库存满足供货请求，则给配送处理发送配送通知；否则，向采购部门发出缺货通知。3配送处理接到配送通知后，查询供货请求记录文件，更新商品库存记录文件，并向配送部门发送配送单，在配送货品
2、的同时记录配送信息至商品配送记录文件。4采购部门接到缺货通知后，与供货商洽谈，进行商品采购处理，合格商品入库，并记录采购清单至采购清单记录文件、向配送处理发出配送通知，同时通知财务部门给供货商支付货款。该系统采用结构化方法进行开发，得到待修改的数据流图如下图所示。（分数：15.00）(1).问题 1使用说明中的词语，给出上图中外部实体 E1 至 E4 的名称和数据存储 D1 至 D4 的名称。（分数：7.50）_(2).问题 2以上数据流图中存在四处错误数据流，请指出各自的起点和终点；若将上述四条错误数据流删除，为保证数据流图的正确性，应补充三条数据流，请给出所补充数据流的起点和终点。(起点和
3、终点请采用上述数据流图中的符号或名称)错误数据流*补充的数据流*（分数：7.50）_二、试题二(总题数：1，分数：15.00)说明某汽车维修站拟开发一套小型汽车维修管理系统，对车辆的维修情况进行管理。1对于新客户及车辆，汽车维修管理系统首先登记客户信息，包括：客户编号、客户名称、客户性质(个人、单位)、折扣率、联系人、联系电话等信息；还要记录客户的车辆信息，包括：车牌号、车型、颜色、车辆类别等信息。一个客户至少有一台车。客户及车辆信息如表 1 所示。表 12记录维修车辆的故障信息。包括：维修类型(普通、加急)、作业分类(大、中、小修)、结算方式(自付、三包、索赔)等信息。维修厂的员工分为：维修
4、员和业务员。车辆维修首先委托给业务员。业务员对车辆进行检查和故障分析后，与客户磋商，确定故障现象，生成维修委托书。如表 2 所示。3维修车间根据维修委托书和车辆的故障现象，在已有的维修项目中选择并确定一个或多个具体维修项目，安排相关的维修工及工时，生成维修派工单。维修派工单如表 3 所示。4客户车辆在车间修理完毕后，根据维修项目单价和维修派工单中的工时计算车辆此次维修的总费用，记录在委托书中。根据需求阶段收集的信息，设计的实体联系图(见图 1)和关系模式(不完整)如下所示。图 2-1 中业务员和维修工是员工的子实体。表 1表 2概念结构设计-图 1（分数：15.00）(1).根据问题描述，填写
5、图 1 中(1)(4)处联系的类型。联系类型分为一对一、一对多和多对多三种，分别使用 1:1、1:n 或 1:*、m:n 或*:*表示。（分数：3.75）_(2).1 中的联系并指明其联系类型。联系名可为：联系 1，联系 2，。（分数：3.75）_(3).根据图 1 和说明，将逻辑结构设计阶段生成的关系模式中的空(5)(8)补充完整。（分数：3.75）_(4).根据问题描述，写出客户、委托书和派工单这三个关系的主键。（分数：3.75）_三、试题三(总题数：1，分数：15.00)说明某高等院校的教学管理具有选课管理和成绩管理两大功能。选课管理主要完成以下工作：(1)录入与生成新学期课程表；(2)
6、学生选课注册；(3)查询，学生、教师、教学管理员可以查询课程表，获得课程信息、学生选课信息和学生、教师信息；(4)选课注册信息的统计与报表生成。成绩管理主要的功能为： (1)成绩录入：教学管理员录入学生考试成绩；(2)成绩查询：教师、教学管理员可以查询学生考试成绩。学生只允许查询自己的考试成绩，不允许查询他人的成绩；(3)成绩统计与报表生成：教学管理员进行成绩统计，打印统计报表。把学生选课注册信息传送给财务系统，以便计算学生应交纳的费用。根据需要，系统设计的用例有“选课管理”、“成绩管理”、“查询课程信息”、“选课注册”、“管理开设课程”等用例。其中部分用例说明如下：“查询课程信息”：学生、教
7、师或教学管理员启动查询课程信息时，该用例开始运行。根据输入的查询要求(查询主题或关键字)，显示有关的课程信息；“选课注册”。当学生登录进行选课注册时，该用例开始运行，它提供了选择课程、注册、修改注册、删除注册等功能。学生登录需要用户标识(ID)和口令；“管理开设课程”。 当教学管理员登录系统进行产生选课信息操作时， 该用例开始运行。 它首先检查用户标识(ID)和口令，然后从数据库中取出学生的选课注册数据，按照要求进行分类统计，生成选课注册报表。活动者“学生”与用例“选课注册”的交互关系如下：当“学生”登录系统进入选课注册活动时，首先要输入用户标识(ID)和口令，经系统的“注册表单”接口对象验证
8、，如果正确无误，则“学生”可以进行查询活动或选课活动，否则拒绝进入。若“学生”发出“查询”请求，系统的“选课注册表单”接口对象响应信息给“学生”，及发送增加或删除学生选课数据的消息。 “开设课程”对象响应该消息，找出数据库中的相关数据，增加或删除学生的姓名和所选的课程名，或做相应的修改，并把增加或删除学生课操作成功或失败的信息反馈给“选课注册表单”接口对象，“选课注册表单”接口对象再反馈给“学生”。如果“学生”按下“确认”键，则选课操作得到确认，发出提交请求。“选课注册表单”接口对象响应该请求，并发出“存储”消息。“开设课程”对象响应“存储”消息，进行数据库存储操作，选课数据存入数据库。若“学
9、生”结束选课，发出“退出”系统请求，“注册表单”接口对象响应请求，关闭系统。图 1 为系统的顶层 UML 用例图。图 2 为选课注册顺序图。图 1图 2（分数：15.00）(1).问题 1用例图解释了活动者与用例之间的交互关系。根据系统设计说明，将系统的顶层用例图补充完整。（分数：5.00）_(2).问题 2图 2 为选课注册顺序图，请根据系统设计说明及图中信息，采用说明中的术语将选课注册顺序图补充完整。（分数：5.00）_(3).问题 3UML 设计中交互图通常可以分为哪两类图?绘制交互图对系统的设计有什么作用?（分数：5.00）_四、试题四(总题数：1，分数：15.00)1.说明某汽车制造
10、工厂有两条装配线。汽车装配过程如下图所示，即汽车底盘进入装配线，零件在多个工位装配，结束时汽车自动完成下线工作。(1)e0和 e1表示底盘分别进入装配线 0 和装配线 1 所需要的时间。(2)每条装配线有 n 个工位，第一条装配线的工位为 S0,0，S 0,1，S 0,n-1，第二条装配线的工位为 S1,0，S 1,1，S 1,n-1。其中 S0,k和 S1,k(0kn-1)完成相同的任务，但所需时间可能不同。(3)ai,j表示在工位 Si,j处的装配时间，其中 i 表示装配线(i=0 或 i=1)，j 表示工位号(0jn-1)。(4)ti,j表示从 Si,j 处装配完成后转移到另一条装配线下
11、一个工位的时间。(5)x0和 x1表示装配结束后，汽车分别从装配线 0 和装配线 1 下线所需要的时间。(6)在同一条装配线上，底盘从一个工位转移到其下一个工位的时间可以忽略不计。图 4-17 所示的流程图描述了求最短装配时间的算法，该算法的输入为：n：表示装配线上的工位数；ei：表示 e1和 e2，i 取值为 0 或 1；aij：表示 ai,j，i 的取值为 0 或 1，j 的取值范围为 0n-1；tij：表示 ti,j，i 的取值为 0 或 1，j 的取值范围为 0n-1；xi：表示 x0和 x1，i 取值为 0 或 1。算法的输出为：fi：最短的装配时间；li：获得最短装配时间的下线装配
12、线号(0 或者 1)。算法中使用的 fij表示从开始点到 Si,j处的最短装配时间。（分数：15.00）_五、试题五(总题数：1，分数：11.00)2.【程序说明】本程序先从文件读人各考生的准考证号(设为整型数)及成绩，并将其存放在一棵检索二叉树上，二叉树结点的健值是成绩，每个结点带一链表，链表结点存放取得该成绩的考生的准考证号。然后，程序按中序遍历检索二叉树，从高分到低分输出结果，使每行输出成绩及其取得成绩的考生的准考证号。【程序】#include stdio. h typedef struet idnode int id;struct idnode * next;ldNode;typede
13、f struct marknode Iint mark;ldNode * head;struct marknode * left, * right;MarkNode;char fname = “sp07.dat“;main( )int id, mark;MarkNode * root = null;FILE * fp = fopen(fname,“ r“ );if(!fp) printf(“file%s open error, /n“ , fname);exit(0);while (!feop(fp) fscanf(fp,“ %d%d“, btree(fclose(fp);print(root
14、);btree(MarkNod * * mpptr, int id, int mark)ldNode * ip;MarkNode *mp = * mpptr;if (1) if (mark=p-mark) addldNODE ( (2) , id);else if ( mark mp - mark) btree (else btree(elseImp = ( marknode * ) malloc(sizeo (marknode) );mp - mark = mark;mp - left =mp - right = NULL;(3) addldNode(4) ;addldNode(ldNode
15、 * * ipp, int id)ldNode * ip = * ipp;if ( (5) )addldNode ( (6) ), id;else ip = (ldNode * )malloc(sizeof(ldNode) );sp - id = id;ip - next = NULL;(7) print(MarkNode * rap)ldNode *ip, *ip0;if (mp) print ( mp - left);printf(“ %6d: /t“ ,mp - mark);ip = mp - head;while(ip) printf(“ %6d“ ,ip - id);ip0 =ip;
16、ip = ip - next;free (ip0);printf(“ /n“ ); printf( mp - right); free(mp);（分数：11.00）_中级软件设计师下午试题-109 答案解析(总分：71.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)说明假设某大型商业企业由商品配送中心和连锁超市组成，其中商品配送中心包括采购、财务、配送等部门。为实现高效管理，设计了商品配送中心信息管理系统，其主要功能描述如下：1系统接收由连锁超市提出的供货请求，并将其记录到供货请求记录文件。2在接到供货请求后，从商品库存记录文件中进行商品库存信息查询。如果库存满足供货请
17、求，则给配送处理发送配送通知；否则，向采购部门发出缺货通知。3配送处理接到配送通知后，查询供货请求记录文件，更新商品库存记录文件，并向配送部门发送配送单，在配送货品的同时记录配送信息至商品配送记录文件。4采购部门接到缺货通知后，与供货商洽谈，进行商品采购处理，合格商品入库，并记录采购清单至采购清单记录文件、向配送处理发出配送通知，同时通知财务部门给供货商支付货款。该系统采用结构化方法进行开发，得到待修改的数据流图如下图所示。（分数：15.00）(1).问题 1使用说明中的词语，给出上图中外部实体 E1 至 E4 的名称和数据存储 D1 至 D4 的名称。（分数：7.50）_正确答案：(E1：财
18、务部门 E2：采购部门E3：连锁超市 E4：配送部门D1：采购清单记录文件 D2：商品库存记录文件D3：商品配送记录文件 D4：供货请求记录文件)解析：(2).问题 2以上数据流图中存在四处错误数据流，请指出各自的起点和终点；若将上述四条错误数据流删除，为保证数据流图的正确性，应补充三条数据流，请给出所补充数据流的起点和终点。(起点和终点请采用上述数据流图中的符号或名称)错误数据流*补充的数据流*（分数：7.50）_正确答案：(错误数据流补充的数据流)解析： 分析 本题考查 DFD 的分析与设计，问题一主要考查 DFD 中的外部实体和数据存储，由于在题干中已经提到“系统接收由连锁超市提出的供货
19、请求，并将其记录到供货请求记录文件”，因此可以明确出“连锁超市”外部实体和“供货请求记录文件”数据存储；对应到 DFD 图中为 E3 和 D4。描述中的第二项提出“从商品库存记录文件中进行商品库存信息查询。如果库存满足供货请求，则给配送处发送配送通知；否则，向采购部门发出缺货通知”，因为配送通知需要发送到采购部门，因此采购部门将成为系统的外部实体；同时，商品库存记录文件能够提供库存信息，所以 DFD 图中 E2 和 D2 分别为采购部门和商品配送记录文件。第三项需求“配送处理接到配送通知后，查询供货请求记录文件，更新商品库存记录文件，并向配送部门发送配送单，在配送货品的同时记录配送信息至商品配
20、送记录文件”，所以配送处理需要查询供货请求记录文件，更新商品库存记录文件与商品配送记录文件，因此 D3 为商品配送记录文件；采购处理需要记录采购清单同时通知财务部门，所以 E1 应该为财务部门，D1 为采购清单记录文件，剩下的 E4 则为配送部门。DFD 中出现的错误数据流为：E1 到 E2，E1 与 E2 的数据流不属于系统的范围；D3 到 E4，多余的数据流；D2 到采购处理，数据流方向错误；D4 到供货请求处理，数据流方向错误。需要补充的数据流为：E2 到采购处理，因为 E2 是采购部门，采购部门需要给采购处提供入库商品信息；采购处到 D2 需要一条数据流，因为采购处理需要更改库存信息；
21、供货请求处理到 D4 需要一条数据流，因为供货请求处理需要记录供货请求信息。二、试题二(总题数：1，分数：15.00)说明某汽车维修站拟开发一套小型汽车维修管理系统，对车辆的维修情况进行管理。1对于新客户及车辆，汽车维修管理系统首先登记客户信息，包括：客户编号、客户名称、客户性质(个人、单位)、折扣率、联系人、联系电话等信息；还要记录客户的车辆信息，包括：车牌号、车型、颜色、车辆类别等信息。一个客户至少有一台车。客户及车辆信息如表 1 所示。表 12记录维修车辆的故障信息。包括：维修类型(普通、加急)、作业分类(大、中、小修)、结算方式(自付、三包、索赔)等信息。维修厂的员工分为：维修员和业务
22、员。车辆维修首先委托给业务员。业务员对车辆进行检查和故障分析后，与客户磋商，确定故障现象，生成维修委托书。如表 2 所示。3维修车间根据维修委托书和车辆的故障现象，在已有的维修项目中选择并确定一个或多个具体维修项目，安排相关的维修工及工时，生成维修派工单。维修派工单如表 3 所示。4客户车辆在车间修理完毕后，根据维修项目单价和维修派工单中的工时计算车辆此次维修的总费用，记录在委托书中。根据需求阶段收集的信息，设计的实体联系图(见图 1)和关系模式(不完整)如下所示。图 2-1 中业务员和维修工是员工的子实体。表 1表 2概念结构设计-图 1（分数：15.00）(1).根据问题描述，填写图 1
23、中(1)(4)处联系的类型。联系类型分为一对一、一对多和多对多三种，分别使用 1:1、1:n 或 1:*、m:n 或*:*表示。（分数：3.75）_正确答案：(n 或 m 或* (2) 1 (3) n 或 m 或* (4) n 或 m 或*)解析：(2).1 中的联系并指明其联系类型。联系名可为：联系 1，联系 2，。（分数：3.75）_正确答案：(完整的实体联系图如下图所示。)解析：(3).根据图 1 和说明，将逻辑结构设计阶段生成的关系模式中的空(5)(8)补充完整。（分数：3.75）_正确答案：(客户编号，客户名称，客户性质(6) 委托书编号，客户编号，车牌号，业务员编号或委托书编号，车
24、牌号，业务员编号(7) 委托书编号，维修工编号，维修项目编号 (8) 员工编号，员工姓名)解析：(4).根据问题描述，写出客户、委托书和派工单这三个关系的主键。（分数：3.75）_正确答案：(客户：客户编号委托书：委托书编号派工单：委托书编号，维修项目编号，维修工编号)解析：解析 本题考查数据库设计，设计考点有：数据库的概念结构设计和逻辑结构设计。问题 1由维修委托书的故障描述，维修类型、作业分类，可知，一台车可能有多个故障，对应多个维修委托书，所以(1)空填写：*；题目中“维修车间根据维修委托书和车辆的故障现象，在已有的维修项目中选择并确定一个或多个具体维修项目，安排相关的维修工及工时，生成
25、维修派工单”，很明显，一份委托书包含了一个或多个维修项目，而每个维修项目可以由多个维修工来完成，每一个维修工又可以完成多个维修项目，所以(2)空填写：1，(3)、(4)填写：*。问题 2需要补充车辆和客户之间以及委托书和业务员之间的关系。由题目“一个客户至少拥有一台车”可知，客户和车辆之间是“拥有”关系，且是一对多的关系；在由题目中“业务员对车辆进行检查和故障分析后，与客户磋商，确定故障现象，生成维修委托书”可知，业务员与委托书之间是“委托”关系，且一名业务员可以受理多份委托书，而一份委托书由一名业务员来生成。问题 3本题又是补充逻辑结构设计题，几乎每年都考，这类题目只要仔细看需求分析结果或者
26、仔细观察题目中已知的表，很容易就能做出，关键是需要细心，不要漏掉什么属性。根据客户和车辆信息表可知，客户关系应包括客户编号、客户名称、客户性质、折扣率、联系人等属性，主键显然为客户编号；而车辆关系应包括车牌号、客户编号、车型、颜色、车辆类别等属性，主键为车牌号。根据维修委托书表可知委托书应包括委托书编号、车牌号、客户编号、业务员编号、维修类型等属性，其主键为委托书编号。根据维修派工单可知，派工单应包括委托书编号、维修项目编号、维修工编号、工时等属性，主键是委托书编号、维修项目编号和维修员编号。根据实体联系图知，员工包括业务员和维修工，他们共有的属性是员工编号、员工姓名、工种、员工类型、级别等属
27、性，主键为员工编号。问题 4参考问题 3 的分析。三、试题三(总题数：1，分数：15.00)说明某高等院校的教学管理具有选课管理和成绩管理两大功能。选课管理主要完成以下工作：(1)录入与生成新学期课程表；(2)学生选课注册；(3)查询，学生、教师、教学管理员可以查询课程表，获得课程信息、学生选课信息和学生、教师信息；(4)选课注册信息的统计与报表生成。成绩管理主要的功能为： (1)成绩录入：教学管理员录入学生考试成绩；(2)成绩查询：教师、教学管理员可以查询学生考试成绩。学生只允许查询自己的考试成绩，不允许查询他人的成绩；(3)成绩统计与报表生成：教学管理员进行成绩统计，打印统计报表。把学生选
28、课注册信息传送给财务系统，以便计算学生应交纳的费用。根据需要，系统设计的用例有“选课管理”、“成绩管理”、“查询课程信息”、“选课注册”、“管理开设课程”等用例。其中部分用例说明如下：“查询课程信息”：学生、教师或教学管理员启动查询课程信息时，该用例开始运行。根据输入的查询要求(查询主题或关键字)，显示有关的课程信息；“选课注册”。当学生登录进行选课注册时，该用例开始运行，它提供了选择课程、注册、修改注册、删除注册等功能。学生登录需要用户标识(ID)和口令；“管理开设课程”。 当教学管理员登录系统进行产生选课信息操作时， 该用例开始运行。 它首先检查用户标识(ID)和口令，然后从数据库中取出学
29、生的选课注册数据，按照要求进行分类统计，生成选课注册报表。活动者“学生”与用例“选课注册”的交互关系如下：当“学生”登录系统进入选课注册活动时，首先要输入用户标识(ID)和口令，经系统的“注册表单”接口对象验证，如果正确无误，则“学生”可以进行查询活动或选课活动，否则拒绝进入。若“学生”发出“查询”请求，系统的“选课注册表单”接口对象响应信息给“学生”，及发送增加或删除学生选课数据的消息。 “开设课程”对象响应该消息，找出数据库中的相关数据，增加或删除学生的姓名和所选的课程名，或做相应的修改，并把增加或删除学生课操作成功或失败的信息反馈给“选课注册表单”接口对象，“选课注册表单”接口对象再反馈
30、给“学生”。如果“学生”按下“确认”键，则选课操作得到确认，发出提交请求。“选课注册表单”接口对象响应该请求，并发出“存储”消息。“开设课程”对象响应“存储”消息，进行数据库存储操作，选课数据存入数据库。若“学生”结束选课，发出“退出”系统请求，“注册表单”接口对象响应请求，关闭系统。图 1 为系统的顶层 UML 用例图。图 2 为选课注册顺序图。图 1图 2（分数：15.00）(1).问题 1用例图解释了活动者与用例之间的交互关系。根据系统设计说明，将系统的顶层用例图补充完整。（分数：5.00）_正确答案：(选课管理(2)成绩管理)解析：解析 试题三本题属于 UML 应用题。图 2 为选课注
31、册顺序图。对于问题 1，图 1 为系统的顶层 UML 用例图，它解释了活动者与用例之间的交互关系。根据说明文档可知，(1)、(2)应该是教学管理中选课管理和成绩管理两个功能块。跟财务系统有关的是选课管理，这一点可从“把学生选课注册信息传送给财务系统，以便计算学生应交纳的费用”说明得出。那么可确定(1)选课管理，(2)为成绩管理。对于问题 2。图 2 为选课注册顺序图，根据说明文字可知，学生需要登录系统，并通过身份验证，才能够查询课程开设情况和选修课程。故确定(1)为登录；(2)为查询；(3)为验证；(4)为选课。问题 3 考查交互图相关的基本概念。(2).问题 2图 2 为选课注册顺序图，请根
32、据系统设计说明及图中信息，采用说明中的术语将选课注册顺序图补充完整。（分数：5.00）_正确答案：(登录(2)查询(3)验证(4)选课)解析：(3).问题 3UML 设计中交互图通常可以分为哪两类图?绘制交互图对系统的设计有什么作用?（分数：5.00）_正确答案：(交互图分为顺序图和协同图。它用于描述用例如何实现对象之间的交互，用于建立系统的动态行为模型。在对主要的用例做交互行为的分析后，绘制交互图，能够更清楚地理解用例的行为，从而可以进一步调整用例视图确定的解决方案。)解析：四、试题四(总题数：1，分数：15.00)1.说明某汽车制造工厂有两条装配线。汽车装配过程如下图所示，即汽车底盘进入装
33、配线，零件在多个工位装配，结束时汽车自动完成下线工作。(1)e0和 e1表示底盘分别进入装配线 0 和装配线 1 所需要的时间。(2)每条装配线有 n 个工位，第一条装配线的工位为 S0,0，S 0,1，S 0,n-1，第二条装配线的工位为 S1,0，S 1,1，S 1,n-1。其中 S0,k和 S1,k(0kn-1)完成相同的任务，但所需时间可能不同。(3)ai,j表示在工位 Si,j处的装配时间，其中 i 表示装配线(i=0 或 i=1)，j 表示工位号(0jn-1)。(4)ti,j表示从 Si,j 处装配完成后转移到另一条装配线下一个工位的时间。(5)x0和 x1表示装配结束后，汽车分别
34、从装配线 0 和装配线 1 下线所需要的时间。(6)在同一条装配线上，底盘从一个工位转移到其下一个工位的时间可以忽略不计。图 4-17 所示的流程图描述了求最短装配时间的算法，该算法的输入为：n：表示装配线上的工位数；ei：表示 e1和 e2，i 取值为 0 或 1；aij：表示 ai,j，i 的取值为 0 或 1，j 的取值范围为 0n-1；tij：表示 ti,j，i 的取值为 0 或 1，j 的取值范围为 0n-1；xi：表示 x0和 x1，i 取值为 0 或 1。算法的输出为：fi：最短的装配时间；li：获得最短装配时间的下线装配线号(0 或者 1)。算法中使用的 fij表示从开始点到
35、Si,j处的最短装配时间。（分数：15.00）_正确答案：(这是一道考查动态规划算法求解最优汽车装配线的分析题。当问题具有两个特性，即最优子结构和重叠子问题时，可以考虑用动态规划算法求解问题。用动态规划算法求解具体应用问题具有以下 4个步骤。刻画问题的最优子结构，描述问题的最优解包含子问题的最优解。对于本试题，最短装配时间等于经过装配线 0 的第 n 个工位的最短装配时间加上 x0，或者等于经过装配线 1 的第 n 个工位的最短装配时间加上 x1，取哪条装配线取决于哪个值更小。而经过某条装配线 0/1 的第 i 个工位的最短装配时间又等于经过本条装配线第 i-1 个工位的最短装配时间，或者等于
36、经过另一条装配线第 i-1 个工位的最短装配时间加上从这个工位到装配线 0/1 的迁移时间，取决于哪个值更小。建立最优子结构的递归关系，这是关键的一步。对于本试题，可建立如下的递归关系。)解析：五、试题五(总题数：1，分数：11.00)2.【程序说明】本程序先从文件读人各考生的准考证号(设为整型数)及成绩，并将其存放在一棵检索二叉树上，二叉树结点的健值是成绩，每个结点带一链表，链表结点存放取得该成绩的考生的准考证号。然后，程序按中序遍历检索二叉树，从高分到低分输出结果，使每行输出成绩及其取得成绩的考生的准考证号。【程序】#include stdio. h typedef struet idno
37、de int id;struct idnode * next;ldNode;typedef struct marknode Iint mark;ldNode * head;struct marknode * left, * right;MarkNode;char fname = “sp07.dat“;main( )int id, mark;MarkNode * root = null;FILE * fp = fopen(fname,“ r“ );if(!fp) printf(“file%s open error, /n“ , fname);exit(0);while (!feop(fp) fs
38、canf(fp,“ %d%d“, btree(fclose(fp);print(root);btree(MarkNod * * mpptr, int id, int mark)ldNode * ip;MarkNode *mp = * mpptr;if (1) if (mark=p-mark) addldNODE ( (2) , id);else if ( mark mp - mark) btree (else btree(elseImp = ( marknode * ) malloc(sizeo (marknode) );mp - mark = mark;mp - left =mp - rig
39、ht = NULL;(3) addldNode(4) ;addldNode(ldNode * * ipp, int id)ldNode * ip = * ipp;if ( (5) )addldNode ( (6) ), id;else ip = (ldNode * )malloc(sizeof(ldNode) );sp - id = id;ip - next = NULL;(7) print(MarkNode * rap)ldNode *ip, *ip0;if (mp) print ( mp - left);printf(“ %6d: /t“ ,mp - mark);ip = mp - head;while(ip) printf(“ %6d“ ,ip - id);ip0 =ip;ip = ip - next;free (ip0);printf(“ /n“ ); printf( mp - right); free(mp);（分数：11.00）_正确答案：(1)mp 或 mp!=NULL (2)mp-head 或&(mp-head)(3)&mp-head=NULL (4)*mpptr=mp (5)ip 或 ip!=NULL(6)&ip-next 或&(ip-next) (7)*ipp=ip)解析：
