阅读下列说明和C代码，将应填入（n）处的字句写在答题纸的对应栏内。说明：设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量Wij和价格Cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。采用回溯法来求解该问题。首先定义解空间。解空间由长度为n的向量组成，其中每个分量取值来自集合{1，2，…，m}，将解空间用树形结构表示。接着从根节点开始，以深度优先的方式搜索整个解空间。从根节点开始，根节点成为活节点，同时也成为当前的扩展节点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新节点。判断当前的机器价格（C11）是否超过上限（cc），重量（W11）是否比当前已知的解（最小重量）大，若是，应回溯至最近的一个活节点；若否，则该新节点成为活节点，同时也成为当前的扩展节点，根节点不再是扩展节点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新节点。同样判断当前的机器价格（C11+C21）是否超过上限（cc），重量（W11+W21）是否比当前已知的解（最小重量）大。若是，应回溯至最近的一个活节点；若否，则该新节点成为活节点，同时也成为当前的扩展节点，原来的节点不再是扩展节点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活节点为止。C代码：下面是该算法的C语言实现。（1）变量说明n：机器的部件数。m：供应商数。cc：价格上限。w［］［］：二维数组，w［i］［j］表示第j个供应商供应的第i个部件的重量。c［］［］：二维数组，c［i］［j］表示第j个供应商供应的第i个部件的价格。bestW：满足价格上限约束条件的最小机器重量。bestC：最小重量机器的价格。bestX［］：最优解，一维数组，bestX［i］表示第i个部件来自哪个供应商。cw：搜索过程中机器的重量。cp：搜索过程中机器的价格。x［］：搜索过程中产生的解，x［i］表示第i个部件来自哪个供应商。i：当前考虑的部件，从0到n-1。j：循环变量（2）函数backtrack -题库考试答案搜索网

阅读下列说明和C代码，将应填入（n）处的字句写在答题纸的对应栏内。说明：设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量Wij和价格Cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。采用回溯法来求解该问题。首先定义解空间。解空间由长度为n的向量组成，其中每个分量取值来自集合{1，2，…，m}，将解空间用树形结构表示。接着从根节点开始，以深度优先的方式搜索整个解空间。从根节点开始，根节点成为活节点，同时也成为当前的扩展节点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新节点。判断当前的机器价格（C11）是否超过上限（cc），重量（W11）是否比当前已知的解（最小重量）大，若是，应回溯至最近的一个活节点；若否，则该新节点成为活节点，同时也成为当前的扩展节点，根节点不再是扩展节点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新节点。同样判断当前的机器价格（C11+C21）是否超过上限（cc），重量（W11+W21）是否比当前已知的解（最小重量）大。若是，应回溯至最近的一个活节点；若否，则该新节点成为活节点，同时也成为当前的扩展节点，原来的节点不再是扩展节点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活节点为止。C代码：下面是该算法的C语言实现。（1）变量说明n：机器的部件数。m：供应商数。cc：价格上限。w［］［］：二维数组，w［i］［j］表示第j个供应商供应的第i个部件的重量。c［］［］：二维数组，c［i］［j］表示第j个供应商供应的第i个部件的价格。bestW：满足价格上限约束条件的最小机器重量。bestC：最小重量机器的价格。bestX［］：最优解，一维数组，bestX［i］表示第i个部件来自哪个供应商。cw：搜索过程中机器的重量。cp：搜索过程中机器的价格。x［］：搜索过程中产生的解，x［i］表示第i个部件来自哪个供应商。i：当前考虑的部件，从0到n-1。j：循环变量（2）函数backtrack

问答题

2021-09-01 12:07

查看答案

正确答案

（1）bestX［j］=x［j］
（2）j<m
（3）x［i］=j
（4）cw<bestW
（5）cp=cp-c［i］［j］

试题解析

标签：算法设计和分析中级软件设计师

感兴趣题目

阅读以下说明和C++代码，将应填入_____处的字句写在答题纸的对应栏内。【说明】已知类LinkedList表示列表类，该类具有4个方法：addElement（）、lastElement（）、numberOfElement（）以及removeLastElement（）。4个方法的含义分别如下。voidaddElement（Obect）：在列表尾部添加一个对象。ObjectlastElement（）：返回列表尾部对象。intnumberOfElement（）：返回列表中对象的个数。voidremoveLastElement（）：删除列表尾部的对象。现需要借助LinkedList来实现一个Stack栈类，C++代码1和C++代码2分别采用继承和组合的方式来实现。【C++代码1】

【C++代码2】

【问题】若类LinkedList新增加了一个公有的方法removeElement（intindex），用于删除列表中第index个元素，则在用继承和组合两种实现栈类Stack的方式中，哪种方式下Stack对象可访问方法removeElement（intindex）？__（5）__（A.继承B.组合）

阅读下列说明和Java代码，将应填入（n）处的字句写在答题纸的对应栏内。说明：某饭店在不同的时段提供多种不同的餐饮，其菜单的结构图如图10.43所示

。现在采用组合（Composition）模式来构造该饭店的菜单，使得饭店可以方便地在其中添加新的餐饮形式，得到如图10.44所示的类图。其中MenuComponent为抽象类，定义了添加（add）新菜单和打印饭店所有菜单信息（print）的方法接口。类Menu表示饭店提供的每种餐饮形式的菜单，如煎饼屋菜单、咖啡屋菜单等。每种菜单中都可以添加子菜单，例如图10.43中的甜点菜单。类Menultem表示菜单中的菜式。

Java代码如下：

阅读以下说明和C函数，将应填入____处的语句或语句成分写在答题纸的对应栏内。已知单链表L含有头节点，且节点中的元素值以递增的方式排列。下面的函数DeleteList在L中查找所有值大于minK且小于maxK的元素，若找到，则逐个删除，同时释放被删节点的空间。若链表中不存在满足条件的元素，则返回-1，否则返回0。例如，某单链表如图11-3所示。若令minK为20，maxK为50，则删除后的链表如图11-4所示。

链表节点类型定义如下：

【C函数】

阅读下列说明和C代码，将应填入（n）处的字句写在答题纸的对应栏内。说明：设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量Wij和价格Cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。采用回溯法来求解该问题。首先定义解空间。解空间由长度为n的向量组成，其中每个分量取值来自集合{1，2，…，m}，将解空间用树形结构表示。接着从根节点开始，以深度优先的方式搜索整个解空间。从根节点开始，根节点成为活节点，同时也成为当前的扩展节点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新节点。判断当前的机器价格（C11）是否超过上限（cc），重量（W11）是否比当前已知的解（最小重量）大，若是，应回溯至最近的一个活节点；若否，则该新节点成为活节点，同时也成为当前的扩展节点，根节点不再是扩展节点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新节点。同样判断当前的机器价格（C11+C21）是否超过上限（cc），重量（W11+W21）是否比当前已知的解（最小重量）大。若是，应回溯至最近的一个活节点；若否，则该新节点成为活节点，同时也成为当前的扩展节点，原来的节点不再是扩展节点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活节点为止。 C代码：下面是该算法的C语言实现。（1）变量说明n：机器的部件数。m：供应商数。cc：价格上限。w［］［］：二维数组，w［i］［j］表示第j个供应商供应的第i个部件的重量。c［］［］：二维数组，c［i］［j］表示第j个供应商供应的第i个部件的价格。bestW：满足价格上限约束条件的最小机器重量。bestC://最小重量机器的价格。bestX［］：最优解，一维数组，bestX［i］表示第i个部件来自哪个供应商。cw：搜索过程中机器的重量。cp：搜索过程中机器的价格。x［］：搜索过程中产生的解，x［i］表示第i个部件来自哪个供应商。i：当前考虑的部件，从0到n-1。j：循环变量（2）函数backtrack 代码如下：

阅读下列说明，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】某出版社要制作一批电子出版物，主要工作是将原始的一些纸质文档数字化，并利用多媒体软件制作成多媒体光盘的形式发行，其制作的基本流程图如图14-3所示。

目前制作多媒体作品的软件主要有两种类型：专门的多媒体制作工具和高级语言。试分析这两种工具的特点，并指出该出版社应该选用哪种类型的工具。

阅读以下说明和C函数，将应填入____处的语句或语句成分写在答题纸的对应栏内。说明1：函数deldigit（char*s）的功能是将字符串s中的数字字符去掉，使剩余字符按原次序构成一个新串，并保存在原串空间中。其思路是：先申请一个与s等长的临时字符串空间并令t指向它，将非数字字符按次序暂存入该空间，最后再复制给s。【C函数】

说明2：函数reverse（char*s，intlen）的功能是用递归方式逆置长度为len的字符串s。例如，若串s的内容为"abcd"，则逆置后其内容变为"dcba"。【C函数】

软件设计规格说明书包括设计说明、文件结构和全局数据等，下列选项中，应属于模块说明的内容是______。

阅读以下说明和C++代码，将应填入____处的语句或语句成分写在答题纸的对应栏内。某数据文件students.txt的内容为100名学生的学号和成绩，下面的程序将文件中的数据全部读入对象数组，按分数从高到低进行排序后选出排名前30%的学生。【C++代码】

软件体系结构的评估与分析是指通过对复杂应用系统软件体系结构设文档、设计过程、代码、实现过程的评估与审查等手段来判断软件的（），增强软件的质量；在真正的错误的设计导致真的灾难前（），选择更好的结构或（）结构的设计。

概要设计通过对系统的结构表示进行细化，得到软件的数据结构和算法。

请认真阅读下列材料，并按要求作答。根据教学目标和重点，设计方程的解与解方程概念部分的教学并简要说明设计理由。

论设计模式在软件开发中的应用设计模式描述了在特定场景下解决一般设计问题的类和相互通信的对象。一个设计模式命名、抽象并确定了一个通用设计结构的主要方面，这些设计结构能被用来构造可复用的面向对象设计。现在，设计模式已经广泛地应用在软件开发中。请围绕"设计模式在软件开发中的应用"论题，依次对以下3个方面进行论述： ①概要叙述你参与分析和开发的应用项目，以及你所担任的主要工作。 ②简要介绍设计模式的基本概念及分类，详细说明在你所参与分析和开发的应用项目中应用了哪些设计模式、方法，以及选用它们的原因。 ③分析并讨论使用设计模式的效果，并分析和评价设计模式对软件开发的影响。