已知非齐次递归方程：其中，b、c是常数，g（n）是n的某一个函数。则f（n）...

问答题 已知非齐次递归方程：其中，b、c是常数，g（n）是n的某一个函数。则f（n）的非递归表达式为：现有Hanoi塔问题的递归方程为：，求h（n）的非递归表达式。

利用给出的关系式，此时有：b=2,c=1,g(n)=1,从n递推到1，有：

1.问答题求证：O（f（n））+O（g（n））=O（max{f（n），g（n）}）。

2.问答题举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。

3.填空题用回溯法解批处理作业调度问题时，该问题的解空间结构为（）结构。

4.填空题用回溯法解0/1背包问题时，该问题的解空间结构为（）结构。

5.填空题回溯法的算法框架按照问题的解空间一般分为（）算法框架与（）算法框架。

6.填空题用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）

7.填空题回溯法是指（）。

8.填空题所谓最优子结构性质是指（）。

9.填空题所谓贪心选择性质是指（）。

10.问答题 有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为多少？

{1，4，8，11}