算法设计和分析复习题2.doc

算法设计与分析复习题1、分治法的基本思想：是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。2、贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择，3、?Prim算法：设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i?S，j?V-S，且c[j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。4、什么是剪枝函数：回溯法有哪些信誉好的足球投注网站解空间树时，通常采用两种策略避免无效有哪些信誉好的足球投注网站，提高回溯法的有哪些信誉好的足球投注网站效率。其一是用约束函数在扩展结点处剪?去不满足约束的子树；其二是用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。6、??分支限界法的基本思想：(1)分支限界法常以广度优先或以最小耗费(最大效益)优先的方式?有哪些信誉好的足球投注网站问题的解空间树。(2)在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致?非最优解的儿子结点被舍弃，其余儿子结点?被加入活结点表中。(3)此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需的解或活结点表这空时为止。5、?什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。6、?最优子结构性质：该问题的最优解包含着其子问题的最优解。7、?回溯法：是一个既带有系统性又带有跳跃性的有哪些信誉好的足球投注网站算法。这在问题的解空间树中，按深度优先策略，从根结点出发有哪些信誉好的足球投注网站解空间树。算法有哪些信誉好的足球投注网站至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的有哪些信誉好的足球投注网站，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略有哪些信誉好的足球投注网站。8、Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。9、?算法满足的性质：输入、输出、确定性、有限性。10、程序与算法不同：程序不满足有限性。11、输入：有零个或多个外部量作为输入。12、输出：算法产生至少一个量作为输出。13、确定性：组成算法的每条指令是清晰的，无歧义的。14、有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。15、递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。16、递归算法的缺点：运行效率较低，耗费的计算时间和占用的存储空间都多。为了达到此目的，根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。17、合并排序的时间复杂度是：T(n)=O(nlogn)。18、快速排序的时间复杂度是：T(n)=O(nlogn)。19、动态规划算法的基本要素：最优子结构性质和子问题重叠性质。20、贪心算法的基本要素：贪心选择性质和最优子结构性质。21、?前缀码：对每一个字符规定一个0、1串作为其代码，并要求任一字符的代码都?不是其他字符代码的前缀，这种编码称为前缀码。22、?哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。23、哈夫曼编码的平均码长为B(T)=24、Dijkstra算法是解单源最短路径问题的贪心算法。时间复杂度是O（n?）。25、生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。26、最常见的分支限界法有两种：队列式（FIFO）分支限界法和优先队列式分支限界法。27、?概率算法可分为4类：数值概率算法、蒙特卡罗算法、拉斯维加斯算法和舍伍德算法。28、数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。29、蒙特卡罗算法用于求问题的准确解。能求得问题的一个解，但这个解未必是正确的。30、拉斯维加斯算法不会得到不正确的解。但有时用拉斯维加斯算法找不到解。31、舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。32、回溯法效率的因素：（1）产生x[k]的时间。（2）满足显约束的x[k]值