算法期末复习题final.doc

《算法期末复习题final.doc》由会员分享，可在线阅读，更多相关《算法期末复习题final.doc（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

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

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

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

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

6、行次数有限，而且执行时间有限 A. (1)(2)(3) B. (1)(2)(4) C. (1)(3)(4) D.(1) (2)(3)(4)25、背包问题的贪心算法所需的计算时间为（ B ）A. O（n2n） B. O（nlogn） C.O（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问题规模相同，问题性质相同 B问题规模相同，问题性质不同C问题规模不同，问题性质相同 D问题规模不同，问题性质不同29、下面是贪心算法的基本要素的是（C ）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解30. 函数的渐进表达式是（ D ）。A. O() B. O() C. O() D.O()二、填空题1、解决0/1背包问题可以使用动态规划、回溯法和分支限界

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

9、条 指令 是清晰的，无歧义的。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 3. for j

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

11、n flag=true; output x1.n else k= (3) (4) end if end if end while (5) end while if 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个矩阵M1, M2, , Mn , Mi 为riri+1阶矩阵，i=1, 2, , n，求计算M1M2Mn所需的最少数量乘法次数。记 Mi, j=MiMi+1Mj , i=j。设Ci, j, 1=

12、i=j=n, 表示计算Mi, j的所需的最少数量乘法次数，则算法 MATCHAIN输入：矩阵链长度n, n个矩阵的阶r1.n+1, 其中r1.n为n个矩阵的行数，rn+1为第n个矩阵的列数。输出：n个矩阵链乘所需的数量乘法的最少次数。for i=1 to n Ci, i= （1） for d=1 to n-1 for i=1 to n-d j= (2) Ci, j= for k=i+1 to j x= (3) if xCi, j then (4) =x end if end for end for end for return (5) end MATCHAIN (1) 0 (2) i+d (3

13、) 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=false k=1 ; x1=0 while (1) while xk=1 (2) xk+1 (3) k+1 (4) xk=0 (5) k=k-1 4. 递归的快速排序算法：template vo

14、id QuickSort (Type a , int low, int high) if ( (1) ) int i=Partition(a, low, high); QuickSort（a, low, i-1）; (2) ; 解：（1）low high （2）QuickSort（a, i+1, high）5、n后问题的递归的回溯算法，设已经存在全局变量n代表皇后个数。void Queen:Backtrack(int t) if ( (1) ) sum+; /sum表示可行解的个数 else for (int i=1; i n (2) Backtrack(t+1)三、 简答、计算题 1、对于图

15、所示多段图，用动态规划法求从顶点0到顶点12的最短路径，写出求解过程。首先求解初始子问题，可直接获得：d(0, 1)=c015(01)d(0, 2)=c023(02)再求解下一个阶段的子问题，有：d(0,3)= d(0, 1)+ c13 =6 (13)d(0,4)=mind(0,1)+ c14 ,d(0,2)+ c24=8(14)d(0,5)=min d(0,1)+ c15, d(0,2)+ c25 = 10(25)d(0,6)= d(0,2)+ c26 = 9 (26)再下一阶段：d(0,7) = min d(0,3)+ c37, d(0,4)+ c47 = 11 (47)d(0,8) =

16、min d(0,3)+ c38, d(0,4)+ c48, d(0,5)+ c58, d(0,6)+ c68 = 13(48)d(0,9) = min d(0,5)+ c59, d(0,6)+ c69 = 13 (59)再下一阶段：d(0,10) = min d(0,7)+ c7_10, d(0,8)+ c8_10 = 14 (710)d(0, 11) = min d(0,7)+ c7_11, d(0,8)+ c8_11, d(0,8)+ c9_11 = 15 (811)最后：d(0, 12) = min d(0,10)+ c10_12, d(0,11)+ c11_12 = 18 (1012)

17、即，最短路径为18, 其中一条最短路径为：01471012 （具体路径可能不止一条）2、对于字符集合M=A,B,C,D,E,F，设这些字符在文本中出现的频率分别为8,1,3,10,6,5，画出字符集合M的Huffman编码树，并给出各字符的Huffman编码。字符集合M的Huffman编码树是：各字符的Huffman编码：A: 01 B:1000 C: 1001 D: 11 E:00 F: 1013 . 用动态规划法求如下0/1背包问题的最优解：有5个物品，其重量分别为（3,2,1,4,5），价值分别为（25,20,15,40,50），背包容量为6. 写出求解过程（设计表格和填写表格）解：设计

18、一个二维表 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 = 50152035405565V(5,6) 即为问题的最优解，最大价值为65。 经过回溯得到物

19、品组合为第3和第5个物品装入背包。4. 归并排序算法对下列实例排序，写出算法执行过程。 A=(48,12,61,3,5,19,32,7)解： 拆分： 48,12,61,3 5,19,32,748,12 61,3 5,19 32,748 12 61 3 5 19 327 合并：12,483,615,197,323, 12,48, 61 5, 7, 19，32 3,5, 7,12，19，32，48,61 5、简述分治法的基本思想。答：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。6、由于贪心算法是一种只顾眼前的步骤，而难以顾及全局步骤的算法，所以它通常表现出哪些特点？）不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外）策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 策略多样，结果也多样。 算法实现过程中，通常用到辅助算法：排序7、简述动态规划算法的基本步骤 找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。