东南大学算法设计与分析复习题 2012年
什么是最坏情况时间复杂性?什么是平均情况时间复杂性?
答:最坏情况时间复杂性是规模为n的所有输入中,基本运算执行次数为最多的时间复杂性。
平均情况时间复杂性是规模为n的所有输入的算法时间复杂度的平均值 (一般均假设每种输入情况以等概率出现)。
什么是相互独立的函数序列?何时称函数项μk(x)能被其它函数项线性表出?
答:设{μ0(x), μ1(x), μ2(x), ... ,μn(x), ...}是某一数域上的函数序列, (x的值以及μk(x)(k=0,1,2, )的值都在同一个数域中) 任取μk(x)(k=0,1,2, ),不存在数域中的数α1,α2, ,αp,使得μk (x) = α1μi1(x) + α2μi2 (x) + + αpμip (x) ,即任何一个函数项μk(x)不能被其它函数项线性表出。
根据特征根的情况,常系数线性递归方程的解有哪几种不同的形式?
答:1.若方程(**)恰有r个互不相同的特征根α1,α2, ,αr (即i≠j时有αi≠αj),则齐次方程(*)的解为 an=A1+ A2+ +Ar(齐通解,即齐次方程的通解) (A1~Ar为待定系数,可由r个连续的边界条件唯一确定)
2.若α1,α2是(**)方程的一对共扼复数根ρ和ρ, eiθeiθ.则这两个根对应的解的部分为Aρncos(nθ)+Bρnsin(nθ) (A,B为实的待定系数)
3.若α是(**)方程的k重根,则α对应的解的部分为 C1αn+ C2 nαn+ C3 n2αn+ +Ck nk-1αn (C1~Ck为待定常数)
4.若(*)方程中的f(n)≠0(非齐次),且q(n)是(*)的一个解, 则(*)方程的解为: (*)的齐通解(含有待定系数)+ q(n) (非齐特解), (齐通解中的待定系数由边界条件唯一确定)
求和中的通项与积分中的被积函数之间有什么样的关系?
答:求和中的通项的表达形式一般就是被积函数,一般用放缩的方法求得通项得上下界。
分治法求最大、最小元算法的主要思想?
答:当n=2时,一次比较就可以找出两个数据元素的最大元和最小元。 当n>2时,可以把n个数据元素分为大致相等的两半, 一半有 n/2 个数据元素,而另一半有 n/2 个数据元素。 先分别找出各自组中的最大元和最小元,然后 将两个最大元进行比较,就可得n个元素的最大元; 将两个最小元进行比较,就可得n个元素的最小元。
求最大、最小元算法的时间复杂度(比较次数)下界是多少?分治算法在什么情况下可以达到下界?
东南大学算法设计与分析复习题_理学_高等教育_教育专区。算法设计与分析期末考试提纲的参考资料。什么是基本运算? 什么是基本运算? 答:基本运算是解决问题时占支配...
算法设计与分析复习题_IT/计算机_专业资料。算法设计与分析复习题算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性,0 个或多个输入...
算法设计与分析复习题_工学_高等教育_教育专区。算法设计与分析复习题 1 一个... 算法设计与分析期末试题... 3页 免费 东南大学算法设计与分析... 22页 ...
算法设计与分析复习题_计算机软件及应用_IT/计算机_专业资料。西南交大 算法 ... 东南大学算法设计与分析... 22页 免费 算法设计与分析期末试题... 3页 ...
算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性... 东南大学算法设计与分析... 22页 免费 算法设计与分析试题(A) 3页 免费 ...
算法设计与分析复习题目及答案(物联班)_IT认证_资格考试/认证_教育专区。一。选择题 1、二分搜索算法是利用( A、分治策略 B、动态规划法 )实现的算法。 C...
算法设计与分析复习题 1、分治法的基本思想:是将一个规模为 N 的问题分解为 K 个规模较小的子问题,这些子问题互相独立且与原问 、分治法的基本思想: 题相同...
算法设计与分析考试复习题_工学_高等教育_教育专区。该文档用于算法设计与分析考试的复习,文档中有选择填空和知识点总结,涵盖了大量的考点信息,适合大学本科生复习...
算法分析与设计—部分复习题答案_计算机软件及应用_IT/计算机_专业资料。西南交大 算法考试题目算法设计与分析复习题 1、 一个算法应有哪些主要特征? 有限性、确定...
计算机算法设计与分析复习题_工学_高等教育_教育专区。选填,简要介绍文档的主要内容,方便文档被更多人浏览和下载。《算法分析与设计》期末复习题一、 选择题 1....
热门文档