算法设计与分析复习题目及答案.doc

分治法
1、二分搜索算法是运用（ 分治方略）实现算法。
9. 实现循环赛日程表运用算法是（分治方略 ）
27、Strassen矩阵乘法是运用（分治方略 ）实现算法。
34．实现合并排序运用算法是（分治方略 ）。
实现大整数乘法是运用算法（ 分治方略 ）。
17．实现棋盘覆盖算法运用算法是（分治法 ）。
29、使用分治法求解不需要满足条件是（子问题必要是同样 ）。
不可以使用分治法求解是（0/1背包问题 ）。
动态规划
下列不是动态规划算法基本环节是（ 构造最优解 ）
下列是动态规划算法基本要素是（子问题重叠性质 ）。
下列算法中普通以自底向上方式求解最优解是（动态规划法 ）
备忘录办法是那种算法变形。（ 动态规划法 ）
最长公共子序列算法运用算法是（ 动态规划法 ）。
矩阵连乘问题算法可由（动态规划算法B）设计实现。
实现最大子段和运用算法是（  动态规划法   ）。
贪心算法
能解决问题：单源最短途径问题，最小耗费生成树问题，背包问题，活动安排问题，
不能解决问题：N皇后问题，0/1背包问题
是贪心算法基本要素是（贪心选取性质和最优子构造性质）。
回溯法
回溯法解旅行售货员问题时解空间树是（ 排列树 ）。
剪枝函数是回溯法中为避免无效搜索采用方略
回溯法效率不依赖于下列哪些因素（ 拟定解空间时间）
分支限界法
最大效益优先是（ 分支界限法 ）一搜索方式。
分支限界法解最大团问题时，活结点表组织形式是（ 最大堆 ）。
分支限界法解旅行售货员问题时，活结点表组织形式是（ 最小堆 ）
优先队列式分支限界法选用扩展结点原则是（ 结点优先级 ）
在对问题解空间树进行搜索办法中,一种活结点最多有一次机会成为活结点是( 分支限界法 ).
从活结点表中选取下一种扩展结点不同方式将导致不同分支限界法,如下除( 栈式分支限界法 )之外都是最常用方式.
（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选用下一种节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定优先级选用优先级最高节点成为当前扩展节点。
（最优子构造性质）是贪心算法与动态规划算法共同点。
贪心算法与动态规划算法重要区别是（ 贪心选取性质   ）。
回溯算法和分支限界法问题解空间树不会是( 无序树 ).
14．哈弗曼编码贪心算法所需计算时间为（   B     ）。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
21、下面关于NP问题说法对的是（B ）
A NP问题都是不也许解决问题
B P类问题包括在NP类问题中
C NP完全问题是P类问题子集
D NP类问题包括在P类问题中
40、背包问题贪心算法所需计算时间为（  B      ）
A、O（n2n）     B、O（nlogn）    C、O（2n）      D、O（n）
42．0-1背包问题回溯算法所需计算时间为（  A      ）
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
.
（   B     ）。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
53．采用贪心算法最优装载问题重要计算量在于将集装箱依其重量从小到大排序，故算法时间复杂度为 ( B ) 。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
56、算法是由若干条指令构成有穷序列，并且满足如下性质（ D ）
输入：有0个或各种输入
输出：至少有一种输出
拟定性：指令清晰，无歧义
有限性：指令执行次数有限，并且执行时间有限
A (1)(2)(3) B(1)(2)(4) C(1)(3)(4) D (1) (2)(3)(4)
57、函数32n+10nlogn渐进表达式是( B ).
A. 2n B. 32n C. nlogn D. 10nlogn
59、用动态规划算法解决最大字段和问题，其时间复杂性为( B ).

61、设f(N),g(N)是定义在正数集上正函数,如果存在正常数C和自然数N0,使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时有下界g(N),记作
f(N)∈○(g(N)),即f(N)阶( A )g(N)阶.

二、填空题
2、程序是 算