算法期末复习题final

1、算法期末复习题final算法分析与设计期末复习题目一、选择题1下列算法中通常以自底向上的方式求解最优解的是（B）。A、备忘录法B、动态规划法C、贪心法D、回溯法2、衡量一个算法好坏的标准是（C ）。A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短3、以下不可以使用分治法求解的是（D ）。A 棋盘覆盖问题 B 选择问题 C 归并排序4下列是动态规划算法基本要素的是（A、定义最优解 B、构造最优解D 0/1背包问题D）。C、算出最优解D、子问题重叠性质5采用广度优先策略搜索的算法是（A）。A、分支界限法B、动态规划法C、贪心法D、回溯法6、合并排序算法是利用（A）实现的算法。A、分治策

2、略B 、动态规划法C、贪心法D 、回溯法7、下列不属于影响程序执行时间的因素有哪些？（C）A算法设计的策略B问题的规模C编译程序产生的机器代码质量D计算机执行指令的速度8、使用分治法求解不需要满足的条件是（A ）。A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解9、下面问题（ B ）不能使用贪心法解决。A 单源最短路径问题B N 皇后问题C 最小花费生成树问题D 背包问题10. 一 个问 题可 用动 态规 划算 法或 贪心 算法 求解的 关键 特征 是问 题的（B）。算法期末复习题finalA、重叠子问题B、最优子结构性质C、贪心选择性质D、定

3、义最优解11.以深度优先方式系统搜索问题解的算法称为(D)。A、分支界限算法B 、概率算法C、贪心算法D 、回溯算法12.实现最长公共子序列利用的算法是（B）。A、分治策略B、动态规划法C、贪心法D、回溯法13下列算法具有最优子结构的算法是A概率算法 B 回溯法（D）C分支限界法D 动态规划法14. 算法分析是（ C）A. 将算法用某种程序设计语言恰当地表示出来B. 在抽象数据集合上执行程序 , 以确定是否会产生错误的结果C. 对算法需要多少计算时间和存储空间作定量分析D. 证明算法对所有可能的合法输入都能算出正确的答案15 衡量一个算法好坏的标准是（C ）A. 运行速度快 B.占用空间少 C

4、. 时间复杂度低 D.代码短16. 二分搜索算法是利用（ A）实现的算法。A. 分治法B. 动态规划法C.贪心法D.回溯法17用贪心法设计算法的关键是（B ）。A. 将问题分解为多个子问题来分别处理B. 选好最优量度标准C. 获取各阶段间的递推关系式D. 满足最优性原理18. 找最小生成树的算法 Kruskal 的时间复杂度为（ D ）（其中 n 为无向图的结点数， m为边数）AO(n2) B O(mlogn) C O(nlogm) D O(mlogm)19. 回溯法搜索状态空间树是按照（ C ）的顺序。20. 采用广度优先策略搜索的算法是（ A ）。A. 分支界限法B. 动态规划法C. 贪心

5、法D.回溯法n21. 函数 32 +10nlogn 的渐进表达式是 ( B).A.O( 2n)B. O( 32n)C. O( nlogn)D. O( 10nlogn)22. 二分搜索算法的时间复杂性为（ C ）。A.O( n 2)B.O(n )C.O(log n )D. O(n log n)23、快速排序算法的时间复杂性为（D ）。A.O( n 2)B.O(n )C.O(log n )D. O(n log n)24、算法是由若干条指令组成的有穷序列，而且满足以下性质（D）A. 输入：有 0 个或多个输入B.输出：至少有一个输出C. 确定性：指令清晰，无歧义 D.有限性：指令执行次数有限，而且执

6、行时间算法期末复习题final有限A. (1)(2)(3)B. (1)(2)(4)C. (1)(3)(4)D.(1) (2)(3)(4)25、背包问题的贪心算法所需的计算时间为（A. O （ n2n）B. O（ nlogn ）C.OB）（ 2n）D.O（n）26. 下列算法中不能解决0/1 背包问题的是（A）A 贪心法B 动态规划C 回溯法D 分支限界法27. 在寻找 n 个元素中第 k 小元素问题中，若使用快速排序算法思想，运用分治算法对 n 个元素进行划分，应如何选择划分基准？下面(D)答案解释最合理。A随机选择一个元素作为划分基准B取子序列的第一个元素作为划分基准C用中位数的中位数方法寻

7、找划分基准D以上皆可行。但不同方法，算法复杂度上界可能不同28. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题， 最后将子问题的解组合起来形成原问题的解。 这要求原问题和子问题 ( C ) 。A问题规模相同，问题性质相同C问题规模不同，问题性质相同29、下面是贪心算法的基本要素的是（B问题规模相同，问题性质不同D问题规模不同，问题性质不同C）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解30. 函数 3n 2 10n 的渐进表达式是（ D ）。A. O( 3n2)B. O(3 ) C. O( 10n ) D.O( n 2)二、填空题1、解决

8、0/1 背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法，分支限界法。2、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界， N 皇后问题和 0/1 背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0/1背包问题，只使用约束条件进行裁剪的是N皇后问题。3.贪心算法基本要素有最优度量标准和 最优子结构 。4.回溯法解旅行售货员问题时的解空间树是排列树。5.二分搜索算法是利用分治策略实现的算法。算法期末复习题final6. 算法的复杂性有时间复杂性和空间复杂性之分。7、程序是算法用某种程序设计语言的具体

9、实现。8、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。9. 矩阵连乘问题的算法可由动态规划设计实现。10回溯法搜索解空间树时， 常用的两种剪枝函数为约束函数和限界函数。11.任何可用计算机求解的问题所需的时间都与其规模有关。12.快速排序算法的性能取决于划分的对称性。13. 背包问题的贪心算法void Knapsack(int n,float M,float v,float w,float x)Sort(n,v,w);int i;for (i=1;i=n;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c - =wi;if (i=1算法期末

10、复习题final3.for j=1 to n4.count =count+15.end for6.n=n/27.end whileend COUNT15.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和 有限性四条性质。16. 快速排序、插入排序和选择排序算法中，快速排序算法是分治算法。17.下面 算法 的基 本语句是 _ S = S + i*j;_,算法 的时 间复杂 度是_O(n 2)_int fun(int n)int S = 0;for (int i=1; i =n; i+ )for(int j=1; j=1while(1)xk=xk+1if color(k) theni

11、f(2)thenflag=true; output x1.nelsek=(3)(4)end ifend ifend while(5)end whileif not flag then output “no solution”end m-COLORING(1) xkm(2) k=n(3) k+1(4) xk=0(5) k=k-12下面是求解矩阵链乘问题的动态规划算法。矩阵链乘问题：给出 n 个矩阵 M 1 2n, Mi为iri+1 阶矩阵，, M , Mri=1,2, , n，求计算 M 1M 2 M n 所需的最少数量乘法次数。记 M i, j =Mi M i+1M j , i=j 。设 Ci

12、, j, 1=i=j=n,表示计算 M i, j 的所需的最少数量乘法次数，则C i, j0, ijmin Ci , k - 1 Ck, jri rkrj 1 , iji k j算法 MATCHAIN输入：矩阵链长度n, n 个矩阵的阶 r1.n+1, 其中 r1.n 为 n 个矩阵的行数，算法期末复习题finalrn+1 为第 n 个矩阵的列数。输出： n 个矩阵链乘所需的数量乘法的最少次数。for i=1 to n Ci, i=（1）for d=1 to n-1for i=1 to n-dj=(2)Ci, j= for k=i+1 to jx=(3)if xCi, j then(4) =x

13、end ifend forend forend forreturn(5)end MATCHAIN(1)0(2) i+d(3) Ci, k-1+Ck, j+ri*rk*rj+1(4)Ci, j(5) C1, n3.下面是用回溯法解n 皇后问题的算法（求出所有解） 。n 皇后问题：在 n x n 棋盘上放置 n 个皇后使得任何两个皇后不能互相攻击。（如果两个皇后处在同一行，或同一列，或同一斜线上，则她们能互相攻击。）算法 NQUEENS输入：正整数 n。输出： n 皇后问题的所有解x1.n,若无解，则输出No solution。flag=falsek=1 ;x1=0while(1)while xk

14、=1(3) k+1(2) xk+1(4) xk=0(5) k=k-14. 递归的快速排序算法： template void QuickSort (Type a , int low, int high) if (1)int i=Partition(a, low, high);QuickSort（ a, low, i-1）;(2);解：（1）low high算法期末复习题final（ 2） QuickSort（a, i+1, high）5、 n 后问题的递归的回溯算法， ，设已经存在全局变量n 代表皇后个数。void Queen:Backtrack(int t) if (else(1)for (i

15、nt i=1; i n(2) Backtrack(t+1)三、简答、计算题1、对于图所示多段图， 用动态规划法求从顶点0 到顶点 12 的最短路径， 写出求解过程。首先求解初始子问题，可直接获得：d(0, 1)=c01 5(0 1)d(0, 2)=c02 3(0 2)再求解下一个阶段的子问题，有：d(0,3)= d(0, 1)+ c13 =6 (1 3)=8(1 4)d(0,4)=mind(0,1)+ c,d(0,2)+ c1424 = 10(2 5)d(0,5)=min d(0,1)+ cd(0,2)+ c15,25d(0,6)= d(0,2)+ c26 = 9 (26)再下一阶段：d(0,

16、4)+ c = 11 (4 7)d(0,7) = min d(0,3)+ c37,47d(0,8)= min d(0,3)+ c38, d(0,4)+ c48, d(0,5)+ c58, d(0,6)+ c68 = 13(4 8)d(0,9)= min d(0,5)+ c59, d(0,6)+ c69 = 13 (5 9)再下一阶段：d(0,10) = min d(0,7)+ c7_10, d(0,8)+ c8_10 = 14 (7 10)算法期末复习题finald(0, 11) = min d(0,7)+ c7_11, d(0,8)+ c8_11, d(0,8)+ c9_11 = 15 (8

17、 11)最后：d(0,11)+ c = 18 (10 12)d(0, 12) = min d(0,10)+ c10_12,11_12即，最短路径为18, 其中一条最短路径为： 0147 1012（具体路径可能不止一条）2、对于字符集合M=A,B,C,D,E,F ，设这些字符在文本中出现的频率分别为8,1,3,10,6,5，画出字符集合 M 的 Huffman 编码树，并给出各字符的Huffman编码。字符集合 M 的 Huffman 编码树是：各字符的 Huffman 编码：A: 01B:1000C: 1001D: 11E:00F: 1013 . 用动态规划法求如下0/1 背包问题的最优解：有

18、5 个物品，其重量分别为（ 3,2,1,4,5），价值分别为（ 25,20,15,40,50），背包容量为 6. 写出求解过程（设计表格和填写表格）解：设计一个二维表 V(i, j) 表示将前 i 个物品装进容量为 j 的背包所能获得的最大价值，根据以下递推式填表：?若 wi j,V(i, j) = V(i 1, j)?若 wi = j, V(i, j)= max V(i-1, j) , V(i-1, j - wi) + vij = 0j = 1j = 2j = 3j = 4j = 5j = 6i = 00000000i = 100025252525i = 2002025254545i = 30152035404560i = 40152035405560i = 50152035405565算法期末复习题finalV(5,6) 即为问题的最优解，