《算法期末（复习题final）》由会员分享，可在线阅读，更多相关《算法期末（复习题final）（13页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计期末复习题目 一、选择题 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、动态规划法C、贪心法D、回溯法 6、合并排序算法是利用（A ）实
2、现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7、下列不属于影响程序执行时间的因素有哪些？（ C ） A算法设计的策略 B问题的规模 C编译程序产生的机器代码质量 D计算机执行指令的速度 8、使用分治法求解不需要满足的条件是（A ） 。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 9、下面问题（ B ）不能使用贪心法解决。 A 单源最短路径问题B N皇后问题 C 最小花费生成树问题 D 背包问题 10. 一 个 问 题 可 用 动 态 规 划 算 法 或 贪 心 算法 求 解 的 关 键 特 征 是 问 题 的
3、（B ） 。 A、重叠子问题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.证明算法对所有可
4、能的合法输入都能算出正确的答案 15 衡量一个算法好坏的标准是（C ） A.运行速度快 B. 占用空间少 C. 时间复杂度低 D. 代码短 16. 二分搜索算法是利用（ A）实现的算法。 A.分治法 B. 动态规划法C.贪心法D.回溯法 17用贪心法设计算法的关键是（ B ） 。 A.将问题分解为多个子问题来分别处理 B.选好最优量度标准 C.获取各阶段间的递推关系式 D.满足最优性原理 18. 找最小生成树的算法Kruskal 的时间复杂度为（ D ） （其中 n 为无向图的结 点数， m为边数） AO(n 2) B O(mlogn) CO(nlogm) DO(mlogm) 19. 回溯法搜
5、索状态空间树是按照（C ）的顺序。 A.中序遍历 B.广度优先遍历 C.深度优先遍历 D. 层次优先遍历 20. 采用广度优先策略搜索的算法是（ A ） 。 A.分支界限法B.动态规划法 C.贪心法 D.回溯法 21. 函数 32 n+10nlogn 的渐进表达式是 ( B ). A.O( 2n) B. O( 32n) C. O( nlogn) D. O( 10nlogn) 22. 二分搜索算法的时间复杂性为（ C ） 。 A.O( 2 n ) B.O( n ) C.O( nlog ) D. O( nnlog ) 23、快速排序算法的时间复杂性为（ D ） 。 A.O( 2 n ) B.O(
6、n ) C.O( nlog ) D. O( nnlog ) 24、算法是由若干条指令组成的有穷序列，而且满足以下性质（ D ） A.输入：有 0 个或多个输入 B.输出：至少有一个输出 C. 确定性：指令清晰，无歧义 D. 有限性：指令执行次数有限，而且执行时间 有限 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 回溯
7、法 D 分支限界法 27. 在寻找 n 个元素中第 k 小元素问题中，若使用快速排序算法思想，运用分治 算法对 n 个元素进行划分，应如何选择划分基准？下面(D) 答案解释最合理。 A随机选择一个元素作为划分基准 B取子序列的第一个元素作为划分基准 C用中位数的中位数方法寻找划分基准 D以上皆可行。但不同方法，算法复杂度上界可能不同 28. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问 题，分别解决子问题， 最后将子问题的解组合起来形成原问题的解。这要求原问 题和子问题( C ) 。 A问题规模相同，问题性质相同B问题规模相同，问题性质不同 C问题规模不同，问题性质相同D问
8、题规模不同，问题性质不同 29、下面是贪心算法的基本要素的是（C ） 。 A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解 30. 函数 nn103 2 的渐进表达式是（ D ） 。 A. O( 2 3n ) B. O( 3) C. O(n10 ) D.O( 2 n ) 二、填空题 1、解决 0/1 背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排 序的是动态规划，需要排序的是回溯法，分支限界法。 2、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函 数的界，N皇后问题和 0/1 背包问题正好是两种不同的类型，其中同时使用约束 条件和目标函数的界进行裁剪的
9、是 0/1背包问题，只使用约束条件进行 裁剪的是 N皇后问题。 3. 贪心算法基本要素有最优度量标准和 最优子结构。 4. 回溯法解旅行售货员问题时的解空间树是排列树。 5. 二分搜索算法是利用分治策略实现的算法。 6. 算法的复杂性有时间复杂性和空间复杂 性之分。 7、程序是算法用某种程序设计语言的具体实现。 8、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。 9. 矩阵连乘问题的算法可由动态规划设计实现。 10回溯法搜索解空间树时， 常用的两种剪枝函数为约束函数和限界 函数。 11. 任何可用计算机求解的问题所需的时间都与其规模有关。 12. 快速排序算法的性能取决于划分的对
10、称性。 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=1 to n 4. count =count+1 5. end for 6. n=n/2 7. end while end COUNT 15.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有 限性四条性质。 16. 快速排序、插入
11、排序和选择排序算法中，快速排序算法是分治算法。 17. 下面 算法 的基 本语句是 _ S = S + i*j;_, 算法 的时 间复杂 度是 _O( 2 n )_ 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) then flag=true; output x1.n else k= (3) (4) end if end if end while (5) end while if not flag then output “
12、 no solution” end m-COLORING (1) xkm (2) k=n (3) k+1 (4) xk=0 (5) k=k-1 2下面是求解矩阵链乘问题的动态规划算法。 矩阵链乘问题：给出 n 个矩阵 M1, M2, , Mn , Mi 为 riri+1阶矩阵，i=1, 2, , n，求计算 M1M2Mn所需的最少数量乘法次数。 记 Mi, j=MiMi+1Mj , i=j。设 Ci, j, 1=i=j=n, 表示计算 Mi, j的所需 的最少数量乘法次数，则 ji ,rrrjCk,1-k, i Cmin ji ,0 j, i C 1jki jki 算法 MATCHAIN 输入
13、：矩阵链长度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) Ci, k-1+Ck, j+ri*rk*rj+1 (4)
14、Ci, j (5) C1, n 3.下面是用回溯法解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 void QuickSo
15、rt (Type a , int low, int high) (4) 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、对于图所示多段图， 用动态规划法求从顶点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) 再下一阶段：
