算法设计和复习题

算法设计与分析复习题
2022-2023
一、程序阅读分析
1、（10分）一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。阅读程序1，回答问题。

def greedy():
n=100
k=5
d=[20,80,39,40,50,43]
num=0
for I in range(k):
if d[i]>n:
print(‘no way’)
return
I,s=0,0
While i<=k:
S =d[i]
If s>=n:
S=d[i]
Num =1
I =1
Print(mun)
Greedy()

（1）代码的输入和输出分别是什么？（4分）
无需输入
输出为3
（2）代码选用的数据结构是什么？（1分）
列表
（3）代码选用的算法设计策略是什么？（2分）
贪心算法
（4）请改用自然语言描述代码1的求解步骤。（3分）
在该程序中 n 代表加满油能够走的距离， k 表示的是加油站的数量， d 列表表示每个加油站之间的距离其中第一个数据是第一个加油站到起点的距离，最后一个数据是最后一个加油站到终点的距离，在接下来的求解步骤中首先对 d 中数组的数量进行判断，若大于加满油的最高里程数，则输出 no way ，接着用 while 循环对每段距离进行检索判断， s 作为叠加距离数，如果叠加距离数大于了100,则证明需要加油一次，给 numi 计数加一，若不大于
100,则进行下一段距离叠加。以此类推得到最终的加油次数 num

2、（10分）阅读算法1，回答问题。
int BinarySearch(int s[],int x,int low,int high){
if(low>high) //递归结束条件
return -1;
int middle=(low high)/2; //计算middle值(查找范围的中间值)
if(x==s[middle]) //x等于s[middle]，查找成功
return middle;
else if(x<s[middle]) //x小于s[middle]，则在前半部分查找
return BinarySearch(s,x,low,middle-1);
else //x大于s[middle]，则在后半部分查找
return BinarySearch(s,x,middle 1,high);

（1）算法1的功能是什么？（3分）
査找元素（二分查找）
（2）请你设计至少4组输入，验证算法1的正确性。（4分）
输入: S =[12,15,20,34,62] x =12 low =0 high =4
因为10w< high , 故程序执行求出 middle =2，指向20，由于 S [ middle ]> x ，会进入 else if ( x < s [ middle ]）分支。进入递日 s =[12,15,20,34,62], x =12, low =0 high == middle -1=1 low < high 所以程序继续执行求出 middle =0（向下取整），由于 S [ middle ]= x ，所以返回 middle ，进入上一层递归，最后返回 middle = O 的结果，查找结束
（3）请改用自然语言描述算法1。（3分）
用 low 表示下界，用 high =( low high )/2用 middle 与 x 进行比较：① middle > x 则进行右递归查找 middle < x 则进行右递归 gmiddle = x 则查找成功返回 middle

3、（10分）阅读算法2，回答问题。
kn(int w[],int v[],int n,int C)//参数分别为物品重量、物品价值、物品数量、容量
for(int i=0;i<=n;i )
dp[i][0]=0;
for(int j=0;j<=C;j )]
dp[n][j]=0;
for(int i=n-1;i>=0;i–)
for(int j=0;j<=C;j )
if(j>=w[i-1])
dp[i][j]=max(dp[i 1][j],dp[i 1][j-w[i-1]]) v[i-1];
else dp[i][j]= dp[i 1][j];

（1）算法2设计策略是什么？（1分）
0-1背包的动态规划算法
（2）请根据算法2，写出递归关系式（包括递归方程和停止条件，缺一不可）。（3分）
递归方程： c [ i ] j ]= max { c [ i -1][ j ]. c [ i -1][ j - wi ] vi )停止条件：连加和 wi * xi >= w ( w 为背包可以容纳的重重量， wi 为第个物品重量） xiE (0,1}1<= i <= n
（4）解出该题的最优值和最优解（2分）
最优值 C [] jl = c [ i -1] jl 或者 c [ ti [ j ]= max ( c [ i -1] j ]. c [ i -1] j - wi ] vi ）最优解=(x1,x2,x3,x4… xn )=(0-1序列0代表不装，1代表装入）
二、算法设计：（每题13分，共 26 分）

1. （13分）阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有N堆金币，第i堆金币的总重量和总价值分别是m,v。阿里巴巴有一个承重量为T的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？
   （1）请给出存储已知数据的数据结构（2分）
   （2）请给出你选择的算法策略（2分）
   （3）请写出算法步骤（任选一种自然语言、伪代码、程序进行描述）（6分）
   （4）假设背包里有4个物品，请自行设计一个算法，并给出输出结果（物品的重量、价值、背包容量自拟）（3分）
   (1）数组
   (2）贪心算法
   (3）计算所有物品单位重量的价值，并按照单位重量的价值大小排序，依据贪心算法的策略将拍好的序列的物品依次向背包装入，可以分割物品直到背包正好装满
   (4）信息：
   物品编号：1234
   物品重量：2265
   物品价值：6364
   背包容量为6
   计算单位重量价值大小排序物品1，物品2，物品3，物品4
   ①将物品1装入，重量变为2②将物品2装入，装入变为2 2=4
   ③将物品3装入时，不能全部容量，所以将其进行分割，装入物品的1/3部分，背包容量正好装满，算法结束输出物品1，物品2，物品3的1/3部分
   总价值：11

2.（13分）游艇俱乐部在长江上设置了n个游艇出租站，游客可以在上游的出租站租用游艇，在下游的任何一个游艇出租站归还游艇。游艇出租站i到出租站j（i<j）之间的租金为r(i, j)。求解从游艇出租站1到游艇出租站n所需的最少的租金。
（1）写出选用的算法策略（2分）。
（2）写出该算法策略的思想（4分）。
（3）写出求解问题所用的数据结构（2分）。
（4）写出求解问题的算法步骤（可以选择自然语言、伪码、流程图、程序设计语言中的任何一种形式描述）（5分）。
（5）分析算法的时间复杂度和空间复杂度（2分）。
(1）动态规划算法

(2) d [ i ] j ］表示第个站点到第站点的最少租金。举出2个站点的最少租金，3个站点的最少租金．. n 个站点的最少租金。状态转移方程为 dpil [ j ]= min ( dp [ i ][ k ] dp [ k ] j ], dp [ i 们0)
(3）两个二位数组r00和dp00
(4) void rent0{
for ( int d =3; d < n ; d ){ for ( int i =1; i < n - d 1; i )
int j = i d -1;
for ( int k = i 1; k < j ; k ){
if ( dp [ i ] j ]> dp [ i ][ k ] dp [ k ] j ]) dp [ ijl = dp [ i ][ k ] dp [ k ] jl ;
}
}
}
(5）时间复杂度： O ( n -3n)空间复杂度： o ( n )

三、复杂度分析及创新：（每题10分，共 30 分）
1、分析算法3的时间复杂度和空间复杂度。
int partition(int r[], int low, int high){
int i=low, j=high, pivot=r[low];
while(i<j){
while(i<j && r[j]>pivot) j–; //从右向左扫描
if(i<j)
swap(r[i ], r[j]);
while(i<j && r[i]<=pivot) i ; //从左向右扫描
if(i<j)
swap(r[i], r[j–]);
}
return i;
}

时间复杂度：
最坏： O ( n * n )
最好： T ( n )= o (1) n <=1
2T( n /2) O ( n ) n >1
由主方法得 O ( nlogn )
空间复杂度：
最坏： o ( n )
最好： O ( logn )

2、请分析算法4的时间复杂度和空间复杂度，并给出一个更好的求解方法及求解步骤。
nQueens (int t)
{
if (t==n)
print(x);
else{
for(i=0;i<n;i )
{x[t]=i;
if(OK(t))
nQueens(t 1);
}
}

时间复杂度： O ( n * n )
空间复杂度：0( n !)
算法改进：利用约束条件和限界条件判断是否为可行解，从而避免了无效搜索，从而使时间复杂度变为 O ( n !)

3、（10分）请分析算法5的时间复杂度和空间复杂度，并给出算法5的非递归算法。
Def backtrack( t){//地图着色问题
Global colors,x,sum1,n,m,a
if(t>n){ //到达叶子,找到一个着色方案
sum1 =1
colors.append(x[:])
else:
for I in range(1,m 1):
x[t]=i
if(Ok(t)):
backtrack(t 1)

时间复杂度： O ( n * m ’ n ）空间复杂度： O ( n !）非递归算法
Def backtrack ( t ){
Global colors , x ,sum1, n . m , a ; if ( t > n ){
sum1 =1;
colors . append ( x [:]) else (
for ( int i = O ; i < n ; i ){
if ( color [ i ]==1&& sum [ i ]==sum1[ m ]){
return false ;
}
}
return true ;
}
}}

四、综合应用题（ 14 分） 评卷人 得分

1、三个矩阵大小分别为34、45、56，求其相乘的最优结合次序。
（1）写出所用的求解方法（4分）
（2）描述该方法求解的步骤（4分）
（3）给出求解过程（4分）
（4）给出求解结果（2分）。 
(1）可使用动态规划算法
(2）定义一个二维数组 m 存储最少乘法次数，二维数组 s 存储最优决策并分为初始化为0。按照区间长度（即剛﹣ i ）升序的原则，依次采用下式子计算所有的 m [ i ] j ］和 s []:
m [ i ] ji = min ( mu ][ k ] m [ k 1][ j ] P [ i -1] P [ k ] P [ j ]), i <= k < j
二 S [］门设置为达到最小值的 k 值，根据从 s [1][ n ］开始，从 s 的值依次构造最优解
(3）区间长度为1:
m [1][2]= P [0JP[1] P [2]=3°445=60, s [1][2]=1 m [2][3]= P [1] P [2] P [3]=45*6=120, s [1][1]=2
区间长度为2:
m [1][3]= min ( m [1][2] P [0] P [2] P [3], m [1][3] P [ O ] P [1] P [3])= min (150,192)=150, s [1][3]=2
(4）构造解根据 s 的值可以知道最优相乘次序：(A1’A2)A3

2021-2022
一、程序阅读分析（共50分）

1. （10分）阅读“算法1”，分析算法的功能、时间复杂度，并写出n=5时的求解过程。
   int fac(int n){
   if(n0||n1)
   return 1;
   else
   return n*fac(n-1);
   }

2. （10分）阅读“算法2”，分析算法的功能、时间复杂度，设计一个输入序列，并写出该输入序列的划分过程。
   int partition(int r[], int low, int high){
   int i=low, j=high, pivot=r[low];
   while(i<j){
   while(i<j && r[j]>pivot) j–; //从右向左扫描
   if(i<j)
   swap(r[i ], r[j]);
   while(i<j && r[i]<=pivot) i ; //从左向右扫描
   if(i<j)
   swap(r[i], r[j–]);

3. （10分）阅读“算法3”，分析算法的功能、时间复杂度，并给出一个例子，展示算法的运行过程。
   int BinarySearch(int s[],int x,int low,int high){
   if(low>high) //递归结束条件
   return -1;
   int middle=(low high)/2; //计算middle值(查找范围的中间值)
   if(x==s[middle]) //x等于s[middle]，查找成功
   return middle;
   else if(x<s[middle]) //x小于s[middle]，则在前半部分查找
   return BinarySearch(s,x,low,middle-1);

4. （10分）阅读“算法4”，算法中的a[]是一个整数序列，分析算法的时间复杂度，设计一个n=4的实例，并写出对应的算法求解过程。
   int LIS(){//最长上升子序列
   int ans=0;
   memset(dp,0,sizeof(dp)); //初始化dp[]为0
   for(int i=1;i<=n;i ){
   dp[i]=1;
   for(int j=1;j<i;j )
   if(a[j]<a[i]) //更新以a[i]结尾的最长上升子序列的长度
   dp[i]=max(dp[i],dp[j] 1);

5. （10分）“算法5”为回溯法求地图着色问题的函数，请写出该问题解的形式、解空间的组织结构和搜索条件。
   void backtrack(int t){//地图着色问题
   if(t>n){ //到达叶子,找到一个着色方案
   for(int i=1;i<=n;i ) //输出该着色方案
   cout<<x[i]<<" ";
   return;
   }
   for(int i=1;i<=m;i ){ //每个结点尝试m种颜色
   x[t]=i;
   if(judge(t))//第t个结点可以涂x[t]号色
   backtrack(t 1);
   }
   }

二、算法设计（共20分）
6. （10分）电文中有6种字符a, b, c, d, e, f，出现频率分别为0.2, 0.1, 0.06, 0.04, 0.44, 0.16，求解这6个字符的最优编码方案。
（1）描述所用的编码方法（2分）。
（2）写出每个字符的编码（6分）。
（3）求该编码方案的平均码长（2分）。

7. （10分）给定7个建筑物及其之间的网络布线成本，求使各个建筑物之间网络连通的最小布线费用。
   （1）写出所用的求解方法（2分）。
   （2）描述该方法求解的步骤（4分）。
   （3）写出求解过程（写明选择的边）（2分）。
   （4）写出最小布线费用（2分）。
   

三、综合应用（共30分）
1、（15分）游艇俱乐部在长江上设置了n个游艇出租站，游客可以在上游的出租站租用游艇，在下游的任何一个游艇出租站归还游艇。游艇出租站i到出租站j（i<j）之间的租金为r(i, j)。求解从游艇出租站1到游艇出租站n所需的最少的租金。
（1）写出选用的算法策略（2分）。
（2）写出该算法策略的思想（4分）。
（3）写出求解问题所用的数据结构（2分）。
（4）写出求解问题的算法步骤（可以选择自然语言、伪码、流程图、程序设计语言中的任何一种形式描述）（5分）。
（5）分析算法的时间复杂度和空间复杂度（2分）。

2、（15分）假设一个购物车的容量为W，超市里有n个物品，每个物品都有重量和价值。物品不能拆分，求解在不超过购物车容量的前提下，装入哪些物品使购物车内物品价值之和最大。
（1）写出选用的算法策略（2分）。
（2）写出该算法策略的思想（4分）。
（3）写出求解问题所用的数据结构（2分）。
（4）写出求解问题的算法步骤（可以选择自然语言、伪码、流程图、程序设计语言中的任何一种形式描述）（5分）。
（5）分析算法的时间复杂度和空间复杂度（2分）。

答案：
一、程序阅读分析（每小题10分，共50分）
1．（1）功能：求阶乘。（2分）
（2）时间复杂度：O(n)。（2分）
（3） n=5时的求解过程： 5fac(4)–4fac(3)–3fac(2)–2fac(1) fac(5)=120。（6分）
2．（1）功能：划分函数，将数据划分为两个子序列，右侧大于等于左侧元素。（2分）
（2）时间复杂度：O(n)。（2分）
（3）例如，30 24 5 58 18 36 12 42 39，结果12 24 5 18 30 36 58 42 39。（6分）
3．（1）功能：二分搜索或二分查找。（2分）
（2）时间复杂度：O(logn) （2分）
（3）例如，5 8 15 17 25 30 34 39 45 52 60，查找17，第1次和30比较，第2次和15比较，第3次查找成功。（6分）
4．（1）算法时间复杂度：O(n2)。（2分）
（2） n=4时的求解过程：例如，1 7 3 5，最长上升子序列为3，过程略。（8分）
5．（1）解的形式：{x1，x2，…，xi，…，xn}，xi =1，2，…，m（i=1,2,3,…,n）。（2分）
（2）组织结构：m叉树。（2分）
（3）搜索条件：第t个结点的色号与前t−1个结点中有边相连的结点颜色不同。（6分）
二、程序设计（共 20 分）
1．（1）将字符的使用频率作为叶子节点的权值，每次从树的集合中取出没有双亲且权值最小的两棵树作为左右子树，构造一棵新树，新树根节点的权值为其左右孩子节点权值之和，并将新树插入树的集合中。（2分）
（2）a,b,c,d,e,f 的最优编码：01,0000,00010,00011, 1,001。（6分）
（3）平均码长：2.22。（2分）
2．（1）Kruskal算法。（2分）
（2）将所有边按权值从小到大排序，边集TE={ }，每个顶点初始化一个集合号。找权值最小的边（i，j）。如果顶点i和j位于两个不同连通分支，则将边（i，j）加入边集，并将两个连通分支进行合并。如果选取边数等于n−1，算法结束。（4分）
（3）选择边4—5，5—6，3—6，1—2，2—5，5—7。（2分）
（4）最小布线费用：31。（2分）
三、综合应用（每题 15 分，共 30 分）

1. （1）动态规划算法。（2分）
   （2）dp[i][j]表示第i个站点到第j个站点的最少租金。枚举2个站点的最少租金，3个站点的最少租金，…，n个站点的最少租金。状态转移方程： （4分）
   （3）数据结构：两个二维数组r[][]和dp[][]。（2分）
   （4）算法步骤：
   void rent(){
   for(int d=3;d<=n;d ){//区间长度d
   for(int i=1;i<=n-d 1;i ){//状态起点i，终点j
   int j=i d-1;
   for(int k=i 1;k<j;k ){//枚举决策点k
   if(dp[i][j]>dp[i][k] dp[k][j])
   dp[i][j]=dp[i][k] dp[k][j];
   }
   }
   }
   }（5分）
   （5）时间复杂度：O(n3)，空间复杂度：O(n2)。（2分）
2. （1）回溯法。（2分）
   （2）解向量为（x1,x2,…,xn），xi=0或1(i=1,2,…,n)。解空间是一棵子集树，深度为4。
   约束条件：cw w[t]<=W
   限界条件：cp rp>bestp，其中cp表示当前已装入背包的物品的总价值，rp表示剩余物品的总价值，bestp表示当前找到的最优价值。（4分）
   （3）数据结构：x[]，bestx[]。（2分）
   （4）搜索过程：首先将根结点加入活结点表（用于存放活结点的数据结构），接着从活结点表中取出根结点，使其成为当前扩展结点，一次性生成其所有孩子结点，判断孩子结点是舍弃还是保留，舍弃那些导致不可行解或导致非最优解的孩子结点，其余的被保留在活结点表中。再从活结点表中取出一个活结点作为当前扩展结点，重复上述扩展过程，一直持续到找到所需的解或活结点表为空时为止。由此可见，每一个活结点最多只有一次机会成为扩展结点。（5分）
   （5）时间复杂度：O(2n)，空间复杂度：O(n)。（2分）

2020-2021
一、程序阅读题：（每题10 分，共50 分） 评卷人 得分

1、请阅读“算法1”，写出其功能，求出其时间复杂度（需要写出求解过程）。
void f（int a[],int n）
{
if( n > 1)
{
for(i=0;i<n-1;i )
if(a[i]<a[n-1])
swap(&a[i],&a[n-1]);// 以常数时间交换
f(a,n-1);
}
}

2、“算法2”中，arr是一个非降序数组（有大量重复元素），n为其大小，分析算法功能，并设计一个输入，给出对应的算法输出结果。
lowerbound(int arr[], int n,int key)
int low=0,high=n-1,mid;
while(low<high)
{
mid=(low high)/2;
if(arr[mid]<key)
low=mid 1;
else
high=mid;
}
return low;

3、“算法3”为求0-1背包问题的动态规划算法，请写出该问题中目标函数、约束条件和算法对应的状态转移方程。
kn(int w[],int v[],int n,int C)//参数分别为物品重量、物品价值、物品数量、容量
for(int i=0;i<=n;i )
dp[i][0]=0;
for(int j=0;j<=C;j )]
dp[n][j]=0;
for(int i=n-1;i>=0;i–)
for(int j=0;j<=C;j )
if(j>=w[i-1])
dp[i][j]=max(dp[i 1][j],dp[i 1][j-w[i-1]]) v[i-1];
else dp[i][j]= dp[i 1][j];

4、“算法4”是硬币找零问题的贪心算法，其中coins是存储硬币面值的数组（最小面值为1且已升序排序），n为面值数量,x[]为输出数组，m为待找零的钱数。请描述该算法的贪心策略，并设计一个该算法无法生成最优解的输入。
mincoin(int coins[],int n,int x[],int m)
{
int rm=m;
for(int i=n-1;i>=0&&rm>0;i–)
{
if(rm>coins[i])
{
x[i]=rm/coins[i];
rm%=coins[i];
}
}
}

5、“算法5”是求n皇后问题所有解的回溯算法，请按顺序写出n=4时算法所有输出。
nQueens (int t)
{
if (t==n)
print(x);
else{
for(i=0;i<n;i )
{x[t]=i;
if(OK(t))
nQueens(t 1);
}
}

二、应用题：（第1题8分，第2题12分，共 20 分） 评卷人 得分
1、选择一种算法，生成下图的最小生成树。
（1）描述所用的生成方法（4分）
（2）给出该图按照该方法求最小生成树的过程及结果（4分）。

2、三个矩阵大小分别为34、45、5*6，求其相乘的最优结合次序。
（1）写出所用的求解方法（2分）
（2）描述该方法求解的步骤（4分）
（3）给出求解过程（4分）
（4）给出求解结果（2分）。

三、分析编程题：（每小题15分，共 30分） 评卷人 得分

1、给定n个活动，需要安排所在的会议室，不能有两个活动同时在一个会议室中。第i个活动起始时间、终止时间分别为si、ei，如果将它安排在某个会议室，则开区间(si,ei)表示的时间段内不能有第二个活动。请设计一算法，判定是否能够用m(0<m<=n)个会议室，安排这些活动。
（1）给出选用的算法策略（2分）
（2）写出该算法策略的思想（4分）
（3）写出算法中所用的数据结构（2分）
（4）给出求解问题的算法步骤（可以选择自然语言、伪码、流程图、程序设计语言中的任何一种形式描述）（7分）

2、现有一个二叉树采用二叉链表形式存储，编程求其中根到叶的最短路径（如果有多条，只需输出一个）。
（1）给出选用的算法策略（2分）
（2）写出该算法策略的思想（4分）
（3）写出求解问题时所用的数据结构（2分）

答案：
一、程序阅读题：（每题10 分，共50 分）
1、请阅读“算法1”，写出其功能，求出其时间复杂度（需要写出求解过程）
答： 算法功能为对序列a进行降序排序；(4分)
for循环中，比较次数大约为2n次，而交换次数不大于n次，所以其时间可用n表示
算法执行时间递归式当n>1时T(n)=T(n-1) n ,T(1)=1 （3分）
展开该递归式得 T(n)= n (n-1) … 1≈1/2nn=Θ(nn)（3分）
评分标准：不完全正确者酌情扣分。
2、“算法2”中,arr是一个非降序数组（有大量重复元素），n为其大小，分析算法功能，并设计一个输入，给出对应的算法输出结果。
答： 算法的功能为求arr中不小于key的第一个元素（如果没有，则返回值为n）（5分）
例如：若 arr[]={12,13,13,14,14,15,15,15,16,17},key=15,则返回值为5 （5分）
评分标准：不完全正确者酌情扣分。
3、“算法3”为求0-1背包问题的动态规划算法，请写出该问题中目标函数、约束条件和算法对应的状态转移方程。
答：该问题的目标函数为 Max(Sum(xivi)),i=0…n-1,其中xi=0,1,记录第i个物品是否选择，vi为第i个物品的价值；（2分）
约束条件为 Sum(xi*wi)<=C，其中wi为第i个物品的重量;（2分）
算法对应的状态转移方程为:（6分）

4、“算法4”是硬币找零问题的贪心算法，其中coins是存储硬币面值的数组（最小面值为1且已升序排序）,n为面值数量,x[]为输出数组,m为待找零的钱数。请描述该算法的贪心策略，并设计一个该算法无法生成最优解的输入。
答： 贪心策略(5分)：优先使用面值较大的硬币
反例（5分）：coins[]={1,2,5,7},m=10，按照贪心算法需要3个硬币(7,2,1)，显然存在更优解(5,5)
评分标准：不完全正确者酌情扣分。
5、“算法5”是求n皇后问题所有解的回溯算法，请回答写出n=4时算法所有输出。
答：有2个解分别为：(1,3,0,2)和(2,0,3,1) （各5分）

二、计算题：（第1题8分，第2题12分）
1、选择一种算法，生成下图的最小生成树。
答： Kruskal算法：将连通网中所有的边按照权值大小做升序排序，从权值最小的边开始选择，只要此边不和已选择的边一起构成环路，就可以选择，直到选择了n-1条边为止。（3分）
边的选择过程为（2，3）、（2，4）、（4，5），（5，6）、（1，2）。（5分，各1分）

2、求三个矩阵A1、A2、A3的矩阵连乘问题，其大小分别为34、45、56、63。 
答： (1)可使用动态规划方法求解;（2分）
(2)定义一个二维数组m存储最少乘法次数，二维数组s存储最优决策并分别初始化为0;（1分）
按照区间长度(即j-i)升序的原则，依次采用下式计算所有的m[i][j]和s[i][j]：
m[i][j]=min{m[i][k] m[k 1][j] P[i-1]P[k]P[j]},i<=k<j （1分）
而s[i][j]设置为达到最小值的k值；（1分）
根据从s[1][n]开始,从s的值依次构造最优解（1分）
(3)区间长度为1: （2分）
m[1][2]=P[0]P[1]P[2]=345=60,s[1][2]=1;
m[2][3]=P[1]P[2]P[3]=456=120,s[1][2]=2;
区间长度为2：（2分）
m[1][3]=min(m[1][2] P[0]P[2]P[3],m[2][3] P[0]P[1]P[3])=min(150,192)=150,s[1][3]=2
(4)构造解：根据s的值可知最优相乘次序为 (A1*A2)*A3（2分）。

三、算法设计题：（每小题15分，共 30分）
1、给定n个活动，需要安排所在的会议室，不能有两个活动同时在一个会议室中。第i个活动起始时间、终止时间分别为si、ei。请设计一算法，判定是否能够用m(0<m<=n)个会议室，安排这些活动。
答：（1）贪心法；（2分）
（2）贪心法是指在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，通过若干次的贪心选择而得出最优解或较优解的一种方法。（4分）
（3）可以分别用数组s[],e[]存储活动的起始时间和终止时间 （2分）
（4）先将s、e分别从小到大排序，然后按照s的顺序依次确定每个活动是否需要一个新的会议室。（2分）
count=0;
for(int i=0,j=0;i<n;i )//e[j]为当前所有会议室中最后一个活动结束时间的最小值 （5分）
if(s[i]<e[j]){
count ;
if(count>m) return false;
}
else j ;
return true;

2、现有一个二叉树采用二叉链表形式存储，编程输出求其中根到叶的最长路径，如果有多条，只需要输出一个。
答：（1）回溯法 （2分）
（2）回溯法在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该节点是否包含问题的解。如果不包含，则跳过对以该节点为根的子树的搜索，逐层向其它祖先节点回溯。否则，进入该子树，继续按照深度优先策略搜索。(4分)
（3）为了存储当前路径，可以使用一个栈；为了存储最长路径,可使用一个数组（2分）
（4）void longest(binode*p,int t) {
if(!p) return; （1分）
else {
x[t]=p; （1分）
if(!p->lchild&!p->rchild) {（1分）
if(t> maxt){ copy(maxx,x); maxt=t;}（1分）
}
longest(p->lchild,t 1); （1分）
longest(p->rchild,t 1); （1分）
if(t==0) print(maxx) （1分）
}
}

这篇好文章是转载于：学新通技术网