【计算机类职业资格】计算机水平考试中级软件设计师2008年下半年下午真题及答案解析.doc

《【计算机类职业资格】计算机水平考试中级软件设计师2008年下半年下午真题及答案解析.doc》由会员分享，可在线阅读，更多相关《【计算机类职业资格】计算机水平考试中级软件设计师2008年下半年下午真题及答案解析.doc（15页珍藏版）》请在麦多课文档分享上搜索。

1、计算机水平考试中级软件设计师 2008 年下半年下午真题及答案解析(总分：105.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)阅读下列说明和图，回答问题 1 至问题 3，将解答填入对应栏内。【说明】某营销企业拟开发一个销售管理系统，其主要功能描述如下：1接受客户订单，检查库存货物是否满足订单要求。如果满足，进行供货处理：修改库存记录文件，给库房开具备货单并且保留客户订单至订单记录文件；否则进行缺货处理：将缺货订单录入缺货记录文件。2根据缺货记录文件进行缺货统计，将缺货通知单发给采购部门。3根据采购部门提供的进货通知单进行进货处理：修改库存记录文件，并从缺货记录文

2、件中取出缺货订单进行供货处理。4根据保留的客户订单进行销售统计，打印统计报表给经理。现采用结构化方法对销售管理系统进行分析与设计，获得如下图所示的顶层数据流图和 0 层数据流图。（分数：15.00）(1).【问题 1】使用说明中的词语，给出上述顶层数据流图中的外部实体 E1E4 的名称。（分数：5.00）_(2).【问题 2】使用说明中的词语，给出上述 0 层数据流图中的数据存储 D1D3 的名称。（分数：5.00）_(3).【问题 3】上述 0 层数据流图中缺少了 4 条数据流，根据说明及顶层数据流图提供的信息，分别指出这 4 条数据流的起点和终点。 起 点 终 点（分数：5.00）_二、B

3、试题二/B(总题数：1，分数：15.00)阅读下列说明和图，回答问题 1 至问题 4，将解答填入对应栏内。【说明】某宾馆拟开发一个宾馆客房预订子系统，主要是针对客房的预订和入住等情况进行管理。【需求分析结果】1员工信息主要包括：员工号、姓名、出生年月、性别、部门、岗位、住址、联系电话和密码等信息。岗位有管理和服务两种。岗位为“管理”的员工可以更改(添加、删除和修改)员工表中本部门员工的岗位和密码，要求将每一次更改前的信息保留；岗位为“服务”的员工只能修改员工表中本人的密码，且负责多个客房的清理等工作。2部门信息主要包括：部门号、部门名称、部门负责人、电话等信息。一个员工只能属于一个部门，一个部

4、门只有一位负责人。3客房信息包括：客房号、类型、价格、状态等信息。其中类型是指单人间、三人间、普通标准间、豪华标准间等；状态是指空闲、入住和维修。4客户信息包括：身份证号、姓名、性别、单位和联系电话。5客房预定情况包括：客房号、预定日期、预定入住日期、预定入住天数、身份证号等信息。一条预定信息必须且仅对应一位客户，但一位客户可以有多条预定信息。【概念模型设计】根据需求阶段收集的信息，设计的实体联系图(不完整)如下图所示。（分数：15.00）(1).【问题 1】根据问题描述，填写上图中(1)(3)处联系的类型。联系类型分为一对一、一对多和多对多三种，分别使用 1:1，1:n 或 1:*，m:n

5、或*:*表示。（分数：3.75）_(2).【问题 2】补充上图中的联系并指明其联系类型。（分数：3.75）_(3).【问题 3】根据需求分析结果和上图，将逻辑结构设计阶段生成的关系模式中的空(4)(8)补充完整。(注：一个空可能需要填多个属性)（分数：3.75）_(4).【问题 4】若去掉权限表，并将权限表中的操作权限属性放在员工表中(仍保持管理和服务岗位的操作权限规定)，则与原有设计相比有什么优缺点(请从数据库设计的角度进行说明)。（分数：3.75）_三、B试题三/B(总题数：1，分数：15.00)阅读下列说明和图，回答问题 1 至问题 4，将解答填入对应栏内。【说明】在线会议审稿系统(On

6、line Reviewing System，ORS)主要处理会议前期的投稿和审稿事务，其功能描述如下：1用户在初始使用系统时，必须在系统中注册(register)成为作者或审稿人。2作者登录(login)后提交稿件和浏览稿件审阅结果。提交稿件必须在规定提交时间范围内，其过程为先输入标题和摘要、选择稿件所属主题类型、选择稿件所在位置 (存储位置)。上述几步若未完成，则重复；若完成，则上传稿件至数据库中，系统发送通知。3审稿人登录后可设置兴趣领域、审阅稿件给出意见以及罗列录用和(或)拒绝的稿件。4会议委员会主席是一个特殊审稿人，可以浏览提交的稿件、给审稿人分配稿件、罗列录用和(或)拒绝的稿件以及关

7、闭审稿过程。其中，关闭审稿过程须包括罗列录用和(或)拒绝的稿件。系统采用面向对象方法开发，使用 UMi 进行建模。在建模用例图时，常用的方式是先识别参与者，然后确定参与者如何使用系统来确定用例，每个用例可以构造一个活动图。参与者名称、用例和活动名称分别参见以下各表。参与者列表 名称 说明 名称 说明User 用户 Author 作者Reviewer 审稿人 PCChair 委员会主席用例名称列表名称 说明 名称 说明login 登录系统 register 注册submit paper 提交稿件 browse review results 浏览稿件审阅结果close reviewing proc

8、ss 关闭审稿过程 assign paper to reviewer 分配稿件给审稿人set preferences 设定兴趣领域 enter review 审阅稿件给出意见list accepted/rejectedpapers罗列录用或/和拒绝的稿件browse submittedpapers浏览提交的稿件活动名称列表名称 说明 名称 说明select paper location 选择稿件位置 upload paper 上传稿件select subject group 选择主题类型 send notification 发送通知enter title and abstract 输入标题和摘

9、要系统的部分用例图和提交稿件的活动图分别见下图。（分数：15.00）(1).【问题 1】根据说明中的描述，使用参与者列表的英文名称，给出 ORS 用例图中 A1A4所对应的参与者。（分数：3.75）_(2).【问题 2】根据说明中的描述，使用用例名称列表中的英文名称，给出 ORS 用例图中 U1一 U3 所对应的用例。（分数：3.75）_(3).【问题 3】根据说明中的描述，给出 ORS 用例图中U (1) /U和U (2) /U所对应的关系。（分数：3.75）_(4).【问题 4】根据说明中的描述，使用用例名称列表和活动名称列表中的英文名称，给出提交稿件过程的活动图中 ActionlActi

10、on4 对应的活动。（分数：3.75）_四、B试题四/B(总题数：1，分数：15.00)阅读下列说明，回答问题 1 至问题 3，将解答填入对应栏内。【说明】某餐厅供应各种标准的营养套餐。假设菜单上共有 n 项食物 m1，m 2，m n，每项食物 mi的营养价值为vi，价格为 pi其中 i1，2，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过 M 的营养价值最大的套餐。（分数：15.00）(1).【问题 1】下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)处。伪代码中的主要变量说明如下。n：总的食物项数；v：营养价值数组，下标从 1 到 n，对

11、应第 1 到第 n 项食物的营养价值；p：价格数组，下标从 1 到 n，对应第 1 到第 n 项食物的价格；M：总价格标准，即套餐的价格不超过 M；x：解向量(数组)，下标从 1 到 n，其元素值为 0 或 1，其中元素值为 0 表示对应的食物不出现在套餐中，元素值为 1 表示对应的食物出现在套餐中；nv：n+1 行 M+1 列的二维数组，其中行和列的下标均从 0 开始，nvij表示由前 i 项食物组合且价格不超过 j 的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为 nvnM。伪代码如下：MaxNutrientValue(n，v，p，M，x)1 for i0 to n2 nvi0 0

12、3 for j1 to M4 nv0j05 for i1 to n6 for j1 to M7 if jpi /若食物 mi不能加入到套餐中8 nvij nvi-1j9 else if U(1) /U10 nvij nvi-1j11 else12 nvij nvi-1j-pi + vi13 j M14 for in downto 115 if U(2) /U16 xi 017 else18 xi 119 U (3) /U20 return x and nvnM（分数：5.00）_(2).【问题 2】现有 5 项食物，每项食物的营养价值和价格如下表所示。 编 码 营养价值 价 格m1 200 5

13、0m2 180 30m3 225 45m4 200 25m5 50 5食物营养价值及价格表若要求总价格不超过 100 的营养价值最大的套餐，则套餐应包含的食物有U (4) /U(用食物项的编码表示)，对应的最大营养价值为U (5) /U。（分数：5.00）_(3).【问题 3】问题 1 中伪代码的时间复杂度为U (6) /U(用 O 符号表示)。（分数：5.00）_五、B试题五/B(总题数：1，分数：15.00)1.【说明】 已知集合 A 和 B 的元素分别用不含头结点的单链表存储，函数 Difference()用于求解集合 A与 B 的差集，并将结果保存在集合 A 的单链表中。例如，若集合

14、A5，10， 20，15，25，30，集合B5，15，35，25，如图(a)所示，运算完成后的结果如图(b)所示。 （分数：15.00）_六、B试题六/B(总题数：1，分数：15.00)2.【说明】 已知某类库开发商提供了一套类库，类库中定义了 Application 类和 Document 类，它们之间的关系如下图所示。其中，Application 类表示应用程序自身，而 Document 类则表示应用程序打开的文档。Application 类负责打开一个已有的以外部形式存储的文档，如一个文件，一旦从该文件中读出信息后，它就由一个 Document 对象表示。 当开发一个具体的应用程序时，开

15、发者需要分别创建自己的Application 和 Document 子类，例如上图中的类 MyApplication 和类 MyDocument，并分别实现Application 和 Document 类中的某些方法。 已知 Application 类中的 openDocument 方法采用了模板方法(Template Method)设计模式，该方法定义了打开文档的每一个主要步骤，如下所示： （分数：15.00）_七、B试题七/B(总题数：1，分数：15.00)3.【说明】 已知某类库开发商捉供了一套类库，类库中定义了 Application 类和 Document 类，它们之间的关系如下图所

16、示，其中，Application 类表示应用程序自身，而 Document 类则表示应用程序打开的文档。Application 类负责打开一个已有的以外部形式存储的文档，如一个文件，一旦从该文件中读出信息后，它就由一个 Document 对象表示。 （分数：15.00）_计算机水平考试中级软件设计师 2008 年下半年下午真题答案解析(总分：105.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)阅读下列说明和图，回答问题 1 至问题 3，将解答填入对应栏内。【说明】某营销企业拟开发一个销售管理系统，其主要功能描述如下：1接受客户订单，检查库存货物是否满足订单要求。

17、如果满足，进行供货处理：修改库存记录文件，给库房开具备货单并且保留客户订单至订单记录文件；否则进行缺货处理：将缺货订单录入缺货记录文件。2根据缺货记录文件进行缺货统计，将缺货通知单发给采购部门。3根据采购部门提供的进货通知单进行进货处理：修改库存记录文件，并从缺货记录文件中取出缺货订单进行供货处理。4根据保留的客户订单进行销售统计，打印统计报表给经理。现采用结构化方法对销售管理系统进行分析与设计，获得如下图所示的顶层数据流图和 0 层数据流图。（分数：15.00）(1).【问题 1】使用说明中的词语，给出上述顶层数据流图中的外部实体 E1E4 的名称。（分数：5.00）_正确答案：()解析：E

18、1：客户 E2：采购部门 E3：库房 E4：经理(2).【问题 2】使用说明中的词语，给出上述 0 层数据流图中的数据存储 D1D3 的名称。（分数：5.00）_正确答案：()解析：D1：缺货记录文件 D2：库存记录文件 D3：订单记录文件(3).【问题 3】上述 0 层数据流图中缺少了 4 条数据流，根据说明及顶层数据流图提供的信息，分别指出这 4 条数据流的起点和终点。 起 点 终 点（分数：5.00）_正确答案：()解析：起 点 终 点库存记录文件或 D2 处理订单进货处理 供货处理订单记录文件或 D3 销售统计缺货记录文件或 D1 进货处理注：数据流之间没有顺序关系试题一分析本题考查

19、DFD 的应用，属于比较传统的题目，需要细心分析题目中所描述的内容。数据流图(Data Flow Diagram，DFD)是一种便于用户理解、分析系统数据流程的图形工具。它摆脱了系统的物理内容，精确地在逻辑上描述系统的功能、输入、输出和数据存储等，是系统逻辑模型的重要组成部分。问题 1考查顶层 DFD。顶层 DFD 通常用来确定系统边界，其中只包含一个唯一的加工(即待开发的系统)、外部实体以及外部实体与系统之间的输入输出数据流。题目要求根据描述确定图中的外部实体。分析题干中描述并结合已给出的顶层数据流图，可知该销售管理系统中有客户、采购部门、库房、经理。题干中提供的关键信息如下：接受客户订单；

20、给库房开具备货单；将缺货通知单发给采购部门；打印统计报表给经理。问题 2考查 0 层 DFD，要求确定 0 层数据流图中的数据存储，题目中提到的数据存储有订单记录文件、库存记录文件和缺货记录文件。在题中给出的 0 层 DFD 中，与数据存储 D1 相关的数据流有两条，来自“处理订单”；到达“缺货统计”，分析“1接受客户订单，检查库存货物是否满足订单要求。如果满足，进行供货处理：修改库存记录文件，给库房开具备货单并且保留客户订单至订单记录文件；否则进行缺货处理：将缺货订单录入缺货记录文件。”，确定 D1 应是“缺货记录文件”。分析 0 层数据流图，到达 D2 的数据流分别来自“供货处理”和“进货

21、处理”，由“3根据采购部门提供的进货通知单进行进货处理：修改库存记录文件，并从缺货记录文件中取出缺货订单进行供货处理。”，确定 D2 为“库存记录文件”。由描述“给库房开具备货单并且保留客户订单至订单记录文件”，确定D3 为“订单记录文件”。问题 3考查缺失的数据流。比较顶层和 0 层数据流图可知，顶层数据流图中的数据流已全部体现在 0 层数据流图中。图中缺失数据流最明显的地方是“销售统计”加工只有流出的数据流而没有流入的数据流，由“给库房开具备货单并且保留客户订单至订单记录文件，根据保留的客户订单进行销售统计”可知，应存在一条从 D3(订单记录文件)至销售统计的数据流。由“接受客户订单，检查

22、库存货物是否满足订单要求”可知，处理订单时需要来自库存记录文件的数据流。当发生缺货情况时，除了“根据缺货记录文件进行缺货统计，将缺货通知单发给采购部门”，采购部门还需根据缺货记录文件进行进货处理。一旦进货成功，就可进行供货处理。二、B试题二/B(总题数：1，分数：15.00)阅读下列说明和图，回答问题 1 至问题 4，将解答填入对应栏内。【说明】某宾馆拟开发一个宾馆客房预订子系统，主要是针对客房的预订和入住等情况进行管理。【需求分析结果】1员工信息主要包括：员工号、姓名、出生年月、性别、部门、岗位、住址、联系电话和密码等信息。岗位有管理和服务两种。岗位为“管理”的员工可以更改(添加、删除和修改

23、)员工表中本部门员工的岗位和密码，要求将每一次更改前的信息保留；岗位为“服务”的员工只能修改员工表中本人的密码，且负责多个客房的清理等工作。2部门信息主要包括：部门号、部门名称、部门负责人、电话等信息。一个员工只能属于一个部门，一个部门只有一位负责人。3客房信息包括：客房号、类型、价格、状态等信息。其中类型是指单人间、三人间、普通标准间、豪华标准间等；状态是指空闲、入住和维修。4客户信息包括：身份证号、姓名、性别、单位和联系电话。5客房预定情况包括：客房号、预定日期、预定入住日期、预定入住天数、身份证号等信息。一条预定信息必须且仅对应一位客户，但一位客户可以有多条预定信息。【概念模型设计】根据

24、需求阶段收集的信息，设计的实体联系图(不完整)如下图所示。（分数：15.00）(1).【问题 1】根据问题描述，填写上图中(1)(3)处联系的类型。联系类型分为一对一、一对多和多对多三种，分别使用 1:1，1:n 或 1:*，m:n 或*:*表示。（分数：3.75）_正确答案：()解析：(1)n，或 m，或， (2)n，或 m，或： (3)n，或 m，或。(2).【问题 2】补充上图中的联系并指明其联系类型。（分数：3.75）_正确答案：()解析：需要增加员工和权限之间 m：1 的联系。 或者 (3).【问题 3】根据需求分析结果和上图，将逻辑结构设计阶段生成的关系模式中的空(4)(8)补充完

25、整。(注：一个空可能需要填多个属性)（分数：3.75）_正确答案：()解析：问题 3 (4)员工号，部门号 (5)客房号 (6)身份证号 (7)岗位 (8)客房号，身份证号(4).【问题 4】若去掉权限表，并将权限表中的操作权限属性放在员工表中(仍保持管理和服务岗位的操作权限规定)，则与原有设计相比有什么优缺点(请从数据库设计的角度进行说明)。（分数：3.75）_正确答案：()解析：若将权限表中的操作权限属性放在员工表中，则相同岗位的操作权限在员工表中重复存储，存在数据冗余。 试题二分析 本题考查数据库系统中实体联系模型(E-R 模型)的设计和关系模式的设计。 两个实体型之间的联系可以分为三类

26、：一对一联系(1:1)、一对多联系(1:n)和多对多联系(m:n)。 本题中员工和部门之间的所属联系类型为 m:1，因为题中一个员工只能属于一个部门，一个部门可以有多名员工。所以空(1)应填 m。 本题中客户和客房之间的预定联系类型为 m:n，因为题中一位客户可以预订多间客房，而客房在不同的时间段可以被多个客户预订。所以空(2)、空(3)应分别填 m 和 n。 根据题意，岗位有管理和服务两种。岗位为“管理”的员工可以更改(添加、删除和修改)员工表中本部门员工的岗位和密码，要求将每一次更改前的信息保留；岗位为“服务”的员工只能修改员工表中本人的密码，且负责多个客房的清理等工作。所以，需要增加管理

27、员和权限之间 m:1 的联系。 或者表示为 三、B试题三/B(总题数：1，分数：15.00)阅读下列说明和图，回答问题 1 至问题 4，将解答填入对应栏内。【说明】在线会议审稿系统(Online Reviewing System，ORS)主要处理会议前期的投稿和审稿事务，其功能描述如下：1用户在初始使用系统时，必须在系统中注册(register)成为作者或审稿人。2作者登录(login)后提交稿件和浏览稿件审阅结果。提交稿件必须在规定提交时间范围内，其过程为先输入标题和摘要、选择稿件所属主题类型、选择稿件所在位置 (存储位置)。上述几步若未完成，则重复；若完成，则上传稿件至数据库中，系统发送通

28、知。3审稿人登录后可设置兴趣领域、审阅稿件给出意见以及罗列录用和(或)拒绝的稿件。4会议委员会主席是一个特殊审稿人，可以浏览提交的稿件、给审稿人分配稿件、罗列录用和(或)拒绝的稿件以及关闭审稿过程。其中，关闭审稿过程须包括罗列录用和(或)拒绝的稿件。系统采用面向对象方法开发，使用 UMi 进行建模。在建模用例图时，常用的方式是先识别参与者，然后确定参与者如何使用系统来确定用例，每个用例可以构造一个活动图。参与者名称、用例和活动名称分别参见以下各表。参与者列表 名称 说明 名称 说明User 用户 Author 作者Reviewer 审稿人 PCChair 委员会主席用例名称列表名称 说明 名称

29、 说明login 登录系统 register 注册submit paper 提交稿件 browse review results 浏览稿件审阅结果close reviewing procss 关闭审稿过程 assign paper to reviewer 分配稿件给审稿人set preferences 设定兴趣领域 enter review 审阅稿件给出意见list accepted/rejectedpapers罗列录用或/和拒绝的稿件browse submittedpapers浏览提交的稿件活动名称列表名称 说明 名称 说明select paper location 选择稿件位置 uploa

30、d paper 上传稿件select subject group 选择主题类型 send notification 发送通知enter title and abstract 输入标题和摘要系统的部分用例图和提交稿件的活动图分别见下图。（分数：15.00）(1).【问题 1】根据说明中的描述，使用参与者列表的英文名称，给出 ORS 用例图中 A1A4所对应的参与者。（分数：3.75）_正确答案：()解析：A1：User A2：Author A3：Reviewer A4：PCChair(2).【问题 2】根据说明中的描述，使用用例名称列表中的英文名称，给出 ORS 用例图中 U1一 U3 所对应的

31、用例。（分数：3.75）_正确答案：()解析：U1：list accepted/rejected papers U2：browse submitted papers U3：assign paper to reviewer 注：U2 和 U3 的答案可互换(3).【问题 3】根据说明中的描述，给出 ORS 用例图中U (1) /U和U (2) /U所对应的关系。（分数：3.75）_正确答案：()解析：(1)：extend(2)：include(4).【问题 4】根据说明中的描述，使用用例名称列表和活动名称列表中的英文名称，给出提交稿件过程的活动图中 ActionlAction4 对应的活动。（分

32、数：3.75）_正确答案：()解析：Action1：enter title and abstract Action2：select subject group Action3：select paper location Action4：upload paper 试题三分析 本题涉及面向对象系统开发时的 UML 用例图、活动图以及用例之间的关联关系。 构建用例图时，常用的方式是先识别参与者，然后确定用例。创建参与者之间的继承关系是为了简化绘图。继承关系可以通过子类型“是一种”父类型进行判定。在本题中，作者和审稿人分别是一种用户，委员会主席是一种特殊审稿人。因此，A1：User、 A2：Autho

33、r、A3：Reviewer、A4：PCChair。 考查用例时，通过判断用例是哪一个特定参与者发起或者触发，来建立和参与者之间的关联。审稿人可以设定兴趣领域、审阅稿件给出意见和罗列录用或/和拒绝的稿件，因此 U1：list accepted/rejiected papers，会议委员会主席可以浏览提交的稿件、给审稿人分配稿件、罗列录用和(或)拒绝的稿件以及关闭审稿过程，U2 和 U3 分别为 browse submitted papers 和assign paper to reviewer(可互换)。 考查用例之间的关系时，extend(扩展)关系可以通过判断是否可以从一个用例的执行中，在需要

34、时转向执行另一个用例，执行完返回继续，即存在extend关系。include(包含)定义了用例之间的包含关系，用于一个用例包含另一个用例的行为的建模，通过这种方式，可以把抽象(公共)行为从多个行为中分离出来。本题中，只有作者能提交稿件，“提交稿件”时判断是否登录，如果没有登录，先“登录”，然后返回继续提交稿件，所以(1)处应填extend。审稿人可以罗列录用和(或)拒绝的稿件，会议委员会主席在关闭审稿过程时须包括罗列录用和(或)拒绝的稿件，即用例“list accepted/rejected papers”和用例“close reviewing process”存在包含关系，所以(2)处应填i

35、nclude。 可以通过为每个用例构造一个活动图对用例进一步细化。构造活动图时可以通过如下步骤进行：从一个作为起点的初始节点开始；为用例的每个主要步骤添加一个动作：从一个活动到另一个活动、决策点或终点添加一条流；在流分解成不同路线的地方添加决策，并用一个合并将各个流重新合并；在有并行执行活动的地方添加分支和联合；用一个单一的活动终止符号结束。本题中，根据说明中条目 2 中描述的提交稿件的过程构建活动图，所以 Actionl 处填enter title and abstract、Action2 处填 select subject group、 Action3 处填 select paper lo

36、cation、Action4 处填 upload paper。四、B试题四/B(总题数：1，分数：15.00)阅读下列说明，回答问题 1 至问题 3，将解答填入对应栏内。【说明】某餐厅供应各种标准的营养套餐。假设菜单上共有 n 项食物 m1，m 2，m n，每项食物 mi的营养价值为vi，价格为 pi其中 i1，2，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过 M 的营养价值最大的套餐。（分数：15.00）(1).【问题 1】下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)处。伪代码中的主要变量说明如下。n：总的食物项数；v：营养价值数组，

37、下标从 1 到 n，对应第 1 到第 n 项食物的营养价值；p：价格数组，下标从 1 到 n，对应第 1 到第 n 项食物的价格；M：总价格标准，即套餐的价格不超过 M；x：解向量(数组)，下标从 1 到 n，其元素值为 0 或 1，其中元素值为 0 表示对应的食物不出现在套餐中，元素值为 1 表示对应的食物出现在套餐中；nv：n+1 行 M+1 列的二维数组，其中行和列的下标均从 0 开始，nvij表示由前 i 项食物组合且价格不超过 j 的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为 nvnM。伪代码如下：MaxNutrientValue(n，v，p，M，x)1 for i0 t

38、o n2 nvi0 03 for j1 to M4 nv0j05 for i1 to n6 for j1 to M7 if jpi /若食物 mi不能加入到套餐中8 nvij nvi-1j9 else if U(1) /U10 nvij nvi-1j11 else12 nvij nvi-1j-pi + vi13 j M14 for in downto 115 if U(2) /U16 xi 017 else18 xi 119 U (3) /U20 return x and nvnM（分数：5.00）_正确答案：()解析：(1)nvi-1jnvi-1j-pi+vi (2)nvijnvi-1j (

39、3)jj-pi(2).【问题 2】现有 5 项食物，每项食物的营养价值和价格如下表所示。 编 码营养价值价 格m1 200 50m2 180 30m3 225 45m4 200 25m5 50 5食物营养价值及价格表若要求总价格不超过 100 的营养价值最大的套餐，则套餐应包含的食物有U (4) /U(用食物项的编码表示)，对应的最大营养价值为U (5) /U。（分数：5.00）_正确答案：()解析：(4)m 2，m 3，m 4 (注：答案中食物编码无前后顺序关系) (5) 605(3).【问题 3】问题 1 中伪代码的时间复杂度为U (6) /U(用 O 符号表示)。（分数：5.00）_正确答案：()解析：(6)O(nM)，或 O(nM)，或 O(n