《算法设计复习简答题资料》由会员分享，可在线阅读，更多相关《算法设计复习简答题资料（2页珍藏版）》请在装配图网上搜索。
1、1、 什么是算法？算法的特征？算法和程序的区别通俗的讲，算法是指解决问题的方法和过程。严格地讲，算法是满足下述性质的指令序列： 输入：有零个或多个外部量作为算法的输入 输入：算法产生至少一个量作为输出 确定性：组成算法的每条指令是清晰的、无歧义的 有限性：算法中每条指令的执行次数有限，执行每次指令的时间也有限区别：程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性。例如操作系统，它是在无限循环中执行的程序，因而不是算法。然而可把操作系统的各种任务看成一些单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法实现。该子程序得到输出结果后便终止。2、 算法的复杂性？有几个要素
2、？算法的复杂性是算法运行所需要的计算机资源总和的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。要素：算法要解的问题的规模、算法的输入和算法本身的函数。3、 分治法的基本思想？分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归的解这些子问题，然后将各子问题的解合并得到原问题的解。4、 用分治策略思想来简述快速排序的算法步骤。对于输入的子数组ap:r，按以下3个步骤进行排序。1）分解：以ap为基准元素将ap:r划分成3段ap:q-1,aq和aq+1:r,使得ap:q-1中任何元素小于等于aq,而aq+1:r中任何元素大于
3、等于aq。下标q在划分过程中确定。2）递归求解：通过递归调用快速排序算法，分别对ap:q-1和aq+1:r进行排序。3）合并：由于对ap:q-1和aq+1:r的排序是就地进行的，所以在ap:q-1和aq+1:r都已排好的序后不需要执行任何计算，ap:r就已排好序。5、 简述动态规划的算法步骤。 找出最优解的性质，并刻画其结构特征； 递归地定义最优值； 以自底向上的方式计算出最优值； 根据计算最优值时得到的信息，构造最优解6、 简述贪心算法与动态规划法的基本要素。贪心算法的基本要素：贪心选择性质和最优子结构性质。动态规划算法的基本要素是：最优子结构性质和子问题重叠性质。7、 用贪心策略思想简述P
4、rim算法的算法步骤。设G=(V,E)是连通带权图，V=1,2,n。1.首先置S=12.只要S是V的真子集，就进行下一步的贪心选择。3.选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。直到S=V为止。4.在这个过程中选取到的所有边恰好构成G的一棵最小生成树。8、 用贪心策略思想简述Kruskal算法的算法步骤。设无向连通带权图G=(V,E),V=1,2,n。1.将G的n个顶点看成n个孤立的连通分支，将所有的边按权从小到大排序。2.从第一条边开始，依边权递增的顺序查看每一条边。3.当查看到第k条边(v,w)时，a.如果端点v和w分别是当前两个不同的连通分支T1和T2中的顶点时，
5、就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；b.如果断点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。4.直到只剩下一个连通分支时为止。此时，这个连通分支就是G的一棵最小生成树。9、 简述分支限界和回溯法的不同点。 求解目标不同，回溯法的求解目标是找出解空间树中满足约束条件的所有解，分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。 对解空间树的搜索方式不相同，回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。10、 简
6、述回溯法的算法步骤。1.针对所给问题，定义问题的解空间；2.确定易于搜索的解空间结构；3.以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。11、 什么是剪枝函数？有何作用？为何要在分支限界法中使用？用约束函数在扩展结点处剪去不满足约束的子树；和用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。采用剪枝函数，可避免无效搜索，提高回溯法的搜索效率。在分支限界法中使用剪枝函数，可以加速搜索。该函数给出每一个可行结点相应的子树可能获得的最大价值的上界。如果这个上界不比当前最优值更大，则说明相应的子树中不含问题的最优解，因而可以剪去。另一方面，也可以将上界函数确定的每个结点的上界值作为优先级，以该优先级的非增序抽取当前扩展结点。这种策略有时可以更迅速地找到最优解。编程：1.回溯法2.分枝限界法3.贪新算法4.分治算法（迭代，递归）计算：2.最长子序列递归公式： cij=0 i=0,j=0 ci-1j-1+1 i,j0;xi=yimaxcij-1,ci-1j i,j0;xiyi
算法设计复习简答题资料
