发布时间 : 星期二 文章湖南工程学院 计算机算法设计与分析 期末考试复习题更新完毕开始阅读6827a5912cc58bd63186bda6
样也可避免相同子问题的重复求解。
6．递归的二分查找算法在divide阶段所花的时间是 O(1) ，conquer阶段所花的时间是
T(n/2) ，算法的时间复杂度是 O( log n) 。
7．Prim算法利用贪心 策略求解 最小生成树问题，其时间复杂度是 O(n2) 。 8．背包问题可用 贪心法 ， 回溯法 等策略求解。
9．用动态规划算法计算矩阵连乘问题的最优值所花的时间是 O(n3) ， 子问题空间大小是
O(n2) 。
10．图的m着色问题可用 回溯 法求解，其解空间树中叶子结点个数是 mn ，解空间树中每
个内结点的孩子数是 m 。
11．单源最短路径问题可用贪心法 、 分支限界 等策略求解。 12、一个算法的优劣可以用（时间复杂度）与（空间复杂度）与来衡量。 13、回溯法在问题的解空间中，按（深度优先方式）从根结点出发搜索解空间树。 14、直接或间接地调用自身的算法称为（递归算法）。
15、? 记号在算法复杂性的表示法中表示（渐进确界或紧致界）。
16、在分治法中，使子问题规模大致相等的做法是出自一种（平衡(banlancing)子问题）的思想。 17、动态规划算法适用于解（具有某种最优性质）问题。
18、贪心算法做出的选择只是（在某种意义上的局部）最优选择。 19、最优子结构性质的含义是（问题的最优解包含其子问题的最优解）。 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概率算法有数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法
34以自顶向下的方式求解最优解的有（贪心算法）
35、下列算法中通常以自顶向下的方式求解最优解的是（贪心法）。
36、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是（回溯法） 37、旅行售货员问题不能用（）解决 可以用回溯法解决，分支限界法，NP完全性理论与近似算法
38、贪心算法不能解决（0-1背包问题 N皇后问题）。可以解决背包问题 39、投点法是（概率算法）的一种。
40、若线性规划问题存在最优解，它一定不在（可行域内部）
二、简答题
1、（8分）写出下列复杂性函数的偏序关系（即按照渐进阶从低到高排序）：
2n3nlognn!nlognn23nn103 2n3nn!nn
参考解答：10lognnlognn22、（8分）现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程表： （1） 每个选手必须与其他选手各赛一次； （2） 每个选手一天只能赛一次； （3） 循环赛一共进行n – 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 s(i) f(i) 1 0 6 2 3 5 3 1 4 4 5 9 5 3 8 6 5 7 7 11 13 8 8 12 9 8 11 10 6 10 同一时刻，该羽毛球场只能租借给一位客户，请设计一个租用安排方案，在这10位客户里面，使得体育馆能尽可能满足多位客户的需求，并算出针对上表的10个客户申请，最多可以安排几位客户申请。
参考解答：将这10位客户的申请按照结束时间f(i)递增排序，如下表：
i s(i) f(i) 1 1 4 2 3 5 3 0 6 4 5 7 5 3 8 6 5 9 7 6 10 8 8 11 9 8 12 10 11 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分）对于矩阵连乘所需最少数乘次数问题，其递归关系式为：
0i?j?? m[i,j]??min{m[i,k]?m[k?1,j]?pi?1pkpj}i?j??i?k?j其中m[i，j]为计算矩阵连乘Ai?Aj所需的最少数乘次数，pi-1为矩阵Ai的行，pi为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为：
A1 50?10 p 0? p 1 参考解答：
A2 10?40 p 1? p 2 A3 40?30 p 2? p 3 A4 30?5 p 3? p 4 请根据以上的递归关系，计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。
?m[1][1]?m[2][4]?p0p1p4?0?8000?50?10?5?10500?m[1][4]?min?m[1][2]?m[3][4]?p0p2p4?20000?6000?50?40?5?36000?m[1][3]?m[4][4]?ppp?27000?0?50?30?5?34500
034??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背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15 + 8 + 6 + 4 = 33，为最大值。
6.请用英文写出三种以上能求解0-1背包问题的设计算法策略。 参考解答：
Dynamic Programming
Backtrack Branch-and-Bound （每答对一条给一分）
7.请说明动态规划方法为什么需要最优子结构性质。
参考解答：最优子结构性质是指大问题的最优解包含子问题的最优解。
动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构
8.请说明：(1)优先队列可用什么数据结构实现？(2)优先队列插入算法基本思想？(3)优先队列插入
算法时间复杂度？ 参考解答：（1）堆。(1分)
（2）在小根堆中，将元素x插入到堆的末尾，
然后将元素x的关键字与其双亲的关键字比较， 若元素x的关键字小于其双亲的关键字，
则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键字大于双亲的关键字，或元素x到根为止。(4分) （3）O( log n)（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)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。
16 最坏情况下的时间复杂性和平均时间复杂性有什么不同？
参考解答：最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：
W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：
A(n) =∑P(I)T(n，I) I∈Dn 17 简述二分检索（折半查找）算法的基本过程。
参考解答：设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果