1、算法分析复习题目及答案

一个。选择题1，二分搜索算法是利用(a)实现的算法。a，分割策略b，动态规划方法c，贪心方法d，回溯方法2、以下不是动态编程算法的基本步骤(a):a，确定最佳解决方案的特征b，配置最佳解决方案c，计算最佳解决方案d，定义最佳解决方案3、最大的优点是(a)搜索方法。a，分支边界方法b，动态规划方法c，贪心方法d，回溯方法4、以下算法有时找不到解决问题的方法是(b)。a，Monte Carlo算法b，拉斯维加斯算法c，shewood算法d，数值概率算法5.以回溯方式解决旅行推销员问题时，空间树为(b)。a、子集树b、阵列树c、深度优秀教师树d、宽度优秀教师树6.在以下算法中，通常自下而上解决最佳解决方案是(b):a，备忘录方法b，动态编程方法c，贪心方法d，回溯方法7、衡量算法好坏的标准是(c)。a快速执行速度b占用空间小c时间复杂性低d代码短8、以下无法使用分割方法解决(d):主板封面问题b选择问题c合并排序D 0/1背包问题9.使用倒圆角日程表的算法为(a)。a，分割策略b，动态规划方法c，贪心方法d，回溯方法10，在以下任意算法中运行时成功有时失败(c)a数值概率算法b舍伍德算法c拉斯维加斯算法d蒙特卡罗算法11.以下不是分支边界方法搜索方法(d):a，宽度优先b，最小消费优先c，最大收益优先d，深度优先12.在以下算法中，用深度优先方案解决问题通常是(d)。a，备忘录方法b，动态编程方法c，贪心方法d，回溯方法13.备忘录方法是那种算法的变体。(b)a，分离法b，动态规划法c，贪婪法d，回溯法14.赫夫曼编码的贪心算法所需的计算时间为(b)。a、O(n2n)B、O(nlogin) c、O(2n)D、O(n)15.分支边界方法解决最大组问题时，活动节点表为(b)。a、最小堆b、最大堆c、堆栈d、数组16.最长公共子序列算法使用的算法为(b)。a，分支边界方法b，动态规划方法c，贪心方法d，回溯方法17.实现电路板覆盖算法使用的算法是(a)。a，分离法b，动态规划法c，贪婪法d，回溯法以下是贪心算法的基本元素(c)。a，重叠子问题b，配置最优解c，贪心选择特性d，定义最优解19.回溯方法的效率不依赖以下因素(d)A.满足显式约束的值数b。约束函数计算时间C.边界函数计算时间d .空间求解时间的确定20.以下哪项是避免无效搜索的回溯方法的策略(b)A.递归函数b .修剪函数c .随机数函数d .搜索函数21、以下关于NP问题的陈述是正确的(b)A NP问题是无法解决的问题B P类问题包含在NP类问题中C NP整体问题是p类问题的子集D NP类问题包含在p类问题中22，Monte Carlo算法是(b)之一。a，分支边界算法b，概率算法c，贪心算法d，回溯算法以下哪种算法不是随机算法(c)A.蒙特卡罗算法b .拉斯维加斯算法c .动态编程算法d .舍伍德算法24.(D)贪心算法和动态编程算法的共同点。a，重叠子问题b，构造最优解c，贪心选择特性d，最优子结构特性矩阵乘法问题的算法可由(b)设计实现。a，分支边界算法b，动态规划算法c，贪心算法d，回溯算法26.用分界法解决旅行推销员问题，活节点的组织形式为(a)。a、最小堆b、最大堆c、堆栈d、数组27，Strassen矩阵乘法是使用(a)实现的算法。a，分割策略b，动态规划方法c，贪心方法d，回溯方法29、使用分割方法解决不能满足的条件是(a)。a子问题必须相同b子问题不能重复可以组合c子问题的解决方案d原始问题和子问题使用相同的方法解决30、下一个问题(b)不能用贪心的方法解决。单源最短路径问题B N皇后问题c最小支出生成树问题d背包问题31，以下算法无法解决0/1背包问题：(a)贪心法b动态规划c回溯法d分支边界法33，在以下任意算法中运行时成功有时失败(c)a数值概率算法b舍伍德算法c拉斯维加斯算法d蒙特卡罗算法34.实现统一排序使用的算法为(a)。a，分割策略b，动态规划方法c，贪心方法d，回溯方法以下是动态编程算法的基本元素(d):a，最佳解决方案定义b，最佳解决方案配置c，最佳解决方案d计算，子问题重叠特性使用宽优先级策略搜索的算法为(a)。a，分支边界方法b，动态规划方法c，贪心方法d，回溯方法38，合并排序算法是使用(a)实现的算法。a，分割策略b，动态规划方法c，贪心方法d，回溯方法39、从以下算法中获得的解决方案可能不正确(b):a，Monte Carlo算法b，拉斯维加斯算法c，shewood算法d，数值概率算法40，背包问题的贪心算法所需的计算时间为(b)a、O(n2n) B、O(nlogin) c、O(2n) D、O(n)41.实现大整数的乘法是使用的算法(c)。a，贪心方法b，动态规划方法c，分割策略d，回溯方法42.0-1背包问题的回溯算法所需的计算时间为(a)a、O(n2n)B、O(nlogin) c、O(2n)D、O(n)43.使用最有效的优先级搜索方法的算法为(a)。a，分支边界方法b，动态规划方法c，贪心方法d，回溯方法贪心算法和动态编程算法的主要区别是(b)。a，最优子结构b，贪婪选择特性c，配置最优解d，定义最优解45.最大子段和利用的算法为(b)。a，分割策略b，动态规划方法c，贪心方法d，回溯方法46.优先队列分支极限法扩展节点选择原则是(c)。a、FIFO b、LIFO c、节点的优先级d、随机47.背包问题的贪心算法所需的计算时间为(b)。a、O(n2n)B、O(nlogin) c、O(2n)D、O(n)48、优先级是(a)搜索方法。a，分支边界方法b，动态规划方法c，贪心方法d，回溯方法49，舍伍德算法是(b)之一。a，分支边界算法b，概率算法c，贪心算法d，回溯算法50，以下算法有时找不到解决问题的方法是(b)。a，Monte Carlo算法b，拉斯维加斯算法c，shewood算法d，数值概率算法51以下随机抽取算法(d)A.贪心算法b .回溯方法c .动态规划算法d .舍伍德算法52.一个问题可以通过动态编程算法或贪心算法解决，其核心特征是问题(b)。a，重叠子问题b，最优子结构特性c，贪心选择特性d，定义最优解53.使用贪心算法的最优装载问题的主计算在按重量追溯排序容器时，算法的时间复杂度为(b)。a、O(n2n)B、O(nlogin) c、O(2n)D、O(n)54.以深度优先顺序在系统中搜寻疑难排解的演算法称为(d)。a，分支边界算法b，概率算法c，贪心算法d，回溯算法55.实现使用最长公共子序列的算法为(b)。a，分割策略b，动态规划方法c，贪心方法d，回溯方法二、填空1.算法的复杂性有时间复杂性和空间复杂性。2、程序是算法用某种编程语言具体实现的。3、算法的“确定性”意味着构成算法的每个指令都清晰、不模糊。矩阵乘法问题的算法可以通过动态编程设计实现。5、拉斯维加斯算法发现的解决方案必须是正确的解决方案。6、算法表示解决问题的方法或过程。7，如分割方法的一般设计模式所示，用它设计的程序通常是递归算法。8、问题的最优子结构特性是用动态编程算法或贪心算法解决该问题的核心特征。9、以深度优先顺序在系统中搜索问题解决方案的算法称为回溯方法。10、数值概率算法通常用于解决数值问题。11、一般计算迭代次数、基本操作的频率或计算步骤的算法时间复杂度。12、利用概率特性计算近似值的概率算法为_ _数值概率算法，在运行时以一定概率精确解决的概率算法为_ _ Monte Carlo算法14，0/1背包故障诊断可以使用动态编程、回溯方法和分支极限法。这里不需要对齐的是动态编程，必须对齐回溯法，分支极限法。15，使用回溯方法的状态空间树修剪分支通常有两个标准。约束和目标函数的边界，皇后问题和0/1背包问题正好是两种不同的类型。其中，使用约束和目标函数的边界修剪是0/1背包问题，仅使用约束修剪是皇后问题。16、贪心选择的特点是贪心算法是第一个可行的基本要素，贪心算法和动态编程算法的主要区别。17，矩阵乘法问题的算法可由动态编程设计实现。18、拉斯维加斯算法找到的解决方案必须是正确的解决方案。19.贪心算法的基本要素是贪心选择质量和最佳子结构特性。21.动态编程算法的基本思想是把要解决的问题分成几个子问题，先解决子问题，然后解决这些子问题。22.算法是由多个命令组成的有限序列，满足输入、输出、确定性和有限四个特性。23、大整数乘积算法采用分割方法设计。24、以面积优先或最小消耗的方式搜索问题解决方案的算法称为分支定界法。25、舍伍德算法总能找到问题的解决方法。26、贪心选择的特点是贪心算法是第一个可行的基本要素，贪心算法和动态编程算法的主要区别。27.快速排序算法是基于分割策略的一种排序算法。28.动态编程算法的两个基本要素是。最佳子结构性质和复叠子问题性质。回溯方法是一种既有系统又有跳跃性的搜索算法。31.分支极限法主要有基于队列(FIFO)的分支极限法和基于优先级队列的分支极限法。32.分支极限法是既有系统又有跳跃性的搜索算法。33.用回溯方法检索空间树时常用的两种修剪函数是约束函数和边界函数。34.可用计算机解决问题所需的时间与大小有关。35.快速排序算法的性能取决于分割对称。三、填补空白的算法1.背包问题的贪心算法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)；I=n；I) if(wIc)break；xI=1；c-=wI；if(I=n)xI=c/wI；2.最大子段和：动态编程算法Int MaxSum(int n，int a)Int sum=0，b=0；/sum存储当前最大的bj，b存储bjfor(intj=1；j=n；J) _if(B0)b=aj；else b=aj；/如果一个部分和为负数，则在以下位置累if(bsum)sum=b；Return sum；贪心算法查找装载问题。第一次V