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