一、选择题
1.二分搜索算法是利用( A )实现的算法。
A、分治策略 B、动态规划法 C、贪心法D、回溯法
- 回溯法解旅行售货员问题时的解空间树是( B )。
- 子集树 B 排列树 C、深度优先生成树 D、广度优先生成树
3.下列算法中通常以自底向上的方式求解最优解的是( B )。
A、备忘录法 B 动态规划法 C、贪心法（自上向下） D、回溯法
4.下面不是分支界限法搜索方式的是( D ).
A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先
5.采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大
排序，故算法的时间复杂度为( B )
- O(n2n) B、O(nlogn) C、O(2n) D、O(n)
6分支限界法解最大团问题时，活结点表的组织形式是( B )。
- 最小堆 B、最大堆 C、栈 D、数组
7、下面问题( B )不能使用贪心法解决。
A单源最短路径问题 B N皇后问题
C最小花费生成树问题 D背包问题
8下列算法中不能解决0/1背包问题的是( A )
A贪心法 B动态规划 C回溯法 D分支限界法
9 .背包问题的贪心算法所需的计算时间为( B )。
A、O(n2n) B O(nlogn) C O(2n) D O(n)
二、填空题
1.算法的复杂性有( 时间 )复杂性和( 空间 )复杂性之分。
2.算法是由若干条指令组成的有穷序列，且要满足输入,( 输出 ),确定性和(有限性 ) 四条性质。其中算法的“确定性”指的是组成算法的每条__指令____ 是清晰的，无歧义的。
3.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是
（ 动态规划 ），需要排序的是 （ 回溯法 ），（ 分支限界法 ）。
解析：
动态规划
回溯法：
分支限界法：
- 动态规划算法的两个基本要素是（ 最优子结构 ）性质和（ 重叠子问题 ）性质。
解析：
- 回溯法是一种既带有（ 系统性 ） 又带有（ 跳跃性 ） 的搜索算法
- 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根 结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为（ (O(h(n))) ）。
-
7.用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一
个儿子所相应的颜色的可用性，则需耗时(渐进时间上限)（ o(mn) ）
Bool Color::ok(int k)
{
for(int j=1;j<=n;j++)
if((a[k][j]==1)&&(x[j]==x[k]))return false;
return true;
}
8.用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为
nm的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则
算法共耗时（ o(mn) ），构造相应的最短距离需要（ O(L) ）时间。
for(int i=0;i<NumOfNbrs;i++)
{
nbr.row=here.row+offset[i].row;
nbr.col=here.col+offset[i].col
if(grid[nbr.row][nbr.col]==0)
{
//该方格未标记
grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;
if((nbr.row==finishrow)&&
(nbrcol==finish.col))
Break;//完成布线
QAdd(nbr);)
}
- 快速排序算法是基于（ 分治策略 ） 的一种排序算法。
-
10（ 贪心选择性质 ）是贪心算法可行的第一个基本要素，也是贪心算法与动态规划
算法的主要区别
