算法分析与设计习题集整理
第一章算法引论
一、填空题：
1、算法运行所需要的计算机资源的量，称为算法复杂性，主耍包括时间复杂度和空间复杂度。
2、多项式A{n) = a m n m+…+ a/ + q的上界为O(rT)。
3、算法的基本特征：输入、输出、确定性、有限性。
4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。
5、计算下面算法的时间复杂度记为：0(n3) 0
for(i=l;i<=n;i++)
for(j=l;j<=n;j++)
{c[i][j]二 0;
for (k二1;k〈=n;k++)
c[i][j]= c[i][j]+a[i][k]*b[k][j];
}
6、描述算法常川的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD图。
7、算法设计的基本要求：正确性和H J读性。
8、计算下面算法的时间复杂度记为：0(/)。
for (i = l； i { y=y+l; for (j=0； j <=2n； j++ ) x + + ； } 9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法分析、算法实现、程序调试、结果整理文档编制。 10、算法是指解决问题的方法或过程。 11、算法由操作、控制结构、数据结构三要素组成。 二、简答题： 1、按照时间复杂度从低到高排列：0(4i?)、0(logn)、0(3")、0(20n)、0(2)、0( n2/3), 0( n!)应该排在哪一位？ 答：0( 2), 0( logn), 0( n2/3), 0( 20n), 0( 4n2), 0( 3n), 0( n!) 2、什么是算法？算法的特征有哪些？ 答:1) 法：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。 通俗讲，算法：就是解决问题的方法或过程。 2)特征：1)算法有零个或多个输入；2)算法有一个或多个输岀；3)确定性；4)有穷性 3、给出算法的定义？何谓算法的复杂性？ 计算下例在最坏情况下的时间复杂性？ for(j=l;j<=n;j++) (1) for(i=l;i<=n;i++) (2) (c[i][j]=O; ⑶ for(k=l;k<=n;k++) (4) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } (5) 答：1)定义：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。 2) 算法的复杂性：指的是算法在运行过程中所需要的资源(时间、空间)多少。所需 资源越多，表明算法的复杂性越高 3) 该算法的主要元操作是语句5,其执行次数是r?次。 故该算法的时间复杂度记 为0 (n 8 )? 4、算法A 和算法B 解同一问题，设算法A 的时间复杂性满足递归方程 ，若要使得算法A 时间复杂性的阶高于算法B 时间复杂性的阶, T(n) = aT(n/4) + n , n > 1 a 的最大整数值可取多少？ 答：分别记算法A 和算法B 的时间复杂性为丁八(n)和T B (n),解相应的递归方程得： T A (n) = O(n 2) 0(n) ,a < 4 T B (n) = < 0(nlogn) ,a = 4 O(n ,og4a ) ,a>4 依题意，要求最人的整数a 使得T B (n) =16o 所以，所求的a 的最人整数值为15。 5、 算法分析的目的？ 答：1)为了对算法的某些特定输入，估算该算法所協的内存空间和运行时间； 2)是为了建立衡最算法优劣的标准，用以比较同一类问题的不同算法。 6、 算法设计常用的技术？(写5种) 答：①分治法；②回溯法； ③贪心法；④动态规划法 ⑤分治限界法；⑥蛮力法；⑦倒推法 三、算法设计题 1、 蛮力法：百鸡百钱问题？ 2、 倒推法：穿越沙漠问题？ 第二章分治算法(1) 一一递归循环 一、 填空题： 1、 总接或间接地调用自身的算法称为 递归算法，用函数自身给出定义的函数称为 递归 函数。 2、 递归方程利约束函数(递归终止条件)是递归函数的两个要素。 二、 判断题： 1、所有的递归函数都能找到对应的非递归定义。 (V ) T(n) = 1 , n = 1 ' T(n) = 4T(n/2) + n , n>l 算法B 的时间复杂性满足递归方程 2、定义递归函数时可以没冇初始值。(X ) 三、简答题： 1、什么是递归算法？递归算法的特点？ 答：1)递归算法:是一个模块(函数、过程)除了可调用其它模块(函数、过程)夕卜，述可以宜接或间接地调用自身的算法。 2)递归算法特点： ①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；(递归终止条件) ②递归中用较小自变量函数值來表达较大自变量函数值；(递归方程式) 2、比较循环与递归的异同？ 答：相同：递归与循环都是解决“重复操作”的机制。 不同：①就效率而言，递归算法的实现往往要比迭代算法耗费更多的时间(调用和返回均需耍额外的吋间)与存贮空间(用来保存不同次调用情况下变量的当前值的栈栈空间)，也限制了递归的深度。②每个迭代算法原则上总可以转换成与它等价的递归算法；反Z不然。③递归的层次是可以控制的，而循坏嵌套的层次只能是固定的，因此递归是比循环更灵活的重复操作的机制。 3、递归算法解题通常有三个步骤？ 答：1)分析问题、寻找递归：找出人规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。 2)设置边界、控制递归：找出停止条件，即算法对解的最小规模问题。 3)设计函数、确定参数：和其它算法模块一样设计函数体屮的操作及相关参数。 四、算法设计题： 1、楼梯上有n个台阶，上楼时可以上1步，也可以上2步，设计一递归算法求出共有多少种上楼方法F(n)o ①写出F(n)的递归表达式？ ②并写岀其相应的递归算法？ 解：①写出F(n)的递归表达式 分析：到n阶有两种走法： 1)n-l阶到n阶； 2)n-2阶到n阶； 1 n=l F(n) = y 2 n=2 J(n-l) + F(n-2) n〉2 ②写出其相应的递归算法？ Int F(int n) { if(n=l) return 1; else if(n=2) return 2; else return F(nT)+ F(n-2); } 2、设a, b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1, 2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1:每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。 ①写出该问题的解题步骤？ ②并写出其相应的递归算法？ 解：①第一步：将n—1个盘子看成一个整体，从A移到C； 第二步：将第n个盘子移到B; 笫三步：将n—1个盘子看成一个整体，从C移到B； ②写出其相应的递归算法： void hanoi (int n, int a, int b, int c) {if (n > 0) { hanoi(nT, a, c, b); move (a, b); hanoi (n-1, c, b, a); } } 第二章分治算法(2)分治算法 一、填空题： 1、在快速排序、插入排序和合并排序算法中，插入排序算法不是分治算法。 2、合并排序算法使用的是分治算法设计的思想。 3、二分捜索算法是利用分治算法思想设计的。 二、简答题： 1、适合用分治算法求解的问题具有的基本特征？ 答：1)该问题的规模缩小到一定的程度就可以容易解决； 2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优了结构性质； 3)该问题所分解出的各个子问题是相互独立的，即子问题Z间不包含公共的子问题。 4)利用该问题分解出子问题解可以合并为该问题解； 2、分治算法基本思想，解题步骤？ 三、算法设计题： 1、改写二分查找算法： 设a[l-n]是一个已经排好序的数组，改写二分查找算法，使得当捜索元索x不在数组中时，返回小于x的最大元素位置i,和大于x的最小元素位置j；当搜索元素x在数组屮时，i和j 和同，均为x在数组中的位置。 并分析具时间复杂度？ 解：int binsearch( int a[n], int x ,) //x 待查数据 {int mid, i , j; low二1; int high二n; wh i 1 e (low<=hi gh) {mid=(low+high)/2; if(a[mid]=x) return i二j=mid; if (a[mid]>x) high 二 midT; //继续在左边查找 else // (a[mid] low二mid+1; //继续在右边查找 i=right; j=left; return 0； //low大于high查找区间为空，查找失败 } 计算时间复杂性为0（logn） 2、棋盘覆盖在一个2k X2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方 格为一特殊方格，「1.称该棋盘为一特殊棋盘。在棋盘覆盖问题中，耍用图示的4种不同形态的 L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 求：①简述分治算法的基本思想？ ②设计该棋盘覆盖问题的分治算法？ ③计算所设计算法的时间复杂度？（要求写出递推公式） 解：①分解： 将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，以便各个击破，分而治之。 对这k个子问题分别求解： 如果子问题的规模仍然不够小,则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止 求小问题解、合并： 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原來问题的解。 ②、③ 3、金块问题（求最大最小元问题） 老板有一袋金块（共n块），最优秀的雇员得到具屮最重的—?块，最差的雇员得到其中最轻的一块。假设有一台比较重聚的仪器，我们希望用最少的比较次数找岀最重的金块。 求：①简述分治算法的基木思想？ ②设计该金块问题的分治算法？ ③计算所设计算法的时间复杂度？（要求写出递推公式） 答：①简述分治算法的基本思想： 问题可以简化为：在含n （n是2的幕5＞二2））个元素的集合中寻找极人元和极小元。 用分治法（二分法）可以用较少比较次数地解决上述问题： 1）将数据等分为两组（两组数据可能差1）,目的是分别选取其中的最大（小）值。 2）递归分解直到每组元素的个数W2,可简单地找到最大（小）值. 3）回溯时将分解的两组解人者取大，小者取小，合并为当前问题的解。 ②、③ 第三章动态规划算法 一、填空题： 1、动态规划寛法中存储子问题的解是为了避免重复求解子问题° 2、（最优子结构）是问题能用动态规划算法求解的前提。 3、矩阵连乘问题的算法可由（动态规划）算法设计实现。 二、判断题： 1、动态规划算法基本要素的是最优子结构。（V ） 2、最优子结构性质是指原问题的最优解包含其子问题的最优解。（V ） 3、动态规划算法求解问题时，分解出来的了问题相互独立。（X） 三、简答题： 1、动态规划算法解题步骤？ 答：①找出最优解的性质，并刻划其结构特征； （即原问题的最优解，包含了子问题的最优解） ②递归地定义最优值； （即子问题具冇匝叠性，由子问题定义原问题） ③以口底向上的方式计算出最优值； ④根据计算最优值时得到的信息，构造授优解； 2、动态规划算法基本思想？ 答：动态规划算法与分治法类似，其基木思想也是将待求解问题分解成若干个子问题；但是经分解得到的了问题往往不是互相独立的。不同了问题的数冃常常只冇多项式屋级。 在用分治法求解时，有些子问题被重复计算了许多次； 如果能够保存已解决的子问题的答案，而在需要时再找岀已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。 3、动态规划与分治算法异同点？ 4、动态规划算法的基本要素？ 四、算法设计与计算题： 1、X =｛X,,X2,L，兀”｝和Y = ｛y[9y29L，片｝的最长公共子序列为 Z = ｛z p z2,L ,zj。问：若用c[i][j]记录序列X产匕,七丄，兀?｝和与=｛儿力丄，兀｝公共了序列长度。求： ①用动态规划法求解吋，计算最优值的递归公式？ ②设计计算最优值的算法？以及构造最优解的算法？ 2、长江游艇俱乐部在长江上设置了 n个游艇出租站1, 2???n.游客可在这些游艇岀租站租用游艇，并在下游的任何一个游艇出租站归还游艇。 游艇出租站i到游艇出租站j之间的租金为r（i, j），其屮l<=i 求：①用动态规划法求解时，计算最优值（最少租金）的递归公式？ ②设计计算最优值（最少租金）的算法？ ③并分析其时间复杂度？ 解：① 0 i = j j] - .i5k ②计算最优值算法 publ ic static void matrixChain(int [] p, int [] [] m, int [] [] s) int n二p. lenglh-1; for (int i = 1; i <= n; i++) m[i] [i] = 0; //I 个站 for (int r = 2; r++) for (int i = 1; i n - r+1; i++) { int j=i+r-l; m[ i][ j] = m[i][i] + m[i+l][ j]; s[ i][ j]二i; //断点位置在i处 for (int k = i+1; k < j; k++) {int t = m[ i][ k] + m[k+l] [ j]; if (t < m[i] [j]) { m[ i][ j] = t; s[ i][ j] = k;} } } } 构造最优解算法 public void traceback( int s[][], int 1,int j) { if(i=j) return; traceback( s, i, s[ i][ j]); traceback( s, s[ i] [ j]+l, j ); System, out. println( “A” + i + “，" + s[ i] [ j] + “A” + s[ i] [ j]+l + “, ” + J ) } //(m[ i, s[ i][ j] ] ) (in[ s[ i] [ j]+l, j ]) ③时间复杂度：0(n3) 第4章贪心算法 一、填空题： 1、某单位给每个职工发工资(精确到元)。为了保证不耍临时兑换零钱，且取款的张数最少, 统计所需各种币值(100, 50, 20, 10,5,2, 1元共七种)的张数。 贪心算法如F： void greedy_zhaoling ( float GZ, int B[ ], int S[ ] ) //GZ 应发工资 { for( j=l, j<=7;j++) //贪心选择，依次给最大币种{ A二GZ/B[ j] ; //A表示对应j币种张数 S[ j]= S[ j ]+A ; //S[ j]存放对应j币种总张数 GZ= GZ-A*B[ j] ; } for (i=l;i<=7;i++) print( B[ i], “——”，S[ i] ) ; //输出币种和对应张数} 2、贪心算法的两个基本要素是(贪心选择性)和(最优子结构)。 3、给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为M,应如何选择装入背包的物品，使得装入背包屮物品的总价值最人。 贪心算法如下： float greedy knapsack ( float M, float w[ ], float p[ ], float x[] ) // x[]背包问题最优解， w[]物品重量，P[]物品价值 { int n二w?length; float pp=0; float mm=M; //pp计算当前总价值，nrni背包剩余载重 for( int i=l;i<=n; i++ ) { float ww[ i]二p[ i] /讥i] ；//计算物品单位价值ww[] x[ i]=0; } //初始化 Mergesort ( w[ ], n ); //按单位价值将物品排序，便于贪心选择 for( int i二1; i<=n; i++ ) //贪心选择，总是选择价值最大放入背包{ if ( w[ i]<=mm ) 〃当前物品小于背包剩余载重 { x[ i]=l; mm二_____ ; pp二 pp + p[ i] ； } else { x[ i]二mm/讥 i]; pp + x[ i]*p[ i] ; break; } //i 部分放入背包 } return pp; } 二、判断题： 1、满足贪心选择性质必满足最优了结构性质。(X ) 三、简答题： 1、贪心算法的基本思想？ 2、贪心算法的基本要素？ 3、贪心算法与动态规划算法的异同？ 四、算法设计题： 1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M=150,如果使用贪心方法求解此背包问题(背包不超载的前提下，装载的物品价值达到最大)。 ①利用贪心算法求解该问题时，为了进行贪心选择，首先应该做什么？ 然后进行贪心装载，给出一种正确的物品装载顺序？并给出其最优装载方案？ ②利用贪心思想设计该普通背包问题的贪心算法？ ③分析其时间复杂度？ 解：①1)依据不同的标准对这些物詁进行排序，标准有重量、价值、单位价值； 2)重量从小到大:FGBAEDC ,得到的贪心解为：FGBAE全部放入,D放入20%，得到价值 为165； 价值从大到小:DFBEGCA ,得到的贪心解为：DFBE全部放入,G放入80% ,得到价值为189； 单位价值从大到小:FBGDECA，得到的贪心解为：FBGD全部放入,E放入87.5% , 得到价值为190. 625； 3)显然使用单位价值得出最佳转载方案。 ②、③ 2、设有n个活动集合，其中每个活动都要求使用同一资源，如足球场，而在同一时间只能 有一个活动使用该资源。 每个活动i 都有一个要求使用该资源起始时间si 和结束时间fi,且si < fi;如果选 择了活动i,则它在半开区间［si , fi ）占用资源。 若两个活动［si , fi ）与［sj , fj ）不相交，则称活动i 与活动j 是相容的； 活动安排问题： 就是在所给的活动集合中选出最大相容活动子集合； 求：①利用贪心算法求解该问题的基本思想？ ②设计该活动安排问题的贪心算法？并分析其时间复杂度？ 求：①利用prim 算法构造其最小生成树，画出其选边的过程？ 并构造其算法？并分析其时间复 杂度？ ②利用kruskal 算法构造其最小生成树，画出其选边的过程? 并构造其算法？并分析其时间复杂度？ 4、对下图中的有向图，应用Dijkstra 算法计算从源（顶点1）到其它顶点间最短路径的过程. 要求：给；|| Dijkstra 算法的迭代过程，计算源到给个顶点的最短路径？（用表表示） 解：见 课本123页 表4-2 解：迭代过程: 迭代 S U d i s t [2] d i s t [ 3] d i s t [4] d i s t [5] 初始 (1} — 10 max int 30 100 1 (1? 2} 2 60 30 100 2 (1, 2,4) 4 50 90 3 (1, 2,4, 3) 3 60 4 <1. 2, 4, 3, 5} 5 10 50 30 60 Di jks t ra 算法的达代*过租: S = V,3、给定下图G=（V, E ）是一个无向连通图, 对每一条边（v, W ）,其权值为c （ V, w ）； 一、填空题 1、回溯法与分支限界法搜索方式不同，回溯法按深度优先_搜索解空间,分支限界法按 广度优先或最小耗费优先搜索解空间。 二、判断题 1、 回溯法屮限界函数的目的是剪去得不到最优解的子树。 （V ） 2、 分支限界法类似丁?回溯法，也是一种在问题的解空间树T 上搜索问题解的算法，两者的 搜索方式是相同的。 （X ） 三、 简答题 1、 简述回溯法和分支限界法的相同点和不同点？ 2、 什么是子集树？什么是排列树？什么叫满m 叉树？ 3、 回溯算法的基本思想？ 回溯算法的解题步骤？ 四、 算法设计题 1、n 皇后问题 在4X4格的棋盘上放置彼此不受攻击的4个皇后。按照国际象棋的规则，皇后可以攻击 与Z 处在同一行或同一列或同一斜线上的棋子。用回溯算法解决4皇后问题: 解：①解空间树 第5章回溯算法 ①构造求解该问题的解空间树? ②设计该4皇后问题的冋溯算法? ②回溯算法 2、0—1背包问题: 假设有3个物品，它们的重量和价值如下表所示。若这些物詁均不可以被分割，且背包 容量M=10,问应该如何装入使背包屮物品的总价值最大? 用回 溯算法求解该0—1背包问题： ① 构造求解该问题的解空间树？ ② 设计该0—1背包问题的冋溯算法？ 解：1）解空间树； 物品 A B 0 重量 6 5 L 5 价值 42 25 30 3、图的着色问题： 如下图，给定无向连通图G和H1种不同的颜色；用这FD种颜色为图G的各个顶点着色, 是否有一?种方法使得图G中每-?条边的两个顶点著不同颜色； 求：①构造求解该问题的解空间树？②设计该图的着色问题回溯算法？ 2)算法： double mcoloring(int inm) {int m=mm; //m 口J用颜色数 double sum二0; //sum当前着色方案数 backtrack ( 1 ); 〃深度优先搜索解空间 return sum; } void backtrack( int t) { if ( t>n ) //搜索到叶子节点 { sum++; //着色方案数加1 for (int i=l; i<=n; i++) system, out. print ( x[ i]); } //输出解，顶点i着颜色x[ i] else //搜索到中间节点 { for(int i=l; i<=m; i++) { x[ t]二i; //顶点t着颜色i二l???ni boolean ok( int k) //当前着色顶点与以前相邻顶点是否同色 { for(int j=l; j<=n; j++) if( a[ k][ j]&&( x[ j]==x[ k] ) ) //数组 a[][]是图的邻接矩阵 //当前顶点k到j有边:a[ k] [ j],且色同:x[ j]==x[ k] return false; else return true;} ③算法分析5种颜色，n个节点) 计算限界函数,一重for循环时间复杂度:0(n); 在最坏的情况下每一个内节点都需要判断约束，内节点个数：l+m+ni* m3+ ... +nf T = (m11-1)/(m -1)个； 故图的m着色问题的回溯算法，时间复杂度为：0(n*m n) 第六章分支限界算法 一、填空题 1、按照活结点表的纽织方式的不同，分支限界法包括队列式分支限界算法和优先队列式 分支限界算法两种形式。 2、回溯法与分支限界法搜索方式不同，回溯法按深度优先捜索解空间,分支限界法按广度优先或最小耗费优先搜索解空间。 3、队列分支限界算法中，通常用队列实现，体现先进先出原则的原则。 4、优先队列式分支限界算法，通常采用堆实现。 6、|叫溯法与分支限界算法求解问题时，需要构造对该问题的解空间结构，其解空间结构通常冇3种形式，分别是_子集树、排列树、满m叉树。 二、判断题 1、分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，两者的搜索方式是相同的。(X) 三、简答题 1、简述分支限界法的基本思想与解题步骤？ 2、分支限界算法与回溯算法异同点？四、算法设计题 1、0—1背包问题： 假设有3个物品，它们的重量和价值如下表所示。若这些物品均不可以被分割，且背包容量M=10，问应该如何装入使背包中物品的总价值最大？ 用分支限界算法求解该0—1背包问题： ①构造求解该问题的解空间树？ ②给出队列式分支限界算法的求解过程？ 如错误！不能通过编辑域代码创建对象。 背包问题的分支限界算法？并分析其时间复杂度? (队列式分支限界，带上界函数) 2、多段图最短路径问题 ■多段滩力有向连通赋仅圉G=（v,E,w）,顶啟合6扮成X 个丙i= ?多段图最短路径I施 令|齐-V, |_ 1,称为S ?卩源点，加巴兀为收点。 求：①构造求解该问题的解空间树？ ②给出队列式分支限界算法的求解过程？ ③设计该问题的分支限界算法？并分析其吋间复朵度? （队列式分支限界，带上界函数） /定义并组织问题的解空间如下: 2）求解过程: 法"队列式（FIFO 先进先出〉分支限界法 ■ 从根结点4开始：椅活结点组一个队歹吐 ?初始时涯缢她5%空. 结点1力II入队列. 结点4为当前扩 纟占: ?结点1的孩子结点久3.4为可行结点.故金弃当诲结点|23|^| | | | | | | | | || | 将结点5. 6力口入话结点&L应 34 5 16 先进先JII城则. 8均是可行结点，加入活结点必孩 .......... 貢到垠后队列为空。 3 ）算法描述：法1 :血盛分支限界法 double shortest( int i) { while （true）//队列不空，捜索问题的解空间 { for ( int j=l; j<=n; j++) //儿子结点入队 { if (a[ i][ j] < Float. MAX_VALUE) // 顶点 i 到顶点 j 可达 { dist[ j]= dist[ i] +a[ i] [ j]; // dist[ i]记录源到顶点 i 的距离 p[ j]二enode. i; // p[ j]记录顶点j的前驱 enQueue(v[ j], j) ; // 结点 j 加入队列 } } ew = ((Integer) queue, remove()). intValue(); // 取队首下一扩展结点 if (ew = -1) //同一层尾部标记ew = -1：同一层结点处理结束 { i「(quouo. isEmplyO) rotum dist [ i]; //判断队歹l!是否为空 else { queue, put (new Integer (-1)) ; } // 同层结点尾部标志ew = ((Integer) queue, remove ()). i nt Vai ue () ; // 取下—扩展结点 i++；//进入下一层 } } } 时间复杂度： 第七章概率算法 1、什么叫概率算法？ 答：概率算法允许算法在执行的过程中随机选择卜?一个计算步骤。 2、概率算法有一个基本特征？ 答：基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。 3、概率算法可以分为哪4类？ 答：1）数值概率算法2）蒙特卡罗算法3）拉斯维加斯算法4）舍伍德算法4、在概率算法中使用的随机数都是一定程度上随机的，即伪随机数；一般随机数 通过线性同余法方法产生。 第8章NP完全性理论 1、什么是易解问题？什么是难解问题？难解问题分为哪两类？ 答：1）易解问题：人们将存在多项式时间算法的问题称为易解问题； 2）难解问题：将需要在指数时间内解决的问题称为难解问题； 3）难解问题有两类：1）不可判定问题 2）非决定的难处理问题。 2、什么是不可判定问题？什么是非决定的难处理问题？ 答：1）不可判定问题：该类问题是不能解问题，它们太难了，以至于根本就不存在能求解它们的任何算法。 2）非决定的难处理问题：这类问题是可判定的（即可解的）。但是，这类问题即使使用非决定的计算机，也不能在多项式时间内求解它们。 3、什么是P类问题？什么是NP完全问题？ 答:1）P类问题：是一类能够用确定性算法在多项式时间内求解的判断问题。事实上，所有易解问题都属于P类问题。 2）NP完全问题：对于某问题，很难找到其多项式时间的算法（或许根木不存在），但是如果给了该问题的一个答案，则可以在多项式时间内判定或验证这个答案是否正确。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。 4、列出几个典型的NP完全问题？ 答：（1）图着色问题COLORING （2）路径问题LONG-PATH （3）顶点覆盖问题VERTEX-COVER （4）子集和问题SUBSET-SUM （5）哈密尔顿回路问题HAM-CYCLE （6）旅行商问题TSP （7）装箱问题BIN-PACKING , 能否用k个箱了来装n个物品； 第九章近似算法 1、所有NP完全问题都还没有多项式时间的算法，然而许多NP完全问题都具有很重要的意义， 对于这类问题通常可以采取以下几种解题策略？ 答：1）只对问题的特姝实例求解；2 ）用动态规划或分支限界法求解。 3 ）启发式方法求解； 4 ）只求近似解 2、利用近似算法求解NP完全问题时，近似算法应该满足下面两个基本的要求？ 答：1）算法的时间复杂性：要求算法能在n的多项式时间内完成。 2）解的近似程度：算法的近似解应满足一定的精度。 通常，用来衡量精度的标准有近似比和相对谋差。 算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程3班 学号 20122668 姓名王建君 指导教师尹治本 2014年10月 实验四 矩阵相乘次序 一、问题提出 用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n }，其中A i 与A i+1是可乘的，i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A 是完全加括号的，则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式：（A 1（A 2（A 3A 4））），（A 1（（A 2A 3）A 4）），（（A 1A 2）（A 3A 4）），（（A 1（A 2A 3））A 4），（（（A 1A 2）A 3）A 4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵，B 是一个q ×r 矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr 次数乘。 （3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A 1A 2）A 3），（A 1（A 2A 3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A 1,A 2,…,A n }（其中矩阵Ai 的维数为p i-1×p i ，i ＝1,2,…,n ），如何确定计算矩阵连乘积A 1A 2…A n 的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 二、求解思路 本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是： 1)计算最优值算法MatrixChain()：建立两张表（即程序中的**m 和**s ，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n 个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。 三、算法复杂度 该算法时间复杂度最高为）（n 3 O 。 四、实验源代码 《算法分析与设计》试卷(A) （时间90分钟满分100分） 一、填空题（30分,每题2分）。 1．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2．在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3．实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4．.广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5．衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6．Strassen矩阵乘法是利用（ A）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是（ A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8．用动态规划算法解决最大字段和问题，其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题，最好用（ B ）算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14．下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15．回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 二、填空题（20分,每空1分）。 1.算法由若干条指令组成的又穷序列，且满足输入、输出、 确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。 西南交通大学2015 — 2016学年第(一)学期考试试卷 课程代码 3244152课程名称 算法分析与设计 考试时间 120分钟 阅卷教师签字： __________________________________ 填空题(每空1分，共15分) 1、 程序是 (1) 用某种程序设计语言的具体实现。 2、 矩阵连乘问题的算法可由 (2) 设计实现。 3、 从分治法的一般设计模式可以看出，用它设计出的程序一般是 (3) 4、 大整数乘积算法是用 (4) 来设计的。 5、 贪心算法总是做出在当前看来 (5) 的选择。也就是说贪心算法并不从整体最优 考虑，它所做出的选择只是在某种意义上的 (6) o 6、 回溯法是一种既带有 (7) 又带有 (8) 的搜索算法。 7、 平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的 (9) 类型 8、 在忽略常数因子的情况下，0、门和0三个符号中， (10) 提供了算法运行时 间的一个上界。 9、 算法的“确定性”指的是组成算法的每条 (11) 是清晰的，无歧义的。 10、 冋题的(12) 是该冋题可用动态规划算法或贪心算法求解的关键特征。 11、 算法就是一组有穷 (13)，它们规定了解决某一特定类型问题的 (14) o 12、 变治思想有三种主要的类型：实例化简，改变表现， (15) o 、 ___________________________________________________________________________________ L 线订装封密 线订装封密 、 __________________ 二 线订装封密 级班 选择题(每题2分，共20 分) 《算法设计与分析》试卷 一．计算题（共25分） 1. 用表示函数f与g之间的关系。（10分，每小题2分） (1) f(n)=10000n g(n)=n-10000 (2) f(n)=2n g(n)=3n/n (3) f(n)=n3log2n g(n)=n2log3n (4) f(n)=log2n g(n)=log3n (5) f(n)=100n+n100 g(n)=n! 2.估计下列算法的时间复杂性的阶。(10分，每小题5分) (1)算法A的时间复杂性为， (2)算法B的时间复杂性为 3. 计算下面算法中count=count+1的执行次数（5分） 算法 COUNT count=0 for i=1 to for j=i to i+5 for k=1 to i2 count=count+1 end for end for end for 二．简答题（共15分） 1. 随机算法分成那几类，各有什么特点？（7分） 2．最大k乘积问题：设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。对于给定的I和k，求出I的最大k乘积。当用动态规划求解该问题时，最优子结构是什么？递归关系式是什么？（8分） 三．算法填空题（共45分，每空3分） 1. 以下是计算x m的值的过程 power ( x, m ) if m=0 then y=_____ (1)_______ else y=_____ (2)_______ 装订 线 y=y*y if m 为奇数 then y=x*y C=multiply( A , B) //计算两个矩阵乘积C=AB。 return C end if end matchain_product 3. 以下是迷宫问题的算法 算法 MAZE 输入：正整数m, n，表示迷宫的数组M[0..m+1, 0..n+1] (迷宫数据存于M[1..m, 1..n]中)，迷宫的入口位置(ix, iy),出口位置(ox, oy)。 输出：迷宫中入口至出口的一条通路，若无通路，则输出no solution。 M[0, 0..n+1]=M[m+1, 0..n+1]=1 《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 15个选择题组成, 每题1分, 共15分。第二部分为”主观题部分”, 由简答题和论述题组成, 共15分。作业总分30分, 将作为平时成 绩记入课程总成绩。 客观题部分: 一、选择题( 每题1分, 共15题) 1、递归算法: ( C ) A、直接调用自身 B、间接调用自身 C、直接或间接 调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模 较小的字问题, 这些子问题: ( D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是: ( C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的: ( A ) A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是: ( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、 形函数 6、哈夫曼编码是: ( B) A、定长编码 B、变长编码 C、随机编码 D、定 长或变长编码 7、多机调度的贪心策略是: ( A) A、最长处理时间作业优先 B、最短处理时间作业优 先 C、随机调度 D、最优调度 8、程序能够不满足如下性质: ( D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是: ( A ) A、递归算法 B、动态规划算法 C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题: ( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是: ( A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策 有可能导致算法: ( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到: ( C ) A、全局最优解 B、 0-1背包问题的解 C、背包问题的 解 D、无解 14、能求解单源最短路径问题的算法是: ( A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是: 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x = 《算法分析与设计》作业（一） 本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由简答题和论述题组成，共15分。作业总分30分，将作为平时成绩记入课程总成绩。 客观题部分： 一、选择题（每题1分，共15题） 1、递归算法：（C ） A、直接调用自身 B、间接调用自身 C、直接或间接调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ） A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是：（C ） A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的：（A ） A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是：（ A ） A、最优子结构 B、重叠子问题 C、贪心选择 D、形函数 6、哈夫曼编码是：（B） A、定长编码 B、变长编码 C、随机编码 D、定长或变长编码 7、多机调度的贪心策略是：（A） A、最长处理时间作业优先 B、最短处理时间作业优先 C、随机调度 D、最优调度 8、程序可以不满足如下性质：（D ） A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是：（A ） A、递归算法 B、动态规划算法 C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题：（ C ） A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是：（A ） A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ） A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到：（C ） A、全局最优解 B、0-1背包问题的解 C、背包问题的解 D、无解 14、能求解单源最短路径问题的算法是：（A ） A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是：（ A ） A、舍伍德算法 B、蒙特卡罗算法 C、拉斯维加斯算法 D、数值随机化算法 主观题部分： 二、写出下列程序的答案（每题2.5分，共2题） 1、请写出批处理作业调度的回溯算法。 #include 《算法分析与设计》试题库 （一） 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是（D ） A. 贪心算法 B.分支限界法 C.分治法 B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move( n, a,b); hanoi(n-1, C, B, A); 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座 B 上，并 D.动态规划算法 3. 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C.最优子结构性质与重叠子问题性质 D.预排序与递归调用 4. 算法分析中，记号0表示(B),记号0表示(A),记号。表示(D) A. 渐进下界 B. 渐进上界 C. 非紧上界 D. 紧渐进界 E. 非紧下界 5. 以下关于渐进记号的性质是正确的有：(A) A. f(n) - P(g(n)),g(n) - 心(h(n))二f(n) - P(h(n)) B. f(n) =0(g(n)),g(n) =0(h(n))二h(n) =0(f(n)) C. O(f(n ))+0(g( n)) = O(mi n{f(n ),g( n)}) D. f(n) =0(g(n)) = g(n) -0(f (n)) 6?能采用贪心算法求最优解的问题，一般具有的重要性质为：(A) A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C. 最优子结构性质与重叠子问题性质 D. 预排序与递归调用 7.回溯法在问题的解空间树中，按(D)策略，从根结点出发搜索解空间树。 A. 广度优先 B.活结点优先 C.扩展结点优先 D.深度优先 内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14 算法设计与分析期末考试模拟试卷 A卷 考试说明： 承诺： 本人已学习了《北京工业大学考场规则》和《北京工业大学学生违纪处分条例》，承诺在考试过程中自觉遵守有关规定，服从监考教师管理，诚信考试，做到不违纪、不作弊、不替考。若有违反，愿接受相应的处分。 承诺人：学号：班号： 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。注：本试卷共三大题，共 6 页，满分100分，考试时答案请写在试卷空白处。 一、算法时间复杂性问题（共30分） Part 1. The Time Complexity Of the Algorithm Test 1、试证明下面的定理：[12分] (1) 如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)+g(n)=O(s(n)+r(n)) (2) 如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)*g(n)=O(s(n)*r(n)) 1. Prove the following Theorem [12 marks] (1) if f(n)=O(s(n)) and g(n)=O(r(n)), to prove f(n)+g(n)=O(s(n)+r(n)) (2) if f(n)=O(s(n)) and g(n)=O(r(n))，to prove f(n)*g(n)=O(s(n)*r(n)) 2、已知有如下的断言： f(n)=O(s(n))并且g(n)=O(r(n))蕴含f(n)-g(n)=O(s(n)-r(n)) 请你举出一个反例。[8分] 2. Known as the following assertion If f(n)=O(s(n)) and g(n)=O(r(n))，then f(n)-g(n)=O(s(n)-r(n)) 。 Please cite a counter-example [8 marks] 3、假设某算法在输入规模为n时的计算时间为：T（n）=3*2n，在A型计算机上实现并完成该算法的时间为t秒，现有更先进的B型计算机，其运算速度为A 型计算机的256倍。试求出若在先进的B型机上运行同一算法则在t秒内能求解输入规模为多大的问题？[10分] 3. Assume that in the case of the input size is n, the computing time of the algorithm required is T（n）=3*2n. It would take t seconds to implement the algorithm on Computer A. Computer B is more advanced. The operation ability of Computer B is 256 times of Computer A. If the same algorithm running on Computer B, please find out the input size so that the algorithm would solve in t seconds.[10 marks] 《算法分析与设计》作业参考答案 作业一 一、名词解释： 1.递归算法：直接或间接地调用自身的算法称为递归算法。 2.程序：程序是算法用某种程序设计语言的具体实现。 二、简答题： 1.算法需要满足哪些性质？简述之。 答：算法是若干指令的有穷序列，满足性质： （1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。 （3）确定性：组成算法的每条指令清晰、无歧义。 （4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。 答：分析分治法能解决的问题主要具有如下特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 答：将递归算法转化为非递归算法的方法主要有： （1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归， 只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推来实现递归函数。 （3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 do for j ←1 to n-i do if a[j] 算法分析与设计复习题及答案一、单选题 1．D 2．B 3．C 4．D 5．D 6．D 7．C 8．D 9．B 10．C 11．D 12．B 13．D 14．C 15．C 16．D 17．D 18．D 19．D 20．C 1．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 2．根据执行算法的计算机指令体系结构，算法可以分为（）。 Ａ精确算法与近似算法Ｂ串行算法语并行算法 Ｃ稳定算法与不稳定算法Ｄ３２位算法与６４位算法 3．具有１0个节点的完全二叉树的高度是（）。 Ａ６Ｂ５Ｃ3Ｄ 2 4．下列函数关系随着输入量增大增加最快的是（）。 Ａlog2n B n2 C 2n D n! 5．下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6．Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7．4个盘子的汉诺塔，至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8．下列序列不是堆的是（）。 A 99，85，98，77，80，60，82，40，22，10，66 B 99，98，85，82，80，77，66，60，40，22，10 C 10，22，40，60，66，77，80，82，85，98，99 D 99，85，40，77，80，60，66，98，82，10，22 9．Strassen矩阵乘法的算法复杂度为（）。 ＡΘ(n3)ＢΘ(n2.807) ＣΘ(n2) ＤΘ(n) 10．集合A的幂集是（）。 A．A中所有元素的集合 B. A的子集合 C． A 的所有子集合的集合 D. 空集 11．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 12．从排序过程是否完全在内存中显示，排序问题可以分为（）。 Ａ稳定排序与不稳定排序Ｂ内排序与外排序 Ｃ直接排序与间接排序Ｄ主排序与辅助排序 13．下列（）不是衡量算法的标准。 Ａ时间效率Ｂ空间效率 Ｃ问题难度Ｄ适应能力 14．对于根树，出度为零的节点为（）。 Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分支节点 15．对完全二叉树自顶向下，从左向右给节点编号，节点编号为１0的父节点编号为（）。 Ａ０Ｂ２Ｃ４Ｄ６ 16．下列程序段的算法时间的复杂度为（）。 for i ←0 to n do for j ←0 to m do 《算法分析与设计》期末试题及参考答案 一、简要回答下列问题： 1.算法重要特性是什么？ 1.确定性、可行性、输入、输出、有穷性 2. 2.算法分析的目的是什么？ 2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 3. 3.算法的时间复杂性与问题的什么因素相关？ 3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。 4.算法的渐进时间复杂性的含义？ 4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的 算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度： W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和： A(n) =∑P(I)T(n，I) I∈Dn 6.简述二分检索（折半查找）算法的基本过程。 6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较， 如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2] 《算法分析与设计》 学习中心： 专业： 学号： 姓名： 作业练习二 一、名词解释 1、MST性质 2、子问题的重叠性质 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。 二、简答题 1、简述动态规划算法求解的基本要素。 答：动态规划算法求解的基本要素包括： 1)最优子结构是问题能用动态规划算法求解的前提； 2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。 2、备忘录方法和动态规划算法相比有何异同简述之。 答：备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。 3、贪心算法求解的问题主要具有哪些性质简述之。 答：贪心算法求解的问题一般具有二个重要的性质： 一是贪心选择性质，这是贪心算法可行的第一个基本要素； 另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 三、算法编写及算法应用分析题 1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。 最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。 《算法分析与设计》期末复习题 一、选择题 1.算法必须具备输入、输出和（ D ）等4个特性。 A．可行性和安全性 B．确定性和易读性 C．有穷性和安全性 D．有穷性和确定性 2.算法分析中，记号O表示（ B ），记号Ω表示（ A ） A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 3.假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并 完成概算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题（ B ）解题方法：3*2^n*64=3*2^x A．n+8 B．n+6 C．n+7 D．n+5 4.设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1， T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（ C ）。 A．O(logN) B．O(N) C．O(NlogN) D．O(N2logN) 5.直接或间接调用自身的算法称为（ B ）。 A．贪心算法 B．递归算法 C．迭代算法 D．回溯法 6.Fibonacci数列中，第4个和第11个数分别是（ D ）。 A．5，89 B．3，89 C．5，144 D．3，144 7.在有8个顶点的凸多边形的三角剖分中，恰有（ B ）。 A．6条弦和7个三角形 B．5条弦和6个三角形 C．6条弦和6个三角形 D．5条弦和5个三角形 8.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A．重叠子问题 B．最优子结构性质 C．贪心选择性质 D．定义最优解 9.下列哪个问题不用贪心法求解（ C ）。 A．哈夫曼编码问题 B．单源最短路径问题 C．最大团问题 D．最小生成树问题 10.下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A．备忘录法 B．动态规划法 C．贪心法 D．回溯法 11.下列算法中不能解决0/1背包问题的是（ A ）。 A．贪心法 B．动态规划 C．回溯法 D．分支限界法 12.下列哪个问题可以用贪心算法求解（ D ）。 A．LCS问题 B．批处理作业问题 C．0-1背包问题 D．哈夫曼编码问题 13.用回溯法求解最优装载问题时，若待选物品为m种，则该问题的解空间树的结点 个数为（）。 A．m! B．2m+1 C．2m+1-1 D．2m 14.二分搜索算法是利用（ A ）实现的算法。 A．分治策略 B．动态规划法 C．贪心法 D．回溯法 15.下列不是动态规划算法基本步骤的是（ B ）。P44 A．找出最优解的性质 B．构造最优解 C．算出最优解(应该是最优值) D．定义最优解 一、选择题 1．一个.java文件中可以有（）个public类。 A．一个B．两个C．多个D．零个 2．一个算法应该是（） A．程序B．问题求解步骤的描述 C．要满足五个基本特性D．A和C 3．用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（）A．唯一性B．有穷性C．有0个或多个输入D．有输出 4．某校有6位学生参加学生会主席竞选，得票数依次为130，20，98，15，67，3。若采用冒泡排序算法对其进行排序，则完成第二遍时的结果是（） A．3，15，130，20，98，67B．3，15，20，130，98，67 C．3，15，20，67，130，98 D．3，15，20，67，98，130 5．下列关于算法的描述，正确的是（） A．一个算法的执行步骤可以是无限的B．一个完整的算法必须有输出 C．算法只能用流程图表示D．一个完整的算法至少有一个输入 6．Java Application源程序的主类是指包含有（）方法的类。 A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法 7．找出满足各位数字之和等于5的所有三位数可采用的算法思路是（） A．分治法B．减治法C．蛮力法D．变治法 8．在编写Java Application程序时，若需要使用到标准输入输出语句，必须在程序的开头写上( )语句。 A、import java.awt.* ; B、import java.applet.Applet ; C、import java.io.* ; D、import java.awt.Graphics ; 9．计算某球队平均年龄的部分算法流程图如图所示，其中：c用来记录已输入球员的人数，sum用来计算有效数据之和，d用来存储从键盘输入的球员年龄值，输入0时表示输入结束。 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性: 确定性,有穷性,可行性,0个或多个输入,一个或多个输出。 2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低。 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解。 6.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai算法设计与分析(作业三)
算法分析与设计试卷
2015年算法分析与设计期末考试试卷B卷
《算法设计与分析》试卷A
算法分析与设计作业及参考答案样本
算法设计与分析试卷A及答案
最新算法分析与设计作业(一)及参考答案讲课讲稿
5.《算法设计与分析》试题库
算法设计与分析试卷(2010)
算法设计与分析试卷及答案
算法分析与设计模拟试卷A
《算法分析与设计》作业参考答案
算法分析与设计复习题及答案
《算法分析与设计》期末试题及参考答案
算法分析与设计(线下作业二)
《算法分析与设计》期末考试复习题纲(完整版)
《算法分析与设计》期末复习题
算法设计与分析试题与答案
相关主题
文本预览