当前位置:首页 >> 数学 >> 算法复习题(精炼版)

算法复习题(精炼版)


填空题
动态规划算法的基本要素为:最优子结构性质与重叠子问题性质 1) 算法分析中,记号 O 表示渐进上界,记号 ? 表示渐进下界, 记号 ? 表示紧渐进界。 2) 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。 3) 分支限界法在问题的解空间树中,按广度优先策略,从根结点出发搜索解空间树。 所谓贪心选择性质是指 (所求问题的整体最优解可以通过一系

列局部最优的选择, 即贪 心选择来达到) 。 所谓最优子结构性质是指(问题的最优解包含了其子问题的最优解) 。 回溯法是指(具有限界函数的深度优先生成法) 。 回溯法的算法框架按照问题的解空间一般分为(子集树)算法框架与(排列树)算法框 架。 4) 5) 6) 7) 8) 9) 10) 11) 12) 二分搜索算法是利用分治策略实现的算法。 衡量一个算法好坏的标准是时间复杂度低 最长公共子序列算法利用的算法是动态规划法 Strassen 矩阵乘法是利用分治策略实现的算法 回溯法搜索状态空间树是按照深度优先遍历的顺序。 算法中通常以自底向下的方式求解最优解的是动态规划法 背包问题的贪心算法所需的计算时间为 O(nlogn) 0-1 背包问题的回溯算法所需的计算时间为 O(n2n) 用动态规划算法解决最大字段和问题,其时间复杂性为 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 着色问题可用 回溯 树中每个内结点的孩子数是 m

规模

有关。

法求解,其解空间树中叶子结点个数是 。

mn

,解空间

简答题
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)

当 i ? 0 或 j? 0 时 ?0 ? c[i, j ]? ?c [ i? 1 , j ? 1 ]? 1 当i, j ? 0 且 xi ? yi时 ?m a x ( c [ i, j ?1 ] , c [ i? 1 , j ]) 当 i , j ? 0 且 xi ? yi时 ?
(2) Y X B C D A 0 0 0 0 A 0 0 0 0 1 B 0 1 1 1 1 C 0 1 2 2 2 B 0 1 2 2 2 最长公共子序列: {BC}

2. 对下列各组函数 f (n) 和 g (n), 确定 f (n) = O (g (n)) 或 f (n) =Ω (g (n))或 f(n) = θ (g(n)),并简要说明理由。 (1) f(n)=2n ; (2) f(n)= n ; (3) f(n)=100; (4) f(n)=n3 ; (5) f(n)=3n ; 答: (1) f(n) = O(g(n)) (2) f(n) = Ω (g(n)) (3) f(n) = θ (g(n)) 因为 g(n)的阶比 f(n)的阶高。 因为 g(n)的阶比 f(n)的阶低。 因为 g(n)与 f(n)同阶。 g(n)=n! g (n)=log n2 g(n)=log100 g(n)= 3n g(n)=2n

(4) f(n) = O(g(n)) (5) f(n) = Ω (g(n))

因为 g(n)的阶比 f(n)的阶高。 因为 g(n)的阶比 f(n)的阶低。

3.对下图所示的连通网络 G,用克鲁斯卡尔(Kruskal)算法求 G 的最小生成树 T,请写出在算法执行过程中,依次加入 T 的边集 TE 中的边。说明该算法的贪心 策略和算法的基本思想,并简要分析算法的时间复杂度。
1 11 5 18 21 26 6 17 19 15 2 9 4 6 7 3

答: TE={(3,4), (2,3),(1,5),(4,6) (4,5)} 贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。 基本思想:首先将图中所有顶点都放到生成树中,然后每次都在连接两个不 同连通分量的边中选权值最小的边, 将其放入生成树中, 直到生成树中有 n-1 条边。 时间复杂度为:O(eloge) 4. 请用分治策略设计递归的归并排序算法,并分析其时间复杂性(要求:分别 给出 divide、conquer、combine 这三个阶段所花的时间,并在此基础上列出递归 方程,最后用套用公式法求出其解的渐进阶) 。 答 : 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 阶段的时间复杂性: Combine 阶段的时间复杂性:

2T(n) Θ (n)

θ(1) ? T(n)? ? ?θ(n) ?2T(n/2)

当n ? 1 当n ? 1
因为 f(n)与 nlog ba 同阶,

用套用公式法:a=2, b=2, nlog ba = n , f(n)=n, ∴T(n) =Θ (nlogn)

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)=?(n)。 8. 考虑使用动态规划方法求解下列问题: 01背包数据如下表,求:能够放入背包的最有价值的物品集合。

物品 i 1 2 3 4

重量 wi w1=2 w2=1 w3=3 w4=2

价值 vi v1=12 v2=10 v3=20 v4=15

承重量 W

W=5

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

V(0, j) = 0(0个物品) ,V(i, 0) = 0(承重量0) V(i, j) = V(i-1, j) V(i, j) = max { 第 i 个物品不能装入, , j < wi (超重) } j > wi (不超重)

i在最优子集中

i不在最优子集中

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

V i=0 1 2 3 4

j=0 0 0 0 0 0

1 0

2 0

3 0

4 0

5 0

答: V(0, j) = 0(0个物品) ,V(i, 0) = 0(承重量0) V(i, j) = V(i-1, j) 第 i 个物品不能装入, , j < wi (超重) } j > wi (不超重)

V(i, j) = max { vi + V(i-1,j-wj) i在最优子集中

V(i-1, j)

i不在最优子集中

V i=0 1 2 3 4

j=0 0 0 0 0 0

1 0 0 10 10 10

2 0 12 12 12 15

3 0 12 22 22 25

4 0 12 22 30 30

5 0 12 22 32 37

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























11,请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20, 15, 10},
价值为{20, 30, 25},背包容量为25时搜索空间树。 答: 解空间树:

1 1 0

2 1 0 1

9

0

3 0 1

6

10 0

3 0 1 0

1

1

4

5

7
1

8

11

12

14

15

1

0

2 1 0 10 0 1 0 1

9 0 13 1 0

6 1

8 不可行解 价值=20 价值=55

11

12 价值=30

14 价值=25

15 价值=0


更多相关文档:

...第九章 第一节算法的概念与程序框图课时精练试题 文...

【金版学案】2015届高考数学总复习 第九章 第一节算法的概念与程序框图课时精练试题 文(含解析)_数学_高中教育_教育专区。第九章 算法初步、 统计与统计案例、 ...

数据结构与算法复习题10(C语言版)

数据结构与算法复习题10(C语言版)_总结/汇报_应用文书。数据结构与算法复习题(C语言版)习题10 解答判断题: 判断题: 1.排序的功能是将一个数据元素(或记录)的...

数据结构与算法C++版_模拟试题

数据结构与算法C++版_模拟试题_IT/计算机_专业资料。一份数据结构与算法的模拟...递归算法的程序结构比迭代算法的程序结构更为精炼 C)树是一种线性结构 D)用...

1.1.1算法概念试题教师版

1.1.1算法概念试题教师版_数学_高中教育_教育专区。1.1.1 算法的概念 一、...(1)这个算法解决的问题是___; (2)当输入的 x 值为___时,输入值与输出值...

中南民族大学算法复习资料(习题-中文版)

中南民族大学算法复习资料(习题-中文版)_高等教育_教育专区。中南民族大学算法复习资料(习题-中文版) 一,选择题 1,下列公式可被视为一个计算三角形面积的一面...

算法设计与分析期末试题终极版

算法设计与分析期末试题终极版_其它_高等教育_教育专区。1 、用计算机求解问题的...1 、用计算机求解问题的步 骤: 1、问题分析 2、数学模型建 立 3、算法设计...

算法设计与分析期末试题_考试版

算法设计与分析期末试题_考试版_工学_高等教育_教育专区。1、用计算机求解问题的步骤: 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法...

算法复习题1

算法复习题1_数学_高中教育_教育专区。1、二分搜索算法是利用( A、分治策略 ...科目三实际道路驾驶考试注意事项 驾考新题抢先版文档贡献者 维达pp休 贡献于2013...

算法复习整理(第2版)

算法复习整理(第2版)_计算机软件及应用_IT/计算机_专业资料。算法分析课程改进算法和提高计算机处理能力对算法速度的影响 (课堂 上讲过相关提高算法效率的实例) 上界...

算法设计与分析期末试题 考试版

算法设计与分析期末试题 考试版_工学_高等教育_教育专区。算法设计与分析(第2版)吕国英主编(第三章课后习题)1、用计算机求解问题的步骤: 、用计算机求解问题的步骤...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com