文档介绍：软件设计师-常用算法设计方法
(总分：，做题时间：90 分钟)
(总题数：20，分数：)
利用贪心法求解0/1背包问题时，(26)能够确保获得最优解。用动态规划方求解0/1背包问题时，将“用前i个物品来装容量是x问题的解空间。
(分数： )
深度优先
广度优先 V
自底向上
拓扑序列
解析：［分析］分支-限界算法是在问题的解空间树上搜索问题解的算法，它的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出一个目标函数达到极大或极小的解，即在某种意义下的最优解。
分支—限界算法以广度优先的方式搜索解空间，其搜索策略是在扩展节点处先生成其所有的儿子节点，然后再从当前节点表中选择下一个扩展节点。
下面的程序段违反了算法的(2)原则。
Void sam()
int n=2; while(!odd(n)) n+=2 printf(n);
(分数：)
有穷性丿
确定性
可行性
健壮性
解析：［分析］一个算法要求必须总是在执行有穷步之后结束，并月-每一步都可在有穷时间内完成。上述程序段违反了算法的有穷性性质，理论上将导致过程不可终止。
设求解某问题的递归算法如下：
F(int n)
if n=1
Move(1)
else
F(n-1)；
Move(n)；
F(n-1)；
求解该算法的计算时间时，仅考虑算法 Move 所做的计算为主要计算，且 Move 为常数级算法。则算法 F 的计算时间T(n)的递推关系式为丄9)；设算法Move的计算时间为k,当n=4时，算法F的计算时间为(10)。
(分数：)
T(n)=T(n-1)+1
T(n)=2T(n-1)
T(n)=2T(n-1)+1 丿
T(n)=2T(n+1)+1
解析：
14k
15k 丿
16k
17k
解析：［分析］考虑递推关系时，只要看else部分，显然有：T(n)=2T(n-1)+1。T(1)=1,据上述递推关系可得 T(4)=15。
贪婪法是一种(20)的算法。
(分数： )
不求最优，只求满意丿
只求最优
求取全部可行解
求取全部最优解
解析：［分析］贪心法是一种不追求最优解，只希望得到较为满意解的方法。贪心法(或称贪婪法)一般可以
快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。
在数据压缩编码的应用中，哈夫曼(Huffman)算法可以用来构造具有皿)的二叉树，这是一种采用了_(191 的算法。
(分数：)
前缀码
最优前缀码丿
后缀码
最优后缀码
解析：
贪心 V
分治
递推
回溯
解析：［分析］给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码。相反，给定一个序列的集合，若不存在一个序列是另一个序列的后缀，则该序列集合称为后缀码。平均码长或文件总长最小的前缀编码称为最优的前缀码，最优的前缀码对文件的压缩效果亦最佳。
利用哈夫曼树很容易求出给定字符集及其概率分布的最优前缀码。哈夫曼编码是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据文件压缩掉20%〜90%，其压缩效率取决于被压缩文件的特征。在构造哈夫曼树的过程