算法分析作业.docx

《算法分析作业.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、D、定义最）。D回溯法D回溯法回溯法D回溯法D回溯法D、算法分析练习题（一）、选择题1、二分搜索算法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（A）。A、找出最优解的性质B、构造最优解C、算出最优解优解3．下列算法中通常以自底向上的方式求解最优解的是（BA、备忘录法B动态规划法C、贪心法4、衡量一个算法好坏的标准是（C）。A运行速度快B占用空间少C时间复杂度低D代码短5、以下不可以使用分治法求解的是（D）。A棋盘覆盖问题B选择问题C归并排序D0/1背包问题6.实现循环赛日程表利用的算法是（A）。A、

2、分治策略B、动态规划法C、贪心法7.备忘录方法是那种算法的变形。（B）A、分治法B动态规划法C、贪心法D8．最长公共子序列算法利用的算法是（B）。A、分支界限法B动态规划法C贪心法9．实现棋盘覆盖算法利用的算法是（A）。A、分治法B动态规划法C、贪心法10、矩阵连乘问题的算法可由（B）设计实现'A、分支界限算法B、动态规划算法C、贪心算法回溯算法11、Strassen矩阵乘法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法12、使用分治法求解不需要满足的条件是（A）。A子问题必须是一样的B子问题不能够重复C子问题的解可以合并D原问题和子问题

3、使用相同的方法解13、下列算法中不能解决0/1背包问题的是（A）A贪心法B动态规划C回溯法D分支限界法A）。C、贪心法D回溯法D)0C、算出最优解D、子问题14•实现合并排序利用的算法是（A、分治策略B、动态规划法15•下列是动态规划算法基本要素的是（A、定义最优解B、构造最优解重叠性质16.下列算法中通常以自底向下的方式求解最优解的是（B）A、分治法B、动态规划法C、贪心法D回溯法17、合并排序算法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法C)oC、分治策略D回溯法B)0C、贪心法D回溯法18•实现大整数的乘法是利用的算法（A、贪心

4、法B、动态规划法19.实现最大子段和利用的算法是（A、分治策略B、动态规划法20.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B）。A、重叠子问题B最优子结构性质C贪心选择性质D定义最优解21.实现最长公共子序列利用的算法是（B）。A、分治策略B、动态规划法C、贪心法D回溯法二、填空题1、算法的复杂性有时间复杂性和空间复杂性之分。2、程序是算法用某种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。4、矩阵连乘问题的算法可由动态规划设计实现。5、算法是指解决问题的一种方法或一个过程。6从分治法的一般设计模式可以

5、看出，用它设计出的程序一般是递归算法7、矩阵连乘问题的算法可由动态规划设计实现。8、动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。9、算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。10、大整数乘积算法是用分治法来设计的。11、快速排序算法是基于分治策略的一种排序算法。12、动态规划算法的两个基本要素是.性质和性质。13、任何可用计算机求解的问题所需的时间都与其规模有关。14、快速排序算法的性能取决于划分的对称性o15、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成

6、若干子问题时，这些子问题的规模都大致相同。16、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为0(),在最坏情况下，搜索的时间复杂性为0(logn)o17、已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程：0(1)n2T(n)2T(n/2)0(n)n2解得此递归方可得T(n)=0(nlogn)。18、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。19、递归的二分

7、查找算法在divide阶段所花的时间是0(1)，conquer阶段所花的时间是T(M2)，算法的时间复杂度是—0(logn)o20、用动态规划算法计算矩阵连乘问题的最优值所花的时间是0(n3)，子冋题空间大小是0(n2)。21、一个算法的优劣可以用(时间复杂度)与(空间复杂度)与来衡量。22、直接或间接地调用自身的算法称为(递归算法)。23、记号在算法复杂性的表示法中表示(渐进确界或紧致界)。24、在分治法中，使子问题规模大致相等的做法是出自一种(平衡子问题)的思想。25、动态规划算法适用于解(具有某种最优性质)问题26、最优子结构性质的含义是（问题的最优解包含

8、其子问题的最优解）。27