期末总复习提要2010VIP专享VIP免费

华南师范大学计算机学院2010-06AlgorithmsDesignTechniquesandAnalysis算法设计技巧与分析期末总复习课考试题型各章复习提要考试题型简答题(每题5分，共20分)如何理解算法复杂度？如何理解渐近表达复杂度的记号？简述分析一个算法的时间复杂度的基本步骤及各个步骤的要点。如果图用邻接矩阵来表示，那么图的深度优先算法的时间复杂度是什么？图用邻接表来表示呢？考试题型计算题(每题7-8分，共15分)给出下列递归方程的解：f(n)=5f(n-1)-6f(n-2),n>2;f(0)=1,f(1)=0.使用记号表示下列函数：n2+1000nlog10n+100n考试题型算法分析题(10分)考虑下列算法COUNT，其输入为正整数n。AlgorithmCOUNT(1)count←0(2)fori←1ton(3)j←n/2(4)whilej1(5)count←count+1(6)ifjisoddthenj←0elsej←j/2(7)endwhile(8)endfor考试题型(a)当n是2的整数次幂时，步骤(5)要执行多少次？(b)当n是3的奇数次幂时，步骤(5)要执行多少次？(c)将算法的时间复杂度用记号O表示出来。(d)将算法的时间复杂度用记号表示出来。(e)记号O和，哪一个更适合表示该算法的时间复杂度?考试题型应用题(每题15分左右，共55分)归纳技术、分治法：考虑使用归并排序给序列{10,8,2,4,12,6}排序。请给出算法执行中各次划分、合并的结果。（可画图表示）动态规划：使用动态规划法来求解下列0/1背包问题的实例：n=5,W={2,1,2,3,3}，P={8,6,7,9,8}，M=6。给出主要步骤的结果。考试题型贪心法：考虑用哈夫曼算法来找字符a,b,c,d,e,f的最优编码。这些字符出现在文件中的频数之比为8:3:5:4:11:7。试给出字符a,b,c,d,e,f的一种最优编码。要求给出主要步骤的结果。图的遍历：画出给定图的深度优先生成树。考试题型回溯法：考虑用回溯算法求解k-着色问题：给定无向图G=,要求使用k种颜色来给图中每个结点着色（每个结点使用k种颜色之一），使得没有两个相邻的结点颜色相同。(a)给出解向量形式，并画出当n=3,k=3时的搜索树。(b)给出剪枝操作。(c)最坏情况下你的算法在搜索树上会生成多少个结点？分析算法的时间复杂度。各章复习要点第一章算法分析的基本概念复习范围1.1---1.14复习要点评价算法性能的几个标准正确性、易读性、健壮性、算法的时间和空间性能：高效率和低存储空间算法复杂度概念(MIA)渐近记号、、的含义P14最优算法的概念P20最好、最坏、平均时间(空间)复杂度P26分析复杂度的主要步骤，各步骤的要点（包括输入大小的确定P31、基本操作的选择P24等）相关习题类型1.14---1.16各章复习要点第二章算法分析的数学基础复习范围2.7----2.8复习要点简单求和公式P48定积分近似求和P50两个重要公式几个例子2.15~2.17简单递归方程的解法P52相关习题类型2.16,2.17,2.18,2.19各章复习要点第五章归纳技术*复习范围5.3,5.4,5.5,5.7复习要点各算法的基本思想能简单应用相关习题类型5.7-5.9,5.17-5.18,5.29各章复习要点第六章分治法复习范围6.1---6.4,6.6---6.7复习要点分治法的适用范围、基本思想各算法的基本思想、复杂度结论能简单应用相关习题类型6.10,6.31,6.36,6.44各章复习要点第七章动态规划法复习范围7.2----7.6P120复习要点动态规法法的适用范围、基本步骤各算法的基本思想能简单应用相关习题类型7.5,7.9,7.15,7.21各章复习要点第八章贪心法复习范围8.1----8.5复习要点贪心法的基本思想各算法的基本思想、复杂度结论(Dijkstra、Prim算法的改进不作要求)能简单应用相关习题类型8.13，8.23,8.24，8.31各章复习要点第九章图的遍历复习范围9.1，9.2，9.4复习要点深度优先遍历和宽度优先遍历的基本思路、时空复杂度注意：应用中需要用到的边的几种类型相关习题类型9.1,9.2,9.6,9.19,9.20,9.31各章复习要点第十三章回溯法复习范围13.1---13.4复习要点掌握回溯法的求解思路、适用范围回溯法设计的几个要素能简单应用例13.113.2相关习题类型13.1,13.9,13.10,13.11算法复杂性算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间...