算法设计复习题.docx

PAGE

PAGE6

一、选择题

1．选出不是算法所必须具备的特征（C）。

A有穷性 B确切性 C高效性 D可行性2．不属于给合问题的是（C）。

AEuler的36名军官问题 B图的Hamiliton C求二项式展开系数 D集合的幂集

下列（ C）不是衡量算法的标准。

A时间效率 B空间效率 C问题的难度 D适应能力

下列函数关系随着输入量增大增加量最快的是（D ）。

Alogn Bn3 C2n Dn!

如果某一算法的执行时间不超过输入规模的2倍，那么算法渐近时间复杂度为（B）。AO(2n) BO(n) C?(n) D?(n)

下列程序段的算法时间复杂度是（D ）

for(i=1;i=n;i++)

for(j=1;i=m;m++)

S;

AO(n2) BO(m2) C O(m+n) DO(mn)

下列程序段S执行次数为（C ）。

for(i=1;i=n;i++)

for(j=1;i=m;m++)

S;

A n2 Bn2/2 C n(n+1) D n(n+1)/28．使用F(n)=n*f(n-1)递归求F（4），递归调用子函数的次数为（D ）。

A 3次 B4次 C 5次 D 8次

递推关系M(n)=M(n-1)+1,M(0)=0的算法时间复杂度为（C ）。

A O(n!) BO(2n) C O(n) D O(1)

与递推关系x(n)=2x(n-1)+1,x(1)=1等价的通项公式为（B ）。

A x(n)=2n B x(n)=2n-1 C x(n)=2n+1 Dx(n)=n!

三个盘子的汉诺塔，至少要执行移动操作次数为（ D ）。

A1次 B 3次 C 6次 D 7次12．Fibonacci数列第10项为（D）。

A 3 B 13 C 21 D 34

13．12个金币中有一枚是假币，至少需要称量的次数是（C ）。

A 0 B 1 C 3 D 4

二维最近邻点问题，如果使用分治法，对于一个子集上的某一点，另一个子集上需要检查的点的个数是（C）。

A 1个 B2个 C 6个 D 8个15．一维最近邻点问题，如果使用分治法，对于一个子集上的某一点，另一个子集上需要检查的点的个数是（B ）。

A 1个 B2个 C 6个 D 8个

下列图形不属于凸集的是（ D ）。

A三角形 B四边形 C 五边形 D 五角星

对于凸集下列说法正确的是（B ）。

A凸集中的所有点都属于凸包；B凸集中任意两点的连线都在凸中；C凸集中任意两点的连线都不在凸集中；D一个点集如果不是凸集，则点集中任意两点的连线都不在凸集中

下列是动态规划算法基本要素的是（A ）。

A最优子结构 B构造最优解 C 贪心选择因子 D界限函数18．下列问题中具有多项式解法的是（C）。

A背包问题 B生成排列序列问题 Cn个元素的排序问题 D集合的幂集问题

如果背包的容量为100，而物体共有10件，则使用动态规划求解背包问题数组大小为

（D）。

A 10 B 100 C 1000 D 10000

排列问题属于（ D ）。

A可解问题 B不可解问题 C P问题 D NP问题

21．（A）算法应用到广度优先遍历策略。

A分支界限法 B动态规划法 C分治法 D回溯法22．Dijstra算法属于（A ）。

A贪心算法 B概率算法 C回溯法 D分支限界法23．若f(n)=2n3+3n，g(n)=100n2+2n+100，则f=O(g)为（B ）。

A真 B假 C无法确定 D均不是

若f(n)=50n+logn，g(n)=10n+loglogn，则f=O(g)为（A ）。

A真 B假 C无法确定 D均不是

Prim算法求最小生成树采用的是（A ）算法思想。

A贪心算法 B动态规划法 C回溯法 D蛮力法二、简答题

给出递推公式x(n)=x(n-1)+n,x(0)=0对应的通项公式计算过程？解：

X(n)-X(n-1)=n

X(n-1)-X(n-2)=n-1

…… ……

X(1)-X(0)=1

X(n)-X(0)=(n+1)n\2

X(n)=(n+1)n\2

?、?、?之间的区别与联系是什么？答：?描述增长率的上限

?用来表示算法的精确阶

?描述增长率的下限

只要当考察问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶，……

3种等渐近符号。

什么是数据结构，什么是算法，两者有什么关系？答：

数据结构：计算机存储/族素质数据的方式。算法：一系列解决问题的指