《算法分析与设计》 年  月期末考试指导一、考试说明（一）考试说明满分为 100 分，考试时间为 90 分钟，考试形式为闭卷。（二）试卷包含的题型及各题型相应的答题技巧1. 单项选择题（每题 1 分，共 10 题，总计 10 分）答题技巧：在每道题可能的答案中选择出最正确的答案，注意答案只有一个。2. 多项选择题（每题 4 分，共 5 题，总计 20 分）答题技巧：在每道题可能的答案中选出全部正确的答案，注意答案不只有一个。3. 程序题（每题 20 分，共 2 题，总计 40 分）答题技巧：写出相应的算法语言。4. 程序应用题（每题 30 分，共 1 题，总计 30 分）答题技巧：写出完整的程序，包括定义部分，解决实际问题。二、重要知识点第一章：算法引论1.算法与程序算法是解一确定类问题的任意一种特殊的方法。在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词。算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。算法严格地讲，是满足下述性质的指令序列： 有零个或多个外部量作为算法的输入 产生至少一个输出量 组成算法的每条指令是清晰的、无歧义的 算法中每条指令的执行次数有限，执行每条指令的时间也有限。程序与算法不同，程序时算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性这一性质。2.算法复杂性分析算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需要的资源越多，该算法的复杂性越高；反之，所需要的资源越少，该算法的复杂性越低。计算机的资源，最重要的是时间和空间。因此，算法的复杂性有时间复杂性和空间复杂性之分。）分析算法的目的。目的在于通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。）重要的假设和约定。假设模型，约定时间和规则等。编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。）如何进行算法分析。对算法进行全面分析，可分两个阶段进行：事前分析和事后测试。并需要分析时间复杂性和空间复杂性。事前分析就算法本身，通过对其执行性能的理论分析，得出关于算法特性时间和空间的一个特征函数（、）与计算机物理软硬件没有直接关系。事后测试将算法编制成程序后实际放到计算机上运行，收集其执行时间和空间占用等统计资料，进行分析判断直接与物理实现有关。）计算时间的渐近表示。计算时间的数量级对算法有效性有决定性的影响）常用的整数求和公式。 private static int partition(int p, int r) { int p; j=r+1; Comparable x=a[p]; while (true) { while (a[++i].compareTo(x) < 0) ; while (a[--j].compareTo(x) >0); if (i>=j) break; Mymath.swap(a, I, j);}a[p]=a[j];a[j]=x;return j;}2. 该问题是一般情况下的背包问题，具有最优子结构性质。设所给背包问题的子问题max Σk =1ickxkΣk =1iakxk≤ j的最优值为 m(i, j)，即 m(i, j)是背包容量为 j，可选择物品为 1，2，…, i 时 背包问题的最优值。由背包问题的最优子结构性质，可以建立计算 m(i, j)的递归式如下：按此递归式计算出的 m(n,b)为最优值。算法所需的计算时间为 O(nb)。四、程序应用题1、分析与解答： 与最大团问题的解法十分相似。public class MaxClique { static int [] x; static int n; static int cn; static int bestn; static int [] bestn; static Boolean [][] a;public static int maxClique(int [] v) { x = new int[n+1];m(i, j )={m(i−1 , j ) 0≤ j<aimax {m(i−1 , j ),m(i, j−ai)+ci} ai≤ jm(0 , j)=m (i , 0)=0 ;m(i, j )=− ∞, j <0 cn=0; bestn=0; bestx=v; backtrack(1); return bestn;}private static void backtrack(int i){ // 计算最大团 if (i > n) { // 到达叶结点 for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestn = cn; return; } // 检查顶点 i 与当前团的连接 int OK = 1; for (int j = 1; j < i; j++) if (x[j] && a[i][j] == 0) { // i 与 j 不相连 OK = 0; break; } if (OK) { // 进入左子树 x[i] = 1; cn++; Backtrack(i+1); x[i] = 0; cn--; } if (cn + n - i >= bestn) { // 进入右子树 x[i] = 0; Backtrack(i+1); }}}2、贪心策略：最短服务时间优先double greedy(int[] a) { int n=a.length; sort(a); for (int i=1; i<n; i++) a[i] += a[i-1]; double t=0; for (i=0; i<n; i++) t+=a[i]; t/=n; return t;}说明：本考试指导只适用于  学期  月期末考试使用，包括正考和重修内容。指导中的章节知识点涵盖考试所有内容，给出的习题为考试类型题，习题答案要点只作为参考，详见课程讲义或笔记。如果在复习中有疑难问题请到课程答疑区提问。最后祝大家考试顺利！ 上界函数：定义 如果存在两个正常数  和 ，对于所有的 ，有 则记作 含义：如果算法用 值不变的同一类数据在某台机器上运行时，所用的时间总是小于的一个常数倍。则 是计算时间 的一个上界函数。 的数量级就是 。试图求出最小的 ，使得 。第二章：递归与分治策略1.递归的概念自己调用自己的函数称为递归函数直接递归：®间接递归：®® ®!®完整的递归定义必须满足如下条件：包含一个基本部分，对于  的一个或多个值， 必须是直接定义的（即非递归）。在递归部分中，右侧所出现的所有  的参数都必须有一个比  小。2.分治法的基本思想分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。分析从分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。3.分治法能解决的问题（）二分搜索技术（折半查找）（）大整数的乘法（）"# 矩阵乘法（）棋盘覆盖（）合并排序（）快速排序（$）线性时间选择（）最接近点对问题4.合并排序合并排序的基本思想是基于分治策略的。基本设计思想：将原始数组 % 中的元素分成两个子集合：%&ë'û和 %ë'û(&。分别对这两个子集合单独分类，然后将已分类的两个子序列归并成一个含有  个元素的分类好的序列。这样的一个分类过程称为归并分类合并排序5.快速排序快速排序的基本思想是基于分治策略的。对于输入的子序列 p[m..n]，如果规模足够小则直接进行排序，否则分三步处理：分解(Divide)：将输入的序列 p[m..n]划分成两个非空子序列 p[m..k]和 p[k+1..n]，使p[m..k]中任一元素的值不大于 p[k+1..n]中任一元素的值。递归求解(Conquer)：通过递归调用快速排序算法分别对 p[m..k]和 p[k+1..n]进行排序。合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在 p[m..k]和p[k+1..n]都排好序后不需要执行任何计算 p[m..n]就已排好序。 这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。快速排序：通过反复地对待排序集合进行划分达到排序目的的排序算法。在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。快速排序算法的性能取决于划分的对称性。通过修改算法 partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在 a[p:r]中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。第三章：动态规划1.动态规划算法的基本思想动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的，不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。2.掌握设计动态规划算法的步骤（１）找出最优解的性质，并刻划其结构特征。（２）递归地定义最优值。（３）以自底向上的方式计算出最优值。（４）根据计算最优值时得到的信息，构造最优解。3.动态规划算法的基本要素（1）最优子结构（2）重叠子问题（3）备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。动态规划算法与备忘录方法：相同： 用表格保存已解决子问题的答案，用数组 m[ ][ ]记录子问题的最优值，耗时 O(n3)。不同： 动态规划算法是自底向上递归，面向问题的所有子问题都至少要解一次。备忘录方法是自顶向下递归，面向问题的部分子问题可不必求解。4.动态规划可以解决的问题（1）矩阵连乘问题；（2）最长公共子序列；（3）凸多边形最优三角剖分；（4）多边形游戏； （5）图像压缩；（6）电路布线；（7）流水作业调度；（8）背包问题；（9）最优二叉搜索树。5.流水作业调度问题所有满足 Johnson 法则的调度均为最优调度。 第四章：贪心算法1.贪心算法的基本要素）贪心选择性质。 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，而每一次选择又依赖于以往做的选择。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 ）最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。) 背包问题与背包问题极为相似，都具有最优子结构性质，但背包问题可以用贪心算法求解，而 )背包问题却不能用贪心算法求解。2.贪心算法可以解决的问题（1）活动安排问题；（2）最优装载问题；（3）哈夫曼编码；（4）单源最短路径；（5）最小生成树；（6）多机调度问题。3.贪心算法解决单源最短路径问题*+,# 算法是解单源最短路径问题的贪心算法。其基本思想史，设置顶点集合 " 并不断地做贪心选择来扩充这个集合。一个顶点属于集合 " 当且仅当从源到该顶点的最短路径长度已知。初始时，" 中仅含有源。设  是  的某一个顶点，把从源到  且中间经过 "中顶点的路称为从源到  的特殊路径，并用数组 - 记录当前每个顶点所对应的最短特殊路径长度。*+,# 算法每次从 .)" 中取出具有最短特殊路长度的顶点 ，将  添加到 "中，同时对数组 - 进行必要的修改。一旦 " 包含了所有 . 中顶点，- 就记录了从源到所有其他顶点之间的最短路径长度。4.最小生成树问题最小生成树的贪心算法有 Kruskal 算法和 Prime 算法。第五章：回溯法1.回溯法应用情况：有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。回溯法的基本做法：回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法解题时遇到的典型解空间树为子集树和排列树。) 背包的解空间为子集树。旅行售货员问题的解空间为排列树。在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。常用的回溯策略有递归回溯和迭代回溯。常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。2.回溯法可以解决的问题（1）装载问题；（2）批处理作业调度；（3）符号三角形问题（4）n 后问题；（5）0-1 背包问题； （6）最大团问题；（7）图的 m 着色问题（8）旅行售货员问题（9）圆排列问题（10）电路板排列问题3.最大团问题给定无向图 G=(V,E),令 U 为无向图 G 的顶点的子集，当且仅当对于 U 中的任意点 u 和v，(u , v)是图 G 的一条边时，U 定义了一个完全子图（complete subgraph）。子图的尺寸为图中顶点的数量。当且仅当一个完全子图不被包含在 G 的一个更大的完全子图中时，它是图 G 的一个团。 G 的最大团是指 G 中所含顶点数最多的团。解空间：子集树可行性约束函数：顶点 i 到已选入的顶点集中每一个顶点都有边相连。 上界函数：有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。 第六章：分支限界法的基本思想1. 分支限界法的基本思想（）求解目标：分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （）搜索方式：分支限界法以广度优先或以最小耗费优先的方式搜索解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 选择下一个 /)结点有两类常用的方法：）队列式01分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个借点为当前扩展结点。 ）优先队列式分支限界法。按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。分支限界法的基本框架包括队列式与优先队列式。2.分支限界法的解空间包括子集树、排列树以及图。其中装载问题的解空间为子集树 。旅行售货员问题解空间为排列树。3.分支限界法可以解决的问题（1）单源最短路径问题（2）装载问题；（3）布线问题（4）0-1 背包问题； （5）最大团问题；（6）旅行售货员问题第七章：概率算法（随机化算法）1.在解决最接近点对问题时采用了鸽舍原理。在计算 π 值、计算定积分时采用了随机投点法。在解决 n 后问题时采用了拉斯维加斯算法。2.常用的概率算法降低算法的复杂性，随机性选择常比最优选择省时。4 种常用的概率算法：（1）数值概率算法常用于数值问题的求解。（2）蒙特卡罗算法得到的解未必是正确的。解的正确概率依赖于算法所用的时间。（3）拉斯维加斯算法找到的解一定是正确解，但它有一个显著特征是它所做的随机性决策有可能导致算法找不到所需的解，找到正确解的概率依赖于算法所用的时间。（4）舍伍德算法总能求得问题的正确解。消除最坏情形与特定实例之间的关联。三、重点习题一、单项选择题、递归算法（ ） %、直接调用自身 2、间接调用自身 3、直接或间接调用自身 *、不调用自身、分治法的基本思想是将一个规模为  的问题分解为 , 个规模较小的字问题，这些子问题（ ）%、相互独立 2、与原问题相同 3、相互依赖 *、相互独立且与原问题相同、备忘录方法的递归方式是（ ）%、自顶向下 2、自底向上 3、和动态规划算法相同 *、非递归的、回溯法的求解目标是找出解空间中满足约束条件的（ ）%、所有解 2、一些解 3、极大解 *、极小解、贪心算法和动态规划算法共有特点是（ ）%、最优子结构 2、重叠子问题 3、贪心选择 *、形函数、贪心算法能得到： （ ）%、全局最优解 2、) 背包问题的解 3、背包问题的解 *、无解$、能求解单源最短路径问题的算法是： （ ）%、分支限界法 2、动态规划 3、线形规划 *、蒙特卡罗算法、不属于单纯形算法基本步骤的是： （ ）%、选入基变量 2、选离基变量 3、作转轴变化 *、初始化4、单纯形法中的退化是迭代过程中，常数列的某个元素变为： （ ）%、2、无穷大 3、无穷小 *、随机数 、快速排序算法和线性时间选择算法的随机化版本是： （ ）%、舍伍德算法 2、蒙特卡罗算法 3、拉斯维加斯算法 *、数值随机化算法二、多项选择题  、快速排序的基本步骤包括： （ ）%、分解 2、递归求解 3、合并 *、最优子结构、算法复杂性体现在： （ ）%、时间复杂性 2、空间复杂性 3、指令复杂性 *、代码复杂性、单纯形算法包括以下步骤： （ ）%、选入基变量 2、选离基变量 3、做转轴变换 *、寻找目标函数、动态规划算法的基本要素是（ ）%、最优子结构性质 2、子问题重叠性质 3、分解成相同子问题 *、子问题规模变小 、分支限界法选择活结点扩展最常用的两种方式为（ ）%、012、5013、优先队列式 *、最近最少使用、下列算法可以采用分治法（ ）%、合并排序 2、二分搜索技术 3、快速排序 *、整数因子分解三、请写出下列试题的程序、请写出快速排序法的程序。、考虑下面的整数线性规划问题。max Σi=1ncixi试设计一个解此问题的动态规划算法，并分析该算法的计算复杂性。四、程序应用题、请写出下列子集和问题的程序# 问题描述：原始部落 678#- 中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何  个人都不是仇敌。6 算法设计：给定 678#- 部落中居民间的仇敌关系，计算组成部落卫队的最佳P(n )={∑i=1naixi≤bxi为非负整数， 1≤i≤n 方案。 数据输入：由文件 9:; 给出输入数据。第  行有  个正整数  和 <，表示678#- 部落中有  个居民，居民间有 < 个仇敌关系。居民编号为 ，，…，。接下来的 < 行中，每行有  个正整数  和 =，表示居民  和居民  是仇敌。- 结果输出：将计算的部落卫队的最佳组成方案输出到文件 9:;。文件的第 行是部落卫队的人数；第  行是卫队组成 ;，1≤i≤n。; 表示居民  不在卫队中，; 表示居民  不在卫队中。输入文件示例 输出文件示例09:;9:;$#: 、问题描述：设有  个顾客同时等待一项服务。顾客  需要的服务时间为 ，1≤i≤n。应如何安排  个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是  个顾客等待时间总和除以 。6: 编程任务：对于给定的  个顾客需要的服务时间，编程计算最优服务次序。: 数据输入： 由文件 9:; 给出输入数据。第  行是正整数 ，表示有  个顾客。接下来的 行中，有  个正整数，表示  个顾客需要的服务时间。-: 结果输出：将编程计算出的最小平均等待时间输出到文件 9:;:输入文件示例 输出文件示例09:;9:; :4444四、 重点练习题参考答案（答案仅供参考）一、单项选择题1、C2、D3、A4、A5、A 、3$、%、*4、%、%二、多项选择题1、ABC2、AB3、ABC 、%2、%3 6、ABC三、程序题1、 分析与解答：private static void qSort(int p, int r) { if (p<r) { int q=partition(p, r); qSort(p, q-1); qSort(q+1, r); }}