2024知到网课 组合优化智慧树答案

第一章 单元测试

1、判断题：设是欧氏平面上三个点，连接这三个点的最小Steiner树长度必小于这三个点形成的赋权完全图的最小生成树长度。（）
A:错
B:对
正确答案:【错】

2、单选题：以下对背包问题最优解的描述，正确的是（）
A:对于离散形式的背包问题，最优解中放入背包的物品大小之和为背包的容量。

B:对于连续形式的背包问题，最优解中放入背包的物品大小之和为背包的容量。

C:对于连续形式的背包问题，放入背包的物品大小之和为背包容量的解必为最优解。

D:对于离散形式的背包问题，放入背包的物品大小之和为背包容量的解必为最优解。

正确答案:【对于连续形式的背包问题，最优解中放入背包的物品大小之和为背包的容量。
】

3、单选题：考虑下面的批排序问题。若干个工件需在一台批处理机上加工，工件的大小为。大小之和不超过的若干个工件可作为一批同时加工，每批的加工时间均相等。工件的完工时间定义为它所在批的完工时间，目标为极小化工件最大完工时间。与该问题等价的问题是（）。
A:台机器的平行机排序问题

B:背包容量为的背包问题

C:其他选项都不对

D:箱容量为的一维装箱问题

正确答案:【箱容量为的一维装箱问题
】

4、多选题：以下字符集，不能作为字母表的是（）。
A:

B:

C:

D:

正确答案:【
;
;
】

5、多选题：考虑单台机排序问题，工件集依次在一机器上加工，机器在同一时间只能加工一个工件，工件的加工时间为，则所有工件的完工时间之和为（）。
A:

B:

C:

D:

正确答案:【
;
】

第二章 单元测试

1、判断题：若，则。 （）
A:对
B:错
正确答案:【错】

2、单选题：设为阶方阵。现用以下算法求。
算法：For i = 1 to n do
For j = 1 to n do
 = 0
For k = 1 to n do

输出
该算法的时间复杂度为（）。
A:

B:

C:

D:

正确答案:【
】

3、单选题：若NP，以下能说明是NP-C问题的是（）。
A:对任意NP，。

B:存在NP，。

C:对任意NP-C，。

D:存在NP-C，。

正确答案:【对任意NP，。
】

4、多选题：设有个城市的TSP问题实例，城市之间距离为，以下是该实例规模合理表达式的有（）。
A:

B:

C:

D:

正确答案:【
;
;
】

5、多选题：设一平行机排序问题算法的时间复杂度为，其中分别为机器数和工件数，为一与实例无关的常数。以下说法准确的有（）。
A:若在该问题中，机器数可能随实例不同而变化，该算法是一个指数时间算法。

B:若在该问题中，机器数是一个固定常数，该算法是一个指数时间算法。

C:若在该问题中，机器数可能随实例不同而变化，该算法是一个多项式时间算法。

D:若在该问题中，机器数是一个固定常数，该算法是一个多项式时间算法。