精品文档---下载后可任意编辑《算法分析与设计》期末复习题一、 选择题1
算法必须具备输入、输出和（ D ）等 4 个特性
A．可行性和安全性 B．确定性和易读性C．有穷性和安全性 D．有穷性和确定性2
算法分析中，记号 O 表示（ B ），记号 Ω 表示（ A ）A
渐进下界 B
非紧上界 D
假设某算法在输入规模为 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(N²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 ）
A．6 条弦和 7 个三角形 B．5 条弦和 6 个三角形C．6 条弦和 6 个三角形 D．5 条弦和 5 个三角形8
一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）
A．重叠子问题 B．最优子结构性质C．贪心选择性质 D．定义最优解9
下列哪个问题不用贪心法求解（ C ）
A．哈夫曼编码问题 B．单源最短路径问题C．最大团问题 D．最小生成树问题10
