【精品文档】如有侵权，请联系网站删除，仅供学习与交流算法期末复习题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、动态规划法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、重叠子问题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 衡量一个算法好坏的标准是（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.层次优先遍历20.采用广度优先策略搜索的算法是（ 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.有限性：指令执行次数有限，而且执行时间有限 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用中位数的中位数方法寻找划分基准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背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划 ，需要排序的是 回溯法 ，分支限界法 。2、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ，只使用约束条件进行裁剪的是 N皇后问题 。3.贪心算法基本要素有 最优度量标准 和 最优子结构 。4.回溯法解旅行售货员问题时的解空间树是 排列树 。5.二分搜索算法是利用 分治策略 实现的算法。6.算法的复杂性有 时间 复杂性和 空间 复杂性之分。7、程序是 算法用某种程序设计语言的具体实现。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 3. for j=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) then 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