西工大算法复习资料总结材料(最终修订版)

《西工大算法复习资料总结材料(最终修订版)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、标准实用笔试部分一．简答题(40分)1.算法的基本概念、性质及其与程序的联系与区别算法：是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。算法性质：输入---有零个或者多个外部量作为算法的输入；输出---算法产生至少一个量最为输出；确定性：组成算法的每条指令是清晰的、无歧义的；有限性：算法中指令的执行次数有限和执行的时间有限。程序：是算法用某种设计语言的具体实现，程序可以不满足算法的有限性。2.大O表示法的含义和渐进时间复杂度（要会计算复杂度）大O表示法：称一个函数g(n)是O(f(n))，当且仅当存在常数c>0和n0>=

2、1，对一切n>n0均有

3、g(n)

4、<=c

5、f(n)

6、成立，也称函数g(n)以f(n)为界或者称g(n)囿于f(n)。记作g(n)=O(f(n))。定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。3.分治法的基本思想是什么分治法的基本思想是：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。4.

7、回溯算法的基本思想及其一般模式（子集树+排列树）基本思想：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。搜索子集树的一般模式：voidsearch(intm){if(m>n)//递归结束条件output();/

8、/相应的处理(输出结果)else{a[m]=0;//设置状态：0表示不要该物品search(m+1);//递归搜索：继续确定下一个物品a[m]=1;//设置状态：1表示要该物品search(m+1);//递归搜索：继续确定下一个物品}}搜索排列树的一般模式：voidsearch(intm){文案大全标准实用if(m>n)//递归结束条件output();//相应的处理(输出结果)elsefor(i=m;i<=n;i++){swap(m,i);//交换a[m]和a[i]if()if(canplace(m))//如果m处可放置searc

9、h(m+1);//搜索下一层swap(m,i);//交换a[m]和a[i](换回来)}}1.动态规划的基本思想、基本步骤、基本要素是什么基本思想：将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。基本步骤：①找出最优解的性质，并刻画其结构特征；②递归地定义最优值；③以自底向上的方式计算出最优值；④根据计算最优值时得到的信息，构造最优解。基本要素：最优子结构性质和子问题重叠问题2.什么是最优子结构性质和子问题重叠性质最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质

10、（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。 子问题重叠性质：指在用递归演算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。 3.分治法与动态规划的联系与区别联系：基本思想相同，即将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。区别：适用于动

11、态规划法求解的问题，经分解得到的子问题往往不是相互独立的。分治法子问题被重复计算多次，而动态规划子问题可用一个表来记录已解决子问题的答案，避免了子问题重复计算的问题。4.动态规划的变形（备忘录方法）与动态规划的联系与区别联系：都用表格保存已解决的子问题的答案区别：备忘录方法的递归方式是自顶向下的，而动态规划的递归方式是自底向上的。5.分支限界法（广度优先搜索）的基本思想是什么文案大全标准实用分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展节点。活结点一旦成为

12、扩展节点，就一次性产生所有儿子节点。在这些儿子节点中，导致不可行解或导致非最优解的儿子节点被舍弃，其余儿子节点被加入活结点表中。此后，从活结点表中取下一节点成为当前扩展节点，并重复上述节点扩展过程，这个过程一直持续到找到所需的解或活结