软件设计师-常用算法设计方法

软件设计师-常用算法设计方法 (总分：29.00，做题时间：90 分钟) 一、 (总题数：20，分数：29.00) 利用贪心法求解 0/1 背包问题时，(26) 能够确保获得最优解。用动态规划方求解 O/1 背包问题时，将“用 前 i 个物品来装容量是 x 的背包”的 0/1 背包问题记为 KNAP(1，i，X)设 f i(X)是 KNAP(1，i，X)最优解的 效益值， 第 j 个物品的重量和放入背包后取得效益值分别为 W 和 p(j=1～n)， 则依次求解 f 0(X)， f1(X)， …， f n(X)的过程中使用的递推关系式为 (27) 。 （分数：2.00） A.优先选取重量最小的物品 B.优先选取效益最大的物品 C.优先选取单位重量效益最大的物品√ D.没有任何准则 解析： A.f i(X)=min{fi-1(X),fi-1(X)+Pi} B.f i(X)=max{fi-1(X),fi-1(X-Wi)+Pi} √ C.f i(X)=min{fi-1(X-Wi),fi-1(X-Wi)+pi) D.f i(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.[log 2n] D.[log 2(n+1)] √ 解析：[分析] 根据二分查找的过程，由于需要栈结构实现递归算法，栈的容量应该要保证能存放查找失败 时所有未完成运行的算法的活动记录。 第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为 n：第二次调用时，无 论是在前半区还是在后半区进行查找， 栈中又加入了一条查找记录， 所确定的查找区间中的元素最多为n/2： 第三次调用时，栈中又加入了—条查找记录，所确定的查找区间中的元素最多为 n/4。依次类推，当所确 定的查找区间中的元素为。时，递归调用该算法的次数为 log 2(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