算法设计期末试卷及答案

一．简述递归动态规划算法的基本步骤，以及动态规划算法与分治法的异同。

设计动态规划算法的主要步骤为：（最长公共子串，0/1背包）

（1）找出最优解的性质，并刻划其结构特征。

（2）递归地定义最优值。

（3）以自底向上的方式计算出最优值。

（4）根据计算最优值时得到的信息，构造最优解

分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。

二．分治法在每一层递归上都有三个步骤：（汉诺塔问题）

1.分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

2.解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；

3.合并：将各个子问题的解合并为原问题的解。

它的一般的算法设计模式如下：

Divide-and-Conquer(P)

1. if |P|≤n0

2. then return(ADHOC(P))

3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk

4. for i←1 to k

5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi

6. T ← MERGE(y1,y2,...,yk) △ 合并子问题

7. return(T)

三．分支限界法的搜索策略：（0/1背包，旅行售货员）

在当前节点（扩展节点）处，先生成其所有的儿子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。

为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处，计算一个函数值（限界），并根据函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。

分支限界法解决了大量离散最优化的问题。

四．回溯法一般步骤：（）

（1）针对所给问题，定义问题的解空间；

（2）确定易于搜索的解空间结构；

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯法可用递归实现：

procedure try(i:integer);

var

begin

if i>n then 输出结果

else for j:=下界 to 上界 do

begin

x[i]:=h[j];

if 可行{满足限界函数和约束条件} then begin 置值；try(i+1); end;

end;

end;

五．贪心算法的步骤：（）

1. 建立数学模型来描述问题。

2. 把求解的问题分成若干个子问题。

3. 对每一子问题求解，得到子问题的局部最优解。

4. 把子问题的解局部最优解合成原来解问题的一个解。

1.当所给问题是从n个元素的集合S中找出S满足某种性质的子集时，相应的解空间称为子集树。例如：n个物品的0-1背包问题所相应的解空间是一棵子集树，这类子集树通常有2^n个叶结点，其结点总数为(2^(n+1))-1。遍历子集树的算法通常需奥秘加(2^n)计算时间。回溯法搜索子集树的算法一般可以描述如下：

void backtrack(int t) {

if (t > n)

output(x);

else

for (int i = 0; i < l; i++) {

x[t] = i;

if (constraint(t) && bound(t))

backtrack(t + 1);

}

}

2.当所给问题的确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶结点。因此遍历排列树需要奥秘加(n!)计算时间。旅行售货员问题的解空间是一棵排列树。回溯法搜索排列树的算法一般可以描述如下：

void backtrack(int t) {

if (t > n)

output(x);

else

for (int i = t; i < n; i++) {

swap(x[t], x[i]);

if (constraint(t) && bound(t))

backtrack(t + 1);

swap(x[t], x[i]);

}

}

1.贪心算法：能够得到某种量度意义下的最优解的分级处理方法称为贪心算法。

2.分治法：分治法的求解思想就是把整个问题分成若干个小问题后分的治之

3.递归过程：一个递归过程的执行类似于多个子程序的嵌套调用，递归过程是

自己调用自己本身代码。

4.动态规划：是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。

5.分支限界法：是一种用于求解组合优化问题的排除非解的搜索算法。

1.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解，这要求原问题和子问题（）。

A.问题规模不同，问题性质相同B.问题规模不同，问题性质不同C.问题规模相同，问题性质不同D.问题规模相同，问题性质相同

2.下面不是分支界限法搜索方式的是（）。

A.广度优先B.最小耗费优先C.最大效益优先D.深度优先

3.动态规划算法的基本要素为（）。

A.最优子结构性质与贪心选择性质B.重叠子问题性质与贪心选择性质

C.最优子结构性性质与重叠子问题性质D.预排序与递归调用

4.下列关于贪心算法和动态规划算法的比较正确的是：（）

A.贪心算法求得的解是整体最优解，而动态规划求得的解可能是局部优化解；

B.动态规划可以解决非最优化问题，而贪心算法只能用于解最优化问题；

C.两者的共同点是求解问题必须具有最优子结构性质，且每次操作都是使所求问题简化为规模更小的子问题；

D.两者都是采用自底向上的方式求解问题；

5.下列算法中通常以深度优先方式系统搜索问题解的是（）。

A.备忘录法 B.动态规划法 C.回溯法 D.贪心法

6.下面哪种函数是回溯法中为避免无效搜索策略采取的策略（）

A.递归函数 B.剪枝函数 C.随机数函数 D.搜索函数

7.下列有关优先队列式分支限界法的描述正确的是：（）

A.活结点堆中结点最后处理的是解空间树中未被剪枝的叶子结点；

B.搜索过程中产生的活结点插入活结点队列中，每次按FIFO的规则选取下一个活结点作为

当前扩展结点，算法直到队列为空结束；

C.算法是采用广度优先的方式搜索解空间树；

D.优先队列式分支限界法一次性将当前扩展结点的所有子结点插入堆中

8.哈夫曼编码的贪心算法所需的计算时间为（）

A.O（n2n） B.(n对数n) C.O(2n) D.O(n)

9.分支限界法解旅行售货员问题时，活结点表的组织形式是（）。

A.最小堆 B.最大堆 C.栈 D.数组

10.下列关于贪心算法描述不正确的是（）

A.贪心算法不是对所有最优化问题都能得到整体最优解

B.贪心算法只能用于求解最优化问题

C.贪心算法的基本要素是贪心选择性质

D.贪心选择性质是指整体最优解可以通过一系列局部最优选择得到

11.回溯法和分支限界法的问题的解空间树不会是（）。

A.有序树 B.子集树 C.排列树 D.无序树

12.最大效益优先是（）的一种搜索方式。

A.分支限界法 B.动态规划法 C.贪心法 D.回溯法

1.汉诺塔问题（将塔座A上的所有圆盘移到塔座C上）

void hanoi(int n,int A,int B,int C)

{

if(n>0){

hanoi(n-1,A,C,B);

_________move(a,b)______;

_hanoi(n-1,c,b,a);_______________;

}

}

2.背包问题的贪心算法

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;

for(i=1;i<=n;i++)

{

if(w[i]>c) break;

x[i]=1;

_____ c=c-w[i];_______________;

}

if（i<=n）

____ x[i]=c/w[i]; ________________;

}

3.快速排序问题

void QuickSort（Type a[],int p,int r）{

if(p

int q=Partition(a,p,r);

_____ QuickSort(a,p,q-1);________;

//对左半段排序

__ QuickSort(a,q+1,r);___________;

//对右半段排序

}

}

4.最大子段和：动态规划算法

int MaxSum（int n,int a[]）

{

int sum=0,b=0;//sum存放当前最大的b[j],b存储b[j]

for（int j=1;j<=n;j++）{

if(b>0) b+=a[j];

else ____ b=a[j] ________________;//

一旦某个区段和为负，则从下一个位置和

if(b>sum)__ sum=b_________;

}