- 对以下排序问题，任一实例的所有可能排序，只要每台机器加工完成前不存在空闲，目标值为常数的有（ ）
- 平行机排序问题的LPT算法可如下描述：将工件按加工时间从大到小顺序排列，再按上述顺序用LS算法安排工件。以下说法正确的有（ ）
- 若问题A可多项式时间归约到问题B，则以下叙述错误的是（ ）
- 两个顶点之间至多只有一条边相连的图称为简单图，图中与一个顶点关联的边的数目称为该顶点的度。下列序列中可以是某个图的所有顶点的度的是（ ）
- 以下说法准确的有（ ）
- 以下叙述结论和逻辑均正确的是（ ）
- 若一博弈的某个策略组合是Nash均衡，以下说法准确的是（ ）
- 设A,B,C三点是等腰直角三角形的三个顶点，则连接这三个顶点的最小Steiner树长度为（ ）
- 89路公交车上设有宽体单人座，可同时坐下两人但空间较普通双人座狭窄。乘车舒适度以单人就坐最佳，与人合坐次之，站立最差。现有两人上车后发现车厢中只余这一个座位。若每人均为自身考虑，自身舒适度愈大愈好。若每人均为对方考虑，对方舒适度愈大愈好，且当对方站立时，宁愿陪同站立而不独坐。对上述两种情形，博弈的纯策略Nash均衡分别为（ ）
- 图的一个边的序列称为途径，若序列中相邻两条边有公共端点。经过任一边至多一次的途径称为迹，经过任意顶点至多一次的途径称为路。则迹未必是路，路未必是迹。（ ）
- Hamilton圈问题和TSP问题的判定形式都是NP-完全问题，因此既存在从前者到后者的多项式时间归约，也存在从后者到前者的多项式时间归约。（ ）
- 一寝室住有四名同学。一日学园举行某项活动，有至少两名同学参与该项活动的寝室将获得奖励。每位同学有参加或不参加两种选择。他们都希望寝室能获得奖励，同时倾向于自己不参加活动。当然在自己参加活动而寝室获得奖励与自己不参加活动而寝室未获奖励之间更偏好前种情况。该博弈的Nash均衡有（ ）。
- 若博弈的某个策略组合不是Nash均衡，则每位参与者均可通过单方面改变自身的策略使其费用减少。（ ）
- 考虑背包问题的下述算法，首先将物品按某种顺序排列，随后逐个放入背包，直至有物品不能放入背包时，算法终止。以下物品排列顺序，可使该算法的最坏情况比为有限常数的是（ ）。
- 以下字符集，不能作为字母表的是（ ）。
- 以下对背包问题最优解的描述，正确的是（ ）
答案:
答案:
答案:
答案:
答案:
答案:LPT算法的最坏情况比不大于LS算法的最坏情况比。###LPT算法给出的排序必是一个Nash均衡。
答案:B必能多项式时间归约到A###若B是NP-难问题，则A也是NP-难问题。###若A多项式时间可解，则B也多项式时间可解。###B不能多项式时间归约到A
答案:
答案:1,1,1,2,3###3,3,3,3
答案:划分问题是NP-完全问题，TSP是NP-难问题。###划分问题是NP-难问题，TSP也是NP-难问题。
答案:
温馨提示支付 ￥3.00 元后可查看付费内容,请先翻页预览!
