计算机算法设计与分析期末考试复习题

1、二分找寻算法是利用（A）实现的算法。A、分治策略B、动向规划法C、贪心法D、回溯法2、以下不是动向规划算法基本步骤的是（A）。A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（A）的一找寻方式。A、分支界限法B、动向规划法C、贪心法D、回溯法4、最长公共子序列算法利用的算法是（B）。A、分支界限法B、动向规划法C、贪心法D、回溯法5.回溯法解TSP问题时的解空间树是（A）。A、子集树B、摆列树C、深度优先生成树D、广度优先生成树6．以下算法中平时以自底向上的方式求解最优解的是（B）。A、备忘录法B、动向规划法C、贪心法D、回溯法7、权衡一个算法利害的标准是（C）。A运转速度快B占用空间少C时间复杂度低D代码短8、以下不能够够使用分治法求解的是（D）。A棋盘覆盖问题B选择问题C归并排序D0/1背包问题9.实现循环赛日程表利用的算法是（A）。A、分治策略B、动向规划法C、贪心法D、回溯法10、实现最长公共子序列利用的算法是（B）。A、分治策略B、动向规划法C、贪心法D、回溯法11．下边不是分支界限法找寻方式的是（D）。A、广度优先B、最小耗费优先C、最大效益优先D、深度优先12．以下算法中平时以深度优先方式系统找寻问题解的是（D）。A、备忘录法B、动向规划法C、贪心法D、回溯法一个问题可用动向规划算法或贪心算法求解的重点特点是问题的（B）。A、重叠子问题B、最优子构造性质C、贪心选择性质D、定义最优解14．广度优先是（A）的一找寻方式。A、分支界限法B、动向规划法C、贪心法D、回溯法15．背包问题的贪心算法所需的计算时间为（B）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）16．实现最大子段和利用的算法是（B）。A、分治策略B、动向规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（A）。A、分治法B、动向规划法C、贪心法D、回溯法18.下边是贪心算法的基本因素的是（C）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解19.回溯法的效率不依赖于以下哪些因素（D）A.知足显拘束的值的个数B.计算拘束函数的时间C.计算限界函数的时间D.确立解空间的时间20.下边哪一种函数是回溯法中为防备无效找寻采纳的策略（B）A．递归函数B.剪枝函数C。随机数函数D.找寻函数21、以深度优先方式系统找寻问题解的算法称为(D)。A、分支界限算法B、概率算法C、贪心算法D、回溯算法22、贪心算法与动向规划算法的主要差别是（B）。A、最优子构造B、贪心选择性质C、构造最优解D、定义最优解23.采纳最大效益优先找寻方式的算法是（A）。A、分支界限法B、动向规划法C、贪心法D、回溯法24.（D）是贪心算法与动向规划算法的共同点。A、重叠子问题B、构造最优解C、贪心选择性质D、最优子构造性质25.矩阵连乘问题的算法可由（B）设计实现。A、分支界限算法B、动向规划算法C、贪心算法D、回溯算法26.0-1背包问题的回溯算法所需的计算时间为（A）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）27、背包问题的贪心算法所需的计算时间为（B）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）29、使用分治法求解不需要知足的条件是（A）。A子问题一定是同样的B子问题不能够够重复C子问题的解能够归并D原问题和子问题使用同样的方法解30、下边问题（B）不能够使用贪心法解决。A单源最短路径问题BN皇后问题C最小花销生成树问题D背包问题31、以下算法中不能够解决0/1背包问题的是（A）A贪心法B动向规划C回溯法D分支限界法32、回溯法找寻状态空间树是依据（C）的序次。A中序遍历B广度优先遍历C深度优先遍历D层次优先遍历33、采纳广度优先策略找寻的算法是（A）。A、分支界限法B、动向规划法C、贪心法D、回溯法34．实现归并排序利用的算法是（A）。A、分治策略B、动向规划法C、贪心法D、回溯法35．以下是动向规划算法基本因素的是（D）。A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质36．以下算法中平时以自底向下的方式求解最优解的是（B）。A、分治法B、动向规划法C、贪心法D、回溯法二、填空题1.算法的复杂性有时间复杂性和空间复杂性之分。2、程序是算法用某种程序设计语言的详尽实现。3、算法的“确立性”指的是组成算法的每条指令是清楚的，无歧义的。4.矩阵连乘问题的算法可由动向规划设计实现。5、算法是指解决问题的一种方法或一个过程。6、快速排序算法的性能取决于划分的对称性。7、从分治法的一般设计模式能够看出，用它设计出的程序一般是递归算法。8、问题的最优子构造性质是该问题可用动向规划算法或贪心算法求解的重点特点。9、以深度优先方式系统找寻问题解的算法称为回溯法。10、任何可用计算机求解的问题所需的时间都与其规模有关。11、计算一个算法时间复杂度平时能够计算循环次数、基本操作的频率或计算步。12、回溯法找寻解空间树时，常用的两种剪枝函数为拘束函数和限界函数14、解决0/1背包问题能够使用动向规划、回溯法和分支限界法，此中不需要排序的是动向规划，需要排序的是回溯法，分支限界法。15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：拘束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同样的种类，此中同时使用约束条件和目标函数的界进行裁剪的是0/1背包问题，只使用拘束条件进行裁剪的是N皇后问题。17、回溯法是一种既带有系统性又带有跳跃性的找寻算法。动向规划算法的两个基本因素是.最优子构造性质和重叠子问题性质19.贪心算法的基本因素是贪心选择质和最优子构造性质。21.动向规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，尔后从这些子问题的解获得原问题的解。算法是由若干条指令组成的有穷序列，且要知足输入，输出、确立性和有限性四条性质。23、快速排序算法是基于分治策略的一种排序算法。24、以广度优先或以最小耗费方式找寻问题解的算法称为分支限界法。三、算法设计题1.背包问题的贪心算法，分支限界算法最大子段和:动向规划算法贪心算法求活动安排问题快速排序多机调换问题-贪心算法四、简答题分治法的基本思想分治法与动向规划法的同样点分治法与动