算法复习题.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、回溯法340-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要满足五个基本特性 DA和C45. 用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（ B ） A唯一性 B有穷性 C有0个或多个输入 D有输出46报名参加冬季越野赛跑的某班5位学生的学号是：5，8，11，33，45。利用折半查找，查找学号为33号学生的过程中，依次被访问到的学号是（ D ）A5，11，33 B8，33 C11，45，33 D11，33三、 算法设计题1对于任意非负整数n，计算阶乘函数F(n) = n！的值。因为当n 1时，n！= 123（n-1）n = (n-1)！n。并且根据定义，0！= 1，所以可以使用下面的递归算法计算n！：F(n) = F(n-1) n。请编写Java应用程序，由键盘输入n的值，在屏幕上输出计算的n！的结果。import java.io.*;public class FNstatic long f(int n)long r = 1;if(n != 0)r = n * f(n-1);return r;public static void main(String args) throws IOExceptionbyte buf = new byte10;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个解,则它们的任一线性组合c11+c22+.+css 也是该齐次线性方程组的解向量.由此可知若齐次线性方程组有非零解,则其解有无穷多个,而齐次线性方程组所有解的集合构成一个向量空间,这个向量空间就称为解空间. 解空间也就是一个集合目标函数: 在求解前函数是未知的，按照你的思路将已知条件利用起来，去求解未知量的函数关系式，即为目标函数。最优解: 使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解，都称为该线性规划的一个最优解。最优化问题: 主要是指以下形式的问题： 给定一个函数，寻找一个元素使得对于所有A中的，（最小化）；或者（最大化）。子问题: 就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题分治法: 就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并贪心法: 在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解动态规划: 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法备忘录算法: 备忘录方法是动态规划方法的变形。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上的。回溯法: 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标贪心选择性质: 是指所有问题的整体最优解可以通过一系列局部最优解的选择,即贪心选择来达到最优子结构性质:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质重叠子问题:在用递归算法自顶向下求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次.这些被反复计算的子问题就是重叠子问题.