软件设计师-常用算法设计方法
(总分：29.00，做题时间：90分钟)
一、
(总题数：20，分数：29.00)
利用贪心法求解0/1背包问题时， (26) 能够确保获得最优解。用动态规划方求解O/1背包问题时，将“用前i个物品来装容量是x的背包”的0/1背包问题记为KNAP(1，i，X)设fi(X)是KNAP(1，i，X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为W和p(j=1～n)，则依次求解f0(X)，f1(X)，…，fn(X)的过程中使用的递推关系式为 (27) 。
（分数：2.00）
A.优先选取重量最小的物品 B.优先选取效益最大的物品
C.优先选取单位重量效益最大的物品 √ D.没有任何准则 解析：
A.fi(X)=min{fi-1(X),fi-1(X)+Pi} B.fi(X)=max{fi-1(X),fi-1(X-Wi)+Pi} √ C.fi(X)=min{fi-1(X-Wi),fi-1(X-Wi)+pi) D.fi(X)=max{fi-1(x-Wi),fi-1(X)+Pi}
解析：[分析] 背包问题描述如下：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值和最大。0/1背包：对于每一种物品I装入背包只有一种选择，即要么装入要么不装入，不能装入多次或只装入部分。部分背包则是对于每一种物品I可以只装入部分。
贪心法就是不求最优解，只求可行解的思想，只是局部最优，不考虑整体最优性。因此对于贪心法关键是贪心准则。对于0/1背包，贪心法之所以不一定得到最优解是因为它无法保证最终能将背包容量占满，背包空间的闲置使得背包所装物品的总价值降低了。
动态规划法是将一个不容易解决的较大问题划分为若干个易于解决的小问题。 1.拉斯维加斯(Las Vegas)算法是一种常用的 (3) 算法。
（分数：1.00） A.确定性 B.近似 C.概率 √ D.加密
解析：[分析] 概率算法允许算法在执行过程中可随机地选择下一个计算步骤。在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择要省时，因此概率算法可以在很大程度上降低算法的复杂度。
概率算法通常有两个优点。首先，较之那些我们所知的解决同——问题最好的确定性算法，概率算法所需的运行时间或空间通常小一些；其次，迄今为止所发现的概率算法总是易于理解和实现的。
概率算法可分为四类，分别是数值概率算法、蒙特卡罗算法(Monte Karlo)、拉斯维加斯算法(Las Vegas)和舍伍德算法(Sherwood)。
2.用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为 (11) 。
（分数：1.00） A.n B.[n/2] C.[log2n]
D.[log2(n+1)] √
解析：[分析] 根据二分查找的过程，由于需要栈结构实现递归算法，栈的容量应该要保证能存放查找失败时所有未完成运行的算法的活动记录。
第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n：第二次调用时，无论是在前半区还是在后半区进行查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n/2：第三次调用时，栈中又加入了—条查找记录，所确定的查找区间中的元素最多为n/4。依次类推，当所确定的查找区间中的元素为。时，递归调用该算法的次数为log2(n+1)次，查找结束。 3.快速排序算法采用的设计方法是 (23) 。
（分数：1.00）
A.动态规划法(Dynamic Programming) B.分治法(Divideand Conquer) √ C.回溯法(Backtracking)
D.分枝定界法(Branch and Bound)
解析：[分析] 快速排序算法采用的设计方法是分治法。
4.采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是 (29) 。
（分数：1.00）
A.当前所作出的决策不会影响后面的决策 B.原问题的最优解包含其子问题的最优解 √
C.问题可以找到最优解，但利用贪心法不能找到最优解 D.每次决策必须是当前看来最优的决策才可以找到最优解
解析：[分析] 动态规划策略设计算法的第一步通常是刻画最优解结构。当问题的最优解包含了子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。
动态规划策略设计算法利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。
5.在分支—限界算法设计策略中，通常采用 (4) 搜索问题的解空间。
（分数：1.00） A.深度优先 B.广度优先 √ C.自底向上 D.拓扑序列
解析：[分析] 分支-限界算法是在问题的解空间树上搜索问题解的算法，它的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出一个目标函数达到极大或极小的解，即在某种意义下的最优解。
分支—限界算法以广度优先的方式搜索解空间，其搜索策略是在扩展节点处先生成其所有的儿子节点，然后再从当前节点表中选择下一个扩展节点。 6.下面的程序段违反了算法的 (2) 原则。 Void sam()
int n=2; while(!odd(n)) n+=2 printf(n);
（分数：1.00） A.有穷性 √ B.确定性 C.可行性 D.健壮性
解析：[分析] 一个算法要求必须总是在执行有穷步之后结束，并月-每一步都可在有穷时间内完成。上述程序段违反了算法的有穷性性质，理论上将导致过程不可终止。 设求解某问题的递归算法如下： 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) 。
（分数：2.00） A.T(n)=T(n-1)+1 B.T(n)=2T(n-1) C.T(n)=2T(n-1)+1 √ D.T(n)=2T(n+1)+1 解析： A.14k B.15k √ C.16k D.17k
解析：[分析] 考虑递推关系时，只要看else部分，显然有：T(n)=2T(n-1)+1。 T(1)=1，据上述递推关系可得T(4)=15。
7.贪婪法是一种 (20) 的算法。
（分数：1.00）
A.不求最优，只求满意 √ B.只求最优 C.求取全部可行解 D.求取全部最优解
解析：[分析] 贪心法是一种不追求最优解，只希望得到较为满意解的方法。贪心法(或称贪婪法)一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。
在数据压缩编码的应用中，哈夫曼(Huffman)算法可以用来构造具有 (18) 的二叉树，这是一种采用了 (19) 的算法。
（分数：2.00） A.前缀码 B.最优前缀码 √ C.后缀码 D.最优后缀码 解析： A.贪心 √ B.分治 C.递推 D.回溯
解析：[分析] 给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码。相反，给定一个序列的集合，若不存在一个序列是另一个序列的后缀，则该序列集合称为后缀码。平均码长或文件总长最小的前缀编码称为最优的前缀码，最优的前缀码对文件的压缩效果亦最佳。
利用哈夫曼树很容易求出给定字符集及其概率分布的最优前缀码。哈夫曼编码是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据文件压缩掉20%～90%，其压缩效率取决于被压缩文件的特征。在构造哈夫曼树的过程中，每次都是选取两棵最小权值的二叉树进行合并，因此使用的是贪心算法。 以下不属于算法的基本特征的是 (7) 。穷举法的适用范围是 (8) 。
（分数：2.00） A.有确切定义的 B.可行的 C.可描述的 D.不能有二义性 解析：暂缺答案 A.一切问题
B.解的个数极多的问题 C.解的个数不太多的问题 D.不适合设计算法 解析：暂缺答案
[分析] 此题是考查算法的基本特征以及穷举法的适用范围，这些都很好理解，相信大家都能选择正确。 8.利用动态规划法求解每对节点之间的最短路径问题时，设有向图G=＜V，E＞共有n个节点，节点编号1～n，设C是G的成本邻接矩阵，用Dk(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度(Dn(i,j)即为图G中节点i到j的最短路径长度)，则求解该问题的递推关系式为 (28) 。
（分数：1.00）
A.Dk(i,j)=Dk-1(i,j)+C(i,j)
B.Dk(i,j)=minDk-1(i,j),Dk-1(i,j)+C(i,j) C.Dk(i,j)=Dk-1(i,k)+Dk-1(k,j)
D.Dk(i,j)=minDk-1(i,j),Dk-1(i,k)+Dk-1(k,j) √
解析：[分析] 从“Dk(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度”中，我们得到一个提示，在求i,j之间最短路径的时候，会考虑它经过哪些节点能缩短原来的路径。在 Dk(i,j)=min{Dk-1(i,j),Dk-1(i,k)+Dk-1(k,j)}中，Dk(i,j)表示i到j不经过k的路径长度，而 Dk-1(I,k)+Dk-1(k,j)表示i到j经过k的路径长度，且min()函数用于找最小值，所以此式正确。 9.算法是对问题求解过程的一类精确描述，算法中描述的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明算法具有 (5) 特性。
（分数：1.00） A.正确性 B.确定性 C.可行性 √ D.健壮性
解析：[分析] 一个算法具有下列5个重要特性。
有穷性：一个算法必须总是在执行有穷步之后结束，且每—步都可在有穷时间内完成。
确定性：算法中的每一条指令必须有确切的含义，读者理解时不会产生二义性，并且在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得出相同的输出。
可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。 输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
综卜所述，算法中的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明了算法的可行性特点。
在下列算法设计方法中， (16) 在求解问题的过程中并不从整体最优上加以考虑，而是作出在当前看来是最好的选择。利用该设计方法可以解决 (17) 问题。
（分数：2.00） A.分治法 B.贪心法 √ C.动态规划法 D.回溯法 解析： A.排序 B.检索 C.背包 √ D.0/1背包
解析：[分析] 贪心法是这样的一种解题方法：逐步给出解的各部分，在每一步“贪婪地”选择最好的部分解，但不顾及这样选择对整体的影响，因此一般得到的不是最好的解。
解决背包问题：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。
较高效率地解决背包问题一般用递归和贪心算法，而背包问题规模不是很大的时候，也可以采用穷举法。 对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，利用 (24) 策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n)的正确算法。串 ＜1，0，0，1，O，1，0，1＞和＜0，1，0，1，1,0,1，1＞的最长公共子序列的长度为 (25) 。
（分数：2.00） A.分治 B.贪心 C.动态规划 D.分支—限界 解析：暂缺答案 A.3 B.4 C.5 D.6
2
软件设计师-常用算法设计方法
