算法设计复习题.doc

一、选择题 1．选出不是算法所必须具备的特征（C）。 A有穷性 B确切性 C高效性 D可行性 2．不属于给合问题的是（ C ）。 A Euler的36名军官问题 B 图的Hamiliton C求二项式展开系数 D 集合的幂集 3．下列（ C ）不是衡量算法的标准。 A 时间效率 B 空间效率 C 问题的难度 D 适应能力 4．下列函数关系随着输入量增大增加量最快的是（ D ）。 A logn Bn3 C2n D 5．如果某一算法的执行时间不超过输入规模的2倍，那么算法渐近时间复杂度为（ B ）。 A O(2n) B O(n) C? (n) D ?(n) 6．下列程序段的算法时间复杂度是（ D ） for (i=1;i=n;i++) for (j=1;i=m;m++) S; A O(n2) B O(m2) C O(m+n) D O(mn) 7．下列程序段S执行次数为（ C ）。 for (i=1;i=n;i++) for (j=1;i=m;m++) S; A n2 B n2/2 C n(n+1) D 8．使用F(n)=n*f(n-1)递归求F（4），递归调用子函数的次数为（D ）。 A 3次 B 4次 C 5次 D 8次 9．递推关系M(n)=M(n-1)+1,M(0)=0的算法时间复杂度为（ C ）。 A O(n!) B O(2n) C O(n) D O(1) 10．与递推关系x(n)=2x(n-1)+1,x(1)=1等价的通项公式为（ B ）。 A x(n)=2n B x(n)=2n-1 C x(n)=2n+1 D 11．三个盘子的汉诺塔，至少要执行移动操作次数为（ D ）。 A1次 B 3次 C 6次 D 7次 12．Fibonacci数列第10项为（D）。 A 3 B 13 C 21 13．12个金币中有一枚是假币，至少需要称量的次数是（ C ）。 A 0 B 1 C 3 D 4 14．二维最近邻点问题，如果使用分治法，对于一个子集上的某一点，另一个子集上需要检查的点的个数是（C ）。 A 1个 B 2个 C 6个 D 8个 15．一维最近邻点问题，如果使用分治法，对于一个子集上的某一点，另一个子集上需要检查的点的个数是（ B ）。 A 1个 B 2个 C 6个 D 8个 15．下列图形不属于凸集的是（ D ）。 A 三角形 B 四边形 C 五边形 D 五角星 16．对于凸集下列说法正确的是（ B ）。 A 凸集中的所有点都属于凸包； B 凸集中任意两点的连线都在凸中；C 凸集中任意两点的连线都不在凸集中；D一个点集如果不是凸集，则点集中任意两点的连线都不在凸集中 17．下列是动态规划算法基本要素的是（ A ）。 A 最优子结构 B构造最优解 C 贪心选择因子 D界限函数 18．下列问题中具有多项式解法的是（C）。 A背包问题 B生成排列序列问题 C n个元素的排序问题 D 集合的幂集问题 19．如果背包的容量为100，而物体共有10件，则使用动态规划求解背包问题数组大小为（D ）。 A 10 B 100 C 1000 20．排列问题属于（ 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，