算法期末复习题

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

2、素有哪些？A算法设计的策略问题的规模C编译程序产生的机器代码质量 D 计算机执行指令的速度8、使用分治法求解不需要满足的条件是 A 。A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解9、下面问题 B 不能使用贪心法解决。A 单源最短路径问题B N 皇后问题C 最小花费生成树问题D 背包问题10. 一个问题可用动态规划算法或贪心算法 求解的关键特征是问题的 B 。A、重叠子问题B最优子结构性质C贪心选择性质D定义最优解0D、回溯11. 以深度优先方式系统搜索问题解的算法称为 D A、分支界限算法B、概率算法C、贪心算法算法12. 实现最长公共子序

3、列利用的算法是B。A、分治策略B、动态规划法C、贪心法D回溯法D分支限界法 D 动态规划法13以下算法具有最优子结构的算法是A.概率算法B 回溯法 C14. 算法分析是 CA.将算法用某种程序设计语言恰当地表示出来B .在抽象数据集合上执行程序 , 以确定是否会产生错误的结果C. 对算法需要多少计算时间和存储空间作定量分析D. 证明算法对所有可能的合法输入都能算出正确的答案15 衡量一个算法好坏的标准是 C A. 运行速度快 B. 占用空间少 C. 时间复杂度低 D. 代码短16.二分搜索算法是利用A实现的算法。A.分治法B.动态规划法 C.贪心法 D.回溯法 17用贪心法设计算法的关键是 B

4、 A. 将问题分解为多个子问题来分别处理B. 选好最优量度标准C .获取各阶段间的递推关系式D.满足最优性原理18. 找最小生成树的算法 Kruskal 的时间复杂度为 D 其中 n 为无向图的结 点数，m为边数2AOn2 B Omlogn C Onlog m D Omlogm19. 回溯法搜索状态空间树是按照(C )的顺序。A.中序遍历B. 广度优先遍历C. 深度优先遍历 D.层次优先遍历20. 采用广度优先策略搜索的算法是(A )。A.分支界限法B.动态规划法C.贪心法D.回溯法21. 函数32n+10nlogn的渐进表达式是(B ).(2 n)B. 0( 32n)C. 0( nlog n

5、 ) D. 0( 10nlogn)22. 二分搜索算法的时间复杂性为(C )。(n)(n)(|og n)d. 0(nlogn )23. 快速排序算法的时间复杂性为(D)0(n)(n)(log n)D. 0(nlogn )24. 算法是由假设干条指令组成的有穷序列，而且满足以下性质( D )A.输入：有0个或多个输入B.输出：至少有一个输出C.确定性：指令清晰，无歧义 D.有限性：指令执行次数有限，而且执行时间 有限A. (1) (2)(3) B. (1) (2) C. (1) (3)D.(1)25. 背包问题的贪心算法所需的计算时间为( B )A. 0 (n2n)B. 0(nlogn)(2n)

6、(n)26. 以下算法中不能解决0/1背包问题的是(A )A贪心法B动态规划C回溯法D分支限界法27. 在寻找n个元素中第k小元素问题中，假设使用快速排序算法思想，运用分治 算法对n个元素进行划分，应如何选择划分基准？下面 (D) 答案解释最合理。 A.随机选择一个元素作为划分基准B取子序列的第一个元素作为划分基准C. 用中位数的中位数方法寻找划分基准D. 以上皆可行。但不同方法，算法复杂度上界可能不同28. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。 这要求原问 题和子问题C oA.问题规模相同，问题性质相同B

7、 问题规模相同，问题性质不同CoC、贪心选择性质D定义最优解C.问题规模不同，问题性质相同D 问题规模不同，问题性质不同29、下面是贪心算法的根本要素的是A、重叠子问题 B构造最优解230. 函数3n 10n的渐进表达式是D 2 2A. O 3n B. 03 C. 0 伽 n二、填空题1. 解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划，需要排序的是回溯法 ，分支限界法 o2. 使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束 条件和目标函数的界进行裁剪的是0/1背包

8、问题，只使用约束条件进行裁剪的是 N 皇后问题 o3. 贪心算法根本要素有最优度量标准和最优子结构 。4. 回溯法解旅行售货员问题时的解空间树是排列树 。5. 二分搜索算法是利用分治策略实现的算法。6. 算法的复杂性有 时间复杂性和空间 复杂性之分。7. 程序是用某种程序设计语言的具体实现。8. 算法的“确定性指的是组成算法的每条指令 是清晰的，无歧义的。9. 矩阵连乘问题的算法可由动态规划 设计实现。10. 回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和 限界函数规模 有关。11. 任何可用计算机求解的问题所需的时间都与其12. 快速排序算法的性能取决于 划分的对称性13. 背包问题的

9、贪心算法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 - =if (i14下面算法的根本运算是 _加法或：赋值_运算，该算法中第4步执行 了 2n-1 次。算法COUNT 输入：正整数n (n=2k)输出：count的值。1. cou nt=O2. while n=13. for j=1 to n4. count =co un t+15. end for6. n=n/27. end

10、 whileend COUNT15. 算法是由假设干条指令组成的有穷序列，且要满足输入、输出、确定性和 有限性四条性质。16. 快速排序、插入排序和选择排序算法中，快速排序算法是分治算法。17. 下面算法的根本语句是 S = S + i*j;,算法的时间复杂 度是2O(n )int fun (i nt n)int S = 0;for (i nt i=1; i =n; i+ )for(i nt j=1; j=1while (1)xk=xk+1if color(k) the nif (2) thenflag=true; output x1. nelsek= (4)end ifend ifend w

11、hile(5)end whileif not flag the n output“no soluti onend m-COLORINGk+1(1) xkm k=n xk=0(5) k=k-1 2 下面是求解矩阵链乘问题的动态规划算法。矩阵链乘问题：给出n个矩阵M, M2,M n , Mi为ri ri+1阶矩阵，i=1,2,n，求计算MMM所需的最少数量乘法次数。记 Mi, j =MM+ M , i=j 。设 Ci, j, 1=i=j=n,表示计算 Mj 的所需的最少数量乘法次数，那么.0,i jCi,jmin Ci,k-1 Ck, j rgji k j算法 MATCHAIN输入：矩阵链长度n,

12、 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-dj= _J2)Ci, j=%for k=i+1 to jx= if xCi, j the n =xend ifend forend forend forreturn (5)end MATCHAIN(1) 0(2) i+d (3) Ci, k-1+Ck, j+ri*rk*rj+1 Ci, j (5) C1, n3.下面是用回溯法解n皇后问题的算法(求出所有解)。n

13、皇后问题：在n x n棋盘上放置n个皇后使得任何两个皇后不能互相攻 击。(如果两个皇后处在同一行，或同一列，或同一斜线上，那么她们能互相攻 击。)算法 NQUEENS输入：正整数n。输出：n皇后问题的所有解x1.n, 假设无解，那么输出Nosolutionflag=falsek=1 ; x1=0while while xk nxk=(2)if place(k) the nif k=n the nflag=true ； output x1. nelsek= (4)end ifend ifend while(5)end whileif not flag the n output“ No solut

14、i onend NQUEENS过程 place (k)递归的快速排序算法：template void QuickSort (Type a , i nt low, int high) if ()int i=Partition(a, low, high);Quicksort( a, low, i-1);(2；解：(1) low 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 = 100025

15、252525i = 2002025254545i = 30152035404560i = 40152035405560i = 50152035405565V5,6即为问题的最优解，最大价值为 65。经过回溯得到物品组合为第 3和 第5个物品装入背包。4. 归并排序算法对以下实例排序，写出算法执行过程。A=48,12,61,3,5,19,32,7解：拆分：48,12,61,35,19,32,748,1261,34812 615,1932,73519 32合并:12,483,613, 12,48, 613,5, 7,125,195, 7, 1919，32，48,617,32，325、简述分治法的根本思想。答：分治法的根本思想是将一个规模为 n的问题分解为k个规模较小的子问题, 这些子问题互相独立且与原问题相同；对这 k个子问题分别求解。如果子问 题的规模仍然不够小，那么再划分为 k个子问题，如此递归的进行下去，直到 问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为 一个更