一、选择题
1.二分搜索算法是利用（A ）实现的算法。
A、分治策略
B、动态规划法
C、贪心法
D、回溯法
2. 回溯法解旅行售货员问题时的解空间树是（ A ）。
A、子集树
B、排列树
C、深度优先生成树
D、广度优先生成树
3.下列算法中通常以自底向上的方式求解最优解的是（B ）。
A、备忘录法
B、动态规划法
C、贪心法
D、回溯法
4．下面不是分支界限法搜索方式的是（ D ）。
A、广度优先
B、最小耗费优先
C、最大效益优先
D、深度优先
5．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为 ( B ) 。
A、O（n2n）
B、O（nlogn）
C、O（2n）
D、O（n）
6．分支限界法解最大团问题时，活结点表的组织形式是（ B）。
A、最小堆
B、最大堆
C、栈
D、数组
7、下面问题（B ）不能使用贪心法解决。
A 单源最短路径问题
B N皇后问题
C 最小花费生成树问题
D 背包问题
8.下列算法中不能解决0/1背包问题的是（A ）
A 贪心法
B 动态规划
C 回溯法
D 分支限界法
9.背包问题的贪心算法所需的计算时间为（ B ）
A、O（n2n）
B、O（nlogn）
C、O（2n）
D、O（n）
10.背包问题的贪心算法所需的计算时间为（B ）。
A、O（n2n）
B、O（nlogn）
C、O（2n）
D、O（n）
二、填空题
1.算法的复杂性有复杂性和复杂性之分。
2.算法是由若干条指令组成的有穷序列，且要满足输入、、确定性和四条性质。其中算法的“确定性”指的是组成算法的每条是清晰的，无歧义的。
3.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是，需要排序的是。
4.动态规划算法的两个基本要素是. 性质和性质。
5.回溯法是一种既带有又带有的搜索算法；分支限界法是一种既带有又带有的搜索算法。
6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为。
7.用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）。
Bool Color::OK(int k)
{//
for(int j=1;j<=n;j++)
if((a[k][j]= =1)&&(x[j]= =x[k])) return false;
return true;
}
8.用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为n m
⨯的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则算法共耗时，构造相应的最短距离需要时间。
for (int i = 0; i < NumOfNbrs; i++) {
nbr.row = here.row + offset[i].row;
nbr.col = here.col + offset[i].col;
if (grid[nbr.row][nbr.col] == 0) {
// 该方格未标记
grid[nbr.row][nbr.col]
= grid[here.row][here.col] + 1;
if ((nbr.row == finish.row) &&
(nbr.col == finish.col)) break; // 完成布线
Q.Add(nbr);}
}
9.快速排序算法是基于的一种排序算法。
10. 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别
三．简答题
1.设计动态规划算法的主要步骤是怎么的？请简述。
2.分治法所能解决的问题一般具有哪几个特征？请简述。
3.分支限界法的搜索策略是什么？
四．计算题
1.已知非齐次递归方程：
f(n)bf(n1)g(n)
f(0)c
=-+
⎧
⎨
=
⎩
，其中，b、c是常数，g(n)是n的某一个函数。则f(n)
的非递归表达式为：
n
n n i
i1
f(n)cb b g(i)
-
=
=+∑。
现有Hanoi塔问题的递归方程为：
h(n)2h(n1)1
h(1)1
=-+
⎧
⎨
=
⎩
，求h(n)的非递归表达式。
2.给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。另外，还给定V 中的一个
顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。现采用Dijkstra 算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。
五．程序题
1.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。
2.试用动态规划算法实现下列问题：设A 和B 是两个字符串。我们要用最少的字符操作，将字符串A 转换为字符串B ，这里所说的字符操作包括： （1）删除一个字符。 （2）插入一个字符。
（3）将一个字符改为另一个字符。 请写出该算法。
答案：
一、AABDB BBABB 二、
1. 时间 空间
4
3 2 1 {1} 初始 dist[5]
dist[4] dist[3] dist[2] u S 迭代
2. 输出 有限性 指令
3. 动态规划 回溯法 分支限界法
4. 最优子结构 重叠子问题
5. 系统性 跳跃性 系统性 跳跃性
6. （O(h(n))）
7. O （mn ）
8. O(mn) O(L)
9. 分治策略 10. 贪心选择性质 三、
1.（1）找出最优解的性质，并刻划其结构特征。 （2）递归地定义最优值。
（3）以自底向上的方式计算出最优值。
（4）根据计算最优值时得到的信息，构造最优解。
2. （1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质; （3） 利用该问题分解出的子问题的解可以合并为该问题的解；
（4）原问题所分解出的各个子问题是相互的，即子问题之间不包含公共的子问题。
3. 在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。
四、 1.解：利用给出的关系式，此时有：b=2, c=1, g(n)=1, 从n 递推到1，有：
n 1
n 1
n 1i i 1
n 1n 22n h(n)cb
b g(i)
22...22121----=--=+=+++++=-∑ 2.
60
30
50
10
5
{1，2，3，4，5}
4
60 30 50 10 3 {1，2，4，3} 3 90 30 50 10 4 {1，2，4} 2 100 30 60 10 2 {1，2} 1 100 30 10 - {1} 初始 dist[5] dist[4] dist[3]
dist[2] u S 迭代
1.解：int greedy(vecter { int sum=0,k=x.size(); for(int j=0;j cout<<”No solution”< } For(int i=0,s=0;i if(s>n){sum++;s=x[i];} } return sum; } 2.解：此题用动态规划算法求解： int dist() { int m=a.size(); int n=b.size(); vector for(int i=1;i<=n;i++)d[i]=i; for(i=1;i<=m;i++){ int y=i-1; for(int j=1;j<=n;j++){ int x-y; y=d[j]; int z=j>1?d[j-1]:i; int del=a[i-1]==b[j-1]?0:1; d[j]=min(x+del,y+1,z+1); } } return d[n]; } 一、填空题（每小题3分，共30分） 1、一个算法的优劣可以用与与来衡量。 2、这种不断回头寻找目标的方法称为。 3、直接或间接地调用自身的算法称为。 4、 记号在算法复杂性的表示法中表示。 5、由分治法产生的子问题往往是，这就为使用提供了方便。 6、建立计算模型的目的是为了使。 7、下列各步骤的先后顺序是。①调试程序②分析问题③设计算法④编写程序。 8、最优子结构性质的含义是。 9、贪心算法从初始阶段开始，每一个阶段总是作一个使的贪心选择。 10、拉斯维加斯算法找到的解一定是。 二、选择题（每小题2分，共20分） 1、哈夫曼编码可利用（）算法实现。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是基本计算模型的是（）。 A、RAM B、ROM C、RASP D、TM 3、下列算法中通常以自顶向下的方式求解最优解的是（）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 4、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是( ) A、回溯法 B、分支限界法 C、回溯法和分支限界法 D、动态规划 5、秦始皇吞并六国使用的远交近攻，逐个击破的连横策略采用了以下哪种算法思想？ A、递归； B、分治； C、迭代； D、模拟。 6、FIFO是（）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 7、投点法是（）的一种。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 8、若线性规划问题存在最优解，它一定不在（） A．可行域的某个顶点上 B．可行域的某条边上 C．可行域内部 D．以上都不对 9、在一般输入数据的程序里，输入多多少少会影响到算法的计算复杂度，为了消除这种影响可用（）对输入进行预处理。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 10、若L是一个NP完全问题，L经过多项式时间变换后得到问题l，则l是( ). A、P类问题 B、NP难问题 C、NP完全问题 D、P类语言 三、简答题（每小题5分，共20分） 1、采用高级程序设计语言表达算法，主要好处是： 2、由于贪心算法是一种只顾眼前的步骤，而难以顾及全局步骤的算法，所以它通常表现出哪些特点？ 3、求下列函数的渐近表达式： n2 ; 14+5/n+1/n2; 1- 10n 4、简述动态规划算法的基本步骤 四、算法设计题（每小题15分，共30分） 1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M ＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树并计算各个节点处的限界函数值，最后给出装载方案及背包中物品的重量和价值。 2、用单纯形法解下列线性规划问题 5 3223max x x x z -+-=10 83412427235 3263 245321=++-=+-=+-+x x x x x x x x x x x 6 ,5,4,3,2,10 =≥i x i 填写初始单纯型表 2）写出每一步的入基变量和离基变量 3）填写最终单纯型表并给出最优解 物品 B C D E F G 重量 5 3 6 5 4 1 2 5 价值 4 3 0 5 3 5 4 3 目标函数的最大值为： 最优解为： 参 一、填空 1、空间复杂度时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 二、选择 1 2 3 4 5 6 7 8 9 10 C B C A B A B C B A 三、简答题 1、 高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度），而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：①因为： ;0 1- 10n n )1- 10n n( lim 2 2 2 = + - + →∞ n n由渐近表达式的定义易知：1- 10n n2 2+ 是 n;的渐近表达式。 ②因为： ;0 n 1/ 5/n 14 14 ) n 1/ 5/n 14 ( lim 2 2 = + + - + + ∞ → n由渐近表达式的定义易知： 14是14+5/n+1/ n2的渐近表达式。 4、找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】a a a b a a c Q1 1 1 x= 2 1 x= 3 1 x= 41 x= 50 x= 60 x= 70 x= d e e 4 x= 3 x= 4 1 x= e 5 1 x= f 6 x= g 5 x= h 4 x= i 2 x= j 1 x= a． 150115 4040305035190.625 40 - ++++⨯=7 (1,1,1,1,,0,0) 8 b. 150115 4040305030177.5 60 - ++++⨯=7 (1,1,1,1,0,,0) 12 c．4040305010170 ++++=(1,1,1,1,0,0,1) d. 150105 4040303530167.5 60 - ++++⨯=3 (1,1,1,0,1,,0) 4 e. 150130 4040503530175 60 - ++++⨯=1 (1,1,0,1,1,,0) 3 f. 150130 4040503510170.71 35 - ++++⨯=4 (1,1,0,1,1,0,) 7 g. 40405030160 +++=(1,1,0,1,0,1,0) h. 150140 4040353010146.85 35 - ++++⨯=2 (1,1,0,0,1,1,) 7 i. 150125 4030503530167.5 60 - ++++⨯=5 (1,0,1,1,1,,0) 12 j. 150145 4030503530157.5 60 - ++++⨯=1 (0,1,1,1,1,,0) 12 在Q1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。即在背包中装入物品F、B、G、D、A时达 到最大效益，为170，重量为150。【结论2分】 2、初始单纯型表如下： 1）（5分） x2 x3 x5 z 0 -1 3 -2 x1 7 3 -1 2 x4 12 -2 4 0 x6 10 -4 3 8 2）第一步入基变量x3、离基变量x4 第二步入基变量x2、离基变量x1 3）（6分）x1 x4 x5 z 11 -1/5 -4/5 -12/5 x2 4 5/2 1/10 4/5 x3 5 1/5 3/10 2/5 x6 11 1 -1/2 10 目标函数的最大值为11 最优解为：x*=(0,4,5,0,0,11) （其中表格填写占11分，目标函数的最大值2分，最优解为占2分） 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算。此外，算法还应具有以下五个重要特性:______,______,____,______,______。 2.算法的复杂性有_______和________之分，衡量一个算法好坏的标准是____________。 3.某一问题可用动态规划算法求解的显著特征是______________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 5.设S=｛X1，X2，···，X n｝是严格递增的有序集，利用二叉树的结点来存储S中的元素，在表示S的二叉搜索树中搜索一个元素X，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i，其概率为b i。（2）在二叉搜索树的叶结点中确定X∈（X i，X i+1），其概率为a i。在表示S的二叉搜索树T中，设存储元素X i的结点深度为C i；叶结点（X i，X i+1）的结点深度为d i，则二叉搜索树T的平均路长p为多少？假设二叉搜索树T[i][j]=｛X i，X i+1，···，X j｝最优值为m[i][j]，W[i][j]= a i-1+b i+···+b j+a j，则m[i][j](1<=i<=j<=n)递归关系表达式为什么？ 6.描述0-1背包问题。 三、简答题（30分） 1.流水作业调度中，已知有n个作业，机器M1和M2上加工作业i所需的时间分别为a i和 b i，请写出流水作业调度问题的johnson法则中对a i和b i的排序算法。（函数名可写为sort(s,n)） 2.最优二叉搜索树问题的动态规划算法（设函数名binarysearchtree)） 答案： 一、填空 1．确定性有穷性可行性 0个或多个输入一个或多个输出 2.时间复杂性空间复杂性时间复杂度高低 3. 该问题具有最优子结构性质4.{BABCD}或{CABCD}或{CADCD ｝ 5.一个（最优）解 6.子问题 子问题 子问题 7.回溯法 8. o(n*2n ) o(min{nc,2n }) 9.最优子结构 重叠子问题 10.动态规划法 二、综合题 1.①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3.步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4.解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） A B C F E D G K J I H O N M L 1 1 1 0 0 0 0 1 0 1 1 0 1 0 5.二叉树T的平均路长P=∑ =+ n i1 Ci) (1 * bi+∑ = n j0 dj * aj { m[i][j]=0 (i>j) 6.已知一个背包的容量为C，有n件物品，物品i的重量为W i，价值为V i，求应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 三、简答题 1. void sort(flowjope s[],int n) { int i,k,j,l; for(i=1;i<=n-1;i++)//-----选择排序 { k=i; while(k<=n&&s[k].tag!=0) k++; if(k>n) break;//-----没有a i，跳出 else { for(j=k+1;j<=n;j++) if(s[j].tag==0) if(s[k].a>s[j].a) k=j; swap(s[i].index,s[k].index); swap(s[i].tag,s[k].tag); } } m[i][j]=W[i][j]+min{m[i][k]+m[k+1][j]} (1<=i<=j<=n,m[i][i-1]=0)l=i;//-----记下当前第一个b i的下标 for(i=l;i<=n-1;i++) { k=i; for(j=k+1;j<=n;j++) if(s[k].b swap(s[i].tag,s[k].tag); } } 2. void binarysearchtree(int a[],int b[],int n,int **m,int **s,int **w) { int i,j,k,t,l; for(i=1;i<=n+1;i++) { w[i][i-1]=a[i-1]; m[i][i-1]=0; } for(l=0;l<=n-1;l++)//----l是下标j-i的差 for(i=1;i<=n-l;i++) { j=i+l; w[i][j]=w[i][j-1]+a[j]+b[j]; m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];s[i][j]=i; for(k=i+1;k<=j;k++) { t=m[i][k-1]+m[k+1][j]+w[i][j]; if(t m[i][j]=t; s[i][j]=k; } } } } 一、填空题（本题15分，每小题1分） 1、算法就是一组有穷的，它们规定了解决某一特定类型问题的。 2、在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型 是、、。 3、算法的复杂性是的度量，是评价算法优劣的重要依据。 4、计算机的资源最重要的是和资源。因而，算法的复杂性有和之分。 5、f(n)= 6×2n+n2，f(n)的渐进性态f(n)= O( ) 6、贪心算法总是做出在当前看来的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某 种意义上的。 7、许多可以用贪心算法求解的问题一般具有2个重要的性质：性质和性质。 二、简答题（本题25分，每小题5分） 1、简单描述分治法的基本思想。 2、简述动态规划方法所运用的最优化原理。 3、何谓最优子结构性质？ 4、简单描述回溯法基本思想。 5、何谓P、NP、NPC问题 三、算法填空（本题20分，每小题5分） 1、n后问题回溯算法 (1)用二维数组A[N][N]存储皇后位置,若第i行第j列放有皇后,则A[i][j]为非0值,否则值为0。 (2)分别用一维数组M[N]、L[2*N-1]、R[2*N-1]表示竖列、左斜线、右斜线是否放有棋子，有则值为1,否则值为0。for(j=0;j 2 ； if(i==N-1) 输出结果； else 3 ；; /*试探下一行*/ 4 ； /*去皇后*/ 5 ；; } 2、数塔问题。有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。 for(r=n-2;r>=0;r--) //自底向上递归计算 for(c=0; 1 ;c++) if( t[r+1][c]>t[r+1][c+1]) 2 ； else 3 ； 3、Hanoi算法 Hanoi(n,a,b,c) if （n==1） 1 ； else { 2 ； 3 ； Hanoi(n-1,b, a, c); } 4、Dijkstra算法求单源最短路径 d[u]:s到u的距离 p[u]:记录前一节点信息 Init-single-source(G,s) for each vertex v∈V[G] do { d[v]=∞; 1 } d[s]=0 Relax(u,v,w) if d[v]>d[u]+w(u,v) then { d[v]=d[u]+w[u,v]; 2 } dijkstra(G,w,s) 1. Init-single-source(G,s) 2. S=Φ 3. Q=V[G] 4.while Q<> Φ do u=min(Q) S=S∪{u} for each vertex 3 do 4 四、算法理解题（本题10分） 根据优先队列式分支限界法，求下图中从v1点到v9点的单源最短路径，请画出求得最优解的解空间树。要求中间被舍弃的结点用×标记，获得中间解的结点用单圆圈○框起，最优解用双圆圈◎框起。 五、算法理解题（本题5分） 设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表： ①每个选手必须与其他n-1名选手比赛各一次； ②每个选手一天至多只能赛一次； ③循环赛要在最短时间内完成。 （1）如果n=2k，循环赛最少需要进行几天； （2）当n=23=8时，请画出循环赛日程表。 六、算法设计题（本题15分） 分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。 七、算法设计题（本题10分） 通过键盘输入一个高精度的正整数n(n的有效位数≤240)，去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n 和s，寻找一种方案，使得剩下的数字组成的新数最小。 【样例输入】 178543 S=4 【样例输出】 13 一、填空题（本题15分，每小题1分） 1．规则一系列运算 2. 随机存取机RAM(Random Access Machine)；随机存取存储程序机RASP(Random Access Stored Program Machine)；图灵机(Turing Machine) 3. 算法效率 4. 时间、空间、时间复杂度、空间复杂度 5．2n 6．最好局部最优选择 7. 贪心选择最优子结构 二、简答题（本题25分，每小题5分） 6、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相且与原问题相同； 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 7、“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如 若这个决策序列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。 8、某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 9、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中， 每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。 10、P(Polynomial问题)：也即是多项式复杂程度的问题。 NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。 NPC(NP Complete)问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。 三、算法填空（本题20分，每小题5分） 1、n 后问题回溯算法 (1) !M[j]&&!L[i+j]&&!R[i-j+N] (2) M[j]=L[i+j]=R[i-j+N]=1; (3) try(i+1,M,L,R,A) (4) A[i][j]=0 (5) M[j]=L[i+j]=R[i-j+N]=0 2、数塔问题。 （1）c<=r (2)t[r][c]+=t[r+1][c] （3）t[r][c]+=t[r+1][c+1] 3、Hanoi 算法 （1）move(a,c) （2）Hanoi(n-1, a, c , b) （3）Move(a,c) 4、（1）p[v]=NIL （2）p[v]=u (3) v ∈adj[u] （4）Relax(u,v,w) 四、算法理解题（本题10分） 五、（1）8天（2分）； （2）当n=23=8时，循环赛日程表（3分）。 六、算法设计题（本题15分） （1）贪心算法 O （nlog （n ）） 首先计算每种物品单位重量的价值Vi/Wi ，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入 背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C ，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下： void Knapsack(int n,float M,float v[],float w[],float x[]) {Sort(n,v,w); int i; for (i=1;i<=n;i++) x[i]=0; float c=M; 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 for (i=1;i<=n;i++) {if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; } （2）动态规划法 O(nc) m(i ，j)是背包容量为j ，可选择物品为i ，i+1，…，n 时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i ，j)的递归式如下。 void KnapSack(int v[],int w[],int c,int n,int m[][11]) {int jMax=min(w[n]-1,c); for (j=0;j<=jMax;j++) /*m(n,j)=0 0= for (j=w[n];j<=c;j++) /*m(n,j)=v[n] j>=w[n]*/ m[n][j]=v[n]; for (i=n-1;i>1;i--) { int jMax=min(w[i]-1,c); for (j=0;j<=jMax;j++) /*m(i,j)=m(i+1,j) 0= for (j=w[i];j<=c;j++)/*m(n,j)=v[n] j>=w[n]*/ 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]); } （3）回溯法 O(2n ) cw:当前重量 cp:当前价值 bestp ：当前最优值 void backtrack(int i) //回溯法 i 初值1 { 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); } i i i i w j w j j i m v w j i m j i m j i m <≤≥⎩ ⎨⎧++-++=0),1(}),1(),,1(max{),(n n n w j w j v j n m <≤≥⎩⎨⎧=00),(下载本文
