川农大算法分析期末复习

《川农大算法分析期末复习》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计复习题判断题1选择题：15判断题1.算法就是一组有穷的规则。答案：正确2.概率算法中蒙特卡罗算法得到的解必是正确的。答案：错误3.程序和算法一样，都是某种程序设计语言的具体实现。答案：错误4.合并排序算法是渐近最优算法。答案：正确5.递归定义必须是有确切含义是指必须一步比一步简单，最后是有终结的，决不能无限循环下去。答案：正确6.二分搜索方法在最坏的情况下用O(logn)时间完成搜索任务。答案：正确7.能否利用分治法完全取决于问题是否具有如下特征：利用该问题分解出的子问题的解可以合并为该问题的解。答案：正确8.分治法的基本思

2、想是将一个规模较大的问题分解成若干个规模较小的子问题，这些子问题之间并不一定相互独立。答案：错误9.递归算法的效率往往很低，费时和费内存空间。答案：正确10.当一个问题具有最优子结构性质时只能用动态规划方法求解。答案：错误11.如果一类活动过程一个阶段的决策确定以后，常影响到下一个阶段的决策，则称它为多阶段决策问题。答案：正确12.反复应用分治手段，不能使子问题与原问题类型一致而其规模却不断缩小。答案：错误13.裴波那契数列的定义：f(n)=f(n-1)+f(n-2),f(0)=1,f(1)=2，其数据的定义形式不是按递归定义。答案：错误

3、14.0-1背包问题与背包问题这两类问题都可以用贪心算法求解。答案：错误15.证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。答案：错误16.子问题之间不包含公共的子问题，这个条件涉及到分治法的效率。答案：正确17.概率算法允许在执行过程中随机地选择下一个计算步骤。答案：正确18.二分搜索法的二分查找只适用于顺序存储结构。答案：正确19.要想在电脑上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度。答案：正确20.用回溯法解题一个显著特征是在搜索过程中动态产生问题的解空间。答案：错误21.从分治法

4、的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。因此，分治法的计算效率通常可以用递归方程来进行分析。答案：正确22.多阶段决策问题中，每一个阶段可能有若干个决策可供选择答案：正确23.拉斯维加斯算法不会得到不正确的解，但有时找不到解。答案：正确24.在通往边界条件的递归调用过程中，系统用堆栈保存的每次调用的中间结果是局部变量和返回地址值。答案：正确25.要想在电脑上扩大所处理问题的规模，有效的途径是提高算法的计算复杂度。答案：错误26.程序必须满足算法具有数据输出的性质。答案：正确27.反复应用分治手段，可以使子问题与原问题类

5、型一致而其规模却不断缩小答案：正确28.一个算法产生一个或多个输出，它们是同输入有某种特定关系的量答案：正确29.最优子结构性质特征反映了递归思想的应用答案：正确30.递归边界本身并不使用递归的定义答案：正确31.用分治法求解一个问题，所需的时间是由子问题的个数、大小以及把这个问题分解为子问题所需的工作总量来确定的。答案：正确32.应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。答案：正确33.好的约束函数能显著地减少所生成的结点数，但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在

6、生成结点数与约束函数计算量之间的折衷。答案：正确34.一个递归定义必须是有确切含义的，必须一步比一步简单，最后是有终结的，不能无限循环下去。答案：正确35.最优子结构性质是应用分治法的前提。答案：正确36.操作系统，它是一个在无限循环中执行的程序，因而不是一个算法。答案：正确37.有些数据结构如二叉树等，由于其本身的递归特性、特别适合用递归的形式来描述。答案：正确38.概率算法的一个基本特征是，对所求问题的同一个实例用同一个算法求解两次一定能得到完全相同的效果。答案：错误39.问题可以分解为若干个规模较小的相同问题，即称该问题具有最优子结

7、构性质。答案：错误40.递推是从内边界条件出发，通过递推式达到边界条件。答案：正确41.所有的递归函数都能找到对应的非递归定义。 答案：正确42.定义递归函数时可以没有初始值。答案：错误43.动态规划算法的基本要素是最优子结构。答案：正确44.最优子结构性质是指原问题的最优解包含其子问题的最优解。答案：正确45.动态规划算法求解问题时，分解出来的子问题相互独立。答案：错误46.满足贪心选择性质必满足最优子结构性质。答案：错误47.回溯法中限界函数的目的是剪去得不到最优解的子树。答案：正确48.分支限界法类似于回溯法，也是一种在问题的解空间

8、树T上搜索问题解的算法，两者的搜索方式是相同的。答案：错误49.任何递归算法都有递归出口。答案：正确50.递归算法的执行效率比功能相同的非递归算法的执行效率高。答案：错误51.递归算法不能转换