WORD格式
9. 实现循环赛日程表利用的算法是（分治策略
27、Strassen矩阵乘法是利用（分治策略
）实现的算法。
）
分治法
1、二分搜索算法是利用（
分治策略）实现的算法。
34．实现合并排序利用的算法是（分治策略
）。
实现大整数的乘法是利用的算法（
分治策略 ）。
17．实现棋盘覆盖算法利用的算法是（分治法
）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的 不可以使用分治法求解的是（
0/1背包问题
）。
动态规划
下列不是动态规划算法基本步骤的是（
构造最优解
）
下列是动态规划算法基本要素的是（子问题重叠性质
）。下列算法中通常以自底向上的方式求解最优解的是（动态规划法
备忘录方法是那种算法的变形。（
动态规划法
）
最长公共子序列算法利用的算法是（
动态规划法
）。
矩阵连乘问题的算法可由（动态规划算法
B）设计实现。
实现最大子段和利用的算法是（
动态规划法
）。贪心算法
能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题
是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）
回溯法
回溯法解旅行售货员问题时的解空间树是（
排列树）。
剪枝函数是回溯法中为避免无效搜索采取的策略
回溯法的效率不依赖于下列哪些因素（
确定解空间的时间）专业资料整理
）。 ）
。
WORD格式
分支限界法
最大效益优先是（
分支限界法解旅行售货员问题时，活结点表的组织形式是（
的是( 分支限界法
点为扩展节点。
（ 2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为
B P类问题包含在NP类问题中
C NP完全问题是P类问题的子集
D NP类问题包含在P类问题中
40、背包问题的贪心算法所需的计算时间为（
B
）
贪心算法与动态规划算法的主要区别是（ 回溯算法和分支限界法的问题的解空间树不会是
贪心选择性质
( 无序树
).
）。
当前扩展节点。
从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法 ,以下除
( 栈式分支限界法 )之外都是最常见的方式 .
（1）队列式(FIFO)分支限界法：按照队列先进先出（ FIFO）原则选取下一个节
).
优先队列式分支限界法选取扩展结点的原则是（ 在对问题的解空间树进行搜索的方法中
结点的优先级
）
,一个活结点最多有一次机会成为活结点
最小堆 ）
分支界限法
）的一搜索方式。
最大堆 ）。
分支限界法解最大团问题时，活结点表的组织形式是（
（最优子结构性质）是贪心算法与动态规划算法的共同点。
14．哈弗曼编码的贪心算法所需的计算时间为（
C、O（2n） A、O（n2n） B、O（nlogn）
21、下面关于 NP问题说法正确的是（ B）
A NP问题都是不可能解决的问题
B
）。
D、O（n）
专业资料整理
WORD格式
A、O（n2）
42．0-1背包问题的回溯算法所需的计算时间为（
A、O（n2n）
.
47.背包问题的贪心算法所需的计算时间为（
A、O（n2）
（ 2）输出：至少有一个输出
（ 3）确定性：指令清晰，无歧义
（ 4）有限性：指令执行次数有限，而且执行时间有限
A(1)(2)(3) B(1)(2)(4) C(1)(3)(4)D(1)(2)(3)(4)
n
n 、函数 的渐进表达式是(B).
57 32+10nlog
f(N)∈○(g(N)),即f(N)的阶(
2、程序是
3、算法的“确定性”指的是组成算法的每条
6、算法是指解决问题的
7、从分治法的一般设计模式可以看出，
用它设计出的程序一般是
递归算法
。
一种方法
或 一个过程
。
指令
是清晰的，无歧义的。
算法
用某种程序设计语言的具体实现。
A.不高于B.不低于C.等价于D.逼近
A
)g(N)的阶.
61、设f(N),g(N)是定义在正数集上的正函数
,如果存在正的常数
C和自然数N0, g(N),记作
A.2
n
nn
B、O（nlogn） C、O（2）
A
n
D、O（n） ）
B、O（nlogn）C、O（2n）D、O（n）
B D、O（n）
）。
B、O（nlogn）C、O（2）
n
53．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大
排序，故算法的时间复杂度为 ( B ) 。
nn
A、O（n2） B、O（nlogn）C、O（2） D、O（n）
56、算法是由若干条指令组成的有穷序列，而且满足以下性质（ （ 1）输入：有0个或多个输入
D
）
B.32
n
C.nlog
n
D.10nlog
(B
).
n
59、用动态规划算法解决最大字段和问题，其时间复杂性为 A.logn
B.n
C.n
2
D.nlogn
使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时有下界
二、填空题
专业资料整理
WORD格式
11、计算一个算法时间复杂度通常可以计算
或计算步。
14、解决0/1背包问题可以使用动态规划、 序的是
动态规划
回溯法和分支限界法，其中不需要排
，分支限界法
。
循环次数
、 基本操作的频率
，需要排序的是 回溯法
15、使用回溯法进行状态空间树裁剪分支时一般有两个标准： 约束条件和目标函
数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束 条件和目标函数的界进行裁剪的是0/1 裁剪的是
N皇后问题
。
背包问题
又带有
约束函数 规模
，只使用约束条件进行
限界
跳跃性
30.回溯法是一种既带有 的搜索算法。
系统性
33．回溯法搜索解空间树时，常用的两种剪枝函数为
函数
。
和
34. 任何可用计算机求解的问题所需的时间都与其 35. 快速排序算法的性能取决于 36. Prim算法利用
是 O(n)
2有关。
划分的对称性。 策略求解
贪心 。
最小生成树
问题，其时间复杂度
37. 图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是 m
n
，解空间树中每个内结点的孩子数是 m 。
4. 若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。
5. 用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解
n
8.0-1 背包问题的回溯算法所需的计算时间为 __o(n*2)__,用动态规划算法所需
n
的计算时间为___o(min{nc,2 }_。 1. 写出设计动态规划算法的主要步骤。
①问题具有最优子结构性质；②构造最优值的递归关系表达式；3最优值的算法描述；④构造
最优解；
2. 流水作业调度问题的johnson算法的思想。
①令N1={i|ai
专业资料整理
相关推荐：
loading