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