算法复习题(精炼版)

填空动态规划算法的基本要素是：最优子结构性质和重叠子问题性质1)在算法分析中，标记0代表渐近上界，标记代表渐近下界，标记代表紧渐近界。2)回溯法根据问题的解空间树中的深度优先策略从根节点搜索解空间树。3)分枝定界法根据问题的解空间树中的广度优先策略从根节点搜索解空间树。所谓贪婪选择性质是指(问题的全局最优解可以通过一系列局部最优选择来实现，即贪婪选择)。所谓最优子结构性质是指(问题的最优解包括其子问题的最优解)。回溯法是回溯法，指的是(带界函数的深度优化法)。回溯法的算法框架一般根据问题的解空间分为(子集树)算法框架和(树的排列)算法框架。4)采用分治策略实现二进制搜索算法。5)衡量算法质量的标准是低时间复杂度6)最长公共子序列算法使用的算法是动态规划法7) Strassen矩阵乘法是通过分治策略实现的算法8)回溯法按照深度优先遍历的顺序搜索状态空间树。9)在算法中，通常采用动态规划方法自下而上求解最优解。10)背包问题的贪婪算法所需的计算时间为0(nlogn)11)0-1背包问题的回溯算法所需的计算时间为0(n2n)12)用动态规划算法求解最大字段和问题，时间复杂度为n13)算法是一组有限规则，其中规则指定了一系列操作来解决特定类型的问题。此外，该算法还应具有以下五个重要特征：_有限、确定、可行、输入和输出。1.算法的复杂度分为时间复杂度和空间复杂度。2.程序是编程语言中算法的具体实现。3.算法的“确定性”意味着构成算法的每一条指令都是清晰明确的。4.矩阵乘法问题的算法可以通过动态规划设计来实现。6.算法是指解决问题的方法或过程。7.从分治法的一般设计模式可以看出，用它设计的程序一般都是递归算法。8.问题的最优子结构性质是问题可以用动态规划算法或贪婪算法求解的关键特征。9.以深度优先的方式系统地搜索问题的解的算法称为回溯法。10.数值概率算法通常用于解决数值问题。15.用回溯法切割状态空间树的分支时，一般有两个标准：约束条件的界和目标函数。N皇后问题和0/1背包问题是两种不同的类型。其中，0/1背包问题是通过同时利用约束条件和目标函数的界来切割的，而N皇后问题是仅利用约束条件来切割的。16.贪婪选择是贪婪算法的第一基本要素，也是贪婪算法与动态规划算法的主要区别。17.矩阵乘法问题的算法可以通过动态规划设计来实现。19.贪婪算法的基本要素是贪婪选择质量和最优子结构性质。21.动态规划算法的基本思想是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解中得到原问题的解。23.大整数积算法采用分治法设计。26.贪婪选择是贪婪算法的第一基本要素，也是贪婪算法与动态规划算法的主要区别。27.快速排序是一种基于分治策略的排序算法。30.回溯是一种既系统又跳跃的搜索算法。33.用回溯法搜索解空间树时，两种常用的剪枝函数是约束函数和约束函数。34.所需时间37.图的M着色问题可以用回溯法来解决。解决方案空间树中的叶节点数为mn，解决方案空间树中每个内部节点的子节点数为m简短回答问题1.用计算机解决问题：1.问题分析2。数学模型的建立。算法设计和选择。算法索引5。算法分析6。算法实现。程序调试。结果整理和文件2.最优二叉搜索树问题的动态规划算法void binarysearchtree(int a，int b)，int n，int *m，int *s，int *w)I，j，k，t，l；对于(I=1；I=n1；(I)wII-1=aI-1；I-1=0；对于(l=0；l=n-1；L)/-l是下标j-i之间的差。对于(I=1；I=n-l；(I)j=I l；wIj=wIj-1ajbj；mIj=mII-1mI 1jwIj；对于(k=I 1；k=j。k)t=mIk-1mk 1jwIj；if(t1)。编写的递归函数有：内部纤维(内部n) if (n=0)返回0；如果(n=1)返回1；如果(n1)返回光纤(n-1)光纤(n-2)；2.算法定义：算法是指一个过程，在这个过程中，当解决问题时，可以根据某些机械步骤获得问题的结果。3.算法的三要素1.行动2。控制结构3。数据结构4.该算法具有以下5个属性：贫困：一个算法必须总是在执行一个糟糕的步骤后结束，并且每个步骤必须在一个糟糕的时间内完成。确定性：算法中的每条指令都必须有确切的含义。一点也不含糊。只有一个入口和一个出口。可行性：算法是可行的，也就是说，算法描述的操作可以通过执行已经执行了有限次数的基本操作来实现。输入：一个算法有零个或多个输入，它们来自一组特定的对象。输出：一个算法有一个或多个与输入有特定关系的输出。常用的算法有迭代法、分治法、贪心法、动态规划法、回溯法和分枝定界法8.分治法的基本思想是：一个大小为n的问题被分解成k个较小的子问题，这些子问题彼此独立，并且与原问题相同。递归地解决这些子问题，然后合并每个子问题的解以获得原始问题的解。9.分治法解决的问题一般有以下特点：(1)通过在一定程度上缩小规模，问题很容易解决；(2)问题可以分解成几个较小的相同问题，即问题具有最优子结构性质；(3)由问题分解的子问题的解可以组合成问题的解；(4)由问题分解的子问题是相互独立的，即子问题不包含一般的子问题。10.分治法的基本步骤分治法在递归的每一层都有三个步骤：(1)分解：将原问题分解成若干个子问题，这些子问题规模小，相互独立，形式与原问题相同；(2)求解：如果子问题规模小，容易求解，直接求解，否则递归求解每个子问题；(3)合并：将每个子问题的解合并成原问题的解。11.动态规划的基本思想动态规划的本质是分治思想和解决冗余。因此，动态规划是一种通过将问题实例分解成更小且相似的子问题并存储子问题的解以避免重复计算来解决优化问题的算法策略。13.分治法和动态规划法的相似之处在于：要解决的问题被分解成几个子问题。首先求解子问题，然后从这些子问题的解中得到原始解。两者的区别在于它适用于用动态规划方法求解的问题，而分解得到的子问题往往不是相互独立的。然而，通过分解由分治法解决的问题而获得的子问题通常彼此独立。14.追溯方法回溯法也被称为启发式方法。该方法首先暂时放弃对问题规模的限制，按照一定的顺序逐一列举和测试问题的候选解。当发现当前候选解不能是解时，选择下一个候选解；如果当前候选人满足除问题规模要求之外的所有其他要求，则当前候选人解决方案的规模将继续扩大，调查将继续进行。如果当前候选解决方案满足包括问题规模在内的所有要求，则候选解决方案就是问题的解决方案。在回溯法中，放弃当前候选解并找到下一个候选解的过程称为回溯。扩展当前候选解决方案的规模以继续探测的过程称为前向探测。20.回溯法中常用的两种典型的解空间树是子集树和树的排列。当给定的问题是从N个元素的集合S中寻找满足某个性质的子集时，相应的解空间树称为子集树。这种子集树通常有2n个叶节点，遍历子集树需要O(2n)个计算时间。当给定的问题是确定满足一定性质的n个元素的排列时，相应的解空间树称为树的排列。这种排列的树通常有N！两个叶子节点。遍历树的排列需要O(n！)计算时间。22.请描述动态规划算法和贪婪算法的异同。共同点：需要最佳的子结构特性，它们都用于解决优化问题。差异：动态规划：根据子问题的解决方案，在每一步做出选择。贪婪方法：每一步都做一个选择不依赖于子问题的解决。动态规划方法的条件：子问题的重叠性质。贪婪方法的条件：最优子结构性质；贪婪选择的本质。动态规划：自下而上求解；贪婪方法：自上而下的解决方案。当贪婪方法可用时，动态规划方法可能不适用。当动态规划方法可用时，贪婪方法可能不适用。23.请解释为什么动态规划方法需要最佳的子结构特性。回答：最优子结构性质意味着大问题的最优解包含子问题的最优解。动态规划方法是自下而上地计算每个子问题的最优解，即首先计算子问题的最优解，然后用子问题的最优解构造大问题的最优解，因此需要最优子结构。26.在算法的复杂性分析中，O、和的含义是什么？在忽略常数因子的情况下接下来，o、和分别为算法的运行时间提供了什么界限？回答：如果有两个正态数C和N0，并且对于所有的NN0，有|f(N)|C|g(N)|，那么它被记录为：f(N)=O(g(N)。这时我们说f(N)的阶不高于g(N)的阶。如果有两个正常数C和自然数N0，那么当N N0时，有|f(N)|C|g(N)|，它被表示为f (n)=(g (n)。这时，我们说f(N)的阶不低于g(N)的阶。如果有正规数c1、c2和n0，对于所有nn0，有c1|g(N)| |f(N)| c2|g(N)|它被记录为f(N)=(g，(N)o、和分别提供算法运行时间的上限、下限和平均值。1.用动态规划策略解决最长公共子序列问题；(1)给出了计算最优值的递推公式。(2)给定两个序列X=B，C，D，A，Y=A，B，C，B，请使用动态规划策略找到其最长的公共子序列并要求该过程。回答：(1)(2)Y A B C BX0 0 0 0B0 0 1 1 1C0 0 1 2 2D0 0 1 2 2A01 1 2 2最长公共子序列：BC2.对于下列函数组f (n)和g (n)，确定f (n)=O (g (n)或F (n)= (g (n)或f(n)=(g(n)，并简要说明原因。(1)f(n)=2n；g(n)=n！(2)f(n)=；g (n)=log n2(3)f(n)=100；g(n)=log100(4)f(n)=n3；g(n)=3n(5)f(n)=3n；g(n)=2n回答：(1)f(n)=0(g(n)，因为g(n)的阶数高于f(n)。(2) f(n)= (g(n)，因为g(n)的阶数低于f(n)。(3) f(n)=(g(n)，因为g(n)与f(n)的阶数相同。(4) f(n)=O(g(n)，因为g(n)的阶数高于f(n)。(5) f(n)= (g(n)，因为g(n)的阶数低于3.对于下图所示的连接网络G，使用Kruskal算法找到G的最小生成树T。请在边集中写下在算法执行期间依次添加到T的边。阐述了贪婪策略和算法的基本思想，并简要分析了算法的时间复杂度。12345618111715192126679回答：TE=(3，4)、(2，3)、(1，5)、(4，6)(4，5)贪婪策略是从