算法复习题精炼版汇编

1、学习-好资料填空题动态规划算法的基本要素为：最优子结构性质与重叠子问题性质1）算法分析中，记号 0表示渐进上界，记号 门表示渐进下界，记号0表示紧渐进界。2）回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。3）分支限界法在问题的解空间树中，按广度优先策略，从根结点出发搜索解空间树。所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到）。所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。回溯法是指（具有限界函数的深度优先生成法）。回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架。4）二分搜索算法是利

2、用分治策略实现的算法。5）衡量一个算法好坏的标准是时间复杂度低6）最长公共子序列算法利用的算法是动态规划法7）Strassen矩阵乘法是利用分治策略实现的算法8）回溯法搜索状态空间树是按照深度优先遍历的顺序。9）算法中通常以自底向下的方式求解最优解的是动态规划法10）背包问题的贪心算法所需的计算时间为0（nlogn ）11）0-1背包问题的回溯算法所需的计算时间为O（n2n）12）用动态规划算法解决最大字段和问题，其时间复杂性为n13）一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性：_有穷性，确定性， 可行性，输入，输出。1

3、. 算法的复杂性有 时间复杂性和 复杂性之分。2、 程序是 算法用某种程序设计语言的具体实现。3、 算法的“确定性”指的是组成算法的每条指令 是清晰的，无歧义的。4. 矩阵连乘问题的算法可由动态规划设计实现。6、 算法是指解决问题的一种方法 或一个过程。7、 从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法 。8、 问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。9、 以深度优先方式系统搜索问题解的算法称为回溯法 。10、 数值概率算法常用于数值问题的求解。15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包

4、问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0/1 背包问题，只使用约束条件进行裁剪的是N 皇后问题学习-好资料16、 贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。17、 矩阵连乘问题的算法可由动态规划设计实现。19.贪心算法的基本要素是贪心选择质和最优子结构性质。21.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解 二问题，然后从这些 子问题 的解得到原问题的解。23、大整数乘积算法是用分治法 来设计的。26、 贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。27.快速排序算法是

5、基于分治策略的一种排序算法。30.回溯法是一种既带有系统性 又带有跳跃性的搜索算法。33回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和 限界函数。34.任何可用计算机求解的问题所需的时间都与其规模 有关。35快速排序算法的性能取决于划分的对称性。37.图的m着色问题可用 回溯法求解，其解空间树中叶子结点个数是 m"_，解空间树中每个内结点的孩子数是m 。简答题1用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析 &算法实现7、程序调试8、结果整理文档编制2. 最优二叉搜索树问题的动态规划算法void bin arysearch

6、tree(i nt a,i nt b,i nt n ,i nt *m,i nt *s,i nt *w)int i,j,k,t,l;for(i=1;i<=n+1;i+)wii-1=ai-1;mii-1=0;for(l=0;l<=n-1;l+)-1是下标 j-i 的差for(i=1;i<=n-l;i+)更多精品文档学习 好资料j=i+l; wij=wij-1+aj+bj; mij=mii-1+mi+1j+wij; sij=i;for(k=i+1;k<=j;k+) t=mik-1+mk+1j+wij; if(t<mij) mij=t; sij=k;编写计算斐波那契(Fi

7、bonacci)数列的第n项函数fib (n)斐波那契数列为：0、1、1、2、3、，即：fib(0)=0;fib(1)=1;fib(n)=fib(n-1)+fib(n-2) (当 n>1 时)。 写成递归函数有：int fib(int n) if (n=0) return 0;if (n=1) return 1;if (n>1) return fib(n-1)+fib(n-2);2. 算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程3. 算法的三要素1、操作 2、控制结构 3、数据结构4. 算法具有以下 5 个属性 ： 有穷性：一个算法必须总是在执行有

8、穷步之后结束， 且每一步都在有穷时间 内完成。确定性： 算法中每一条指令必须有确切的含义。 不存在二义性。 只有一个入 口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本 运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出， 这些输出同输入有着某些特定关系的量。经常采用的算法主要有迭代法、分治法、贪婪法、动态规划法、回溯法、分支 限界法8. 分治法的基本思想是：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立 且与原问题相同。 递归地解这些子问题， 然后将各个子问题的解合并得到

9、原问题 的解。9. 分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有 最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不 包含公共的子子问题。10、分治法的基本步骤 分治法在每一层递归上都有三个步骤：（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题 形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地 解各个子问题；（3）合并：将各个子问题的解合并为原问题的解。11. 动

10、态规划的基本思想动态规划的实质是 分治思想 和解决冗余 ，因此，动态规划 是一种将问题实例 分解为更小的、 相似的子问题， 并存储子问题的解而避免计算重复的子问题， 以 解决最优化问题的算法策略。13. 分治法与动态规划法的相同点是： 将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的 解得到原问题的解。两者的不同点是 ：适合于用动态规划法求解的问题，经分解得到的子问题往 往不是互相独立的。 而用分治法求解的问题， 经分解得到的子问题往往是互相独 立的。14. 回溯法 回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将 问题的候选解按某种顺序逐一枚举和检验。 当

11、发现当前候选解不可能是解时， 就 选择下一个候选解； 倘若当前候选解除了还不满足问题规模要求外， 满足所有其 他要求时，继续扩大当前候选解的规模， 并继续试探。 如果当前候选解满足包括 问题规模在内的所有要求时， 该候选解就是问题的一个解。 在回溯法中， 放弃当 前候选解， 寻找下一个候选解的过程称为回溯。 扩大当前候选解的规模， 以继续 试探的过程称为向前试探。20. 回溯法中常见的两类典型的解空间树是子集树和排列树。当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应 的解空间树称为子集树。这类子集树通常有 2n 个叶结点，遍历子集树需 O（2n） 计算时间 。当所给的问题是确

12、定 n 个元素满足某种性质的排列时， 相应的解空间树称 为排列树。这类排列树通常有n!个叶结点。遍历排列树需要 0（ n!）计算时间。更多精品文档学习-好资料22 .请叙述动态规划算法与贪心算法的异同。共同点：都需要最优子结构性质，都用来求有优化问题。不同点：动态规划：每一步作一个选择一依赖于子问题的解。贪心方法：每一步作一个选择一不依赖于子问题的解。动态规划方法的条件：子问题的重叠性质。可用贪心方法的条件：最优子结构性质；贪心选择性质。动态规划：自底向上求解；贪心方法：自顶向下求解。可用贪心法时，动态规划方法可能不适用；可用动态规划方法时，贪心法可能不适用。23.请说明动态规划方法为什么需要

13、最优子结构性质。答：最优子结构性质是指大问题的最优解包含子问题的最优解。动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构.26.在算法复杂性分析中，0、Q、E这三个记号的意义是什么？在忽略常数 因子的情况下，0、Q、分别提供了算法运行时间的什么界？答：如果存在两个正常数c和NO,对于所有的NNO,有f(N)|wC|g(N)|,则记作：f(N)=O(g(N)。这时我们说f(N)的阶不高于g(N)的阶。若存在两个正常数C和自然数NO，使得当N > NO时有|f(N)|>C|g(N)|，记为 f(N)=?

14、(g(N)。这时我们说f(N)的阶不低于g(N)的阶。如果存在正常数c1,c2和nO,对于所有的nnO,有c1|g(N)| < |f(N)| < c2|g(N)| 则记作 f(N)=(g,(N)0、Q、分别提供了算法运行时间的上界、下界、平均1 用动态规划策略求解最长公共子序列问题:(1) 给出计算最优值的递归方程。(2) 给定两个序列X=B,C,D,A，Y=A,B,C,B，请采用动态规划策略求出 其最长公共子序列，要求给出过程。答：9当：=0或 j 0时ci, j = ci -1,j -11当i, j0且xyi时max(ci, j -1, ci -1,j)当 i, j >

15、0且x、丰 时YABC BX00 0B0011 1*、C0012“D0012t2A011 :2 2最长公共子序列：BC2.对下列各组函数 f (n)和 g (n),确定 f (n) = O (g (n)或 f (n) = Q (g (n)或 f(n)=0 (g(n)，并简要说明理由。(1) f(n )=2n ；g( n)=n! f(n)=、n ；g (n )=log n2(3) f(n)=100;g(n )=log1003(4) f(n)=n ;g(n)= 3n f(n)=3 n ；g(n )=2n答：(1) f(n) = O(g(n)因为g(n)的阶比f(n)的阶高 f(n) = Q (g(

16、n)因为g(n)的阶比f(n)的阶低 f(n) = 0 (g(n)因为g(n)与f(n)同阶。(4) f(n) = 0(g(n)因为g(n)的阶比f(n)的阶高。(5) f(n) = Q (g(n)因为g(n)的阶比f(n)的阶低。3对下图所示的连通网络 G,用克鲁斯卡尔(Kruskal)算法求G的最小生成树T,请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的贪心 策略和算法的基本思想，并简要分析算法的时间复杂度。答：TE=(3,4), (2,3),(1,5),(4,6)( 4,5)贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。基本思想：首先将图中所有顶点都放到生

17、成树中，然后每次都在连接两个不 同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边。时间复杂度为：O(eloge)4请用分治策略设计递归的归并排序算法，并分析其时间复杂性(要求：分别 给出divide、conquer、combine这三个阶段所花的时间，并在此基础上列出递归 方程，最后用套用公式法求出其解的渐进阶)。答 : Template <class Type>void MergeSort (Type a , i nt left, int right) if (left<right) int i= ( left+right)/2;MergeSort

18、( a, left, i);MergeSort( a, i+1, right);Merge(a, b, left, right);Copy(a, b, left, right);Divide阶段的时间复杂性：0(1)Con quer阶段的时间复杂性：2T( n)Comb ine阶段的时间复杂性： (n)T(n)；0 (1)2T(n/2) +9 (n)当n1更多精品文档因为f(n)与nlog ba同阶,用套用公式法：a=2, b=2,g ba = n , f(n)=n. T(n) = (nlogn)7. 考虑在序列A1.n中找最大最小元素的问题。一个分治算法描述如下：如果 n < 2就直接

19、求解。否则，将序列等分成两个子序列 A1.n/2和An/2+仁n，分别 找出这两子序列的最大最小元素x1,y1和x2,y2;然后据此求出A1.n的最大元素 x=maxx1,x2及最小元素y=miny1,y2。请给出该算法计算时间T(n)满足的递归 方程，并解方程来确定算法的时间复杂度。假定 n=2k(k为正整数)。答：算法时间复杂度满足如下递归方程：T(n)=2T(n/2)+2 (n>2)； T=1。因为n=2 k( k为正整数)，所以，T( n)= T(2 k)= 2T(2 k-1)+2= 22T(2 k-2)+ 22+2?k-1k_23 2=2T(2)+ 2 +?+23+22+2k-132=2 +?+2 +2 +2。因此，T(n)=0(n)。8. 考虑使用动态规划方法求解下列问题：01背包数据如下表，求：能够放入背包的最有价值的物