电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

期末总复习提要2010VIP免费

期末总复习提要2010_第1页
1/21
期末总复习提要2010_第2页
2/21
期末总复习提要2010_第3页
3/21
华南师范大学计算机学院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算法复杂性算法复杂性是算法运行所需要的计算机资源的量,需要时间资源的量称为时间...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

期末总复习提要2010

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部