算法复习题(精炼版).doc

填空题
动态规划算法的基本要素为：最优子结构性质与重叠子问题性质
1) 算法分析中，记号O表示渐进上界，记号表示渐进下界， 记号表示紧渐进界。
2) 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。
3) 分支限界法在问题的解空间树中，按广度优先策略，从根结点出发搜索解空间树。
所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到）。
所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。
回溯法是回溯法是指（具有限界函数的深度优先生成法）。
回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架。
4) 二分搜索算法是利用分治策略实现的算法。
5) 衡量一个算法好坏的标准是时间复杂度低
6) 最长公共子序列算法利用的算法是动态规划法
7) Strassen矩阵乘法是利用分治策略实现的算法
8) 回溯法搜索状态空间树是按照深度优先遍历的顺序。
9) 算法中通常以自底向下的方式求解最优解的是动态规划法
10) 背包问题的贪心算法所需的计算时间为O（nlogn）
11) 0-1背包问题的回溯算法所需的计算时间为O（n2n）
12) 用动态规划算法解决最大字段和问题，其时间复杂性为n
13) 一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_有穷性，确定性，可行性，输入，输出。
1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。
2、程序是 算法     用某种程序设计语言的具体实现。
3、算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。
4.矩阵连乘问题的算法可由 动态规划 设计实现。
6、算法是指解决问题的 一种方法 或 一个过程 。
7、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。
8、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。
9、以深度优先方式系统搜索问题解的算法称为 回溯法 。
10、数值概率算法常用于 数值问题 的求解。
15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ，只使用约束条件进行裁剪的是 N皇后问题 。
16、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
17、矩阵连乘问题的算法可由 动态规划 设计实现。
19.贪心算法的基本要素是 贪心选择 质和 最优子结构 性质 。
21. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题 的解得到原问题的解。
23、大整数乘积算法是用 分治法 来设计的。
26、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
27.快速排序算法是基于 分治策略 的一种排序算法。
30.回溯法是一种既带有 系统性 又带有 跳跃性 的搜索算法。
33．回溯法搜索解空间树时，常用的两种剪枝函数为 约束函数 和 限界函数 。
34.任何可用计算机求解的问题所需的时间都与其 规模 有关。
35.快速排序算法的性能取决于 划分的对称性 。
37. 图的m着色问题可用 回溯 法求解，其解空间树中叶子结点个数是 mn ，解空间树中每个内结点的孩子数是 m 。
简答题
1.用计算机求解问题的步骤：
1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制
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])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}

编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。
　　斐波那契数列为：0、1、1、2、3、……，即：
　　fib(0)=0;
　　fib(1)=1;
　　fib(n)=fib(n-1)+fib(n-2) （当n>1时）。
　　写成递归函数有：
　　int fib(int n)
　　{ if (n==0) return 0;
　　if (n==1) return 1;
　　if (n>1) return fib(n-1)+fib(n-2);
　　}

2. 算法定义：
算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程
3.算法的三要素
1、操作2、控制结构3、数据结构
4. 算法具有以下5个属性：
　　有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
　　确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口
　　可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
　　输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
　　输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

经常采用的算法主要有迭代法、分治法、贪婪法、动态规划法、回溯法、分支限界法
8.分治法的基本思想是：
将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。
9.分治法所能解决的问题一般具有以下几个特征：
（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

10、分治法的基本步骤
分治法在每一层递归上都有三个步骤：
（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
（3）合并：将各个子问题的解合并为原问题的解。
11. 动态规划的基本思想
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
13. 分治法与动态规划法的相同点是：
将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。
14. 回溯法
      回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。
20. 回溯法中常见的两类典型的解空间树是子集树和排列树。
当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O(2n)计算时间 。
当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。
22. 请叙述动态规划算法与贪心算法的异同。
共同点：
都需要最优子结构性质，
都用来求有优化问题。
不同点：
动态规划：每一步作一个选择—依赖于子问题的解。
贪心方法：每一步作一个选择—不依赖于子问题的解。
动态规划方法的条件：子问题的重叠性质。
可用贪心方法的条件：最优子结构性质；贪心选择性质。
动态规划：自底向上求解；
贪心方法： 自顶向下求解。
可用贪心法时，动态规划方法可能不适用；
可用动态规划方法时，贪心法可能不适用。
23. 请说明动态规划方法为什么需要最优子结构性质。
答：
最优子结构性质是指大问题的最优解包含子问题的最优解。
动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构.
26. 在算法复杂性分析中，O、Ω、Θ这三个记号的意义是什么？在忽略常数因子的情况
下，O、Ω、Θ分别提供了算法运行时间的什么界？
答：
如果存在两个正常数c和N0,对于所有的N≥N0，有|f(N)|≤C|g(N)|，则记作：f(N)= O(g(N))。这时我们说f(N)的阶不高于g(N)的阶。
若存在两个正常数C和自然数N0，使得当N ≥ N0时有|f(N)|≥C|g(N)|，记为f(N)=Ω(g(N))。这时我们说f(N)的阶不低于g(N)的阶。
如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g(N)| ≤|f(N)| ≤ c2|g(N)|
则记作 f(N)= (g,(N))
O、Ω、Θ分别提供了算法运行时间的上界、下界、平均
1．用动态规划策略求解最长公共子序列问题：
（1）给出计算最优值的递归方程。
（2）给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公共子序列，要求给出过程。
答：
(1)

(2)
　　　Ｙ　Ａ　Ｂ　Ｃ　Ｂ
Ｘ　　　　0　 0　 0　 0
Ｂ　　0　 0　 1　 1　 1
Ｃ　　0　 0　 1　 2　 2
Ｄ　　0　 0 1 2 2
Ａ　　0 1 1 2 2 最长公共子序列：｛ＢＣ｝

2．对下列各组函数f (n) 和g (n)，确定f (n) = O (g (n)) 或f (n) =Ω(g (n))或f(n) =θ(g(n))，并简要说明理由。
(1) f(n)=2n； g(n)=n!
(2) f(n)=； g (n)=log n2
(3) f(n)=100； g(n)=log100
(4) f(n)=n3； g(n)= 3n
(5) f(n)=3n； g(n)=2n
答：
(1) f(n) = O(g(n)) 因为g(n)的阶比f(n)的阶高。
(2) f(n) = Ω(g(n)) 因为g(n)的阶比f(n)的阶低。
(3) f(n) = θ(g(n)) 因为g(n)与f(n)同阶。
(4) f(n) = O(g(n)) 因为g(n)的阶比f(n)的阶高。
(5) f(n) = Ω(g(n)) 因为g(n)的阶比f(n)的阶低。
3．对下图所示的连通网络G，用克鲁斯卡尔(Kruskal)算法求G的最小生成树T,请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。
1
2
3
4
5
6
18
11
17
15
19
21
26
6
7
9
答：
TE={(3,4), (2,3),(1,5),（4,6）（4,5）}
贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。
基本思想：首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边。
时间复杂度为：O(eloge)
4. 请用分治策略设计递归的归并排序算法，并分析其时间复杂性（要求：分别给出divide、conquer、bine这三个阶段所花的时间，并在此基础上列出递归方程，最后用套用公式法求出其解的渐进阶）。
答 ： Template <class Type>
void MergeSort (Type a[ ], int left, int right)
{ if (left<right)
{ int i=（left+right）/2;
MergeSort（a, left, i）;
MergeSort（a, i+1, right）;
Merge(a, b, left, right);
Copy(a, b, left, right);
}
}
Divide 阶段的时间复杂性： O(1)
Conquer阶段的时间复杂性： 2T(n)
bine阶段的时间复杂性： Θ(n)

用套用公式法：a=2, b=2, nlog ba = n , f(n)=n, 因为f(n)与nlog ba 同阶，
∴T(n) =Θ(nlogn)

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
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
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

7.考虑在序列A[1..n]中找最大最小元素的问题。一个分治算法描述如下：如果n≤2 就直接求解。否则，将序列等分成两个子序列A[1..n/2]和A[n/2+1..n]，分别找出这两子序列的最大最小元素x1,y1 和x2,y2；然后据此求出A[1..n]的最大元素x=max{x1,x2}及最小元素y=min{y1,y2}。请给出该算法计算时间T(n)满足的递归方程，并解方程来确定算法的时间复杂度。假定n=2k（k 为正整数）。
答：
算法时间复杂度满足如下递归方程：
T(n)=2T(n/2)+2（n>2）；T(2)=1。
因为 n=2 k（k 为正整数），所以，
T(n)= T(2 k)= 2T(2 k-1)+2= 22T(2 k-2)+ 22+2
⋯
= 2k-1T(2)+ 2k-2+⋯+23+22+2
= 2k-1+⋯+23+22+2。因此，T(n)=Q(n)。
8. 考虑使用动态规划方法求解下列问题：
01背包数据如下表，求：能够放入背包的最有价值的物品集合。

物品
i
重量 wi
价值 vi
承重量 W
1
w1=2
v1=12
W=5
2
w2=1
v2=10
3
w3=3
v3=20
4
w4=2
v4=15

如设： V(i, j) —— 前 i 个物品中能够装入承重量 j 的背包中的最大总价值。请将如下递推式填写完整：

V(0, j) = 0（0个物品），V(i, 0) = 0（承重量0）
V(i, j) = V(i-1, j) 第 i 个物品不能装入， j < wi （超重）
V(i, j) = max { , } j > wi （不超重）
i在最优子集中 i不在最优子集中

自底向上：按行或列填写下表。

V
j=0
1
2
3
4
5
i=0
0
0
0
0
0
0
1
0

2
0

3
0

4
0

V
j=0
1
2
3
4
5
i=0
0
0
0
0
0
0
1
0

2
0

3
0

4
0

答：
V(0, j) = 0（0个物品），V(i, 0) = 0（承重量0）
V(i, j) = V(i-1, j) 第 i 个物品不能装入， j < wi （超重）
V(i, j) = max { vi + V(i-1,j-wj) , V(i-1, j) } j > wi （不超重）
i在最优子集中 i不在最优子集中

V
j=0
1
2
3
4
5
i=0
0
0
0
0
0
0
1
0

2
0

3
0

4
0

V
j=0
1
2
3
4
5
i=0
0
0
0
0
0
0
1
0
0
12
12
12
12
2
0
10
12
22
22
22
3
0
10
12
22
30
32
4
0
10
15
25
30
37

9.请画出用回溯法解4皇后问题的解空间树和搜索空间树：
解空间树：

用回溯法的搜索空间树：

11，请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20, 15, 10}，价值为{20, 30, 25}，背包容量为25时搜索空间树。
答：
解空间树：
1
1
1
1
1
1
0
0
0
0
0
0
0
1
1
2
3
4
5
7
8
11
12
14
15
3
10
6
9
1
不可行解
价值=20
价值=55
价值=30
价值=25
价值=0
1
1
1
1
0
0
0
0
0
0
1
1
2

8
11
12
14
15
13
10
6
9