算法期末复习题final.doc

《算法期末复习题final.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、贪心法D、回溯法6、合并排序算法是利用（   A     ）实现的算法。A、分治策略  B、动态规划法  C、贪心法   D、回溯法7、下列不属于影响程序执行时间的因素有哪些？（C）A．算法设计的策略B．问题的规模C．编译程序产生的机器代码质量D．计算机执行指令的速度8、使用分治法求解不需要满足的条件是（A）。A子问题必须是一样的B子问题不能够重复C子问题的解可以合并D原问题和子问题使用相同的方法解9、下面问题（B）不能使用贪心法解决。A单源最短路径问题BN皇后问题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.在抽象数据集合上执行程序

4、,以确定是否会产生错误的结果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为边

5、数）A．O(n2)B．O(mlogn)C．O(nlogm)D．O(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()

6、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小

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

8、，问题性质不同29、下面是贪心算法的基本要素的是（  C    ）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解30.函数的渐进表达式是（D）。A.O()B.O()C.O()D.O()二、填空题1、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需