算法复习题.doc

算法复习试题
一、 名词解释：
1、 算法：就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。
2、 贪心算法：能够得到某种量度意义下的最优解的分级处理方法称为贪心算法。
3、 分治法：分治法的求解思想就是把整个问题分成若干个小问题后分的治之
4、 递归过程：一个递归过程的执行类似于多个子程序的嵌套调用，递归过程是自己调用自己本身代码。
递归算法的特点：思路清晰，算法的描述简洁且易理解。
5、集合：在研究某一类对象时，可把这类对象的整体称为集合。
6、生成树：设G=(V,E)是一个无向连通图。如果G的生成子图T=(V,E')是一棵树，则称T是G的一棵生成树。
7、算法具有以下5个属性：
有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口
可行性：就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
8、迭代法：称辗转法，是一种不断用变量的旧值递推出新值的解决问题的方法。
9、贪婪法: 是一种不追求最优解，只希望得到较为满意解的方法。贪婪法不要回溯
10、动态规划：是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
11、 分支限界法：是一种用于求解组合优化问题的排除非解的搜索算法。
12、 树：树是一个或多个结点的有限集合。
12、 二元树：它是结点的有限集合，它或者为空，或者由一个根和两棵树
（左子树和右子树）的不相交的二元树所组成。
13、 二分检索树：T是一棵二元树，它或者为空，或者其每个结点含有一个可比 较大小的数据元素。
14、 图：图是数据结构，一个图G是由称之为结点V和边E的两个集合组成的
15、 最优解：使目标函数取极值（极大值或极小值）的可行解。
16、 回溯法：回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。

二、选择题
1、二分搜索算法是利用（   A      ）实现的算法。
A、分治策略   B、动态规划法   C、贪心法    D、回溯法
2、下列不是动态规划算法基本步骤的是（  A   ）。
A、找出最优解的性质  B、构造最优解  C、算出最优解  D、定义最优解
3、最大效益优先是（  A  ）的一搜索方式。
A、分支界限法      B、动态规划法    C、贪心法    D、回溯法
4、在下列算法中有时找不到问题解的是（  B ）。
A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法  D、数值概率算法
5. 回溯法解旅行售货员问题时的解空间树是（ A ）。
A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树
6．下列算法中通常以自底向上的方式求解最优解的是（   B   ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
7、衡量一个算法好坏的标准是（ C ）。
A 、运行速度快 B、占用空间少 C、时间复杂度低 D、代码短
8、以下不可以使用分治法求解的是（ D ）。
A、 棋盘覆盖问题 B、选择问题 C 、归并排序 D 、0/1背包问题
9. 实现循环赛日程表利用的算法是（  A   ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
10、下列随机算法中运行时有时候成功有时候失败的是（ C ）
A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法
11．下面不是分支界限法搜索方式的是（     D     ）。
A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先
12下列算法中通常以深度优先方式系统搜索问题解的是 （ D ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
13.备忘录方法是那种算法的变形。（ B ）
A、分治法 B、动态规划法 C、贪心法 D、回溯法
14．哈弗曼编码的贪心算法所需的计算时间为（   B     ）。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）

15．分支限界法解最大团问题时，活结点表的组织形式是（    B    ）。
A、最小堆 B、最大堆 C、栈 D、数组
16．最长公共子序列算法利用的算法是（    B       ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
17．实现棋盘覆盖算法利用的算法是（     A      ）。
A、分治法 B、动态规划法 C、贪心法 D、回溯法
18.下面是贪心算法的基本要素的是（   C     ）。
A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解
19.回溯法的效率不依赖于下列哪些因素（ D ）
A.满足显约束的值的个数 B. 计算约束函数的时间
C. 计算限界函数的时间 D. 确定解空间的时间
20. 动态规划算法的基本要素为（ C ）
A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质
C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用
21、下面关于NP问题说法正确的是（ B ）
A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中
C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中
22.下列哪一种算法不是随机化算法（    C     ）
A. 蒙特卡罗算法B. 拉斯维加斯算法C.动态规划算法D.舍伍德算法
23. （  D  ）是贪心算法与动态规划算法的共同点。
A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质
24. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。
A、最小堆 B、最大堆 C、栈 D、数组
25、Strassen矩阵乘法是利用（    A     ）实现的算法。
A、分治策略   B、动态规划法   C、贪心法    D、回溯法
26、使用分治法求解不需要满足的条件是（ A ）。
A 子问题必须是一样的 B 子问题不能够重复
C 子问题的解可以合并 D 原问题和子问题使用相同的方法解
27、下面问题（ B ）不能使用贪心法解决。
A 单源最短路径问题 B、 N皇后问题 C、 最小花费生成树问题D、 背包问题
28、下列算法中不能解决0/1背包问题的是（ A ）
A 贪心法 B 动态规划 C 回溯法 D 分支限界法
29、回溯法搜索状态空间树是按照（C ）的顺序。
A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历
30．实现合并排序利用的算法是（     A    ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
31．下列是动态规划算法基本要素的是（   D   ）。
A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质
32．采用广度优先策略搜索的算法是（     A      ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
33．实现大整数的乘法是利用的算法（      C   ）。
A、贪心法 B、动态规划法 C、分治策略 D、回溯法
34．0-1背包问题的回溯算法所需的计算时间为（  A   ）
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
35．贪心算法与动态规划算法的主要区别是（  B         ）。
A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解
36.下列哪一种算法是随机化算法（    D     ）
A. 贪心算法 B. 回溯法 C.动态规划算法 D.舍伍德算法
37. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。
A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解
38．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为 ( B ) 。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
39. 以深度优先方式系统搜索问题解的算法称为 ( D ) 。
A、分支界限算法      B、概率算法    C、贪心算法  D、回溯算法
40.应用Johnson法则的流水作业调度采用的算法是（D）
A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法
41. 算法分析中，记号O表示（ B ）， 记号表示（ A ）， 记号表示（ D ） 。
A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界

42. 能采用贪心算法求最优解的问题，一般具有的重要性质为：（ A ）
A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质
C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用
43.一个.java文件中可以有（ A ）个public类。
A．一个 B．两个 C．多个 D．零个
44.一个算法应该是（  C    ）
A．程序     B．问题求解步骤的描述     C．要满足五个基本特性     D．A和C
45. 用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（ B ）
A．唯一性 B．有穷性 C．有0个或多个输入 D．有输出
46．报名参加冬季越野赛跑的某班5位学生的学号是：5，8，11，33，45。利用折半查找，查找学号为33号学生的过程中，依次被访问到的学号是（ D ）
A．5，11，33 B．8，33 C．11，45，33 D．11，33
三、 算法设计题
1．对于任意非负整数n，计算阶乘函数F(n) = n！的值。因为当n ≥ 1时，n！= 1×2×3×……×（n-1）×n = (n-1)！×n。并且根据定义，0！= 1，所以可以使用下面的递归算法计算n！：F(n) = F(n-1) × n。
请编写Java应用程序，由键盘输入n的值，在屏幕上输出计算的n！的结果。
import java.io.*;
public class FN
{
static long f(int n)
{
long r = 1;
if(n != 0)
r = n * f(n-1);
return r;
}
public static void main(String args[]) throws IOException
{
byte[] buf = new byte[10];
System.out.println("请输入一个整数：");
System.in.read(buf);
String str=new String(buf);
int n=Integer.parseInt(str.trim());
long result = f(n);
System.out.println(n + "!=" + result);
}
}

2、 用贪心法求下图的最小生成树

3、马步问题：在n*n的方棋盘中，马只能走“日”字。马从初始位置（x0,y0）出发，
把棋盘的每一格都走一次，且只走一次（遍历）。求出n=5时马的行走路线。
4、 某市场营销人员从他所在城市(顶点1)出发，到其他5个城市去做市场调查，如下图19所示。请设计行走路线。

四、 填空题
1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。
2、程序是 算法     用某种程序设计语言的具体实现。
3、算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。
4.矩阵连乘问题的算法可由 动态规划 设计实现。
5、拉斯维加斯算法找到的解一定是 正确解。
6、算法是指解决问题的 一种方法 或 一个过程 。
7、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。
8、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。
9、以深度优先方式系统搜索问题解的算法称为 回溯法 。
10、数值概率算法常用于 数值问题 的求解。
11、利用概率的性质计算近似值的随机算法是__数值概率算法，运行时以一定的概率得到正确解的随机算法是__蒙特卡罗算法_____________________。
12、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划 ，需要排序的是 回溯法 ，分支限界法 。
13、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
114、矩阵连乘问题的算法可由 动态规划 设计实现。

15、拉斯维加斯算法找到的解一定是 正确解。
16.贪心算法的基本要素是 贪心选择 质和 最优子结构 性质 。
17. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题 的解得到原问题的解。
18、大整数乘积算法是用 分治法 来设计的。
19、以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。
20、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
21.快速排序算法是基于 分治策略 的一种排序算法。
22.分支限界法主要有 队列式 分支限界法和 优先队列式 分支限界法。
23.任何可用计算机求解的问题所需的时间都与其 规模 有关。
24.快速排序算法的性能取决于 划分的对称性 。
1． 算法的渐进时间复杂度分析，能够对给定的代码段（伪代码段）进行时间复杂度分析，能够对用关于问题规模n的函数表示的时间复杂度计算其渐进阶。
2． 概念
算法: 算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤
递归算法: 递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数来表示问题的解
可行解: 满足某线性规划所有的约束条件的任意一组决策变量的取值，都称为该线性规划的一个可行解
解空间: 如果ξ1,ξ2,...ξs是一般齐次线性方程组的s个解,则它们的任一线性组合c1ξ1+c2ξ2+...+csξs 也是该齐次线性方程组的解向量.由此可知若齐次线性方程组有非零解,则其解有无穷多个,而齐次线性方程组所有解的集合构成一个向量空间,这个向量空间就称为解空间. 解空间也就是一个集合
目标函数: 在求解前函数是未知的，按照你的思路将已知条件利用起来，去求解未知量的函数关系式，即为目标函数。
最优解: 使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解，都称为该线性规划的一个最优解。
最优化问题: 主要是指以下形式的问题： 给定一个函数，寻找一个元素使得对于所有A中的，（最小化）；或者（最大化）。
子问题: 就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题
分治法: 就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并
贪心法: 在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解
动态规划: 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法
备忘录算法: 备忘录方法是动态规划方法的变形。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上的。
回溯法: 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标
贪心选择性质: 是指所有问题的整体最优解可以通过一系列局部最优解的选择,即贪心选择来达到

最优子结构性质:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质
重叠子问题:在用递归算法自顶向下求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次.这些被反复计算的子问题就是重叠子问题.