1、-网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法2.程序3.递归函数4.子问题的重叠性质5.队列式分支限界法6.多机调度问题7.最小生成树二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。2.简述回溯法解题的主要步骤。3.简述动态规划算法求解的基本要素。4.简述回溯法的基本思想。5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。1
2、0.简述分析贪心算法与动态规划算法的异同。三、算法编写及算法应用分析题：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，r
3、4=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(
17、12)，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
18、 32 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;els
19、e 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因此，最佳乘积序列为
21、（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=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 soluti
23、on”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(
24、int 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; flo
26、at x=ap; while (1) while(a+ix); if(i=j) break; ai ;ap=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;复杂性分析：由于是从头到尾扫描各个元素，而每个元素都要与
28、max和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?h
29、max: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;
30、i=1; 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用于判别重复元
31、素。Template 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=jM
32、ax;j+) 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
33、(nak) 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
35、=lcs_len(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. cd. e. f. g. h. i.j. 在Q1处获得该问题的最优解为，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大
