下载文档原格式
算法设计与分析■期末考试题整理1、一个算法应有哪些主要特征？又穷性，确定性，可行性，0个或多个输入，一个或多个输岀2、分治法(Divide and Conquer)与动态规划(Dynamic Programming)有什么不同？分治算法会重复的求解公共了问题，会做许多不必要的T作，而动态规划对每个了问题Z 求解一次，将其结果存入一张表屮，从而避免了每次遇到各个了问题有从新求解。
3、试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。
贪心算有效性：最小生成树、哈弟曼、活动安排、单元最短路径。
无效反例：0——I背包问题，无向图找嚴短路径问题。
4、求解方程fi[l)=f(2)=l。
由f(n)=f(n-1 )+f(n-2) nJ'得f(n)-f(n-l)-f(n-2)=0M得方程的特征方程为/ _兀一1 = 0,设特征方程的2个根本分别为"，兀2,则可得尤]=心=匕二2,则有- 21 4- V5 … 1 — yl~5 n/S) = C|(—y—) +C2(—y—)乂/•⑴= .f(2) “可得可得C] = a,c2 = hf(n) = a(^y+b(^)5、求解方稈T(n)=2T(n/2)+l, T(l)=l,设尸2匚r(n) = 2r(n/2) + l2T(n/2) = 22T(n/22) + 222T(/7/22)=23T(A?/23)+222iTS/2z) = 25S/2*) + 2"T上面所有式子相加，相消得T(n) = 2*7(1) + 2°+2,+22 + + 2^ -J-2*=2k +1* --------1-2=2A+, -16、编写一个Quick Sorting算法，并分析时间复杂性。
int part(int *a,int p,int r){int i,j,x,t;x=a[r];i=p-l；fbrOP；jv=r・l；j40{if(aU]<=x){汁+；t=a[i];a[i]=a[j]；aU]=t；}}t=a[i+l]；a[i+l]=a[r];a[r]=t;return 汁1;}void quicksort(int *a,int p,int r){intq;if(pvr){q=part(a,p,r);quicksort(a,p,q-l);quicksort(a,q+l,r);}快速排序时间复杂度最坏情况为OS?),平均为O(nlogn);7、利用Quick Sorting的原理，编写一个查找第k小元索的算法。
《算法分析与设计》期末复习题一、选择题1.算法必须具备输入、输出和（ D ）等4个特性。
A．可行性和安全性 B．确定性和易读性C．有穷性和安全性 D．有穷性和确定性2.算法分析中，记号O表示（ B ），记号Ω表示（ A ）A.渐进下界B.渐进上界C.非紧上界D.紧渐进界3.假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。
在某台计算机上实现并完成概算法的时间为t秒。
现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（ B ）解题方法：3*2^n*64=3*2^xA．n+8 B．n+6C．n+7 D．n+54.设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1，T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（ C ）。
A．O(logN) B．O(N)C．O(NlogN) D．O(N²logN)5.直接或间接调用自身的算法称为（ B ）。
A．贪心算法 B．递归算法C．迭代算法 D．回溯法6.Fibonacci数列中，第4个和第11个数分别是（ D ）。
A．5，89 B．3，89C．5，144 D．3，1447.在有8个顶点的凸多边形的三角剖分中，恰有（ B ）。
A．6条弦和7个三角形 B．5条弦和6个三角形C．6条弦和6个三角形 D．5条弦和5个三角形8.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。
A．重叠子问题 B．最优子结构性质C．贪心选择性质 D．定义最优解9.下列哪个问题不用贪心法求解（ C ）。
A．哈夫曼编码问题 B．单源最短路径问题C．最大团问题 D．最小生成树问题10.下列算法中通常以自底向上的方式求解最优解的是（ B ）。
A．备忘录法 B．动态规划法C．贪心法 D．回溯法11.下列算法中不能解决0/1背包问题的是（ A ）。
A．贪心法 B．动态规划C．回溯法 D．分支限界法12.下列哪个问题可以用贪心算法求解（ D ）。
《算法分析与设计》期末测验复习题纲(完整版)————————————————————————————————作者：————————————————————————————————日期：《算法分析与设计》期末复习题一、选择题1.算法必须具备输入、输出和（ D ）等4个特性。
A．可行性和安全性 B．确定性和易读性C．有穷性和安全性 D．有穷性和确定性2.算法分析中，记号O表示（ B ），记号Ω表示（ A ）A.渐进下界B.渐进上界C.非紧上界D.紧渐进界3.假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。
在某台计算机上实现并完成概算法的时间为t秒。
现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（ B ）解题方法：3*2^n*64=3*2^xA．n+8 B．n+6C．n+7 D．n+54.设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1，T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（ C ）。
A．O(logN) B．O(N)C．O(NlogN) D．O(N²logN)5.直接或间接调用自身的算法称为（ B ）。
A．贪心算法 B．递归算法C．迭代算法 D．回溯法6.Fibonacci数列中，第4个和第11个数分别是（ D ）。
A．5，89 B．3，89C．5，144 D．3，1447.在有8个顶点的凸多边形的三角剖分中，恰有（ B ）。
A．6条弦和7个三角形 B．5条弦和6个三角形C．6条弦和6个三角形 D．5条弦和5个三角形8.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。
A．重叠子问题 B．最优子结构性质C．贪心选择性质 D．定义最优解9.下列哪个问题不用贪心法求解（ C ）。
A．哈夫曼编码问题 B．单源最短路径问题C．最大团问题 D．最小生成树问题10.下列算法中通常以自底向上的方式求解最优解的是（ B ）。
《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？2.算法分析的目的是什么？3.算法的时间复杂性与问题的什么因素相关？4.算法的渐进时间复杂性的含义？5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？6.简述二分检索（折半查找）算法的基本过程。
7.背包问题的目标函数和贪心算法最优化量度相同吗？8.采用回溯法求解的问题，其解如何表示？有什么规定？9.回溯法的搜索特点是什么？10.n皇后问题回溯算法的判别函数place的基本流程是什么？11.为什么用分治法设计的算法一般有递归调用？12.为什么要分析最坏情况下的算法时间复杂性？13.简述渐进时间复杂性上界的定义。
14.二分检索算法最多的比较次数？15.快速排序算法最坏情况下需要多少次比较运算？16.贪心算法的基本思想？17.回溯法的解（x1,x2,……x n）的隐约束一般指什么？18.阐述归并排序的分治思路。
19.快速排序的基本思想是什么。
20.什么是直接递归和间接递归？消除递归一般要用到什么数据结构？21.什么是哈密顿环问题？22.用回溯法求解哈密顿环，如何定义判定函数？23.请写出prim算法的基本思想。
二、复杂性分析1、MERGESORT(low，high)if low<high；then mid←(low，high)/2；MERGESORT(low，mid)；MERGESORT(mid+1，high)；MERGE(low，mid，high)；endifend MERGESORT2、procedure S1(P，W，M，X，n)i←1; a←0while i≤ n doif W(i)>M then return endifa←a+ii←i+1 ;repeatend3.procedure PARTITION(m,p)Integer m,p,i;global A(m:p-1)v←A(m);i←mlooploop i←i+1 until A(i) ≥v repeatloop p←p-1 until A(p) ≤v repeatif i<pthen call INTERCHANGE(A(i),A(p))else exitendifrepeatA(m) ←A(p);A(p) ←vEnd PARTITION4.procedure F1(n)if n<2 then return(1)else return(F2(2,n,1,1))endifend F1procedure F2(i,n,x,y)if i≤nthen call F2(i+1,n,y,x+y)endifreturn(y)end F25.procedure MAX(A,n,j)xmax←A(1);j←1for i←2 to n doif A(i)>xmax then xmax←A(i); j←i;endif repeatend MAX6.procedure BINSRCH(A,n,x,j)integer low,high,mid,j,n;low←1;high←nwhile low≤high domid←|_(low+high)/2_|case:x<A(mid):high←mid-1:x>A(mid):low←mid+1:else:j ←mid; returnendcase repeat j ←0 end BINSRCH三、算法理解1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。
计算机算法设计与分析期末复习资料一填空题（20x1=20分）1.当有多个算法来解决集合问题时，选择算法的主要原则是选择复杂度最低的算法。
2.函数本身定义的函数是递归函数。
该算法适用于求解动态规划问题。
4.贪心算法的两个基本要素是最优子结构性质、贪心选择性质。
5.在搜索解空间树时，回溯方法通常使用深度优先的方法来提高搜索效率，以避免无效搜索。
6.根据不同的求解目标，分枝定界法和回溯法分别通过广度优先遍历或最小代价优先和深度优先搜索解空间树。
7.分支界限法和回溯法主要区别在于求解目标和搜索方式不同。
8.在执行分支定界法时，通常使用该方法来实现最大优先级队列。
9.依据求解所花费的时间和所得到的结果不同，随机化算法大致分为数值随机化算法、蒙特卡罗算法、拉斯维加斯算法和舍伍德算法四类。
10.产生伪随机数最常用的方法是线性同余法。
11.线性规划算法中旋转轴变化的目的是调整基准内变量和基准外变量的位置。
12.在最大网络流问题中，增广路径是剩余网络中容量大于0的路径。
13.应用于动态规划的待解决问题的两个基本要素是：。
14.算法必须满足的四个特征是输入、输出、确定性和有限性。
15.算法复杂性依赖于、、三个方面的复杂因素。
16.实现递归调用的关键是17.动态规划算法解决问题的重要线索是问题的性质。
18.最优子结构性质是贪婪算法的关键特征。
19.分支界限法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
20.有两种常见的解空间树：子集树和置换树。
21.分支界限算法依据其从和节点表中选择获得下一扩展节点的不同方式被分为22.对于任何约束标准线性规划问题，只要基本变量设置为0，就可以得到一个解。
三概念题（6x2=12分）1.算法复杂度：指算法运行所需的计算机资源量。
需要时间资源的量称为时间复杂度，需要空间资源源的量称为空间复杂性。
2.递归算法：直接或间接调用自身的算法称为递归算法。
《算法分析与设计》期末试题及参考答案《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？1.确定性、可行性、输入、输出、有穷性2.2.算法分析的目的是什么？2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。
3.3.算法的时间复杂性与问题的什么因素相关？3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。
4.算法的渐进时间复杂性的含义？4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。
时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。
5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。
最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max{ T(n，I) } , I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n) =∑P(I)T(n，I) I∈Dn6.简述二分检索（折半查找）算法的基本过程。
6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]<="">7.背包问题的目标函数和贪心算法最优化量度相同吗？7. 不相同。
目标函数：获得最大利润。
最优量度：最大利润/重量比。
8.采用回溯法求解的问题，其解如何表示？有什么规定？8. 问题的解可以表示为n元组：（x1,x2,……x n），x i∈S i, S i为有穷集合，x i∈S i, （x1,x2,……x n）具备完备性，即（x1,x2,……x n）是合理的，则（x1,x2,……x i）(i<n)一定合理。
算法设计与分析复习题目及答案.docx一。
选择题1、二分搜索算法是利用（A）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（B）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（A）的一搜索方式。
A、分支界限法B、动态规划法C、贪心法D、回溯法4、在下列算法中有时找不到问题解的是（B）。
A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法5. 回溯法解旅行售货员问题时的解空间树是（B）。
A、子集树B、排列树C、深度优先生成树D、广度优先生成树6．下列算法常以自底向上的方式求解最优解的是（B）。
A、备忘录法B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是（ C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短8、以下不可以使用分治法求解的是（ D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1 背包问题9. 实现循环赛日程表利用的算法是（A）。
A、分治策略B、动态规划法C、贪心法D、回溯法10、下列随机算法中运行时有时候成功有时候失败的是（ C ）A 数值概率算法B 舍伍德算法C 拉斯维加斯算法D 蒙特卡罗算法11．下面不是分支界限法搜索方式的是（DA、广度优先B、最小耗费优先C、最大效益优先12．下列算法常以深度优先方式系统搜索问题解的是（A、备忘录法B、动态规划法C、贪心法13.备忘录方法是那种算法的变形。
（ B ）A、分治法B、动态规划法C、贪心法14．哈弗曼编码的贪心算法所需的计算时间为（BnB、 O（nlogn ）n ）A、O（ n2 ）C、O（215．分支限界法解最大团问题时，活结点表的组织形式是（A、最小堆B、最大堆C、栈组）。
D、深度优先D）。
D、回溯法D、回溯法）。
D、 O（ n）B）。
D 、数16．最长公共子序列算法利用的算法是（B）。
A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（A）。
复习一、简答题（每小题5分，选答2题，共10分）1. 什么是算法？试说明算法设计分析过程的一般框架和主要步骤。
2. 简述非递归算法时间效率分析的通用方案。
3. 简述递归算法时间效率的通用方案。
4. 简述蛮力法、分治法、减治法，变治法、时空权衡、动态规划、贪婪技术、迭代改进八种算法设计技术中至少三种技术基本思想或原理。
二、分析题（每小题10分，共20分）1. 考虑下面的算法。
P52算法Mystery(n) //输入：非负整数nS=0for i 1 to n doS S + i*iReturn Sa.该算法求的是什么？b.它的基本操作是什么？c.该基本操作执行了多少次？d.该算法的效率类型是什么？2. 考虑下面的递归算法。
P52算法Secret(A[0..n-1]) //输入：包含n个实数的数组A[0..n-1]minval A[0]; maxval A[0]for i 1 to n-1 doif A[i] < minvalminval A[i]if A[i] > maxvalmaxval A[i]return maxval – minvala.该算法求的是什么？b.它的基本操作是什么？c.该基本操作执行了多少次？d.该算法的效率类型是什么？3. 考虑下面的递归算法P59算法Q(n) //输入：正整数if n=1 return 1else return Q(n-1) + 2*n -1a. 建立该函数值的递推关系并求解，以确定该算法计算的是什么；b. 建立该算法所做的乘法运算次数的递推关系并求解；c. 建立该算法所做的加减运算次数的递推关系并求解。
三、算法设计题（每小题10分，共20分）1. 应用快速排序对序列E，X，A，M，P，L，E按照字母顺序排序。
并画出相应的递归调用树。
(4章分治法)P1022. 对于下面的有向图，应用基于DFS的算法来解拓扑排序问题。
(5章减治法)P133.3. 用自底向上算法为列表1, 8, 6, 5, 3, 7, 4进行堆排序。
算法设计与分析期末考试复习题1．算法有哪些特点？为什么说一个具备了所有特征的算法，不一定就是使用的算法?2．证明下面的关系成立：(参考例题1.5--1.6)（1）logn!=Θ(nlogn) (2)2n=Θ(2n+1)(3)n!=Θ(n n) (4)5n2-6n=Θ(n2)3.考虑下面的算法：输入：n个元素的数组A输出：按递增顺序排序的数组A1. void sort(int A[],int n)2. {3. int i,j,temp;4. for(i=0;i<n-1;i++)5. for(j=i+1;j<n;j++)6. if(A[j]<A[i]) {7. temp=A[i];8. A[i]=A[j];9. A[j]=temp;10. }11. }（1）什么时候算法所执行的元素赋值的次数最少？最少多少次？（2）什么时候算法所执行的元素赋值的次数最多？最多多少次？4.考虑下面的算法：输入：n个元素的数组A输出：按递增顺序排序的数组A1. void bubblesort(int A[],int n)2. {3. int j,i,sorted;4. i=sorted=0;5. while(i<n-1 && !sorted) {6. sorted=1;7. for(j=n-1;j>i;j--) {8. if(A[j]<A[j-1]) {9. temp=A[j];10. A[j]=A[j-1];11. A[j-1]=temp;12. sorted=0;13. }14. }15. i=i+1;16. }17. }（1）算法所执行的元素比较次数最少是多少次？什么时候达到最少？（2）算法所执行的元素比较次数最多是多少次？什么时候达到最多？（3）算法所执行的元素赋值次数最少是多少次？什么时候达到最少？（4）算法所执行的元素赋值次数最多是多少次？什么时候达到最多？（5）用О、和Ω记号表示算法的运行时间。
WORD 格式《算法分析与设计》期末复习题一、选择题1.算法必须具备输入、输出和（ D）等 4 个特性。
A ．可行性和安全 B性 ．确定性和易读性C ．有穷性和安全 D性 ．有穷性和确定性2.算法分析中，记号 O 表示（ B ），记号 Ω 表示（ A）A. 渐进下界B.渐进上界C. 非紧上界D. 紧渐进界3.假设某算法在输入规模为 n 时的计算时间为 T(n)=3*2^n 。
在某台计算机上实现并完成概算法的时间为 t 秒。
现有另一台计算机，其运行速度为第一台 64 倍，那 的么在这台新机器上用同一算法在 t 秒内能解输入规模为多大的问题？（ B）解题方法： 3*2^n*64=3*2^x．n+8 B．n+6AD．．n+7n+5C4. 设问题规模为N 时，某递归算法的时间复杂度记为T(N) ，已知 T(1)=1 ，T(N)=2T(N/2)+N/2 ，用 O 表示的时间复杂度为（C）。
．O(logN)B．O(N)AC ．O(NlogN) D． O(N2logN)5. 直接或间接调用自身的算法称为 B（）。
A ．贪心算法B．递归算法．迭代算法D．回溯法C6. Fibonacci 数列中，第 4 个和第 11 个数分别是（D）。
A ．5， 89B ．3，89C ．5， 144D．3，1447. 在有 8 个顶点的凸多边形的三角剖分中，恰有（B）。
． 条弦和7 个三角形B． 5 条弦和6 个三角形A 6C ．6 条弦和 6 个三角形D．5 条弦和 5 个三角形8. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题B）。
的（A．重叠子问题 B ．最优子结构性质．贪心选择性质 D ．定义最优解C9. 下列哪个问题不用贪心法求解C（）。
．哈夫曼编码问题 B ．单源最短路径问题A．最大团问题 D ．最小生成树问题C10. 下列算法中通常以自底向上的方式求解最优解的是（B）。
A．备忘录法 B ．动态规划法C．贪心法 D ．回溯法11.下列算法中不能解决 0/1 背包问题的是（ A）。
A．贪心法B．动态规划C．回溯法D．分支限界法专业资料整理WORD格式12.下列哪个问题可以用贪心算法求解（D）。
1专业资料整理WORD格式A．LCS问题 B ．批处理作业问题C．0-1 背包问题 D ．哈夫曼编码问题13. 用回溯法求解最优装载问题时，若待选物品m种，则该问题的解空间树的结为点个数为（）。
A．m! B． 2m+1C．2m+1-1 D．2m14. 二分搜索算法是利用（A）实现的算法。
．分治策略 B ．动态规划法AC．贪心法 D ．回溯法15. 下列不是动态规划算法基本步骤的是（ B ）。
P44A．找出最优解的性质 B ．构造最优解C．算出最优解 ( 应该是最优值 ) D．定义最优解16. 下面问题（ B ）不能使用贪心法解决。
A．单源最短路径问题 B ． N 皇后问题C．最小花费生成树问题 D ．背包问题17.使用二分搜索算法在 n 个有序元素表中搜索一个特定元素，在最好情况和最坏情况下搜索的时间复杂性分别为（ A ）。
P17A．O(1) ， O(logn) B ． O(n) ， O(logn)C．O(1) ， O(nlogn) D ． O(n) ， O(nlogn)18. 优先队列式分支限界法选取扩展结点的原则C ）。
P162 是（A．先进先出 B．后进先出C．结点的优先级 D ．随机19. 下面不是分支界限法搜索方式的是（ D ）。
P161．广度优先 B ．最小耗费优先A．深度优C．最大效益优先 D 先20. 分支限界法解最大团问题时，活结点表的组织形式是（B）。
．最小堆 B ．最大堆AC．栈 D ．数组21. 下列关于计算机算法的描述不正确的是）。
（C P1A．算法是指解决问题的一种方法或一个过程B．算法是若干指令的有穷序列C.算法必须要有输入和输出D．算法是编程的思想22. 下列关于凸多边形最优三角剖分问题描述不正确的A）。
是（A． n+1 个矩阵连乘的完全加括号和n 个点的凸多边形的三角剖分对应B．在有 n 个顶点的凸多边形的三角剖分中，恰n-3 条弦有C．该问题可以用动态规划法来求解D．在有 n 个顶点的凸多边形的三角剖分中，恰n-2 个三角形有23. 动态规划法求解问题的基本步骤不包括（ C ）。
P44A．递归地定义最优值B．分析最优解的性质，并刻画其结构特征C．根据计算最优值时得到的信息，构造最优解( 可以省去的 ) D．以自底向上的方式计算出最优值专业资料整理WORD格式24. 分治法所能解决的问题应具有的关键特征是（C）。
P162专业资料整理WORD格式A．该问题的规模缩小到一定的程度就可以容易地解决B．该问题可以分解为若干个规模较小的相同问题C．利用该问题分解出的子问题的解可以合并为该问题的解D．该问题所分解出的各个子问题是相互独立的下列关于回溯法的描述不正确的是25. （D）。
P114A．回溯法也称为试探法B．回溯法有“通用解题法”之称C．回溯法是一种能避免不必要搜索的穷举式搜索法D．用回溯法对解空间作深度优先搜索时只能用递归方法实现26. 常见的两种分支限界法为（ D ）。
P161A.广度优先分支限界法与深度优先分支限界法；B.队列式（ FIFO）分支限界法与堆栈式分支限界法；C.排列树法与子集树法；D.队列式（ FIFO）分支限界法与优先队列式分支限界法；二、填空题f(n)=3n2)1. n 2 +10 的渐近性态 f(n)=O( ，g(n)=10log3 n的渐近性态 g(n)=O( n ) 。
2. 一个“好”的算法应具有正确性、可读性、健壮性和高效率和低存储量需求等特性。
3. 算法的时间复杂性函数表示C=F(N,I,A)为，分析算法复杂性的目的在于比较求解同意问题的两个不同算法的效率的效率。
4. 构成递归式的两个基本要素是递归的边界条件和递归的定义。
5. 单源最短路径问题可用分支限界法和贪心算法求解。
6. 用分治法实现快速排序算法时，最好情况下的时间复杂性为O(nlogn) ，最坏情况下的时间复杂性为 O(n^2) ，该算法所需的时间与运行时间和划分两方面因素有关。
P267. 0-1 背包问题的解空间树为完全二叉树； n 后问题的解空间树为排列树；8. 常见的分支限界法有队列式FIFO）分支限界法和优先队列式分支限界（法。
9. 回溯法搜索解空间树时常用的两种剪枝函数为约束函数和剪枝函数。
10. 分支限界法解最大团问题时，活结点表的组织形式是最大堆；分支限界法解单源最短路径问题时，活结点表的组织形式是最小堆。
三、算法填空题1.递归求解 Hanoi 塔问题 / 阶乘问题。
例 1: 阶乘函数 n!P12阶乘的非递归方式定义： n! n (n 1) (n2) 21 试写出阶乖的递归式及算法。
递归式为： 1 n 0 边界条件n!n(n 1)!n 0专业资料整理WORD格式3专业资料整理WORD格式递归方程递归算法：intfactorial(intn){if(n==0)return1;递归出口returnn*factorial(n-1);递归调用}例 2: 用递归技术求解Hanoi塔问题,Hanoi塔的递归算法。
P15其中 Hanoi(intn,inta,intc,intb)表示将塔座 A 上的 n 个盘子移至塔座C，以塔座 B 为辅助。
Move(a,c) 表示将塔座 a 上编号为 n 的圆盘移至塔座 c 上。
voidhanoi(intn,inta,intc,intb){if(n>0){hanoi(n-1,a,b,c);move(a,c);hanoi(n-1,b,c,a);}}2.用分治法求解快速排序问题。
快速排序算法P25、作业、课件第 2 章（ 2） 42 页 -50 页template<classType>voidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1,r)；}}专业资料整理WORD格式4专业资料整理WORD格式Partition函数的具体实现template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//将 <x 的元素交换到左边区域//将 >x 的元素交换到右边区域while(true){while(a[++i]<x&&i<r);while(a[--j]>x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}3.用贪心算法求解最优装载问题。
最优装载问题 P95 课件第 4 章 (2) 第 3-8 页template<classType>voidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);for(inti=1;i<=n;i++)x[i]=0;for(intj=1;j<=n&&w[t[j]]<=c;j++){x[t[i]]=1;c-=w[t[j]];}专业资料整理WORD格式}5专业资料整理WORD格式4.用回溯法求解 0-1 背包 / 批处理作业调度 / 最大团问题，要会画解空间树。
例 1：用回溯法求解0-1 背包P133 课件第 5 章 (2) 第 24-38 页template<typenameTypew,typenameTypep>classKnap{private:TypepBound(inti);//计算上界voidBacktrack(inti);Typewc;//背包容量intn;//物品数Typew*w;//物品重量数组Typep*p;//物品价值数组Typewcw;//当前重量Typepcp;//当前价值Typepbestp;//当前最优价值};voidKnap<Typew,Typep>::Backtrack(inti){if(i>n){bestp=cp;return;}if(cw+w[i]<=c)//进入左子树{cw+=w[i];cp+=p[i];Backtrack(i+1);cw-=w[i];cp-=p[i];}if(Bound(i+1)>bestp)//进入右子树Backtrack(i+1);}TypepKnap<Typew,Typep>::Bound(inti){Typewcleft=c-cw;//剩余的背包容量Typepb=cp;//b为当前价值//依次装入单位重量价值高的整个物品专业资料整理WORD格式6专业资料整理WORD格式while(i<=n&&w[i]<=cleft){cleft-=w[i]; b+=p[i];i++; }if(i<=n)//装入物品的一部分b+=p[i]*cleft/w[i];returnb;//返回上界}classObject//物品类{friendintKnapsack(int*,int*,int,int);public:intoperator<(Objecta)const{return(d>=a.d);}intID;//物品编号floatd;//单位重量价值};TypepKnapsack(Typepp[],Typeww[],Typewc,intn){//为 TypepKnapsack 初始化TypewW=0;//总重量TypepP=0;//总价值Object*Q=newObject[n];//创建物品数组，下标从0 开始for(inti=1;i<=n;i++)//初始物品数组数据{Q[i-1].ID=i;Q[i-1].d=1.0*p[i]/w[i];P+=p[i];W+=w[i];}if(W<=c)//能装入所有物品returnP;if(W<=c)//能装入所有物品returnP;QuickSort(Q,0,n-1);//依物品单位重量价值非增排序专业资料整理WORD格式7专业资料整理WORD格式Knap<Typew,Typep>K;K.p=newTypep[n+1];K.w=newTypew[n+1];for(inti=1;i<=n;i++){ K.p[i]=p[Q[i-1].ID];K.w[i]=w[Q[i-1].ID];}K.cp=0; K.cw=0;K.c=c;K.n=n;K.bestp=0;K.Backtrack(1);delete[]Q;delete[]K.w;delete[]K.p;returnK.bestp;}例 2：批处理作业调度课件第5章(2)P2-5问题描述,课本P125-127解空间：排列树算法描述：classFlowshop{static int [][]m,// 各作业所需的处理时间[]x,// 当前作业调度[]bestx,//当前最优作业调度[]f2,// 机器 2 完成处理时间f1,// 机器 1 完成处理时间f,// 完成时间和bestf,// 当前最优的完成时间和n;// 作业数staticvoidBacktrack(inti){if(i>n){ for(intj=1;j<=n;j++)bestx[j]=x[j];bestf=f;}elsefor(intj=i;j<=n;j++){f1+=m[x[j]][1];// 第 j 个作业在第一台机器上所需时间f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2];f+=f2[i];if(f<bestf)//约束函数{ Swap(x[i],x[j]);Backtrack(i+1);Swap(x[i],x[j]);}f1-=m[x[j]][1];f-=f2[i];}}专业资料整理WORD格式8专业资料整理WORD格式例 3：最大团问题，要会画解空间树。
