《算法分析与设计》期末考试复习题纲(完整版)(总18页).doc

算法分析与设计期末复习题一、 选择题1. 算法必须具备输入、输出和（ D ）等4个特性。A可行性和安全性 B确定性和易读性C有穷性和安全性 D有穷性和确定性2. 算法分析中，记号O表示（ B ），记号表示（ A ）A.渐进下界 B.渐进上界C.非紧上界 D.紧渐进界3. 假设某算法在输入规模为n时的计算时间为T(n)=3*2n。在某台计算机上实现并完成概算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（ B ）解题方法：3*2n*64=3*2xAn+8 Bn+6Cn+7 Dn+54. 设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1