算法分析与设计复习题及参考复习资料.docx

《算法分析与设计复习题及参考复习资料.docx》由会员分享，可在线阅读，更多相关《算法分析与设计复习题及参考复习资料.docx（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、网络教化课程考试复习题及参考答案算法分析及设计一、名词说明：1.算法2.程序3.递归函数4.子问题的重叠性质5.队列式分支限界法6.多机调度问题7.最小生成树二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。2.简述回溯法解题的主要步骤。3.简述动态规划算法求解的根本要素。4.简述回溯法的根本思想。5.简要分析在递归算法中消退递归调用，将递归算法转化为非递归算法的方法。6.简要分析分支限界法及回溯法的异同。7.简述算法困难性的概念，算法困难性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的根本思想是什么？合并排序的根本思想是什么？请分别简述之。10

2、.简述分析贪心算法及动态规划算法的异同。三、算法编写及算法应用分析题：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

3、=12，r5=5，r6=50，r7=6，求矩阵链积A1A2A3A4A5A6的最佳求积依次（要求给出计算步骤）。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，这里所说的字符操作包括：删除一个字符。插入一个字符。将一

4、个字符改为另一个字符。请写出该算法。7.对于下图运用Dijkstra算法求由顶点a到顶点h的最短途径。8.试写出用分治法对数组An实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为si，f i，活动i,j相容的条件是：sjf i，问题的解表示为(xi| xi =1，2，n,)，xi表示依次为i的活动编号活动，求一个相容的活动子集，且支配的活动数目最多。10.设x1、x2、x3是一个三角形的三条边，而且x1+x2+x3=14。请问有多少种不同的三角形？给出解答过程。11.设数组A有n个元素，须要找出其中的最大最小值。请给出一个解决方法，并分析其困难性。把n个元素等分为两

5、组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比拟，求出全部元素的最大值和最小值。假如A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描绘，并分析其困难性。12.有n个程序和长度为L的磁带，程序i的长度为ai，已知，求最优解(xi，x2 ，.，xi， xn)，xi =0，1, xi =1，表示程序i存入磁带，xi =0，表示程序i不存入磁带，满意，且存放的程序数目最多。13.试用分治法实现有重复元素的排列问题：设是要进展排列的个元素，其中元素可能一样，试设计计算的全部不同排列的算法。

6、14.试用动态规划算法实现0-1闭包问题，请写出该算法。15.试用贪心算法求解下列问题：将正整数n分解为若干个互不一样的自然数之和，使这些自然数的乘积最大，请写出该算法。16.试写出用分治法对一个有序表实现二分搜寻的算法。17.试用动态规划算法实现最长公共子序列问题，请写出该算法。18.假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包涵量M150，运用回溯方法求解此背包问题，请写出状态空间搜寻树。物品ABCDEFG重量35306050401025价值1040305035403019.求解子集和问题：对于集合S=1，2 ，6，8，求子集，要求该子集的元素之和d=9。画出

7、子集和问题的解空间树；该树运用回溯算法，写出依回溯算法遍历节点的依次；假如S中有n个元素，指定d，用伪代码描绘求解子集和问题的回溯算法。20.求解填字嬉戏问题：在33个方格的方阵中要填入数字1到N（N10）内的某9个数字，每个方格填一个整数，似的全部相邻两个方格内的两个整数之和为质数。试采纳回溯法写出满意这个要求的一种数字填法的算法和满意这个要求的全部数字填法的算法。21.试用动态规划算法实现最大子矩阵和问题：求矩阵A的一个子矩阵，使其各元素之和为最大。22.试用回溯法解决下列整数变换问题：关于整数的变换和定义如下：。对于给定的两个整数和，要求用最少的变换和变换次数将变为。23.关于15谜问题

8、。在一个44的方格的棋盘上，将数字1到15代表的15个棋子以随意的依次置入各方格中，空出一格。要求通过有限次的挪动，把一个给定的初始状态变成目的状态。挪动的规则是：每次只能把空格四周的四格数字（棋子）中的随意一个移入空格，从而形成一个新的状态。为了有效的挪动，设计了估值函数C1(x)，表示在结点x的状态下，没有到达目的状态下的正确位置的棋子的个数。请运用该估计函数，对图示的初始状态，给出访用分支限界方法转换到目的状态的搜寻树。124563791012813141115123456789101112131415初始状态 目的状态参考答案一、名词说明：1.算法：算法是指解决问题的一种方法或一个过程

9、。算法是若干指令的有穷序列，满意性质：（1）输入：有零个或多个外部量作为算法的输入；（2）输出：算法产生至少一个量作为输出；（3）确定性：组成算法的每条指令清楚、无歧义；（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。2.程序：程序是算法用某种程序设计语言的详细实现。3.递归函数：用函数自身给出定义的函数称为递归函数。4.子问题的重叠性质：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算屡次，这种性质称为子问题的重叠性质。5.队列式分支限界法：队列式(FIFO)分支限界法是将活结点表组织成一个队列，并依据队列的先进先出（FIFO）原则选取下一个结点

10、为扩展结点。6.多机调度问题：多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。同时约定每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。7.最小生成树：G=(V,E)是无向连通带权图，G的子图称为G的生成树，生成树上各边权的总和称为该生成树的消耗，在G的全部生成树中，消耗最小的生成树称为G的最小生成树。二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。备忘录方法是动态规划算法的变形。及动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次须要解此问题时，只要简洁地查看该子问题的解答

11、，而不必重新计算。备忘录方法及动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的限制构造及干脆递归方法的限制构造一样，区分在于备忘录方法为每个解过的子问题建立了备忘录以备须要时查看，避开了一样的子问题的重复求解，而干脆递归方法没有此功能。2.简述回溯法解题的主要步骤。回溯法解题的主要步骤包括：1）针对所给问题，定义问题的解空间；2）确定易于搜寻的解空间构造；3）以深度优先方式搜寻解空间，并在搜寻过程中用剪枝函数避开无效搜寻。3.简述动态规划算法求解的根本要素。动态规划算法求解的根本要素包括：1）最优子构造是问题能用动态规划算法求解的前提

12、；2）动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次须要解此子问题时，只是简洁地用常数时间查看一下结果，即重叠子问题。4.简述回溯法的根本思想。回溯法的根本做法是搜寻，在问题的解空间树中，按深度优先策略，从根结点动身搜寻解空间树。算法搜寻至解空间树的随意一点时，先推断该结点是否包含问题的解。假如确定不包含，则跳过对该结点为根的子树的搜寻，逐层向其祖先结点回溯；否则，进入该子树，接着按深度优先策略搜寻。5.简要分析在递归算法中消退递归调用，将递归算法转化为非递归算法的方法。将递归算法转化为非递归算法的方法主要有：1）采纳一个用户定义的栈来模拟系统的递归调用工作栈。该方法

13、通用性强，但本质上还是递归，只不过人工做了原来由编译器做的事情，优化效果不明显。2）用递推来实现递归函数。3）通过Cooper变换、反演化换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空困难度上均有较大改善，但其适用范围有限。6.简要分析分支限界法及回溯法的异同。1）求解目的：回溯法的求解目的是找出解空间树中满意约束条件的全部解，而分支限界法的求解目的则是找出满意约束条件的一个解，或是在满意约束条件的解中找出在某种意义下的最优解。 2）搜寻方式的不同：回溯法以深度优先的方式搜寻解空间树，而分支限界法则以广度优先或以最小消耗优先的方式搜寻解空间树。7.简述算法困难性的概念，算法困难

14、性度量主要指哪两个方面？算法困难性是算法运行所须要的计算机资源的量，须要时间资源的量称为时间困难性，须要的空间资源的量称为空间困难性。这个量应当只依靠于算法要解的问题的规模、算法的输入和算法本身的函数。假如分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示困难性，那么，应当有C=F(N,I,A)。算法困难性度量主要包括算法的时间困难性和算法的空间困难性。8.贪心算法求解的问题主要具有哪些性质？简述之。贪心算法求解的问题一般具有二个重要的性质：一是贪心选择性质，这是贪心算法可行的第一个根本要素；另一个是最优子构造性质，问题的最优子构造性质是该问题可用贪心算法求解的关键特征

15、。9.分治法的根本思想是什么？合并排序的根本思想是什么？请分别简述之。分治法的根本思想：将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1kn，而且子问题及原问题性质一样，原问题的解可由这些子问题的解合并得出。合并排序根本思想：将待排序元素分成大小大致一样的2个子集合，分别对2个子集合进展排序，最终将排好序的子集合合并成为所要求的排好序的集合。10.简述分析贪心算法及动态规划算法的异同。贪心算法和动态规划算法都要求问题具有最优子构造性质，这是两类算法的一个共同点。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进展，以迭代的方式作出相继的贪心选择

16、，每作一次贪心选择就将所求问题简化为规模更小的子问题。三、算法编写及算法应用分析题：1.已知有3个物品：(w1,w2,w3)=(12,10,6), (p1,p2,p3)=(15,13,10), 背包的容积M=20，依据0-1背包动态规划的递推式求出最优解。解：依据递推式 fi（X）maxfi-1(X)，fi-l(Xwi)+pi |Xwi 从i=1开场，最终得到fn（M）f1(1) f1(11)= 0 f1(12) f1(20)= p1=15f2(1) f2(9)= 0f2(10) f2(11)= maxf1(10)，f1(10 w2)+p2 =13f2(12) f2(20)= maxf1(12

17、)，f1(12 w2)+p2=15f3(20)=maxf2(20)，f2(20 w3)+p3 = f2(20 6)+10=25可获得的最大利润为25，最优解为：（1，0，1）2.按要求完成以下关于排序和查找的问题。（1） 对数组A=15，29，135，18，32，1，27，25，5，用快速排序方法将其排成递减序。（2） 请描绘递减数组进展二分搜寻的根本思想，并给出非递归算法。（3） 给出上述算法的递归算法。（4） 运用上述算法对（1）所得到的结果搜寻如下元素，并给出搜寻过程：18，31，135。解：（1）第一步：15 29 135 18 32 1 27 25 5 第二步：29 135 18 3

18、2 27 25 15 1 5 第三步：135 32 29 18 27 25 15 5 1 第四步：135 32 29 27 25 18 15 5 1 （2）根本思想：首先将待搜寻元素v及数组的中间元素进展比拟，假如，则在前半局部元素中搜寻v；若，则搜寻胜利；否则在后半局部数组中搜寻v。非递归算法：输入：递减数组Aleft:right，待搜寻元素v。输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：【3分】int BinarySearch(int A,int left,int right,int v)int mid;while (leftAmid) right=mid-1;else

19、left=mid+1;return -1;（3）递归算法：输入：递减数组Aleft:right，待搜寻元素v。输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：int BinarySearch(int A,int left,int right,int v)int mid;if (leftAmid) return BinarySearch(A,left,mid-1,v);else return BinarySearch(A,mid+1,right,v);elsereturn -1;（4）搜寻18：首先及27比拟，1827，在前半局部搜寻；再次32比拟，3129，此时只有一个元素，未找

20、到，返回-1。 搜寻135：首先及27比拟，13527，在前半局部搜寻；再次32比拟，13532，在前半局部搜寻；及135比拟，一样，返回0。3.已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1A2A3A4A5A6的最佳求积依次（要求给出计算步骤）。解：运用动态规划算法进展求解。求解矩阵为：12345610150330405165520102036033024301950301809301770403000186050150060123456101224220222230344404450560因此，最佳乘积序列为（A

21、1A2）（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=min23,25,28=23, 由于(4)28U 所以节点删除。活节点表=2,3，取最小代价估值节点作为扩展节点：x(2)=2，w1+w2M，节点5是不合理节点；x(2)=3，这是答案节点c(6)=13，即找到了

22、代价为13的解，修改U13，由于活节点表中的节点3有(3)25，所以节点3可以删除。这时L ，算法完毕。最优解X=1,3搜寻产生的状态空间树如下图：12561230251528U=23734X1=1X1=2X2=3X1=3X2=223013131515节点6是答案节点5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。解：int greedy(vecterx,int n) int sum=0,k=x.size();for(int j=0;jn) cout”No solution

23、”endl; return -1;for(int i=0,s=0;in) sum+;s=xi; return sum;6、试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：(1)删除一个字符。(2)插入一个字符。(3)将一个字符改为另一个字符。请写出该算法。解：此题用动态规划算法求解：int dist( ) int m=a.size( ); int n=b.size( ); vectord(n+1,0);for(int i=1;i=n;i+) di=i;for(i=1;i=m;i+) int y=i-1; for(in

24、t j=1;j1?dj-1:i;int del=ai-1= =bj-1?0:1; dj=min(x+del,y+1,z+1);return dn;7、对于下图运用Dijkstra算法求由顶点a到顶点h的最短途径。解：用V1表示已经找到最短途径的顶点，V2表示及V1中某个顶点相邻接且不在V1中的顶点；E1表示参加到最短途径中的边，E2为及V1中的顶点相邻接且间隔 最短的途径。步骤 V1 V2 E1 E21. ab ab2. a,bd ab bd3. a,b,d c,f ab,bd dc,df4. a,b,d,c f ab,bd df5. a,b,c,d,f e ab,bd,dc,df fe6.

25、a,b,c,d,e,fg ab,bd,dc,df,fe eg7. a,b,c,d,e,f,gh ab,bd,dc,df,fe,eggh8. a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 结果：从a到h的最短途径为，权值为18。求全部顶点对之间的最短途径可以运用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短途径，最终可以求得全部顶点对之间的最短途径。8、试写出用分治法对数组An实现快速排序的算法。解：用分治法求解的算法代码如下： int partition(float A,int p,int r) int i=p,j=r+1; floa

26、t x=ap; while (1) while(a+ix); if(i=j) break; aiap=aj; aj=x; return j; void Quicksort( float a, int p, int r ) if( pxk，|xi-xj|xk，（i,j,k=1,2,3），依据x1+x2+x3=14可知1xi7（i=1,2,3）。利用回溯法求解得到：即有4个可行解：（6，6，2），（6，5，3），（6，4，4，）（5，5，4）。11、设数组A有n个元素，须要找出其中的最大最小值。（1） 请给出一个解决方法，并分析其困难性。（2） 把n个元素等分为两组A1和A2，分别求这两组的最大值

27、和最小值，然后分别将这两组的最大值和最小值相比拟，求出全部元素的最大值和最小值。假如A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描绘，并分析其困难性。解：（1）根本思想：从头到尾逐个扫描，纪录最大和最小元素。输入：具有n个元素的数组输出：最大值和最小值步骤：void FindMaxMin(int A, int n, int max, int min)max=min=A0;for (i=1;imax) max=Ai;if (Aimin) min=Ai;困难性分析：由于是从头到尾扫描各个元素，而每个元素都要及max

28、和min比拟一遍，从而时间困难性为：O(n)。（2）void FindMaxMin(int left,int right, int max, int min)if (left=right) max=min=Aleft;else if (left=right-1)max=(AleftAright?Aright:Aleft);min=( AleftAright?Aleft:Aright);elsemid=(left+right)/2;FindMaxMin(left,mid,gmax,gmin);FindMaxMin(mid+1,right,hmax,hmin);max=(gmaxhmax?hmax

29、:gmax);min=(gminhmin?gmin:hmin);12、有n个程序和长度为L的磁带，程序i的长度为ai，已知，求最优解(xi，x2 ，.，xi， xn)，xi =0，1, xi =1，表示程序i存入磁带，xi =0，表示程序i不存入磁带，满意，且存放的程序数目最多。解：由于目的是存放的程序数目最多，所以最优量度应当是minai | ai为程序i的长度，即每次选入的程序都是当前最短的。我们可以将n个程序按a1a2an依次排序，然后从i=1开场依次选择。算法如下：procedure programming(L,n, a, x)begin /n个程序按a1a2an依次排序x0; i=1

30、; while (ai L and in) do xi 1; LL-ai；ii+ 1; end.13、试用分治法实现有重复元素的排列问题：设是要进展排列的个元素，其中元素可能一样，试设计计算的全部不同排列的算法。解：解答如下：Templatevoid Perm(Type list,int k,int m) if(k= =m) for(int i=0;i=m;i+) coutlisti; coutendl;else for(int i=k;i=m;i+) if(ok(list,k,i) sk,listi);Perm(list,k+1,m); sk,listi); 其中ok用于判别重复元素。Tem

31、plate int ok(Type list,int k,int i) if(ik) for(int t=k;tI;t+) if(listt= =listi) return 0; return 1;14、试用动态规划算法实现0-1闭包问题，请写出该算法。解：解答如下：Templatevoid Knapsack(Type v,int w,int c,int n,Type *m)Int jMax=min(wn-1,c); for(int j=0;j=jMax;j+) mnj=0; for(int j=wn;j1;i-) jMax=min(wi-1,c); for(int j=0;j=jMax;j+

32、) mij=mi+1j; for(int j=wi;j=w1) m1c=max(m1c,m2c-w1+v1); TemplateVoid Traceback(Type *m,int w,int c,int n,int x) for(int i=1;in;i+) if(mic= =mi+1c) xi=0;else xi=1,c-=wi;xn=(mnc)?1:0;15、试用贪心算法求解下列问题：将正整数n分解为若干个互不一样的自然数之和，使这些自然数的乘积最大，请写出该算法。解：解答如下：void dicomp(int n,int a) k=1;if(n3) a1=0;return;if(nak)

33、 k+; ak=ak-1+1; n-=ak;if(n= =ak) ak+;n-;for(int i=0;in;i+) ak-i+;16、试写出用分治法对一个有序表实现二分搜寻的算法。解：解答如下：Template int BinarySearch(Type a,const Type& x,int n)/假定数组a已按非递减有序排列，本算法找到x后返回其在数组a中的位置，/否则返回-1 int left=0,right=n-1; while(leftamiddle) left=middle+1; else right=middle-1;return -1;17、试用动态规划算法实现最长公共子序列

34、问题，请写出该算法。解：用动态规划算法求解的算法代码如下： int lcs_len(char *a,char *b,int cN) int m=strlen(a),n=strlen(b),i,j; for(i=0;i=m;i+) ci0=0; for(j=1;j=n;j+) c0j=0; for(i=1;i=m;i+) for(j=1;j=cij-1) cij=ci-1j; else cij=cij-1; return cmn; char *build_lcs(char s,char *a,char *b) int k,i=strlen(a),j=strlen(b),cNN; k=lcs_le

35、n(a,b,c); sk=0; while(k0) if(cij= =ci-1j) i-; else if(cij= =cij-1) j-; else s-k=ai-1; i-,j-;return s; 18、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包涵量M150，运用回溯方法求解此背包问题，请写出状态空间搜寻树。物品ABCDEFG重量35306050401025价值10403050354030解：依据单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为17。则可消费如下的状态空间搜寻树。其中各个节点处的限界函数值通过如下方式求得：ab.

36、cd. 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解空间树如下：R1P1T1X1V11Z11U0S0W0Y0000Q0遍历结点的依次为：A B D H P Q I R S E J T U K V W C F L X Y M Z G N O 用伪代码描绘算法如下：#include#define N 100int