2016计算机算法设计与分析期终考试复习题.doc

V 计算机算法设计与分析复习题 一、题1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有 复杂性和复杂性之分。出自于平衡子问题的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致 。3、使用二分有哪些信誉好的足球投注网站算法在n个有序元素表中有哪些信誉好的足球投注网站一个特定元素，在最佳情况下，有哪些信誉好的足球投注网站的时间复杂性为O（），在最坏情况下，有哪些信誉好的足球投注网站的时间复杂性为O（ ）。 解得此递归方可得T(n)= O（ ）。、动态规划算法有一个变形方法 。这种方法不同于动态规划算法自底向上的填充方向，而是自顶向下的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。12、时间复杂度空间复杂度 13、深度优先方式、递归算法( 记号在算法复杂性的表示法中表示（渐进确界或紧致界）。 16、在分治法中，使子问题规模大致相等的做法是出自一种（平衡(banlancing)子问题、具有某种最优性质 18、最优子结构性质的含义是。 、深度优先。 、拉斯维加斯算法找到的解一定是正确解。O(max{f(n),g(n)})。 23、二分有哪些信誉好的足球投注网站技术是运用（分治最优子结构性质子问题重叠性质最优子结构性质贪心选择性质选择能产生最优解的贪心准则广度优先以最小耗费(最大效益)优先队列式(FIFO)分支限界法优先队列式分支限界法、利用（贪心法）算法实现。 数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法以自顶向下的方式求解最优解的在对问题的解空间树进行有哪些信誉好的足球投注网站的方法中,一个活结点有多次机会成为活结点的是0-1背包问题（）、简答题 参考解答：– 1天。 请利用分治法的思想，给这8位运动员设计一个合理的比赛日程。 参考解答： 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 3、（8分）某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，s(i)表示开始租用时刻，f(i)表示结束租用时刻，10个客户的申请如下表所示： i 1 2 3 4 5 6 7 8 9 10 s(i) 0 3 1 5 3 5 11 8 8 6 f(i) 6 5 4 9 8 7 13 12 11 10 同一时刻，该羽毛球场只能租借给一位客户，请设计一个租用安排方案，在这10位客户里面，使得体育馆能尽可能满足多位客户的需求，并算出针对上表的10个客户申请，最多可以安排几位客户申请。 参考解答：将这10位客户的申请按照结束时间f(i)递增排序，如下表： i 1 2 3 4 5 6 7 8 9 10 s(i) 1 3 0 5 3 5 6 8 8 11 f(i) 4 5 6 7 8 9 10 11 12 13 ⑴选择申请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分）对于矩阵连乘所需最少数乘次数问题，其递归关系式为： 其中m[i，j]为计算矩阵连乘Ai…Aj所需的最少数乘次数，pi-1为矩阵Ai的行，为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为： A1 A2 A3 A4 50(10 10(40 40(30 30(5 p 0( p 1 p 1( p 2 p 2( p 3 p 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背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？ 参考解答：因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15 + 8 + 6 + 4 = 33，为最大值。 6.请用英文写出三种以上能求解0-1背包问题的