文档介绍:算法分析与设计基础知识一、选择题 1、二分搜索算法是利用( A)实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 ( A)。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 (A)。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 ( C)。 A、运行速度快 B、占用空间少 C、时间复杂度低 D、代码短 ( D)。 A、棋盘覆盖问题 B、选择问题 C、归并排序 D、0/1 背包问题 ( C) :(A) . ,一般具有的重要性质为:(A) ,按(D)策略,从根结点出发搜索解空间树。 10. 分支限界法在问题的解空间树中,按( A)策略,从根结点出发搜索解空间树。 11. 下面不是分支界限法搜索方式的是( D)。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 0-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使得对所有 n? n 0有: 0? f(n) ? cg(n) }; B、O(g(n)) ={f(n) |存在正常数 c和n0使得对所有 n? n 0有: 0? cg(n) ? f(n) }; C、O(g(n)) ={f(n) |对于任何正常数 c>0 ,存在正数和 n 0>0使得对所有n? n 0有: 0? f(n)<cg(n) }; D、O(g(n)) ={f(n) |对于任何正常数 c>0 ,存在正数和 n 0>0使得对所有 n? n 0有: 0? cg(n) <f(n) }; 15. 记号?的定义正确的是( B)。 A、O(g(n)) ={f(n) |存在正常数c和n0使得对所有n? n 0有:0? f(n) ? cg(n) }; B、O(g(n)) ={f(n) |存在正常数 c和n0使得对所有 n? n0有:0? cg(n) ? f(n) }; C、(g(n)) ={f(n) |对于任何正常数 c>0 ,存在正数和 n0>0使得对所有n? n0有: 0? f(n)<cg(n) }; D、(g(n)) ={f(n) |对于任何正常数 c>0 ,存在正