软件设计师

《软件设计师》由会员分享，可在线阅读，更多相关《软件设计师（7页珍藏版）》请在金锄头文库上搜索。

1、软件设计师-常用算法设计方法(总分：29.00，做题时间：90 分钟)(总题数：20，分数：29.00)利用贪心法求解0/1背包问题时，(26)能够确保获得最优解。用动态规划方求解0/1背包问题时，将“用 前i个物品来装容量是x的背包”的0/1背包问题记为KNAP(1，i，X)设f/X)是KNAP(1，i，X)最优解的 效益值，第j个物品的重量和放入背包后取得效益值分别为W和p(j=1n)，则依次求解f (X), f (X)， 01f (X)的过程中使用的递推关系式为(27)。n(分数：2.00)A. 优先选取重量最小的物品B. 优先选取效益最大的物品C. 优先选取单位重量效益最大的物品丿D.

2、 没有任何准则解析：A. f(X)=minf-1(X),f-1(X)+PiiiiB. f (X)=maxf -1(X),f -1(X-W )+P 丿iiii iC. f(X)=minf-1(X-W),f-1(X-W)+p)iii ii iD. f(X)=maxf-1(x-W),f-1(X)+Piii ii解析：分析背包问题描述如下：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品 的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值和最大。 0/1 背包：对于每 一种物品 I 装入背包只有一种选择，即要么装入要么不装入，不能装入多次或只装入部分。部分背包则是 对于

3、每一种物品 I 可以只装入部分。贪心法就是不求最优解，只求可行解的思想，只是局部最优，不考虑整体最优性。因此对于贪心法关键是 贪心准则。对于 0/1 背包，贪心法之所以不一定得到最优解是因为它无法保证最终能将背包容量占满，背 包空间的闲置使得背包所装物品的总价值降低了。动态规划法是将一个不容易解决的较大问题划分为若干个易于解决的小问题。1.拉斯维加斯(Las Vegas)算法是一种常用的(3)算法。(分数： 1.00)A. 确定性B. 近似C. 概率丿D. 加密解析： 分析 概率算法允许算法在执行过程中可随机地选择下一个计算步骤。在许多情况下，当算法在执 行过程中面临一个选择时，随机性选择常比

4、最优选择要省时，因此概率算法可以在很大程度上降低算法的 复杂度。概率算法通常有两个优点。首先，较之那些我们所知的解决同问题最好的确定性算法，概率算法所需 的运行时间或空间通常小一些；其次，迄今为止所发现的概率算法总是易于理解和实现的。概率算法可分为四类，分别是数值概率算法、蒙特卡罗算法(Monte Karlo)、拉斯维加斯算法(Las Vegas) 和舍伍德算法(Sherwood)。2用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应 为)。(分数：1.00)A. nB. n/2C. log n2D. log (n+1) V2解析：分析 根据二分查找的过

5、程，由于需要栈结构实现递归算法，栈的容量应该要保证能存放查找失败 时所有未完成运行的算法的活动记录。第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n：第二次调用时，无 论是在前半区还是在后半区进行查找，栈中又加入了一条查找记录,所确定的查找区间中的元素最多为n/2： 第三次调用时，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n/4。依次类推，当所确 定的查找区间中的元素为。时，递归调用该算法的次数为log (n+1 )次，查找结束。23快速排序算法采用的设计方法是(23)。(分数： 1.00)A. 动态规划法(Dynamic Programming)B.

6、分治法(Divideand Conquer) VC. 回溯法(Backtracking)D. 分枝定界法(Branch and Bound)解析： 分析 快速排序算法采用的设计方法是分治法。4. 采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是4K。(分数： 1.00)A. 当前所作出的决策不会影响后面的决策B. 原问题的最优解包含其子问题的最优解 VC. 问题可以找到最优解，但利用贪心法不能找到最优解D. 每次决策必须是当前看来最优的决策才可以找到最优解解析： 分析 动态规划策略设计算法的第一步通常是刻画最优解结构。当问题的最优解包含了子问题的最 优解时，称该问题具有最优子结构性

7、质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重 要线索。动态规划策略设计算法利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造 出整个问题的最优解。5. 在分支一限界算法设计策略中，通常采用4K搜索问题的解空间。(分数： 1.00)A. 深度优先B. 广度优先 VC. 自底向上D. 拓扑序列解析： 分析 分支-限界算法是在问题的解空间树上搜索问题解的算法，它的求解目标是找出满足约束条 件的一个解，或是在满足约束条件的解中找出一个目标函数达到极大或极小的解，即在某种意义下的最优 解。分支限界算法以广度优先的方式搜索解空间，其搜索策略是在扩展节点处先生成其所有的

8、儿子节点，然 后再从当前节点表中选择下一个扩展节点。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=1Move(1)elseF(n-1)；Move(n)；F(n-1)；求解该算法的计算时间时，仅考虑算法 Move 所做的计算为主要计算，且

9、 Move 为常数级算法。则算法 F 的 计算时间T(n)的递推关系式为丄9)；设算法Move的计算时间为k,当n=4时，算法F的计算时间为(10)。(分数：2.00)A. T(n)=T(n-1)+1B. T(n)=2T(n-1)C. T(n)=2T(n-1)+1丿D. T(n)=2T(n+1)+1解析：A. 14kB. 15k 丿C. 16kD. 17k解析：分析考虑递推关系时，只要看else部分，显然有：T(n)=2T(n-1)+1。T(1)=1,据上述递推关系 可得 T(4)=15。7. 贪婪法是一种(20)的算法。(分数： 1.00)A. 不求最优，只求满意丿B. 只求最优C. 求取全

10、部可行解D. 求取全部最优解解析： 分析 贪心法是一种不追求最优解，只希望得到较为满意解的方法。贪心法(或称贪婪法)一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。在数据压缩编码的应用中，哈夫曼(Huffman)算法可以用来构造具有皿)的二叉树，这是一种采用了_(191 的算法。(分数：2.00)A. 前缀码B. 最优前缀码丿C. 后缀码D. 最优后缀码解析：A. 贪心 VB. 分治C. 递推D. 回溯解析：分析 给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码。 相反，给定一个序列的集合，若不存在一个序列是另一个序列的后缀，则

11、该序列集合称为后缀码。平均码 长或文件总长最小的前缀编码称为最优的前缀码，最优的前缀码对文件的压缩效果亦最佳。利用哈夫曼树很容易求出给定字符集及其概率分布的最优前缀码。哈夫曼编码是一种应用广泛且非常有效 的数据压缩技术，该技术一般可将数据文件压缩掉20%90%，其压缩效率取决于被压缩文件的特征。在构 造哈夫曼树的过程中，每次都是选取两棵最小权值的二叉树进行合并，因此使用的是贪心算法。以下不属于算法的基本特征的是九。穷举法的适用范围是4。(分数：2.00)A. 有确切定义的B. 可行的C. 可描述的D. 不能有二义性 解析：暂缺答案A. 一切问题B. 解的个数极多的问题C. 解的个数不太多的问题

12、D. 不适合设计算法 解析：暂缺答案分析 此题是考查算法的基本特征以及穷举法的适用范围，这些都很好理解，相信大家都能选择正确。8利用动态规划法求解每对节点之间的最短路径问题时，设有向图G=V, E共有n个节点，节点编号1 n,设C是G的成本邻接矩阵，用D(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度 k(D (i,j)即为图G中节点i到j的最短路径长度)，则求解该问题的递推关系式为(28)。n(分数：1.00)A. D(i,j)=D-1(i,j)+C(i,j)kkB. D(i,j)=minD-1(i,j),Dk-1(i,j)+C(i,j)kkC. D(i,j)=Dk-1(i

13、,k)+D-1(k,j)kkD. D(i,j)=minD-1(i,j),D-1(i,k)+D-1(k,j)Vkkkk解析：分析从“D (i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度”中，我们得 k到一个提示，在求i,j之间最短路径的时候，会考虑它经过哪些节点能缩短原来的路径。在D (i,j)=minD T(i,j),D T(i,k)+D T(k,j)中，D (i,j)表示 i 到 j 不经过 k 的路径长度，而kkkkkDk-1(I,k)+Dk-1(k,j)表示i到j经过k的路径长度，且min()函数用于找最小值，所以此式正确。9. 算法是对问题求解过程的一类精确描述，算法

14、中描述的操作都是可以通过已经实现的基本操作在限定时 间内执行有限次来实现的，这句话说明算法具有上丄特性。（分数：1.00）A. 正确性B. 确定性C. 可行性丿D. 健壮性解析：分析 一个算法具有下列5 个重要特性。 有穷性：一个算法必须总是在执行有穷步之后结束，且每步都可在有穷时间内完成。 确定性：算法中的每一条指令必须有确切的含义，读者理解时不会产生二义性，并且在任何条件下，算法 只有惟一的一条执行路径，即对于相同的输入只能得出相同的输出。 可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定

15、的对象的集合。 输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。 综卜所述，算法中的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说 明了算法的可行性特点。在下列算法设计方法中，A16L在求解问题的过程中并不从整体最优上加以考虑，而是作出在当前看来是 最好的选择。利用该设计方法可以解决（17）问题。（分数：2.00）A. 分治法B. 贪心法丿C. 动态规划法D. 回溯法 解析：A. 排序B. 检索C. 背包丿D. 0/1 背包解析：分析 贪心法是这样的一种解题方法：逐步给出解的各部分，在每一步“贪婪地”选择最好的部分 解，但不顾及这样选择对整体的影响，因此一般得到的不是最好的解。解决背包问题：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选 中物品的总重量不超过指定的限制重量，但选中物品的价值之和