浙江大学
第一章单元测试
- 设
是欧氏平面上三个点，连接这三个点的最小Steiner树长度必小于这三个点形成的赋权完全图的最小生成树长度。（ ） - 以下对背包问题最优解的描述，正确的是（ ）
考虑下面的批排序问题。若干个工件需在一台批处理机上加工，工件
的大小为
。大小之和不超过
的若干个工件可作为一批同时加工，每批的加工时间均相等。工件的完工时间定义为它所在批的完工时间，目标为极小化工件最大完工时间。与该问题等价的问题是（ ）。- 以下字符集，不能作为字母表的是（ ）。
- 考虑单台机排序问题，工件集
依次在一机器上加工，机器在同一时间只能加工一个工件，工件
的加工时间为
，则所有工件的完工时间之和为（ ）。
A:对 B:错
答案:错
A:对于连续形式的背包问题，最优解中放入背包的物品大小之和为背包的容量。
B:对于离散形式的背包问题，最优解中放入背包的物品大小之和为背包的容量。
C:对于离散形式的背包问题，放入背包的物品大小之和为背包容量的解必为最优解。
D:对于连续形式的背包问题，放入背包的物品大小之和为背包容量的解必为最优解。
答案:对于连续形式的背包问题，最优解中放入背包的物品大小之和为背包的容量。
A:
台机器的平行机排序问题B:箱容量为
的一维装箱问题C:背包容量为
的背包问题D:其他选项都不对
答案:箱容量为
的一维装箱问题A:
B:
C:
D:
答案:
###
###
A:
B:
C:
D:
答案:
###
