算法期中考错题

多机调度问题:设有n个独立的作业{1,2,…,n}，由m台相同的机器{1,2,…,m}进行加工处理，作业i所需的处理时间为ti（1≤i≤n），每个作业均可在任何一台机器上加工处理，但未完工前不允许中断，任何作业也不能拆分成更小的子作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。贪心法求解多机调度问题的贪心策略是（）。
A. 最短处理时间作业优先，即把处理时间最短的作业分配给空闲的机器
B. 最长处理时间作业优先，即把处理时间最长的作业分配给空闲的机器
C. 最短处理时间作业优先，即把处理时间最短的作业分配给最先空闲的机器
D. 最长处理时间作业优先，即把处理时间最长的作业分配给最先空闲的机器
eg: 若2,3,4,5,6,14,16

切原木问题：给定一根长度为N米的原木；另有一个分段价格表，给出长度L=1,2,...,M对应的价格PL。要求找出适当切割原木分段出售所能获得的最大收益RN。例如，根据下面给出的价格表，若要出售一段8米长的原木，最优解是将其切割为2米和6米的两段，这样可以获得最大收益R8=P2+P6=5+17=22。而若要出售一段3米长的原木，最优解是根本不要切割，直接售出。下列哪句陈述是错的？
A. 此问题可以用动态规划求解
B. 若N≤M，则有RN=max{PN,max1≤i≤N{Ri+RN-M}}
C. 若N>M，则有RN=max1≤i≤N{Ri+RN-i}
D. 算法的时间复杂度是O(N2)
Ri+RN-i代表木头一切为二
Ri+RN-M代表i长+切去最大长M后的剩余长
https://www.cnblogs.com/nolca/p/17712407.html#特征

算法的主要特征不包括以下哪一个（ ）？
A. 有穷性
B. 确切性
C. 输入
D. 简洁性

自顶向下的（ ）法其控制结构与直接递归方法的控制结构相同，这个方法为每个解过的子问题用表格保存起来在需要时查看，避免了相同子问题的重复求解，动态规划算法是该方法的变形。
A. 分治
B. 递归
C. 备忘录
D. 贪心
答案：C

活动安排问题：有若干个活动，第i个开始时间和结束时间是[Si,fi)，只有一个会议室，活动之间不能交叠，求最多安排多少个活动。正确的贪心选择（）。
A. 活动最短的优先
B. 活动最长的优先
C. 活动开始时间最早的优先
D. 活动结束时间最早的优先
答案：D（活动不能后延。若是一堆活动最短同时举办，则都举办不了。）

贪心算法则通常以（）的方式做出一系列的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。
A. 随机
B. 自顶向下
C. 自底向上(DP)
D. 优先级
答案：迭代

当一系列子问题的最优解组成了问题的最优解，称此问题具有最优子结构性质。以上说法对吗？（）
错。原问题包含的子问题，不断递归后，才算最优子结构。