v1.0 可编辑可修改11《算法分析与设计》期末复习题一、选择题1.算法必须具备输入、输出和（ D ）等 4 个特性。A．可行性和安全性 B．确定性和易读性C．有穷性和安全性 D．有穷性和确定性2.算法分析中，记号O表示（ B ），记号Ω 表示（ A ）A. 渐进下界 B.渐进上界C.非紧上界 D.紧渐进界3.假设某算法在输入规模为n 时的计算时间为T(n)=3*2^n 。在某台计算机上实现并完成概算法的时间为t 秒。现有另一台计算机，其运行速度为第一台的64 倍，那么在这台新机器上用同一算法在t 秒内能解输入规模为多大的问题（ B ）解题方法： 3*2^n*64=3*2^xA．n+8 B．n+6C．n+7 D．n+54.设问题规模为N 时，某递归算法的时间复杂度记为T(N) ，已知T(1)=1 ，T(N)=2T(N/2)+N/2，用 O表示的时间复杂度为（ C ）。A．O(logN) B．O(N) C．O(NlogN) D．O(N2 logN) 5.直接或间接调用自身的算法称为（ B ）。A．贪心算法 B．递归算法C．迭代算法 D．回溯法6.Fibonacci数列中，第4 个和第 11 个数分别是（ D ）。A．5，89 B．3， 89 C．5，144 D．3， 1447.在有 8 个顶点的凸多边形的三角剖分中，恰有（ B ）。v1.0 可编辑可修改22A．6 条弦和 7 个三角形 B．5 条弦和 6 个三角形C．6 条弦和 6 个三角形 D．5 条弦和 5 个三角形8.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。A．重叠子问题 B．最优子结构性质C．贪心选择性质 D．定义最优解9.下列哪个问题不用贪心法求解（ C ）。A．哈夫曼编码问题 B．单源最短路径问题C．最大团问题 D．最小生成树问题10.下列算法中通常以自底向上的方式求解最优解的是（ B ）。A．备忘录法 B．动态规划法C．贪心法 D．回溯法11.下列算法中不能解决0/1 背包问题的是（ A ）。A．贪心法 B．动态规划C．回溯法 D．分支限界法12.下列哪个问题可以用贪心算法求解（ D ）。A．LCS问题 B．批处理作业问题C．0-1 背包问题 D．哈夫曼编码问题13.用回溯法求解最优装载问题时，若待选物品为m 种，则该问题的解空间树的结点个数为（）。A．m! B．2m+1C．2m+1-1 D．2m14.二分搜索算法是利用（A ）实现的算法。A．分治策略 B．动态规划法C．贪心法 D．回溯法15.下列不是动态规划算法基本步骤的是（B ）。P44A．找出最优解的性质 B．构造最优解C．算出最优解 ( 应该是最优值 ) D．定义最优解v1.0 可编辑可修改3316.下面问...
