算法分析与设计习题集整理.docx
- 文档编号:17053049
- 上传时间:2023-07-21
- 格式:DOCX
- 页数:26
- 大小:246.92KB
算法分析与设计习题集整理.docx
《算法分析与设计习题集整理.docx》由会员分享,可在线阅读,更多相关《算法分析与设计习题集整理.docx(26页珍藏版)》请在冰点文库上搜索。
算法分析与设计习题集整理
算法分析与设计习题集整理
第一章算法引论
一、填空题:
1、算法运行所需要的计算机资源的量,称为算法复杂性,主要包括时间复杂度和空间复杂度。
2、多项式
的上界为O(nm)。
3、算法的基本特征:
输入、输出、确定性、有限性。
4、如何从两个方面评价一个算法的优劣:
时间复杂度、空间复杂度。
5、计算下面算法的时间复杂度记为:
O(n3)。
for(i=1;i<=n;i++)
for(j=1;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、算法设计的基本要求:
正确性和可读性。
8、计算下面算法的时间复杂度记为:
O(n2)。
for(i=1;i {y=y+1; for(j=0;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),O(3n),O(n! ) 2、什么是算法? 算法的特征有哪些? 答: 1)算法: 指在解决问题时,按照某种机械步骤一定可以得到问题结果的处理过程。 通俗讲,算法: 就是解决问题的方法或过程。 2)特征: 1)算法有零个或多个输入;2)算法有一个或多个输出;3)确定性;4)有穷性 3、给出算法的定义? 何谓算法的复杂性? 计算下例在最坏情况下的时间复杂性? for(j=1;j<=n;j++) (1) for(i=1;i<=n;i++) (2) {c[i][j]=0;(3) for(k=1;k<=n;k++)(4) c[i][j]=c[i][j]+a[i][k]*b[k][j];}(5) 答: 1)定义: 指在解决问题时,按照某种机械步骤一定可以得到问题结果的处理过程。 2)算法的复杂性: 指的是算法在运行过程中所需要的资源(时间、空间)多少。 所需资源越多,表明算法的复杂性越高 3)该算法的主要元操作是语句5,其执行次数是n3次。 故该算法的时间复杂度记为O(n3). 4、算法A和算法B解同一问题,设算法A的时间复杂性满足递归方程 ,算法B的时间复杂性满足递归方程 ,若要使得算法A时间复杂性的阶高于算法B时间复杂性的阶,a的最大整数值可取多少? 答: 分别记算法A和算法B的时间复杂性为 和 ,解相应的递归方程得: 依题意,要求最大的整数a使得 〈 。 显然,当a<=4时, 〈 ;当a>4时, 〈 a< =16。 所以,所求的a的最大整数值为15。 5、算法分析的目的? 答: 1)为了对算法的某些特定输入,估算该算法所需的内存空间和运行时间; 2)是为了建立衡量算法优劣的标准,用以比较同一类问题的不同算法。 6、算法设计常用的技术? (写5种) 答: ①分治法;②回溯法;③贪心法;④动态规划法 ⑤分治限界法;⑥蛮力法;⑦倒推法 三、算法设计题 1、蛮力法: 百鸡百钱问题? 2、倒推法: 穿越沙漠问题? 第二章分治算法 (1)----递归循环 一、填空题: 1、直接或间接地调用自身的算法称为递归算法,用函数自身给出定义的函数称为递归函数。 2、递归方程和约束函数(递归终止条件)是递归函数的两个要素。 二、判断题: 1、所有的递归函数都能找到对应的非递归定义。 (√) 2、定义递归函数时可以没有初始值。 (X) 三、简答题: 1、什么是递归算法? 递归算法的特点? 答: 1)递归算法: 是一个模块(函数、过程)除了可调用其它模块(函数、过程)外,还可以直接或间接地调用自身的算法。 2)递归算法特点: ①每个递归函数都必须有非递归定义的初值;否则,递归函数无法计算;(递归终止条件) ②递归中用较小自变量函数值来表达较大自变量函数值;(递归方程式) 2、比较循环与递归的异同? 答: 相同: 递归与循环都是解决“重复操作”的机制。 不同: 就效率而言,递归算法的实现往往要比迭代算法耗费更多的时间(调用和返回均需要额外的时间)与存贮空间(用来保存不同次调用情况下变量的当前值的栈栈空间),也限制了递归的深度。 每个迭代算法原则上总可以转换成与它等价的递归算法;反之不然。 递归的层次是可以控制的,而循环嵌套的层次只能是固定的,因此递归是比循环更灵活的重复操作的机制。 3、递归算法解题通常有三个步骤? 答: 1)分析问题、寻找递归: 找出大规模问题与小规模问题的关系,这样通过递归使问题的规模逐渐变小。 2)设置边界、控制递归: 找出停止条件,即算法可解的最小规模问题。 3)设计函数、确定参数: 和其它算法模块一样设计函数体中的操作及相关参数。 四、算法设计题: 1、楼梯上有n个台阶,上楼时可以上1步,也可以上2步,设计一递归算法求出共有多少种上楼方法F(n)。 ①写出F(n)的递归表达式? ②并写出其相应的递归算法? 解: ①写出F(n)的递归表达式 分析: 到n阶有两种走法: 1)n-1阶到n阶; 2)n-2阶到n阶; 1n=1 F(n)=2n=2 F(n-1)+F(n-2)n>2 ②写出其相应的递归算法? IntF(intn) { if(n=1)return1; elseif(n=2) return2; else returnF(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中任一塔座上。 ①写出该问题的解题步骤? ②并写出其相应的递归算法? 解: ①第一步: 将n-1个盘子看成一个整体,从A移到C; 第二步: 将第n个盘子移到B; 第三步: 将n-1个盘子看成一个整体,从C移到B; ②写出其相应的递归算法: voidhanoi(intn,inta,intb,intc) {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)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质; 3)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。 4)利用该问题分解出子问题解可以合并为该问题解; 2、分治算法基本思想,解题步骤? 三、算法设计题: 1、改写二分查找算法: 设a[1…n]是一个已经排好序的数组,改写二分查找算法,使得当搜索元素x不在数组中时,返回小于x的最大元素位置i,和大于x的最小元素位置j;当搜索元素x在数组中时,i和j相同,均为x在数组中的位置。 并分析其时间复杂度? 解: intbinsearch(inta[n],intx,)//x待查数据 {intmid,i,j;low=1; inthigh=n; while(low<=high) {mid=(low+high)/2; if(a[mid]=x)returni=j=mid; if(a[mid]>x)high=mid-1;//继续在左边查找 else//(a[mid] low=mid+1;//继续在右边查找 } i=right;j=left; return0;//low大于high查找区间为空,查找失败 } 计算时间复杂性为O(logn) 2、棋盘覆盖在一个2k×2k个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。 在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。 求: ①简述分治算法的基本思想? ②设计该棋盘覆盖问题的分治算法? ③计算所设计算法的时间复杂度? (要求写出递推公式) 解: ①分解: 将一个难以直接解决的大问题,分割成一些规模较小的相同子问题,以便各个击破,分而治之。 对这k个子问题分别求解: 如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止 求小问题解、合并: 将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。 ②、③ 3、金块问题(求最大最小元问题) 老板有一袋金块(共n块),最优秀的雇员得到其中最重的一块,最差的雇员得到其中最轻的一块。 假设有一台比较重量的仪器,我们希望用最少的比较次数找出最重的金块。 求: ①简述分治算法的基本思想? ②设计该金块问题的分治算法? ③计算所设计算法的时间复杂度? (要求写出递推公式) 答: ①简述分治算法的基本思想: 问题可以简化为: 在含n(n是2的幂(n>=2))个元素的集合中寻找极大元和极小元。 用分治法(二分法)可以用较少比较次数地解决上述问题: 1)将数据等分为两组(两组数据可能差1),目的是分别选取其中的最大(小)值。 2)递归分解直到每组元素的个数≤2,可简单地找到最大(小)值. 3)回溯时将分解的两组解大者取大,小者取小,合并为当前问题的解。 ②、③ 第三章动态规划算法 一、填空题: 1、动态规划算法中存储子问题的解是为了避免重复求解子问题。 2、(最优子结构)是问题能用动态规划算法求解的前提。 3、矩阵连乘问题的算法可由(动态规划)算法设计实现。 二、判断题: 1、动态规划算法基本要素的是最优子结构。 (√) 2、最优子结构性质是指原问题的最优解包含其子问题的最优解。 (√) 3、动态规划算法求解问题时,分解出来的子问题相互独立。 (X) 三、简答题: 1、动态规划算法解题步骤? 答: ①找出最优解的性质,并刻划其结构特征; (即原问题的最优解,包含了子问题的最优解) ②递归地定义最优值; (即子问题具有重叠性,由子问题定义原问题) ③以自底向上的方式计算出最优值; ④根据计算最优值时得到的信息,构造最优解; 2、动态规划算法基本思想? 答: 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题; 但是经分解得到的子问题往往不是互相独立的。 不同子问题的数目常常只有多项式量级。 在用分治法求解时,有些子问题被重复计算了许多次; 如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。 3、动态规划与分治算法异同点? 4、动态规划算法的基本要素? 四、算法设计与计算题: 1、 和 的最长公共子序列为 。 问: 若用 记录序列 和 公共子序列长度。 求: ①用动态规划法求解时,计算最优值的递归公式? ②设计计算最优值的算法? 以及构造最优解的算法? 2、长江游艇俱乐部在长江上设置了n个游艇出租站1,2…n.游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。 游艇出租站i到游艇出租站j之间的租金为r(i,j),其中1<=i 求: ①用动态规划法求解时,计算最优值(最少租金)的递归公式? ②设计计算最优值(最少租金)的算法? ③并分析其时间复杂度? 解: ① ②计算最优值算法 publicstaticvoidmatrixChain(int[]p,int[][]m,int[][]s) { intn=p.length-1; for(inti=1;i<=n;i++) m[i][i]=0; //1个站 for(intr=2;r<=n;r++) for(inti=1;i<=n-r+1;i++) {intj=i+r-1; m[i][j]=m[i][i]+m[i+1][j]; s[i][j]=i; //断点位置在i处 for(intk=i+1;k {int t=m[i][k]+m[k+1][j]; if(t {m[i][j]=t;s[i][j]=k;} }}} 构造最优解算法 publicvoidtraceback(ints[][],intI,intj) { if(i=j)return; traceback(s,i,s[i][j]); traceback(s,s[i][j]+1,j); System.out.println(“A”+i+“,”+s[i][j]+“A”+s[i][j]+1+“,”+j) }//(m[i,s[i][j]])(m[s[i][j]+1,j]) ③时间复杂度: O(n3) 第4章贪心算法 一、填空题: 1、某单位给每个职工发工资(精确到元)。 为了保证不要临时兑换零钱,且取款的张数最少,统计所需各种币值(100,50,20,10,5,2,1元共七种)的张数。 贪心算法如下: voidgreedy_zhaoling(floatGZ,intB[],intS[])//GZ应发工资 {for(j=1,j<=7;j++)//贪心选择,依次给最大币种 {A=GZ/B[j];//A表示对应j币种张数 S[j]=S[j]+A;//S[j]存放对应j币种总张数 GZ=GZ-A*B[j];} for(i=1;i<=7;i++) print(B[i],“----”,S[i]);//输出币种和对应张数 } 2、贪心算法的两个基本要素是(贪心选择性)和(最优子结构)。 3、给定n种物品和一个背包。 物品i的重量是Wi,其价值为Vi,背包的容量为M,应如何选择装入背包的物品,使得装入背包中物品的总价值最大。 贪心算法如下: floatgreedy_knapsack(floatM,floatw[],floatp[],floatx[]) //x[]背包问题最优解,w[]物品重量,P[]物品价值 {intn=w.length; floatpp=0; floatmm=M;//pp计算当前总价值,mm背包剩余载重 for(inti=1;i<=n;i++) {floatww[i]=p[i]/w[i];//计算物品单位价值ww[] x[i]=0;}//初始化 Mergesort(w[],n);//按单位价值将物品排序,便于贪心选择 for(inti=1;i<=n;i++)//贪心选择,总是选择价值最大放入背包 {if(w[i]<=mm)//当前物品小于背包剩余载重 {x[i]=1;mm=mm-w[i];pp=pp+p[i];} else{x[i]=mm/w[i];pp=pp+x[i]*p[i];break;}//i部分放入背包 } returnpp; } 二、判断题: 1、满足贪心选择性质必满足最优子结构性质。 (X) 三、简答题: 1、贪心算法的基本思想? 2、贪心算法的基本要素? 3、贪心算法与动态规划算法的异同? 四、算法设计题: 1、假设有7个物品,它们的重量和价值如下表所示。 若这些物品均可以被分割,且背包容量M=150,如果使用贪心方法求解此背包问题(背包不超载的前提下,装载的物品价值达到最大)。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 ①利用贪心算法求解该问题时,为了进行贪心选择,首先应该做什么? 然后进行贪心装载,给出一种正确的物品装载顺序? 并给出其最优装载方案? ②利用贪心思想设计该普通背包问题的贪心算法? ③分析其时间复杂度? 解: ①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 若两个活动[si,fi)与[sj,fj)不相交,则称活动i与活动j是相容的; 活动安排问题: 就是在所给的活动集合中选出最大相容活动子集合; 求: ①利用贪心算法求解该问题的基本思想? ②设计该活动安排问题的贪心算法? 并分析其时间复杂度? 3、给定下图G=(V,E)是一个无向连通图,对每一条边(v,w),其权值为c(v,w); 求: ①利用prim算法构造其最小生成树,画出其选边的过程? 并构造其算法? 并分析其时间复杂度? ②利用kruskal算法构造其最小生成树,画出其选边的过程? 并构造其算法? 并分析其时间复杂度? 4、对下图中的有向图,应用Dijkstra算法计算从源(顶点1)到其它顶点间最短路径的过程. 要求: 给出Dijkstra算法的迭代过程,计算源到给个顶点的最短路径? (用表表示) 解: 见课本123页 表4-2 解: 迭代过程: 第5章回溯算法 一、填空题 1、回溯法与分支限界法搜索方式不同,回溯法按深度优先搜索解空间,分支限界法按广度优先或最小耗费优先搜索解空间。 二、判断题 1、回溯法中限界函数的目的是剪去得不到最优解的子树。 (√) 2、分支限界法类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法,两者的搜索方式是相同的。 (X) 三、简答题 1、简述回溯法和分支限界法的相同点和不同点? 2、什么是子集树? 什么是排列树? 什么叫满m叉树? 3、回溯算法的基本思想? 回溯算法的解题步骤? 四、算法设计题 1、n皇后问题 在4×4格的棋盘上放置彼此不受攻击的4个皇后。 按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 用回溯算法解决4皇后问题: ①构造求解该问题的解空间树? ②设计该4皇后问题的回溯算法? 解: ①解空间树 ②回溯算法 2、0-1背包问题: 假设有3个物品,它们的重量和价值如下表所示。 若这些物品均不可以被分割,且背包容量M=10,问应该如何装入使背包中物品的总价值最大? 物品 A B C 重量 6 5 5 价值 42 25 30 用回溯算法求解该0-1背包问题: ①构造求解该问题的解空间树? ②设计该0-1背包问题的回溯算法? 解: 1)解空间树; 3、图的着色问题: 如下图,给定无向连通图G和m种不同的颜色;用这m种颜色为图G的各个顶点着色,是否有一种方法使得图G中每一条边的两个顶点着不同颜色; 求: ①构造求解该问题的解空间树? ②设计该图的着色问题回溯算法? 解: 1)解空间树: 2)算法: doublemcoloring(intmm) {intm=mm;//m可用颜色数 doublesum=0;//sum当前着色方案数 backtrack (1);//深度优先搜索解空间 returnsum; } voidbacktrack(intt) {if(t>n)//搜索到叶子节点 {sum++;//着色方案数加1 for(inti=1;i<=n;i++) system.out.print(x[i]); }//输出解,顶点i着颜色x[i] else//搜索到中间节点 {for(inti=1;i<=m;i++) {x[t]=i;//顶点t着颜色i=1…m if(ok(t))backtrack(t+1); } } } booleanok(intk)//当前着色顶点与以前相邻顶点是否同色 {for(intj=1;j<=n;j++) if(a[k][j]&&(x[j]==x[k])) //数组a[][]是图的邻接矩阵 //当前顶点k到j有边: a[k][j],且色同: x[j]==x[k] returnfalse; elsereturntrue;} ③算法分析(m种颜色,n个节点) 计算限界函数,一重for循环时间复杂度: O(n); 在最坏的情况下每一个内节点都需要判断约束,内节点个数: 1+m+m2+m3+……+mn-1=(mn-1)/(m-1)个; 故图的m着色问题的回溯算法,时间复杂度为: O(n*mn) 第六章分支限界算法 一、填空题 1、按照活结点表的组织方式的不同,分支限界法包括队列式分支限界算法和优先队列式分支限界算法两种形式。 2、回溯法与分支限界法搜索方式不同,回溯法按深度优先搜索解空间,分支限界法按广度优先或最小耗费优
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 设计 习题集 整理