算法分析与设计基础知识习题

算法分析与设计基础知识一、选择题1、二分搜索算法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法2.下列不是动态规划算法基本步骤的是（A）。A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3.回溯法解旅行售货员问题时的解空间树是（A）。A、子集树B、排列树C、深度优先生成树D、广度优先生成树4.衡量一个算法好坏的标准是（C）。A、运行速度快B、占用空间少C、时间复杂度低D、代码短5.以下不可以使用分治法求解的是（D）。A、棋盘覆盖问题B、选择问题C、归并排序D、0/1背包问题6.动态规划算法的基本要素为（C）A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用7.以下关于渐进记号的性质是正确的有：（A）A.f(n)=Θ(g(n)),g(n)=Θ(h(n))⟹𝑓(𝑛)=Θ(h(n))B.f(n)=O(g(n)),g(n)=O(h(n))⟹ℎ(𝑛)=O(f(n))C.O(f(n))+O(g(n))=O(min{f(n),g(n)})D.f(n)=O(g(n))⟺𝑔(𝑛)=𝑂(𝑓(𝑛))8.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用9.回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。A．广度优先B.活结点优先C.扩展结点优先D.深度优先10.分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。A．广度优先B.活结点优先C.扩展结点优先D.深度优先11.下面不是分支界限法搜索方式的是（D）。A、广度优先B、最小耗费优先C、最大效益优先D、深度优先12．分支限界法解0-1背包问题时，活结点表的组织形式是（B）。A、最小堆B、最大堆C、栈D、数组13.常见的两种分支限界法为（D）A、广度优先分支限界法与深度优先分支限界法；B、队列式（FIFO）分支限界法与堆栈式分支限界法；C、排列树法与子集树法；D、队列式（FIFO）分支限界法与优先队列式分支限界法；14、记号O的定义正确的是（A）。A、O(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}；B、O(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0cg(n)f(n)}；C、O(g(n))={f(n)|对于任何正常数c0，存在正数和n00使得对所有nn0有：0f(n)cg(n)}；D、O(g(n))={f(n)|对于任何正常数c0，存在正数和n00使得对所有nn0有：0cg(n)f(n)}；15.记号的定义正确的是（B）。A、O(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}；B、O(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0cg(n)f(n)}；C、(g(n))={f(n)|对于任何正常数c0，存在正数和n00使得对所有nn0有：0f(n)cg(n)}；D、(g(n))={f(n)|对于任何正常数c0，存在正数和n00使得对所有nn0有：0cg(n)f(n)}；16.具有最优子结构的算法有：（D）A．穷举法B．回溯法C．分支限界法D．动态规划法17.实现循环赛日程表利用的算法是（A）。A、分治策略B、动态规划法C、贪心法D、回溯法18.实现最长公共子序列利用的算法是（B）。A、分治策略B、动态规划法C、贪心法D、回溯法19．下列算法中通常以深度优先方式系统搜索问题解的是（D）。A、备忘录法B、动态规划法C、贪心法D、回溯法20.以深度优先方式系统搜索问题解的算法称为(D)。A、分支界限算法B、概率算法C、贪心算法D、回溯算法21．哈弗曼编码的贪心算法所需的计算时间为（B）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）22．最长公共子序列算法利用的算法是（B）。A、分支界限法B、动态规划法C、贪心法D、回溯法23．实现棋盘覆盖算法利用的算法是（A）。A、分治法B、动态规划法C、贪心法D、回溯法24.下面是贪心算法的基本要素的是（C）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解25.回溯法的效率不依赖于下列哪些因素（D）A.满足显约束的值的个数B.计算约束函数的时间C.计算限界函数的时间D.确定解空间的时间26.下面哪种函数是回溯法中为避免无效搜索采取的策略（B）A．递归函数B.剪枝函数C。随机数函数D.搜索函数27.（D）是贪心算法与动态规划算法的共同点。A、重叠子问题B、构造最优解C、贪心选择性质D、最优子结构性质28.矩阵连乘问题的算法可由（B）设计实现。A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法29.分支限界法解旅行售货员问题时，活结点表的组织形式是（A）。A、最小堆B、最大堆C、栈D、数组30、Strassen矩阵乘法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法31、使用分治法求解不需要满足的条件是（A）。A、子问题必须是一样的B、子问题不能够重复C、子问题的解可以合并D、原问题和子问题使用相同的方法解32、下面问题（B）不能使用贪心法解决。A、单源最短路径问题B、N皇后问题C、最小花费生成树问题D、背包问题33、下列算法中不能解决0/1背包问题的是（A）A、贪心法B、动态规划C、回溯法D、分支限界法34、回溯法搜索状态空间树是按照（C）的顺序。A、中序遍历B、广度优先遍历C、深度优先遍历D、层次优先遍历35、采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为(B)。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）36．实现合并排序利用的算法是（A）。A、分治策略B、动态规划法C、贪心法D、回溯法37．下列是动态规划算法基本要素的是（D）。A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质38．下列算法中通常以自底向下的方式求解最优解的是（B）。A、分治法B、动态规划法C、贪心法D、回溯法39．采用广度优先策略搜索的算法是（A）。A、分支界限法B、动态规划法C、贪心法D、回溯法40、合并排序算法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法41、背包问题的贪心算法所需的计算时间为（B）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）42．实现大整数的乘法是利用的算法（C）。A、贪心法B、动态规划法C、分治策略D、回溯法43．采用最大效益优先搜索方式的算法是（A）。A、分支界限法B、动态规划法C、贪心法D、回溯法44．贪心算法与动态规划算法的主要区别是（B）。A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解45.实现最大子段和利用的算法是（B）。A、分治策略B、动态规划法C、贪心法D、回溯法46.优先队列式分支限界法选取扩展结点的原则是（C）。A、先进先出B、后进先出C、结点的优先级D、随机47.背包问题的贪心算法所需的计算时间为（B）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）48、广度优先是（A）的一搜索方式。A、分支界限法B、动态规划法C、贪心法D、回溯法49.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B）。A、重叠子问题B、最优子结构性质C、贪心选择性质D、定义最优解50.算法分析中，记号O表示（B），记号表示（A），记号表示（D）。A、渐进下界B、渐进上界C、非紧上界D、紧渐进界二、填空题1.四后问题的搜索空间为排序树；0-1背包问题的搜索空间为子集树；旅行售货员问题的搜索空间为排序树。2.回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。3.回溯法一般以深度优先的方式搜索解空间树，而分支限界法则一般以广度优先或以最小耗费优先的方式搜索解空间树。4.在忽略常数因子的情况下，O、和三个符号中，O提供了算法运行时间的一个上界。5.分治算法的基本步骤包括(1)分解(2)解决(3)合并。6.回溯算法的基本思想是从根结点出发，按照深度优先策略遍历解空间。7.动态规划和分治法在分解子问题方面的不同点是分解后的子问题往往不相互独立。8.贪心算法中每次做出的贪心选择都是当前的最优选择。9.选择排序、插入排序和归并排序算法中，归并排序算法是分治算法。10.算法的复杂性有时间复杂性和空间复杂性之分。11.程序是算法用某种程序设计语言的具体实现。12.算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。13.矩阵连乘问题的算法可由动态规划设计实现。14.算法是指解决问题的一种方法。15.从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。16.问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。17.以深度优先方式系统搜索问题解的算法称为回溯法。18.计算一个算法时间复杂度通常可以计算的循环次数、基本操作的频度或计算步。19.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法，分支限界法。20.使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0/1背包，只使用约束条件进行裁剪的是N皇后问题。21.贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。22.贪心算法的基本要素是贪心选择性质和最优子结构性质。23.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题最优解，然后从这些子问题的解得到原问题的解。24.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性、有穷性和可行性五条性质。25.大整数乘积算法是用分治法来设计的。26.以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。27.快速排序算法是基于分治策略的一种排序算法。28.动态规划算法的两个基本要素是.最优子结构性质和重叠子问题性质。29.回溯法是一种既带有系统性又带有跳跃性的搜索算法。30.分支限界法主要有队列式分支限界法和优先队列式分支限界法。31.分支限界法是一种既带有系统性又带有跳跃性的搜索算法。32.回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数。33.任何可用计算机求解的问题所需的时间都与其规模有关。34.快速排序算法的性能取决于划分的对称性。35.算法就是一组有穷规则的集合，它们规定了解决某一特定类型问题的步骤。36.算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。37.计算机的资源最重要的是CPU和内存资源。因而，算法的复杂性有时间复杂度和空间复杂度之分。38.f(n)=6×2n+n2，f(n)的渐进性态f(n)=O(n2)39.贪心算法总是做出在当前看来最佳的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的最优值。40.常见的减治策略分为三类：减去一个常量，减去一个常量因子，减可变规模。41.变治思想有三种主要的类型：实例化简，改变表现，问题化简。42.减常量算法是在每次选法迭代中从实例规模中减去一个规模相同的常量。43.减常量因子算法是在每次迭代中从实例规模中减去一个相同的常量因子，也就是每次缩减的实例规模其比例相同。44.堆的构建过程对于堆排序而言是一种变治策略。属于变治思想中的实例化简类型。45.平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的实例化简类型。三、课程内容基本要求1.算法的描述方法：自然语言描述、类程序设计语言或流程图、程序设计语言描述或程序实现。要求能够用上述描述方法对算