算法设计与分析期末复习题

1计算机算法设计与分析复习题一、填空题1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有时间复杂性和空间复杂性之分。2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（1），在最坏情况下，搜索的时间复杂性为O（logn）。4、已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程：22221nnOnTnOnT)()/()()(解得此递归方可得T(n)=O（lognn）。5、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。6．递归的二分查找算法在divide阶段所花的时间是O(1)，conquer阶段所花的时间是T(n/2)，算法的时间复杂度是O(logn)。7．Prim算法利用贪心策略求解最小生成树问题，其时间复杂度是O(n2)。8．背包问题可用贪心法，回溯法等策略求解。9．用动态规划算法计算矩阵连乘问题的最优值所花的时间是O(n3)，子问题空间大小是O(n2)。10．图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是mn，解空间树中每个内结点的孩子数是m。11．单源最短路径问题可用贪心法、分支限界等策略求解。12、一个算法的优劣可以用（时间复杂度）与（空间复杂度）与来衡量。13、回溯法在问题的解空间中，按（深度优先方式）从根结点出发搜索解空间树。14、直接或间接地调用自身的算法称为（递归算法）。15、记号在算法复杂性的表示法中表示（渐进确界或紧致界）。16、在分治法中，使子问题规模大致相等的做法是出自一种（平衡(banlancing)子问题）的思想。17、动态规划算法适用于解（具有某种最优性质）问题。18、贪心算法做出的选择只是（在某种意义上的局部）最优选择。219、最优子结构性质的含义是（问题的最优解包含其子问题的最优解）。20、回溯法按（深度优先）策略从根结点出发搜索解空间树。21、拉斯维加斯算法找到的解一定是（正确解）。22、按照符号O的定义O(f)+O(g)等于O(max{f(n),g(n)})。23、二分搜索技术是运用（分治）策略的典型例子。24、动态规划算法中，通常不同子问题的个数随问题规模呈（多项式）级增长。25、（最优子结构性质）和（子问题重叠性质）是采用动态规划算法的两个基本要素。26、（最优子结构性质）和（贪心选择性质）是贪心算法的基本要素。27、（选择能产生最优解的贪心准则）是设计贪心算法的核心问题。28、分支限界法常以（广度优先）或（以最小耗费(最大效益)优先）的方式搜索问题的解空间树。29、贪心选择性质是指所求问题的整体最优解可以通过一系列（局部最优）的选择，即贪心选择达到。30、按照活结点表的组织方式的不同，分支限界法包括（队列式(FIFO)分支限界法）和（优先队列式分支限界法）两种形式。31、如果对于同一实例，蒙特卡洛算法不会给出两个不同的正确解答，则称该蒙特卡洛算法是（一致的）。32、哈夫曼编码可利用（贪心法）算法实现。33概率算法有数值概率算法，蒙特卡罗（MonteCarlo）算法，拉斯维加斯（LasVegas）算法和舍伍德（Sherwood）算法34以自顶向下的方式求解最优解的有（贪心算法）35、下列算法中通常以自顶向下的方式求解最优解的是（贪心法）。36、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是（回溯法）37、旅行售货员问题不能用（）解决可以用回溯法解决，分支限界法，NP完全性理论与近似算法38、贪心算法不能解决（0-1背包问题N皇后问题）。可以解决背包问题39、投点法是（概率算法）的一种。40、若线性规划问题存在最优解，它一定不在（可行域内部）二、简答题1、（8分）写出下列复杂性函数的偏序关系（即按照渐进阶从低到高排序）：2323log!log10nnnnnnnnn3参考解答：3210loglog23!nnnnnnnnn2、（8分）现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他选手各赛一次；（2）每个选手一天只能赛一次；（3）循环赛一共进行n–1天。请利用分治法的思想，给这8位运动员设计一个合理的比赛日程。参考解答：12345678214365873412785643218765567812346587214378563412876543213、（8分）某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，s(i)表示开始租用时刻，f(i)表示结束租用时刻，10个客户的申请如下表所示：i12345678910s(i)03153511886f(i)65498713121110同一时刻，该羽毛球场只能租借给一位客户，请设计一个租用安排方案，在这10位客户里面，使得体育馆能尽可能满足多位客户的需求，并算出针对上表的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个客户申请。这已经是可以满足的最大客户人数。44、（8分）对于矩阵连乘所需最少数乘次数问题，其递归关系式为：1ikj0[,]min{[,][1,]}ikjijmijmikmkjpppij其中m[i，j]为计算矩阵连乘Ai…Aj所需的最少数乘次数，pi-1为矩阵Ai的行，ip为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为：A1A2A3A4501010404030305p0p1p1p2p2p3p3p4请根据以上的递归关系，计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。参考解答：014024034[1][1][2][4]080005010510500[1][4]min[1][2][3][4]2000060005040536000[1][3][4][4]270000503053450010500mmpppmmmpppmmppp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背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？参考解答：因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15+8+6+4=33，为最大值。6.请用英文写出三种以上能求解0-1背包问题的设计算法策略。参考解答：DynamicProgrammingBacktrackBranch-and-Bound（每答对一条给一分）7.请说明动态规划方法为什么需要最优子结构性质。参考解答：最优子结构性质是指大问题的最优解包含子问题的最优解。动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构8.请说明：(1)优先队列可用什么数据结构实现？(2)优先队列插入算法基本思5想？(3)优先队列插入算法时间复杂度？参考解答：（1）堆。(1分)（2）在小根堆中，将元素x插入到堆的末尾，然后将元素x的关键字与其双亲的关键字比较，若元素x的关键字小于其双亲的关键字，则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键字大于双亲的关键字，或元素x到根为止。(4分)（3）O(logn)（1分）9..设计动态规划算法的主要步骤是怎么的？请简述。参考解答：（1）找出最优解的性质，并刻划其结构特征。(6分)（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。10.分治法所能解决的问题一般具有哪几个特征？请简述。参考解答：（1）该问题的规模缩小到一定的程度就可以容易地解决；(6分)（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。11.分支限界法的搜索策略是什么？参考解答：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。(6分)12算法的要特性是什么？参考解答：确定性、可实现性、输入、输出、有穷性13算法分析的目的是什么？参考解答：分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。14算法的时间复杂性与问题的什么因素相关？参考解答：算法的时间复杂性与问题的规模相关，是问题大小n的函数。15算法的渐进时间复杂性的含义？参考解答：当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级6(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。16最坏情况下的时间复杂性和平均时间复杂性有什么不同？参考解答：最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n)=max{T(n，I)},I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n)=∑P(I)T(n，I)I∈Dn17简述二分检索（折半查找）算法的基本过程。参考解答：设输入是一个按非降次序排列的元素表A[i：j]和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]x，则A[i：(i+j)/2-1]找x，否则在A[(i+j)/2+1：j]找x。上述过程被反复递归调用。18背包问题的目标函数和贪心算法最优化量度相同吗？参考解答：不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。19采用回溯法求解的问题，其解如何表示？有什么规定？参考解答：问题的解可以表示为n元组：（x1,x2,……xn），xi∈Si,Si为有穷集合，xi∈Si,（x1,x2,……xn）具备完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）(in)一定合理。20回溯法的搜索特点是什么？参考解答：在解空间树上跳跃式地深度优先搜索，即用判定函数考察x[k]的取值，如果x[k]是合理的就搜索x[k]为根节点的子树，如果x[k]取完了所有的值，便回溯到x[k-1]。21n皇后问题回溯算法的判别函数place的基本流程是什么？参考解答：将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。22为什么用分治法设计的算法一般有递归调用？参考解答：子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归