1、计算机算法设计与分析复习题一、填空题1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有_时间复杂性和空间复杂性之分。2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致 相同。3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下， 搜索的时间复杂性为0( 1)，在最坏情况下，搜索的时间复杂性为O(_logn_)。4、已知一个分治算法耗费的计算时间 T(n)，T(n)满足如下递归方程：T(n) = 0( 1)(2T (n/2)+0(n)解得此递归方可得T(n)= O (_ n log n。这种方法
2、不同于动态5、动态规划算法有一个变形方法_备忘录方法规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过 的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。6. 递归的二分查找算法在divide阶段所花的时间是 0(1)，conquer阶段所花的时间是 T(n/2)，算法的时间复杂度是O( log n) _。7 . Prim算法利用贪心策略求解最小牛成树问题,其时间复杂度是 O(n2)。回溯法8、 背包冋题可用，等策略求解。9、 用动态规划算法计算矩阵连乘问题的最优值所花的时间是O( n3)，问题空间大小是O( n2)。10、 图的m着色问题可用回溯法求解
3、，其解空间树中叶子结点个数是mn ，解空间树中每个内结点的孩子数是_m。11、 单源最短路径问题可用贪心法、分支限界等策略求解。12、一个算法的优劣可以用(时间复杂度。与(空间复杂度。与来衡量。13、 回溯法在问题的解空间中，按(深度优先方式)从根结点出发搜索解空间树。14、直接或间接地调用自身的算法称为(递归算法)。15、 日记号在算法复杂性的表示法中表示(渐进确界或紧致界)016、 在分治法中，使子问题规模大致相等的做法是出自一种(平衡(banlancing) 子问题。的思想。17、动态规划算法适用于解(具有某种最优性质。问题。18、贪心算法做出的选择只是(在某种意义上的局部。最优选择。1
4、9、20、21、22、23、最优子结构性质的含义是（ 问题的最优解包含其子问题的最优解 ）。 回溯法按（ 深度优先 ）策略从根结点出发搜索解空间树。 拉斯维加斯算法找到的解一定是（ 正确解 ）。按照符号 O 的定义 O（f）+O（g） 等于 O（maxf（n）,g（n） 。 二分搜索技术是运用（ 分治 ）策略的典型例子。 动态规划算法中，通常不同子问题的个数随问题规模呈（ 多项式 ）级增长。最优子结构性质 ）和（ 子问题重叠性质 ）是采用动态规划算法的两个基本29、 择，30、 法）31、24、 25、要素。26、（最优子结构性质 ）和（ 贪心选择性质 ）是贪心算法的基本要素。27、（选择能产
5、生最优解的贪心准则 ）是设计贪心算法的核心问题。28、分支限界法常以（ 广度优先 ） 或（以最小耗费 （最大效益 ）优先）的方式搜 索问题的解空间树。贪心选择性质是指所求问题的整体最优解可以通过一系列 （局部最优 ）的选 即贪心选择达到。按照活结点表的组织方式的不同，分支限界法包括（队列式（FIFO）分支限界 和（ 优先队列式分支限界法 ）两种形式。如果对于同一实例， 蒙特卡洛算法不会给出两个不同的正确解答， 则称该蒙 特卡洛算法是（ 一致的 ）。32、哈夫曼编码可利用（ 贪心法）算法实现。33概率算法有数值概率算法，蒙特卡罗（Monte Carlo ）算法，拉斯维加斯（LasVegas）算法
6、和舍伍德（Sherwood）算法34以自顶向下的方式求解最优解的有（ 贪心算法）35、 下列算法中通常以自顶向下的方式求解最优解的是（贪心法）。36、在对问题的解空间树进行搜索的方法中 , 一个活结点有多次机会成为活结点 的是（ 回溯法）37、 旅行售货员问题不能用（）解决可以用回溯法解决，分支限界法， NP 完 全性理论与近似算法38、贪心算法不能解决（ 0-1 背包问题 N 皇后问题 ）。可以解决背包问题39、投点法是（ 概率算法）的一种。40、若线性规划问题存在最优解，它一定不在（ 可行域内部 ）二、简答题1、（8 分）写出下列复杂性函数的偏序关系（即按照渐进阶从低到高排序）2n 3n
7、log n n! nlog n n2 nn 103参考解答：103 Y log n Y nlog n y n2 3 n!Y nn每个选手必须与其他选手各赛一次; 每个选手一天只能赛一次；循环赛一共进行n - 1天。2、(8分)现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比 赛日程表：(1)(2)请利用分治法的思想，给这8位运动员设计一个合理的比赛日程。 参考解答：(3)表示结束租用时刻，10个客户的申请如下表所示:i12345678910s(i)03153511886f(i)65498713121110同一时刻，该羽毛球场只能租借给一位客户， 请设计一个租用安排方案，在 这10位
8、客户里面，使得体育馆能尽可能满足多位客户的需求，并算出针对上表 的10个客户申请，最多可以安排几位客户申请。参考解答：将这10位客户的申请按照结束时间f(i)递增排序，如下表：i12345678910s(i)13053568811f(i)45678910111213选择申请1 (1,4 )依次检查后续客户申请，只要与已选择的申请相容不冲突，则选择该申请。直 到所有申请检查完毕。申请 4( 5,7 )、申请8( 8,11 )、申请10( 11,13)最后，可以满足：申请1 (1,4 )、申请4(5,7 )、申请8(8,11 )、申请10( 11,13) 共4个客户申请。这已经是可以满足的最大客户
9、人数。4、（8分）对于矩阵连乘所需最少数乘次数问题，其递归关系式为：.I0i=j皿 j=佃nmi,k +mk+1, j + PiPkPjj其中mi，j为计算矩阵连乘Ai, Aj所需的最少数乘次数，“为矩阵Ai的行,p为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为:AAAA50x1010x4040x30305p 0X p 1p 1X p 2P 2% P 3P 3X P 4请根据以上的递归关系，计算出矩阵连乘积A AAA所需要的最少数乘次数。参考解答：m11 + m24 +90944=0+ 8000 + 50咒 10咒 5 = 10500m14 =min m12 +m34 + p? p4 =2
10、0000+ 6000 +50x40x 5 = 36000m13pm44 + Po p3 P4 = 27000 + 0 + 50x 30x 5 = 34500 =105005、（8分）有这样一类特殊0-1背包问题：可选物品 重量越轻的物品价值越高。n=6, c=20，P= （4, 8，15，1，6，3），W=（5，3，2，10，4，8）。其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重 量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的 物品总价值最大，能获得的最大总价值多少？参考解答：因为该0-1背包问题比较特殊，恰好重量越轻的物品价值越高，所 以优先取
11、重量轻的物品放进背包。最终可以把重量分别为2, 3, 4, 5的三个物品放进背包，得到的价值和为15 + 8 + 6 + 4 = 33，为最大值。6. 请用英文写出三种以上能求解0-1背包问题的设计算法策略。参考解答：Dyn amic P rogrammi ngBacktrackBran ch-a nd-Bo und（每答对一条给一分）7. 请说明动态规划方法为什么需要最优子结构性质。参考解答：最优子结构性质是指大问题的最优解包含子问题的最优解。动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解， 然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构8. 请说明：（
12、1）优先队列可用什么数据结构实现？（2）优先队列插入算法基本思想？（3）优先队列插入算法时间复杂度？参考解答：（1）堆。（1分）（2）在小根堆中，将元素x插入到堆的末尾，然后将元素x的关键字与其双亲的关键字比较，若元素x的关键字小于其双亲的关键字，则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比， 直到元素x的关键字大于双亲的关键字，或元素 x到根为止。（4分）（3）0（ log n）（ 1 分）9.设计动态规划算法的主要步骤是怎么的？请简述。参考解答：（1）找出最优解的性质，并刻划其结构特征。（6分）（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值
13、时得到的信息，构造最优解。10. 分治法所能解决的问题一般具有哪几个特征？请简述。参考解答：（1）该问题的规模缩小到一定的程度就可以容易地解决；（6分）（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）禾用该问题分解出的子问题的解可以合并为该问题的解；即子问题之间不包（4）原问题所分解出的各个子问题是相互独立的， 含公共的子问题。，然后再从当前的 为了有效地选择下一扩展结点，加速搜索的进 ，并根据函数值，从当前活结11. 分支限界法的搜索策略是什么？参考解答：在扩展结点处，先生成其所有的儿子结点（分支）活结点表中选择下一个扩展结点。程，在每一个活结点处，计算一个
14、函数值（限界）使搜索朝着解空间上有最优解的分（6分）点表中选择一个最有利的结点作为扩展结点，支推进，以便尽快地找出一个最优解。12算法的要特性是什么？参考解答：确定性、可实现性、输入、输出、有穷性13算法分析的目的是什么？参考解答：分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额 更好的算法。14算法的时间复杂性与问题的什么因素相关？参考解答：算法的时间复杂性与问题的规模相关，是问题大小n的函数。15算法的渐进时间复杂性的含义？参考解答：当问题的规模n趋向无穷大时，影响算法效率的重要因素是 T（n）的 数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用 T（n）的数量级( 阶
15、) 评价算法。时间复杂度 T(n) 的数量级 (阶) 称为渐进时间复杂性。16 最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 参考解答：最坏情况下的时间复杂性和平均时间复杂性考察的是 n 固定时，不同 输入实例下的算法所耗时间。 最坏情况下的时间复杂性取的输入实例中最大的时 间复杂度：W(n) = max T(n , I) , I Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n)=刀 P(I)T(n , I) I Dn17 简述二分检索(折半查找)算法的基本过程。参考解答：设输入是一个按非降次序排列的元素表Ai : j和x，选取A(i+j)/2与 x 比较，如果
16、A(i+j)/2=x，则返回(i+j)/2 ，如果 A(i+j)/2x ，则 Ai :(i+j)/2-1 找x，否则在A (i+j)/2+1: j找x。上述过程被反复递归调用。18 背包问题的目标函数和贪心算法最优化量度相同吗？参考解答: 不相同。目标函数:获得最大利润。最优量度:最大利润 /重量比。19 采用回溯法求解的问题，其解如何表示？有什么规定？参考解答：问题的解可以表示为n元组：(xi,x 2, , Xn),Xi S, S为有穷集合， Xi S, ( xi,x 2, , Xn)具备完备性，即(xi,x 2, , Xn)是合理的，贝(Xl,X2, Xi) (in) 一定合理。20 回溯
17、法的搜索特点是什么？参考解答： 在解空间树上跳跃式地深度优先搜索，即用判定函数考察 xk 的取 值，如果 xk 是合理的就搜索 xk 为根节点的子树， 如果 xk 取完了所有的值， 便回溯到 xk-1 。21 n 皇后问题回溯算法的判别函数 place 的基本流程是什么？参考解答：将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如 果不相容就返回 false ，测试完毕则返回 true 。22 为什么用分治法设计的算法一般有递归调用？参考解答： 子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用 到递归 .23 为什么要分析最坏情况下的算法时间复杂性？参考解答： 最坏情况
18、下的时间复杂性决定算法的优劣， 并且最坏情况下的时间复 杂性较平均时间复杂性游可操作性。f(n) 是一简单函数，存在正整数 T(n)=O(f(n) 。24 简述渐进时间复杂性上界的定义。参考解答： T(n) 是某算法的时间复杂性函数，No和C, nNo,有T(n)vf(n)，这种关系记作25 二分检索算法最多的比较次数？log n参考解答： 二分检索算法的最多的比较次数为26 快速排序算法最坏情况下需要多少次比较运算？参考解答：最坏情况下快速排序退化成冒泡排序，需要比较n2次。27 贪心算法的基本思想？参考解答： 是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一
19、种量度标准；然后按这种量度标准对这n个输入排序，依 次选择输入量加入部分解中。 如果当前这个输入量的加入， 不满足约束条件， 则 不把此输入加到这部分解中28回溯法的解(X1,X2,Xn)的隐约束一般指什么？参考解答：回溯法的解(X1,X2, , Xn )的隐约束一般指个元素之间应满足的某种关系。29 阐述归并排序的分治思路。参考解答： 讲数组一分为二， 分别对每个集合单独排序， 然后将已排序的两个序 列归并成一个含 n 个元素的分好类的序列。 如果分割后子问题还很大， 则继续分 治，直到一个元素。30 快速排序的基本思想是什么。参考解答：快速排序的基本思想是在待排序的 N个记录中任意取一个记
20、录，把该 记录放在最终位置后， 数据序列被此记录分成两部分。 所有关键字比该记录关键 字小的放在前一部分， 所有比它大的放置在后一部分， 并把该记录排在这两部分 的中间，这个过程称作一次快速排序。 之后重复上述过程， 直到每一部分内只有 一个记录为止。31 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？参考解答： 在定义一个过程或者函数的时候又出现了调用本过程或者函数的成 分，既调用它自己本身， 这称为直接递归。 如果过程或者函数 P 调用过程或者函 数Q, Q又调用P,这个称为间接递归。消除递归一般要用到栈这种数据结构。32 什么是哈密顿环问题？参考解答：哈密顿环是指一条沿着图G
21、的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置。33 用回溯法求解哈密顿环，如何定义判定函数？参考解答：当前选择的节点Xk是从未到过的节点,即Xk工Xi(i=1,2, ,k-1)，且 C(Xk-1, Xk)工，如果 k=-1，贝U C(Xk, X1)MX。34 请写出 prim 算法的基本思想。参考解答： 思路是：最初生成树 T 为空，依次向内加入与树有最小邻接边的 n-1 条边。处理过程：首先加入最小代价的一条边到T,根据各节点到T的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变的邻接边排序，再选择 下一条边加入，直至加入 n-1 条边。三、算法设计题1. 【最长上
22、升子序列问题】(8 分)提示：此题可采用动态规划算法实现对于给定的一个序列(a,a2,，a , 1N1000。我们可以得到一些递增 上升的子序列 佝1,42,Qk),这里1 i1 ci2 “ a j;1 j 1I 1 i1; Vj ( j i ),都有 ai = a j即，f(i)是从f(1), f(2),至yf(i-1)中找最大的一个值，再加1。或者1。就是1。主要是看ai这个元素能否加入到之前已经获得的最长上升子序列， 如 果能加入，是之前已获得的最长上升子序列长度加一； 如果不能加入，就取这最 后一个元素作为一个单独子序列，长度为最后，所要求的整个序列的最长公共子序列长度为maxf(i)
23、: 1=i=当前最优解代价（2）若当前代价f（3）见（1）中所画的图。5分（4）最优解为3，1, 2，最优值为25。3分问题描述:“格雷码”是一个长度为2n的序列，满足:4. 【Gray码构造问题】（8分）一一提示：此题可采用分治递归算法实现(a)(b)(c)每个元素都是长度为n比特的串 序列中无相同元素连续的两个元素恰好只有1个比特不同例如：n=2时，格雷码为00, 01，11，10。Gray码是一种编码，这种编码可以避免在读取时，因各数据位时序上的差 异造成的误读。格雷码在工程上有广泛应用。 但格雷码不便于运算，请你设计 种构造方法，输入长度序列n,输出格雷码（你只要做出一种构造方案即可，
24、格 雷码并不唯一）。参考解答：此题可用分治法解决。当n= 1时，输出格雷码0, 1当n1时，格雷码的长度为2n，即共有2n个码序列。此时，将问题一分为二，即上半部分和下半部分。上半部分最高位设为0,下半部分最高位设为1。剩下n-1位的格雷码的构造采用递归的思路。评分准则：1）答到使用分治算法，并且推导出分治算法的过程，边界设定清晰（即当 仅输出1位的格雷码如何处理），本题即可得满分；2）说明使用分治算法，但漏边界条件，扣 2分以上；其它情况酌情考虑。实数。另外，还给定V中的一个点的最短路长度。这里路的长50算从源顶点1到其它顶点间最短5. （ 13分）给定带权有向图34L一旨路上各边10loG
25、 =（V,E），其中每条边的权是非负现在要计算从源到所有其它各顶径。请将此口。现采用 Dijkstra 算法计60 呈填入下表中。迭代Sudist2dist3dist4dist5初始1123420参考解答：（13分）迭代Sudist2dist3dist4dist5初始1-103010011 , 2210603010021 , 2, 441050309031 , 2, 4, 331050306041 , 2, 3, 4, 55105030606. （ 13分）有0-1背包问题如下：n=6, c=20, P= （4, 8，15，1，6，3），W=（5，3，2，10，4，8）。其中n为物品个数，c为
26、背包载重量，P表示物品的价值，W表示物品的 重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到 放进背包的物品总价值最大。P=（15，8, 6, 4, 3，1） W=（2，3, 4, 5, 8，10），单位重量物品价值（7.5 , 2.67, 1.5,0.8,0.375,0.1）参考解答：（13分）可知随着物品的重量增加，物品的价值减少；因此可以用贪心算法来求解。以选 取单位重量物品价值高为贪心策略。1. 先把重量为2的物品放进背包，此时剩余载重量为 17, P为15。2. 把重量为3的物品放进背包，此时剩余载重量为 14, P为23；3. 把重量为4的物品放进背包，此时剩余载重
27、量为 10, P为29；4.把重量为5的物品放进背包，此时剩余载重量为5, P为33.由于85,所以不能再放进背包。结果是把重量为2, 3, 4, 5的物品装进背包，总价值最大为 33.7、将所给定序列a1:n分为长度相等的两段a1:n/2和an/2+1:n，分别求出这两段的最大子段和，则a1:n的最大子段和有哪三种情形？(10分)参考解答：(1) a1:n的最大子段和与a1:n/2的最大子段和相同。(2)a1:n的最大子段和与的最大子段an/2+1:n和相同。a1:n的最大子段和为刀 ak(i=vkv=J)且 1=i=n/2,n/2+1=J10归并排序算法对下列实例排序，写出算法执行过程。A=(48,12,61,3,5,19,32,7)48,12,61,35,19,32,748,1261,35,1932,712,48 3,615,197,3248, 615, 7, 193,5, 7,12,19, 32,48,613, 12,参考解答：,32
