1、一个算法的优劣可以用（时间复杂度）与（空间复杂度）与来衡量。
2、回溯法在问题的解空间中，按（深度优先方式）从根结点出发搜索解空间树。 3、直接或间接地调用自身的算法称为（递归算法）。
4、? 记号在算法复杂性的表示法中表示（渐进确界或紧致界）。
5、在分治法中，使子问题规模大致相等的做法是出自一种（平衡(banlancing)子皇后问题）。可以解决背包问题
28、投点法是（概率算法）的一种。
29、若线性规划问题存在最优解，它一定不在（可行域内部）
30、n皇后问题可以用（ 回溯法）解决。 31、若L是一个NP完全问题，L经过多项式时间变换后得到问题l，则l是( P类问题 ).
32、算法与程序在性质上有所不同，下列性质中，程序可以不满足哪个性质：（ ）。案。对；
8）动态规划算法是用于解最优化问题，采用自顶向下的方式计算出最优解。错；
9）贪心算法和动态规划算法都要求问题必须具有最优子结构性质和贪心选择性质。错； 10）队列式分支限界法将活结点表组织成一个优先队列，并按队列的先进现出原则选取下一个结点称为当前扩展结点。错； 四、算法设计
说明：任意选择所使用的算法策略；要求：说问题）的思想。
6、动态规划算法适用于解（具有某种最优性质）问题。
7、贪心算法做出的选择只是（在某种意义上的局部）最优选择。
8、最优子结构性质的含义是（问题的最优解包含其子问题的最优解）。
9、回溯法按（深度优先）策略从根结点出发搜索解空间树。
10、拉斯维加斯算法找到的解一定是（正确解）。
11、按照符号O的定义O(f)+O(g)等于O(max{f(n),g(n)})。
12、二分搜索技术是运用（分治）策略的典型例子。
13、动态规划算法中，通常不同子问题的个数随问题规模呈（多项式）级增长。 14、（最优子结构性质）和（子问题重叠性质）是采用动态规划算法的两个基本要素。 15、（最优子结构性质）和（贪心选择性质）是贪心算法的基本要素。 16、（选择能产生最优解的贪心准则）是设计贪心算法的核心问题。
17、分支限界法常以（广度优先） 或（以最小耗费(最大效益)优先）的方式搜索问题的解空间树。
18、贪心选择性质是指所求问题的整体最优解可以通过一系列（局部最优）的选择，即贪心选择达到。
19、按照活结点表的组织方式的不同，分支限界法包括（队列式(FIFO)分支限界法）和（优先队列式分支限界法）两种形式。
20、如果对于同一实例，蒙特卡洛算法不会给出两个不同的正确解答，则称该蒙特卡洛算法是（一致的）。
21、哈夫曼编码可利用（贪心法）算法实现。
22概率算法有数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法 23以自顶向下的方式求解最优解的有（贪心算法）
24、下列算法中通常以自顶向下的方式求解最优解的是（C）。 A、分治法B、动态规划法C、贪心法D、回溯法
25、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是（回溯法）
26、旅行售货员问题不能用（）解决 可以用回溯法解决，分支限界法，NP完全性理论与近似算法 27、贪心算法不能解决（0-1背包问题 N有限性！算法的四个性质：输入；输出；确定性；有限性； 33、回溯法在解空间树T上的搜索方式：（分支限界法）
34、动态规划算法的基本步骤不包括下列哪一步：（）包括：划分阶段：选择状态 确定决策并写出状态转移方程 写出规划方程（包括边界条件）：
35、在调试程序过程中，下列哪一种错误是计算机检查不出来的：（逻辑错误） 36、分治算法不包括以下哪项内容：（）包括：二分搜索技术；大整数乘法；Strassen矩阵乘法；棋盘覆盖；合并排序和快速排序；线性时间选择；最接近点对问题；循环赛日程表
37、贪心算法不能解决（0-1背包问题 N皇后问题）。
38、舍伍德算法是（数值概率算法）的一种。
39、若线性规划问题存在最优解，它一定不在（可行域内部）
40、回溯法可以解决的问题包括（N皇后问题；装载问题；批处理作业调度；符号三角形问题；n后问题；0-1背包问题；最大团问题；图的m着色问题；旅行售货员问题；圆排列问题；电路板排列问题；连续邮资问题）
判断题（每小题3分,共15分）
1）分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，两者的求解目标是相同的。对；
2）优先队列式的分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点称为当前扩展结点。对；
3）回溯法求解问题的所有解时，要回溯到根，且根结点的所有子树都被搜索遍才结束。错，搜索到一个解就可结束；
4）动态规划法用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。对；
5）一个直接或间接地调用自身的算法称为递归算法，而一个使用函数自身给出定义的函数称为递归函数。定义递归函数时可以没有初始值。错，应该有初始值；
6）一个直接或间接地调用自身的算法称为递归算法，而一个使用函数自身给出定义的函数称为递归函数。定义递归函数时可以没有初始值。错，应该有初始值；
7）动态规划法用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。在需要时从表中找出以求得的答明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间复杂性。
0-1背包问题 第三章，第五章，第六章 单源最短路径问题 第四章，第六章
0-1背包问题： 算法策略：动态规划算法。动态规划算法基本思想是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。 步骤：1找出最优解的性质，并刻划其结构特征。2递归地定义最优值。3以自底向上的方式计算出最优值。4根据计算最优值时得到的信息，构造最优解。
时间复杂度：改进后算法的计算时间复杂性为O(2^n)。当所给物品的重量wi(1≤i≤n)是整数时，|p[i]|≤c+1，(1≤i≤n)。在这种情况下，改进后算法的计算时间复杂性为O(min{nc,2^n}) 单源最短路径问题： 算法策略：贪心算法。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
步骤：Dijkstra算法是解单源最短路径问题的贪心算法。其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。 时间复杂度：对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-1次，所以完成循环需要O(n^2)时间。算法的其余部分所需要时间不超过O(n^2)。