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

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

2、。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.已知 ，1()*ikkijrAak=1，2，3，4，

3、5，6， r1=5， r2=10， r3=3， r4=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 是两个字符串。我们要用最少的字符操作，将字

4、符串 A 转换为字符串 B，这里所说的字符操作包括：删除一个字符。插入一个字符。将一个字符改为另一个字符。请写出该算法。7.对于下图使用 Dijkstra 算法求由顶点 a 到顶点 h 的最短路径。ahgfedcb121228232238.试写出用分治法对数组 An实现快速排序的算法。9.有 n 个活动争用一个活动室。已知活动 i 占用的时间区域为s i，f i，活动 i,j 相容的条件是：sjf i，问题的解表示为(x i| xi =1，2，n,)，x i表示顺序为 i 的活动编号活动，求一个相容的活动子集，且安排的活动数目最多。10.设 x1、 x2、 x3是一个三角形的三条边，而且 x1

5、+x2+x3=14。请问有多少种不同的三角形？给出解答过程。11.设数组 A 有 n 个元素，需要找出其中的最大最小值。请给出一个解决方法，并分析其复杂性。把 n 个元素等分为两组 A1 和 A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果 A1 和 A2 中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。12.有 n 个程序和长度为 L 的磁带，程序 i 的长度为 ai，已知 ，求最优解(x i，x 2 Lni1，.，x i， xn)，x i

6、 =0，1, xi =1，表示程序 i 存入磁带， xi =0，表示程序 i 不存入磁带，满足 ，且存放的程序数目最多。anii113.试用分治法实现有重复元素的排列问题：设 是要进行排列的 个元素，其中元素),.21nrRn可能相同，试设计计算 的所有不同排列的算法。nr,.2114.试用动态规划算法实现 0-1 闭包问题，请写出该算法。15.试用贪心算法求解下列问题：将正整数 n 分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，请写出该算法。16.试写出用分治法对一个有序表实现二分搜索的算法。17.试用动态规划算法实现最长公共子序列问题，请写出该算法。18.假设有 7 个物品，它

7、们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量 M150，使用回溯方法求解此背包问题，请写出状态空间搜索树。物品 A B C D E F G重量 35 30 60 50 40 10 25价值 10 40 30 50 35 40 3019.求解子集和问题：对于集合 S=1，2 ，6，8，求子集，要求该子集的元素之和 d=9。画出子集和问题的解空间树；该树运用回溯算法，写出依回溯算法遍历节点的顺序；如果 S 中有 n 个元素，指定 d，用伪代码描述求解子集和问题的回溯算法。20.求解填字游戏问题：在 33 个方格的方阵中要填入数字 1 到 N（N10）内的某 9 个数字，每个方格填一

8、个整数，似的所有相邻两个方格内的两个整数之和为质数。试采用回溯法写出满足这个要求的一种数字填法的算法和满足这个要求的全部数字填法的算法。21.试用动态规划算法实现最大子矩阵和问题：求 矩阵 A 的一个子矩阵，使其各元素之和为最大。nm22.试用回溯法解决下列整数变换问题：关于整数 的变换 和 定义如下： 。对ifg2/)(;3)(igif于给定的两个整数 和 ，要求用最少的变换 和 变换次数将 变为 。nmfnm23.关于 15 谜问题。在一个 44 的方格的棋盘上，将数字 1 到 15 代表的 15 个棋子以任意的顺序置入各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标

9、状态。移动的规则是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为了有效的移动，设计了估值函数 C1(x)，表示在结点 x 的状态下，没有到达目标状态下的正确位置的棋子的个数。请使用该估计函数，对图示的初始状态，给出使用分支限界方法转换到目标状态的搜索树。初始状态 目标状态1 2 45 6 3 79 10 12 813 14 11 151 2 3 45 6 7 89 10 11 1213 14 15参考答案一、名词解释：1.算法：算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：（1）输入：有零个或多个外部量作为算法的输入；（2）输出

10、：算法产生至少一个量作为输出；（3）确定性：组成算法的每条指令清晰、无歧义；（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。2.程序：程序是算法用某种程序设计语言的具体实现。3.递归函数：用函数自身给出定义的函数称为递归函数。4.子问题的重叠性质：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。5.队列式分支限界法：队列式(FIFO)分支限界法是将活结点表组织成一个队列，并按照队列的先进先出（FIFO）原则选取下一个结点为扩展结点。6.多机调度问题：多机调度问题要求给出一种作业调度方案，使所给的 n 个作业在尽可

11、能短的时间内由m 台机器加工处理完成。同时约定每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。7.最小生成树：G=(V,E)是无向连通带权图，G 的子图称为 G 的生成树，生成树上各边权的总和称为该生成树的耗费，在 G 的所有生成树中，耗费最小的生成树称为 G 的最小生成树。二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是

12、自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。2.简述回溯法解题的主要步骤。回溯法解题的主要步骤包括：1）针对所给问题，定义问题的解空间；2）确定易于搜索的解空间结构；3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。3.简述动态规划算法求解的基本要素。动态规划算法求解的基本要素包括：1）最优子结构是问题能用动态规划算法求解的前提；2）动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当

13、再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。4.简述回溯法的基本思想。回溯法的基本做法是搜索，在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。将递归算法转化为非递归算法的方法主要有：1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不

14、明显。2）用递推来实现递归函数。3）通过 Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。6.简要分析分支限界法与回溯法的异同。1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？算法复杂性是算法运行所需要的计算机资源的量，需

15、要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用 N、 I 和 A 表示算法要解问题的规模、算法的输入和算法本身，而且用 C 表示复杂性，那么，应该有 C=F(N,I,A)。算法复杂性度量主要包括算法的时间复杂性和算法的空间复杂性。8.贪心算法求解的问题主要具有哪些性质？简述之。贪心算法求解的问题一般具有二个重要的性质：一是贪心选择性质，这是贪心算法可行的第一个基本要素；另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。9.分治法的基本思想是什么？合并排序的基本思想是什么

16、？请分别简述之。分治法的基本思想：将 n 个输入分成 k 个不同子集合，得到 k 个不同的可独立求解的子问题，其中1Amid) right=mid-1;else 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 Binary

17、Search(A,mid+1,right,v);elsereturn -1;（4）搜索 18：首先与 27 比较，1827，在前半部分搜索；再次 32 比较，3129，此时只有一个元素，未找到，返回-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，()1*kkijirAa求矩阵链积 A1A2A3A4A5A6的最佳求积顺序（要求给出计算步骤） 。解：使用动态规划算法进行

18、求解。求解矩阵为：1 2 3 4 5 61 0 150 330 405 1655 20102 0 360 330 2430 19503 0 180 930 17704 0 3000 18605 0 15006 0因此，最佳乘积序列为（A 1A2） （A 3A4） （A 5A6） ） ，共执行乘法 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 ;cx(1)=2， (3)15，U(3)

19、25, x(1)=3， (4)28，U (4)28 , cU=min23,25,28=23, 由于 (4)28U 所以节点删除。活节点表=2,3，取最小代价估值节点c作为扩展节点：x(2)=2，w1+w2M，节点 5 是不合理节点；x(2)=3，这是答案节点 c(6)=13，即找到了代价为 13 的解，修改 U13，由于活节点表中的节点 3 有 (3)25，所以节点 3 可以删除。c这时 L ，算法结束。最优解 X=1,3搜索产生的状态空间树如下图：1 2 3 4 5 61 0 1 2 2 4 22 0 2 2 2 23 0 3 4 44 0 4 45 0 56 0125 61230 2515

20、 28 U=2373 4X1=1X1=2X2=3X1=3X2=223013131515节点 6 是答案节点5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶 n 公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。解：int greedy(vecterx,int n)int sum=0,k=x.size();for(int j=0;jn)coutn) sum+;s=xi; return sum; 6、试用动态规划算法实现下列问题：设 A 和 B 是两个字符串。我们要用最少的字符操作，将字符串 A 转换为字符串 B，这里所说的字符

21、操作包括：(1)删除一个字符。(2)插入一个字符。(3)将一个字符改为另一个字符。请写出该算法。解：此题用动态规划算法求解：int dist( )int m=a.size( );int n=b.size( );vectord(n+1,0); for(int i=1;i1?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 的最短路径。ahgfedcb12122823223解：用 V1表示已经找到最短路径的顶点，V 2表示与 V1中某个顶点相邻接且不在

22、 V1中的顶点；E 1表示加入到最短路径中的边，E 2为与 V1中的顶点相邻接且距离最短的路径。步骤 V 1 V2 E1 E21. a b ab2. a,b d 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. a,b,c,d,e,f g ab,bd,dc,df,fe eg7. a,b,c,d,e,f,g h ab,bd,dc,df,fe,eg gh8. a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 结果：从 a 到 h 的最短路径为 ，权值为 18。a

23、bdfegh求所有顶点对之间的最短路径可以使用 Dijkstra 算法，使其起始节点从 a 循环到 h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。8、试写出用分治法对数组 An实现快速排序的算法。解：用分治法求解的算法代码如下：int partition(float A,int p,int r)int i=p,j=r+1;float x=ap;while (1) while(a+ix);if(i=j) break;ai ;ja;ap=aj;aj=x;return j; void Quicksort( float a, int p, int r )if( pxk，

24、|xi-xj|xk， （i,j,k=1,2,3） ，根据x1+x2+x3=14 可知 1xi7（i=1,2,3） 。利用回溯法求解得到：55 4 3 53 4x1= 6x2= 6x3= 24即有 4 个可行解：（6，6，2） ， （6，5，3） ， （6，4，4， ） （5，5，4） 。11、设数组 A 有 n 个元素，需要找出其中的最大最小值。（1） 请给出一个解决方法，并分析其复杂性。（2） 把 n 个元素等分为两组 A1 和 A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果 A1 和 A2 中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。解：（1）基本思想：从头到尾逐个扫描，纪录最大和最小元素。输入：具有 n 个元素的数组输出：最大值和最小值