算法分析与设计基础知识习题.docx

文档介绍：算法分析与设计基础知识
选择题
1、二分搜索算法是利用( A  )实现的算法。
A、分治策略   B、动态规划法   C、贪心法    D、回溯法
2. 下列不是动态规划算法基本步骤的是(  A   )。
A、找出最优解的性质    B、构造最优解  
C、算出最优解   D、定义最优解
3. 回溯法解旅行售货员问题时的解空间树是( A  )。
A、子集树 B、排列树
C、深度优先生成树 D、广度优先生成树
4. 衡量一个算法好坏的标准是( C )。
A、运行速度快 B、占用空间少 C、时间复杂度低 D、代码短
5. 以下不可以使用分治法求解的是( D )。
A、棋盘覆盖问题 B、选择问题 C、归并排序 D、 0/1背包问题
6. 动态规划算法的基本要素为( C )
A. 最优子结构性质与贪心选择性质

D. 预排序与递归调用
7. 以下关于渐进记号的性质是正确的有:( A )
=Θgn,gn=Θhn⟹fn=Θhn
B. fn=Ogn,gn=Ohn⟹hn=Ofn
C. Ofn+O(gn)=O(minfn,gn)
D. fn=Ogn⟺gn=O(fn)
8. 能采用贪心算法求最优解的问题,一般具有的重要性质为:(A)
A. 最优子结构性质与贪心选择性质

D. 预排序与递归调用
9. 回溯法在问题的解空间树中,按( D )策略,从根结点出发搜索解空间树。
广度优先 B. 活结点优先 D. 深度优先
10. 分支限界法在问题的解空间树中,按(A)策略,从根结点出发搜索解空间树。
A. 广度优先 B. 活结点优先 D. 深度优先
11. 下面不是分支界限法搜索方式的是( D )。
A、广度优先 B、最小耗费优先
C、最大效益优先 D、深度优先
-1背包问题时,活结点表的组织形式是( B )。
A、最小堆 B、最大堆 C、栈 D、数组
13. 常见的两种分支限界法为(D)
A、广度优先分支限界法与深度优先分支限界法;
B、队列式(FIFO)分支限界法与堆栈式分支限界法;
C、排列树法与子集树法;
D、队列式(FIFO)分支限界法与优先队列式分支限界法;
14、记号O的定义正确的是(A)。
A、O(g(n)) = { f(n) | 存在正常数c和n0使得对所有nn0有:0 f(n) cg(n) };
O(g(n)) = { f(n) | 存在正常数c和n0使得对所有nn0有:0 cg(n) f(n) };
O(g(n)) = { f(n) | 对于任何正常数c>0,存在正数和n0 >0使得对所有nn0有:0 f(n)<cg(n) };
O(g(n)) = { f(n) | 对于任何正常数c>0,存在正数和n0 >0使得对所有nn0有:0 cg(n) < f(n) };
15. 记号的定义正确的是(B)。
O(g(n)) = { f(n) | 存在正常数c和n0使得对所有nn0有:0 f(n) cg(n) };
O(g(n)) = { f(n) | 存在正常数c和n0