A卷一、选择题
1二分搜索算法是利用（A）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法
2回溯法解旅行售货员问题时的解空间树是（A）。
A、子集树
B、排列树C、深度优先生成树D、广度优先生成树
3下列算法中通常以自底向上的方式求解最优解的是（B）。
A、备忘录法
B、动态规划法C、贪心法
D、回溯法
4．下面不是分支界限法搜索方式的是（D）。
A、广度优先
B、最小耗费优先C、最大效益优先
D、深度优先
5．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大
排序，故算法的时间复杂度为B
。
A、O（
2
）
B、O（
log
）C、O（2
）
D、O（
）
6．分支限界法解最大团问题时，活结点表的组织形式是（B）。
A、最小堆
B、最大堆
C、栈
D、数组
7、下面问题（B）不能使用贪心法解决。
A单源最短路径问题
BN皇后问题
C最小花费生成树问题
D背包问题
8下列算法中不能解决01背包问题的是（A）
A贪心法B动态规划C回溯法D分支限界法
9背包问题的贪心算法所需的计算时间为（B）
A、O（
2
）B、O（
log
）C、O（2
）
D、O（
）
10背包问题的贪心算法所需的计算时间为（B）。
A、O（
2
）
B、O（
log
）C、O（2
）
D、O（
）
二、填空题
1算法的复杂性有
复杂性和
复杂性之分。
2算法是由若干条指令组成的有穷序列，且要满足输入、
、确定
性和
四条性质。其中算法的“确定性”指的是组成算法的每条
是清晰的，无歧义的。
3解决01背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序
的是
，需要排序的是
，
。
4动态规划算法的两个基本要素是
性质和
性质。
f5回溯法是一种既带有
又带有
的搜索算法；分支
限界法是一种既带有
又带有
的搜索算法。
6用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任
何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根
结点到叶结点的最长路径的长度为h
，则回溯法所需的计算空间通常
为
。
7用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一
个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）
。
BoolColorOKi
tk
fori
tj1j
jifakj1xjxkretur
false
retur
true
8用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为

m的方格阵列，扩展每个结点需O1的时间，L为最短布线路径的长度，则
算法共耗时
，构造相应的最短距离需要
时间。
fori
ti0iNumOfr