1、算法分析与设计习题集整理第一章算法引论一、填空题：1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。2、多项式的上界为O(nm)。3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。5、计算下面算法的时间复杂度记为： O(n3) 。for(i=1;i=n;i+)for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij= cij+aik*bkj; 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD图。7、算法设计的基本要求：正确性 和 可读
2、性。8、计算下面算法的时间复杂度记为： O(n2) 。 for（i1；in; i+） y=y+1; for（j0；j =2n；j+ ） x； 9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法分析、算法实现、程序调试、结果整理文档编制。10、算法是指解决问题的 方法或过程 。11、算法由操作、控制结构、数据结构三要素组成。二、简答题：1、按照时间复杂度从低到高排列：O( 4n2)、O( logn)、O( 3n)、O( 20n)、O( 2)、O( n2/3), O( n!)应该排在哪一位答：O( 2)，O( logn)，O( n2/3)，O( 20n)，O( 4n2
3、)，O( 3n)，O( n!)2、什么是算法算法的特征有哪些答：1）算法：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法：就是解决问题的方法或过程。2）特征：1)算法有零个或多个输入；)算法有一个或多个输出； 3)确定性 ； )有穷性3、给出算法的定义何谓算法的复杂性计算下例在最坏情况下的时间复杂性for(j=1;j=n;j+) (1)for(i=1;i=n;i+) (2) cij=0; (3) for(k=1;k=n;k+) (4) cij= cij+aik*bkj; (5)答：1）定义：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。 2）算法
4、的复杂性：指的是算法在运行过程中所需要的资源（时间、空间）多少。 所需资源越多，表明算法的复杂性越高 3）该算法的主要元操作是语句5，其执行次数是n3次。故该算法的时间复杂度记为O(n3). 4、算法A和算法B解同一问题，设算法A的时间复杂性满足递归方程，算法B的时间复杂性满足递归方程，若要使得算法A时间复杂性的阶高于算法B时间复杂性的阶，a的最大整数值可取多少答：分别记算法A和算法B的时间复杂性为和，解相应的递归方程得： 依题意，要求最大的整数a使得。显然，当a4时， a2写出其相应的递归算法Int F(int n) if(n=1) return 1; else if(n=2) return
5、 2; else return F(n-1)+ F(n-2);2、设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。写出该问题的解题步骤 并写出其相应的递归算法 解：第一步：将n1个盘子看成一个整体，从A移到C； 第二步：将第n个盘子移到B; 第三步：将n1个盘子看
6、成一个整体，从C移到B；写出其相应的递归算法：void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 第二章 分治算法（2）分治算法一、填空题：1、在快速排序、插入排序和合并排序算法中， 插入排序 算法不是分治算法。2、合并排序算法使用的是 分治 算法设计的思想。3、二分搜索算法是利用 分治 算法思想设计的。二、简答题：1、适合用分治算法求解的问题具有的基本特征答：1)该问题的规模缩小到一定的程度就可以容易解决;2)该问题可以分解为若干个规模较小的相
7、同问题，即该问题具有最优子结构性质； 3）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 4）利用该问题分解出子问题解可以合并为该问题解;2、分治算法基本思想，解题步骤 三、算法设计题：1、改写二分查找算法：设a1n是一个已经排好序的数组，改写二分查找算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i，和大于x的最小元素位置j；当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。并分析其时间复杂度 解：int binsearch( int an, int x ,) 3）回溯时将分解的两组解大者取大，小者取小，合并为当前问题的解。 、 第三章动态规划算
8、法一、填空题：1、动态规划算法中存储子问题的解是为了 避免重复求解子问题 。2、（ 最优子结构 ）是问题能用动态规划算法求解的前提。3、矩阵连乘问题的算法可由（动态规划 ）算法设计实现。二、判断题：1、动态规划算法基本要素的是最优子结构。 （ ）2、最优子结构性质是指原问题的最优解包含其子问题的最优解。 （ ）3、动态规划算法求解问题时，分解出来的子问题相互独立。 （ X）三、简答题：1、动态规划算法解题步骤答：找出最优解的性质，并刻划其结构特征;（即原问题的最优解，包含了子问题的最优解）递归地定义最优值;（即子问题具有重叠性，由子问题定义原问题）以自底向上的方式计算出最优值;根据计算最优值时
9、得到的信息，构造最优解;2、动态规划算法基本思想答：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题；但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次；如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。3、动态规划与分治算法异同点4、动态规划算法的基本要素 四、算法设计与计算题：1、和的最长公共子序列为。问：若用记录序列和公共子序列长度。求：用动态规划法求解时,计算最优值的递归公式 设计计算最优值的算法以及构造最优解的算法2、长江游艇俱
10、乐部在长江上设置了n个游艇出租站1,2n.游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i，j)，其中1=ij=n；求：用动态规划法求解时,计算最优值（最少租金）的递归公式设计计算最优值（最少租金）的算法并分析其时间复杂度解：计算最优值算法public static void matrixChain(int p, int m, int s) int n=; for (int i = 1; i = n; i+) mii = 0; 要求：给出Dijkstra算法的迭代过程，计算源到给个顶点的最短路径（用表表示）解：见课本123页表4
11、-2解：迭代过程：第章 回溯算法一、填空题1、回溯法与分支限界法搜索方式不同，回溯法按 深度优先 搜索解空间，分支限界法按 广度优先或最小耗费优先 搜索解空间。二、判断题1、回溯法中限界函数的目的是剪去得不到最优解的子树。 （ ）2、分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，两者的搜索方式是相同的。 （ X ）三、简答题1、简述回溯法和分支限界法的相同点和不同点2、什么是子集树 什么是排列树什么叫满m叉树3、回溯算法的基本思想回溯算法的解题步骤四、算法设计题1、n皇后问题在44格的棋盘上放置彼此不受攻击的4个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一
12、列或同一斜线上的棋子。用回溯算法解决4皇后问题： 构造求解该问题的解空间树 设计该4皇后问题的回溯算法 解：解空间树 回溯算法2、01背包问题：假设有3个物品，它们的重量和价值如下表所示。若这些物品均不可以被分割，且背包容量M10，问应该如何装入使背包中物品的总价值最大物品ABC重量655价值422530用回溯算法求解该01背包问题： 构造求解该问题的解空间树 设计该01背包问题的回溯算法 解：1）解空间树; 2)3、图的着色问题：如下图给定无向连通图G和m种不同的颜色；用这m种颜色为图G的各个顶点着色，是否有一种方法使得图G中每一条边的两个顶点着不同颜色；求：构造求解该问题的解空间树 设计该
13、图的着色问题回溯算法 12345解：1）解空间树： 2）算法:double mcoloring(int mm)int m=mm; ntValue();ntValue(); 回溯法解TSP问题时的解空间树是（ 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背
14、包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 11下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解 14广度
15、优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15背包问题的贪心算法所需的计算时间为（ B ）。 A、O（n2） nB、O（nlogn） C、O（2） nD、O（n） 16实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 17实现棋盘覆盖算法利用的算法是（ A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 18.下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 19.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 C.
16、 计算限界函数的时间 B. 计算约束函数的时间 D. 确定解空间的时间 20.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 21、以深度优先方式系统搜索问题解的算法称为 ( D ) 。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 22、贪心算法与动态规划算法的主要区别是（ B ）。 A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解 23. 采用最大效益优先搜索方式的算法是（ A ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 24. （ D ）是贪心算法与动态规划算法的共同点。 A
17、、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 25. 矩阵连乘问题的算法可由（ B）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 26. 0-1背包问题的回溯算法所需的计算时间为（ A ） A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 27、背包问题的贪心算法所需的计算时间为（ B ） A、O（n2） B、O（nlogn） C、O（2） D、O（n） 29、使用分治法求解不需要满足的条件是（A ）。 A 子问题必须是一样的 B 子问题不能够重复C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 30、下面问题（
18、B ）不能使用贪心法解决。 nnA 单源最短路径问题 B N皇后问题 C 最小花费生成树问题 D 背包问题 31、下列算法中不能解决0/1背包问题的是（A ） A 贪心法 B 动态规划 C 回溯法 D 分支限界法 32、回溯法搜索状态空间树是按照（C ）的顺序。 A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历 33、采用广度优先策略搜索的算法是（ A ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 34实现合并排序利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 35下列是动态规划算法基本要素的是（ D ）。 A、定义最优解 B、
19、构造最优解 C、算出最优解 D、子问题重叠性质 36下列算法中通常以自底向下的方式求解最优解的是（ B ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 二、 填空题 1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。 2、程序是 算法 用某种程序设计语言的具体实现。 3、算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。 4.矩阵连乘问题的算法可由 动态规划 设计实现。 5、算法是指解决问题的 一种方法 或 一个过程 。 6、快速排序算法的性能取决于 划分的对称性 。 7、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。 8、问题的 最优子结构性
20、质 是该问题可用动态规划算法或贪心算法求解的关键特征。 9、以深度优先方式系统搜索问题解的算法称为 回溯法 。 10、任何可用计算机求解的问题所需的时间都与其 规模 有关。 11、计算一个算法时间复杂度通常可以计算 循环次数 、 基本操作的频率 或计算步。 12、回溯法搜索解空间树时，常用的两种剪枝函数为 约束函数 和 限界函数 14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划 ，需要排序的是 回溯法 ，分支限界法 。 15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同
21、时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ，只使用约束条件进行裁剪的是 N皇后问题 。 17、回溯法是一种既带有 系统性 又带有 跳跃性 的搜索算法。 18. 动态规划算法的两个基本要素是. 最优子结构性质和 重叠子问题 性质 19.贪心算法的基本要素是 贪心选择 质和 最优子结构 性质 。 21. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题 的解得到原问题的解。 算法是由若干条指令组成的有穷序列，且要满足输入，输出 、确定性和 有限性 四条性质。 23、快速排序算法是基于 分治策略 的一种排序算法。 24、以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 三、算法设计题 1.背包问题的贪心算法， 分支限界算法 2.最大子段和: 动态规划算法 3.贪心算法求活动安排问题 5.快速排序 6. 多机调度问题-贪心算法 四、简答题 1分治法的基本思想 2. 分治法与动态规划法的相同点 3. 分治法与动态规划法的不同点 4. 分支限界法与回溯法的相同点 5分治法所能解决的问题一般具有的几个特征是： 6. 用分支限界法设计算法的步骤 7. 回溯法中常见的两类典型的解空间树是子集 8. 请简述符号t(n)(g(n), t(n)(g(n),t(n)(g(n)的含义。 9. 分支限界法的搜索策略是：
