2015算法设计与分析考试复习刚要及习题(共12页).doc

《2015算法设计与分析考试复习刚要及习题(共12页).doc》由会员分享，可在线阅读，更多相关《2015算法设计与分析考试复习刚要及习题(共12页).doc（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上计算机算法设计与分析复习题一、填空题1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有 时间 复杂性和空间复杂性之分。2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致 相同 。3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（1），在最坏情况下，搜索的时间复杂性为O（ logn ）。4、已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程：解得此递归方可得T(n)= O（ ）。5、动态规划算法有一个变形方法 备忘录方法 。这种方

2、法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。6递归的二分查找算法在divide阶段所花的时间是 O(1) ，conquer阶段所花的时间是 T(n/2) ，算法的时间复杂度是 O( log n) 。 7Prim算法利用贪心 策略求解 最小生成树问题，其时间复杂度是 O(n2) 。8背包问题可用 贪心法 ， 回溯法 等策略求解。9用动态规划算法计算矩阵连乘问题的最优值所花的时间是 O(n3) ， 子问题空间大小是 O(n2) 。10图的m着色问题可用 回溯 法求解，其解空间树中叶子结点个数

3、是 mn ，解空间树中每个内结点的孩子数是 m 。11单源最短路径问题可用贪心法 、 分支限界 等策略求解。12、一个算法的优劣可以用（时间复杂度）与（空间复杂度）与来衡量。13、回溯法在问题的解空间中，按（深度优先方式）从根结点出发搜索解空间树。14、直接或间接地调用自身的算法称为（递归算法）。15、q 记号在算法复杂性的表示法中表示（渐进确界或紧致界）。16、在分治法中，使子问题规模大致相等的做法是出自一种（平衡(banlancing)子问题）的思想。17、动态规划算法适用于解（具有某种最优性质）问题。18、贪心算法做出的选择只是（在某种意义上的局部）最优选择。19、最优子结构性质的含义是

4、（问题的最优解包含其子问题的最优解）。20、回溯法按（深度优先）策略从根结点出发搜索解空间树。21、拉斯维加斯算法找到的解一定是（正确解）。22、按照符号O的定义O(f)+O(g)等于O(maxf(n),g(n)。23、二分搜索技术是运用（分治）策略的典型例子。24、动态规划算法中，通常不同子问题的个数随问题规模呈（多项式）级增长。25、（最优子结构性质）和（子问题重叠性质）是采用动态规划算法的两个基本要素。26、（最优子结构性质）和（贪心选择性质）是贪心算法的基本要素。27、（选择能产生最优解的贪心准则）是设计贪心算法的核心问题。28、分支限界法常以（广度优先） 或（以最小耗费(最大效益)优

5、先）的方式搜索问题的解空间树。29、贪心选择性质是指所求问题的整体最优解可以通过一系列（局部最优）的选择，即贪心选择达到。30、按照活结点表的组织方式的不同，分支限界法包括（队列式(FIFO)分支限界法）和（优先队列式分支限界法）两种形式。31、如果对于同一实例，蒙特卡洛算法不会给出两个不同的正确解答，则称该蒙特卡洛算法是（一致的）。32、哈夫曼编码可利用（贪心法）算法实现。33概率算法有数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法34以自顶向下的方式求解最优解的有（贪心算法）35、下列算法中通常以自顶向下的方式求解

6、最优解的是（贪心法）。 36、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是（回溯法）37、旅行售货员问题不能用（）解决 可以用回溯法解决，分支限界法，NP完全性理论与近似算法38、贪心算法不能解决（0-1背包问题 N皇后问题）。可以解决背包问题39、投点法是（概率算法）的一种。40、若线性规划问题存在最优解，它一定不在（可行域内部）二、简答题1、（8分）写出下列复杂性函数的偏序关系（即按照渐进阶从低到高排序）：参考解答：2、（8分）现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程表：（1） 每个选手必须与其他选手各赛一次；（2） 每个选手一天只能赛一

7、次；（3） 循环赛一共进行n 1天。请利用分治法的思想，给这8位运动员设计一个合理的比赛日程。参考解答：12345678214365873412785643218765567812346587214378563412876543213、（8分）某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，s(i)表示开始租用时刻，f(i)表示结束租用时刻，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个客户申请。这已经是可以满足的最大客户人数。4、（8分）对于矩阵连乘所需最少数乘

9、次数问题，其递归关系式为：其中mi，j为计算矩阵连乘AiAj所需的最少数乘次数，pi-1为矩阵Ai的行，为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为：A1A2A3A4501010404030305p 0 p 1p 1 p 2p 2 p 3p 3 p 4请根据以上的递归关系，计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。参考解答：5、（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背包问题，

10、应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？参考解答：因为该01背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15 + 8 + 6 + 4 = 33，为最大值。6.请用英文写出三种以上能求解0-1背包问题的设计算法策略。参考解答：Dynamic Programming Backtrack Branch-and-Bound （每答对一条给一分）7.请说明动态规划方法为什么需要最优子结构性质。参考解答：最优子结构性质是指大问题的最优解包含子问题的最优解。动态规划

11、方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构8.请说明：(1)优先队列可用什么数据结构实现？(2)优先队列插入算法基本思想？(3)优先队列插入算法时间复杂度？参考解答：（1）堆。(1分) （2）在小根堆中，将元素x插入到堆的末尾，然后将元素x的关键字与其双亲的关键字比较，若元素x的关键字小于其双亲的关键字，则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键字大于双亲的关键字，或元素x到根为止。(4分)（3）O( log n)（1分）9.设计动态规划算法的主要步骤是怎么的？请简述。参考解答

12、：（1）找出最优解的性质，并刻划其结构特征。(6分) （2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。10.分治法所能解决的问题一般具有哪几个特征？请简述。参考解答：（1）该问题的规模缩小到一定的程度就可以容易地解决；(6分) （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;（3） 利用该问题分解出的子问题的解可以合并为该问题的解； （4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。11.分支限界法的搜索策略是什么？参考解答：在扩展结点处，先生成其所有的儿子结点（分支），然后再从

13、当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。(6分)12 算法的要特性是什么？ 参考解答：确定性、可实现性、输入、输出、有穷性13 算法分析的目的是什么？参考解答：分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。14 算法的时间复杂性与问题的什么因素相关？参考解答：算法的时间复杂性与问题的规模相关，是问题大小n的函数。15 算法的渐进时间复杂性的含义？参考解答：当问题

14、的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。16 最坏情况下的时间复杂性和平均时间复杂性有什么不同？参考解答：最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max T(n，I) , IDn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n) =P(I)T(n，I) IDn17 简述二分检索（折半查找）算法的基本过程。参考解答

15、：设输入是一个按非降次序排列的元素表Ai：j 和x，选取A(i+j)/2与x比较，如果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元组：（x1,x2,xn），xiSi, Si为有穷集合，xiSi, （x1,x2,xn）具备完备性，即（x1,x2,xn）是合理的，则（x1,x

16、2,xi）(in)一定合理。20 回溯法的搜索特点是什么？ 参考解答：在解空间树上跳跃式地深度优先搜索，即用判定函数考察xk的取值，如果xk是合理的就搜索xk为根节点的子树，如果xk取完了所有的值，便回溯到xk-1。21 n皇后问题回溯算法的判别函数place的基本流程是什么？参考解答：将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。22 为什么用分治法设计的算法一般有递归调用？参考解答：子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归.23 为什么要分析最坏情况下的算法时间复杂性？ 参考解答：最坏情况下的时间复

17、杂性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。24 简述渐进时间复杂性上界的定义。参考解答：T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，nNo，有T(n)f(n)，这种关系记作T(n)=O(f(n)。25 二分检索算法最多的比较次数？参考解答：二分检索算法的最多的比较次数为 log n 。26 快速排序算法最坏情况下需要多少次比较运算？参考解答：最坏情况下快速排序退化成冒泡排序，需要比较n2次。27 贪心算法的基本思想？参考解答：是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度

18、标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中28 回溯法的解（x1,x2,xn）的隐约束一般指什么？参考解答：回溯法的解（x1,x2,xn）的隐约束一般指个元素之间应满足的某种关系。29 阐述归并排序的分治思路。参考解答：讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。30 快速排序的基本思想是什么。 参考解答：快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有

19、关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。31 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？参考解答：在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。32 什么是哈密顿环问题？参考解答：哈密顿环是指一条沿着图G的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置。33 用回溯法求解哈密顿环，如何定

20、义判定函数？参考解答：当前选择的节点Xk是从未到过的节点,即XkXi(i=1,2,k-1)，且C(Xk-1, Xk)，如果k=-1，则C(Xk, X1) 。34 请写出prim算法的基本思想。参考解答：思路是：最初生成树T为空，依次向内加入与树有最小邻接边的n-1条边。处理过程：首先加入最小代价的一条边到T，根据各节点到T的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入n-1条边。三、算法设计题1.【最长上升子序列问题】（8分） 提示：此题可采用动态规划算法实现对于给定的一个序列，。我们可以得到一些递增上升的子序列，这里。比如，对于序列(1

21、, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。你的任务：就是对于给定的序列，求出最长上升子序列的长度。要求写出你设计的算法思想及递推函数的公式表达。.参考解答：设表示：从左向右扫描过来直到以元素结尾的序列，获得的最长上升子序列的长度，且子序列包含元素（）。即，是从，到中找最大的一个值，再加1。或者就是1。主要是看ai这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。

22、最后，所要求的整个序列的最长公共子序列长度为maxf(i): 1=i= 当前最优解代价bestf，则剪枝。2分（3）见（1）中所画的图。5分（4）最优解为3，1，2，最优值为25。3分4.【Gray码构造问题】（8分） 提示：此题可采用分治递归算法实现问题描述：“格雷码”是一个长度为的序列，满足：（a）每个元素都是长度为n比特的串（b）序列中无相同元素（c）连续的两个元素恰好只有1个比特不同例如：n=2时，格雷码为00，01，11，10。Gray码是一种编码，这种编码可以避免在读取时，因各数据位时序上的差异造成的误读。格雷码在工程上有广泛应用。但格雷码不便于运算，请你设计一种构造方法，输入长度

23、序列n，输出格雷码（你只要做出一种构造方案即可，格雷码并不唯一）。参考解答：此题可用分治法解决。当n1时，输出格雷码0, 1当n1时，格雷码的长度为，即共有个码序列。此时，将问题一分为二，即上半部分和下半部分。上半部分最高位设为0，下半部分最高位设为1。剩下n-1位的格雷码的构造采用递归的思路。评分准则：1) 答到使用分治算法，并且推导出分治算法的过程，边界设定清晰（即当仅输出1位的格雷码如何处理），本题即可得满分；2) 说明使用分治算法，但漏边界条件，扣2分以上；其它情况酌情考虑。5.（13分）给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点

24、，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。43211初始dist5dist4dist3dist2uS迭代参考解答：（13分）6030501051，2，3，4，546030501031，2，4，339030501041，2，4210030601021，211003010-1初始dist5dist4dist3dist2uS迭代6.（13分）有0-1背包问题如下：n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n为物品个数，c为背包

25、载重量，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的物品放进背包，此时剩余载重量为10，P为29；4.把重量为5的物品放

26、进背包，此时剩余载重量为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=k=J)且1=i=n/2,n/2+1=J=n。 8 写出maxmin算法对下列实例中找最大数和最小数的过程。数组 A=(48,12,61,3,5,19,32,

27、7) 参考解答：写出maxmin算法对下列实例中找最大数和最小数的过程。数组 A=() 1、 48,12,61,3, 5,19,32,72、 48,12 61,3 5,19 32,73、 4861, 123 1932，574、 6132 355、 61 39 速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。 A=(65,70,75,80,85,55,50,2)参考解答：第一个分割元素为65(1) (2) (3) (4) (5) (6) (7) (8) i p65 70 75 80 85 55 50 2 2 865 2 75 80 85 55 50 70 3 765 2 50 80 85 55 75 70 4 665 2 50 55 85 80 75 70 4 655 70 75 80 85 65 50 210 归并排序算法对下列实例排序，写出算法执行过程。 A=(48,12,61,3,5,19,32,7)参考解答： 48,12,61,3 5,19,32,748,12 61,3 5,19 32,712,48 3,61 5,19 7,32 3, 12, 48, 61 5, 7, 19，323,5, 7,12，19，32，48,61 专心-专注-专业