算法分析与设计复习题及参考答案

网络教育课程考试复习 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 及参考答案算法分析与 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 一、名词解释：1.算法2.程序3.递归函数4.子问题的重叠性质5.队列式分支限界法6.多机调度问题7.最小生成树二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。2.简述回溯法解题的主要步骤。3.简述动态规划算法求解的基本要素。4.简述回溯法的基本思想。5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划算法的异同。三、算法编写及算法应用分析题：1.已知有3个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。3.已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序（要求给出计算步骤）。4.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[si，fi]，活动i,j相容的条件是：sj≥fi，问题的解 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示为(xi|xi=1，2…，n,)，xi表示顺序为i的活动编号活动，求一个相容的活动子集，且安排的活动数目最多。10.设x1、x2、x3是一个三角形的三条边，而且x1+x2+x3=14。请问有多少种不同的三角形？给出解答过程。11.设数组A有n个元素，需要找出其中的最大最小值。①请给出一个解决方法，并分析其复杂性。②把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。12.有n个程序和长度为L的磁带，程序i的长度为ai，已知，求最优解(xi，x2，...，xi，…，xn)，xi=0，1,xi=1，表示程序i存入磁带，xi=0，表示程序i不存入磁带，满足，且存放的程序数目最多。13.试用分治法实现有重复元素的排列问题：设是要进行排列的个元素，其中元素可能相同，试设计计算的所有不同排列的算法。14.试用动态规划算法实现0-1闭包问题，请写出该算法。15.试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，请写出该算法。16.试写出用分治法对一个有序表实现二分搜索的算法。17.试用动态规划算法实现最长公共子序列问题，请写出该算法。18.假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题，请写出状态空间搜索树。物品ABCDEFG重量35306050401025价值1040305035403019.求解子集和问题：对于集合S={1，2，6，8}，求子集，要求该子集的元素之和d=9。①画出子集和问题的解空间树；②该树运用回溯算法，写出依回溯算法遍历节点的顺序；③如果S中有n个元素，指定d，用伪代码描述求解子集和问题的回溯算法。20.求解填字游戏问题：在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试采用回溯法写出满足这个要求的一种数字填法的算法和满足这个要求的全部数字填法的算法。21.试用动态规划算法实现最大子矩阵和问题：求矩阵A的一个子矩阵，使其各元素之和为最大。22.试用回溯法解决下列整数变换问题：关于整数的变换和定义如下：。对于给定的两个整数和，要求用最少的变换和变换次数将变为。23.关于15谜问题。在一个4×4的方格的棋盘上，将数字1到15代表的15个棋子以任意的顺序置入各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为了有效的移动，设计了估值函数C1(x)，表示在结点x的状态下，没有到达目标状态下的正确位置的棋子的个数。请使用该估计函数，对图示的初始状态，给出使用分支限界方法转换到目标状态的搜索树。124563791012813141115123456789101112131415初始状态目标状态参考答案一、名词解释：1.算法：算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：（1）输入：有零个或多个外部量作为算法的输入；（2）输出：算法产生至少一个量作为输出；（3）确定性：组成算法的每条指令清晰、无歧义；（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。2.程序：程序是算法用某种程序设计语言的具体实现。3.递归函数：用函数自身给出定义的函数称为递归函数。4.子问题的重叠性质：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。5.队列式分支限界法：队列式(FIFO)分支限界法是将活结点表组织成一个队列，并按照队列的先进先出（FIFO）原则选取下一个结点为扩展结点。6.多机调度问题：多机调度问题要求给出一种作业调度 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。同时约定每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。7.最小生成树：G=(V,E)是无向连通带权图，G的子图称为G的生成树，生成树上各边权的总和称为该生成树的耗费，在G的所有生成树中，耗费最小的生成树称为G的最小生成树。二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。2.简述回溯法解题的主要步骤。回溯法解题的主要步骤包括：1）针对所给问题，定义问题的解空间；2）确定易于搜索的解空间结构；3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。3.简述动态规划算法求解的基本要素。动态规划算法求解的基本要素包括：1）最优子结构是问题能用动态规划算法求解的前提；2）动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。4.简述回溯法的基本思想。回溯法的基本做法是搜索，在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。将递归算法转化为非递归算法的方法主要有：1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2）用递推来实现递归函数。3）通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。6.简要分析分支限界法与回溯法的异同。1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。算法复杂性度量主要包括算法的时间复杂性和算法的空间复杂性。8.贪心算法求解的问题主要具有哪些性质？简述之。贪心算法求解的问题一般具有二个重要的性质：一是贪心选择性质，这是贪心算法可行的第一个基本要素；另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。分治法的基本思想：将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1A[mid])right=mid-1;elseleft=mid+1;}return-1;}（3）递归算法：输入：递减数组A[left:right]，待搜索元素v。输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：intBinarySearch(intA[],intleft,intright,intv){intmid;if(left<=right){mid=int((left+right)/2);if(v==A[mid])returnmid;elseif(v>A[mid])returnBinarySearch(A,left,mid-1,v);elsereturnBinarySearch(A,mid+1,right,v);}elsereturn-1;}（4）搜索18：首先与27比较，18<27，在后半部分搜索；再次与18比较，搜索到，返回5。搜索31：首先与27比较，31>27，在前半部分搜索；再次32比较，31<32，在后半部分搜索，与29比较，31>29，此时只有一个元素，未找到，返回-1。搜索135：首先与27比较，135>27，在前半部分搜索；再次32比较，135>32，在前半部分搜索；与135比较，相同，返回0。3.已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序（要求给出计算步骤）。解：使用动态规划算法进行求解。求解矩阵为：12345610150330405165520102036033024301950301809301770403000186050150060123456101224220222230344404450560因此，最佳乘积序列为（A1A2）（（A3A4）（A5A6）），共执行乘法2010次。4.根据分枝限界算法基本过程，求解0-1背包问题。已知，n=3，M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。解：用x(i)表示第i步选择的物品号，x(1)=1，(２)＝0，U(2)＝23;x(1)=2，(3)＝15，U(3)＝25,x(1)=3，(4)＝28，U(4)＝28,U=min{23,25,28}=23,由于(4)＝28>U所以节点４删除。活节点表Ｌ={2,3}，取最小代价估值节点２作为扩展节点：x(2)=2，w1+w2>M，节点5是不合理节点；x(2)=3，这是答案节点c(6)=13，即找到了代价为13的解，修改U＝13，由于活节点表中的节点3有(3)＝25，所以节点3可以删除。这时L＝｛｝，算法结束。最优解X={1,3}搜索产生的状态空间树如下图：12561230251528U=23734X1=1X1=2X2=3X1=3X2=223013131515节点6是答案节点5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。解：intgreedy(vecterx,intn){intsum=0,k=x.size();for(intj=0;jn){cout<<”Nosolution”<n){sum++;s=x[i];}}returnsum;}6、试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：(1)删除一个字符。(2)插入一个字符。(3)将一个字符改为另一个字符。请写出该算法。解：此题用动态规划算法求解：intdist(){intm=a.size();intn=b.size();vectord(n+1,0);for(inti=1;i<=n;i++)d[i]=i;for(i=1;i<=m;i++){inty=i-1;for(intj=1;j<=n;j++){intx=y;y=d[j];intz=j>1?d[j-1]:i;intdel=a[i-1]==b[j-1]?0:1;d[j]=min(x+del,y+1,z+1);}}returnd[n];}7、对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。解：用V1表示已经找到最短路径的顶点，V2表示与V1中某个顶点相邻接且不在V1中的顶点；E1表示加入到最短路径中的边，E2为与V1中的顶点相邻接且距离最短的路径。步骤V1V2E1E2{a}{b}{}{ab}{a,b}{d}{ab}{bd}{a,b,d}{c,f}{ab,bd}{dc,df}{a,b,d,c}{f}{ab,bd}{df}{a,b,c,d,f}{e}{ab,bd,dc,df}{fe}{a,b,c,d,e,f}{g}{ab,bd,dc,df,fe}{eg}{a,b,c,d,e,f,g}{h}{ab,bd,dc,df,fe,eg}{gh}{a,b,c,d,e,f,g,h}{}{ab,bd,de,df,fe,eg,gh}{}结果：从a到h的最短路径为，权值为18。求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。8、试写出用分治法对数组A[n]实现快速排序的算法。解：用分治法求解的算法代码如下：intpartition(floatA[],intp,intr){inti=p,j=r+1;floatx=a[p];while(1){while(a[++i]x);if(i>=j)break;a[i]};a[p]=a[j];a[j]=x;returnj;}voidQuicksort(floata[],intp,intr){if(pxk，|xi-xj|max)max=A[i];if(A[i]voidPerm(Typelist[],intk,intm){if(k==m){for(inti=0;i<=m;i++)cout<intok(Typelist[],intk,inti){if(i>k)for(intt=k;tvoidKnapsack(Typev,intw,intc,intn,Type**m){IntjMax=min(w[n]-1,c);for(intj=0;j<=jMax;j++)m[n][j]=0;for(intj=w[n];j<=c;j++)m[n][j]=v[n];for(inti=n-1;i>1;i--){jMax=min(w[i]-1,c);for(intj=0;j<=jMax;j++)m[i][j]=m[i+1][j];for(intj=w[i];j<=c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);};m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}TemplateVoidTraceback(Type**m,intw,intc,intn,intx){for(inti=1;ia[k]){k++;a[k]=a[k-1]+1;n-=a[k];};if(n==a[k]){a[k]++;n--;};for(inti=0;iintBinarySearch(Typea[],constType&x,intn){//假定数组a[]已按非递减有序排列，本算法找到x后返回其在数组a[]中的位置，//否则返回-1intleft=0,right=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle+1;if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;}17、试用动态规划算法实现最长公共子序列问题，请写出该算法。解：用动态规划算法求解的算法代码如下：intlcs_len(char*a,char*b,intc[][N]){intm=strlen(a),n=strlen(b),i,j;for(i=0;i<=m;i++)c[i][0]=0;for(j=1;j<=n;j++)c[0][j]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(a[i-1]==b[j-1])c[i][j]=c[i-1][j-1]+1;elseif(c[i-1][j]>=c[i][j-1])c[i][j]=c[i-1][j];elsec[i][j]=c[i][j-1];returnc[m][n];};char*build_lcs(chars[],char*a,char*b){intk,i=strlen(a),j=strlen(b),c[N][N];k=lcs_len(a,b,c);s[k]=’\0’;while(k>0){if(c[i][j]==c[i-1][j])i--;elseif(c[i][j]==c[i][j-1])j--;else{s[--k]=a[i-1];i--,j--;}}returns;}18、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题，请写出状态空间搜索树。物品ABCDEFG重量35306050401025价值10403050354030解：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：a．b.c．d.e.f.g.h.i.j.在Q1处获得该问题的最优解为，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。19、求解子集和问题：对于集合S={1，2，6，8}，求子集，要求该子集的元素之和d=9。①画出子集和问题的解空间树；②该树运用回溯算法，写出依回溯算法遍历节点的顺序；③如果S中有n个元素，指定d，用伪代码描述求解子集和问题的回溯算法。解答：满足要求的子集有[1，2，6]，[1，8]①解空间树如下：R1P1T1X1V1Ô1Z1Â1U0S0W0Y0Ê0Û0Î0Q0②遍历结点的顺序为：ABDHPQIRSEJTUKVWCFLXYMZÊGNÔÛOÂÎ③用伪代码描述算法如下：#include#defineN100intas=0,t=0;intsum;voidbacktrackiter(inti,ints[],intn,intd,intsum){if(i>n)return;else{if(as==d){t++;return;}sum-=s[i];if(as+s[i]<=d){as+=s[i];backtrackiter(i+1,s,n,d,sum);as-=s[i];}if(as+sum>=d)backtrackiter(i+1,s,n,d,sum);sum+=s[i];}}20、求解填字游戏问题：在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试采用回溯法写出满足这个要求的一种数字填法的算法和满足这个要求的全部数字填法的算法。解：为找到一个满足要求的9个数的填法，从还未填一个数开始，按某种顺序（如从小到大的顺序）每次在当前位置填入一个整数，然后检查当前填入的整数是否能满足要求。在满足要求的情况下，继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求，就改变填入的整数。如对当前方格试尽所有可能的整数，都不能满足要求，就得回退到前一方格，并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查，直到找到一个满足问题要求的解，将解输出。回溯法找一个解的算法：{intm=0,ok=1;intn=8;do{if(ok)扩展;else调整;ok=检查前m个整数填放的合理性;}while((!ok||m!=n)&&(m!=0))if(m!=0)输出解;else输出无解 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 ；}如果要找全部解，则在将找到的解输出后，应继续调整最后位置上填放的整数，试图去找下一个解。相应的算法如下：回溯法找全部解的算法：{intm=0,ok=1;intn=8;do{if(ok){if(m==n){输出解；调整；}else扩展;}else调整;ok=检查前m个整数填放的合理性;}while(m!=0);}21、试用动态规划算法实现最大子矩阵和问题：求矩阵A的一个子矩阵，使其各元素之和为最大。解：解答如下：intMaxSum2(intm,intn,int**a){intsum=0;int*b=newint[n+1];for(inti=1;i<=m;i++){for(intk=1;k<=n;k++)b[k]=0;for(intj=i;j<=m;j++){for(intk=1;k<=n;k++)b[k]+=a[j][k];intmax=MaxSum(n,b);if(max>sum)sum=max;}}returnsum;}intMaxSum(intn,int*a){intsum=0,b=0;for(inti=1;i<=n;i++){if(b>0)b+=a[i];elseb=a[i];if(b>sum)sum=b;}Returnsum;}22、试用回溯法解决下列整数变换问题：关于整数的变换和定义如下：。对于给定的两个整数和，要求用最少的变换和变换次数将变为。解：解答如下：voidcompute(){k=1;while(!search(1,n)){k++;if(k>maxdep)break;init();};if(found)output();elsecout<<”NoSolution!”<k)returnfalse;for(inti=0;i<2;i++){intn1=f(n,i);t[dep]=i;if(n1==m||search(dep+1,n1)){Found=true;Out();returntrue;}returnfalse;}23、关于15谜问题。在一个4×4的方格的棋盘上，将数字1到15代表的15个棋子以任意的顺序置入各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为了有效的移动，设计了估值函数C1(x)，表示在结点x的状态下，没有到达目标状态下的正确位置的棋子的个数。请使用该估计函数，对图示的初始状态，给出使用分支限界方法转换到目标状态的搜索树。124563791012813141115123456789101112131415初始状态目标状态解：