《算法设计与分析》复习题_2877007

填空1.直接或间接地调用自身的算法称为递归2.算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。3。以广度优先或以最小耗费方式搜素间题解的算法称为分支限界法4.回溯法解题的显若特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(),则回湖法所需的计算空间通常为o(h(n》5.人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题结论的，叫做算法方案方案；另一类是不能通过若干个步骤直截了当地得出结论，而是需要反复验证才能解决的，叫做启发式方案二方案。6.算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。7。在进行问题的计算复杂性分析之前，首先必须建立求解向题所用的计算模型。3个基本计算模型是随机存取机、随机存取存储程序机方、图家机8.快速排序算法的性能取决于划分的对称性9.计算机的资源最重要的是内存和运草资源。因而，算法的复杂性有时间一和空间之分。10.贪心算法总是做出在当前看来最优的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优解。11.许多可以用贪心算法求解的问题一般具有2个重要的性质：最优子结构的性质和贪心选择的性质。12.常见的两种分支限界法为队列式和优先队列式13.解决0/1背包间题可以使用动态规划、回湖法和分支限界法，其中需要排序的是回湖法,不需要排序的是动态规划和分支限界法14.f(n)=62”+2,fm的渐进性态f(n)=0(2n)15.对于含有n个元素的排列树问题，最好情况下计算时间复杂性为最坏情况下计算时间复杂性为n!一·16.在忽略常数因子的情况下，0、2和日三个符号中，⊙提供了算法运行时间的一个上界17.回潮法的求解过程，即在问题的解空间树中，按深度优先策略从根结点出发搜索解空间树。18.分支限界法的求解过程，即在问题的解空间树中，按广度优先策略从根结点出发搜索解空间树。19.多项式An=amnm+l+an+a的上界为2n20,用分支限界法解布线问题时，对空间树搜索结束的标志是活结点表为空21.使用回湖法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界皇后问题和01背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进第1页共9页