《算法分析与设计》期末复习题
一、选择题
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^x
A．n+8 B ．n+6
C．n+7 D ．n+5
4.设问题规模为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(N2logN)
5.直接或间接调用自身的算法称为
( B )。
A．贪心算法 B ．递归算法C．迭代算法 D ．回溯法
6.Fibonacci数列中，第4个和第11个数分别是( D )。
A．5，89 B ．3，89
C．5，144 D ．3，144
7.在有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. 下列算法中通常以自底向上的方式求解最优解的是( B )。
A．备忘录法 B ．动态规划法
C．贪心法 D ．回溯法
