算法分析与设计智慧树知到期末考试答案章节答案2024年湖南中医药大学

算法分析与设计智慧树知到期末考试答案+章节答案2024年湖南中医药大学在n皇后问题中，如果在棋盘的某一个位置(i,j)去除一个皇后，则()。

答案:M[j]=0###L[i+j]=0###R[i-j+N]=0###A[i][j]=0关于0-1背包问题，以下说法正确的是()。

答案:每种物品均只有一件###对于每种物品，只有装入和不装两种选择，不允许装入物品的一部分###其目标是使得装入背包物品的总价值最大关于部分背包问题的描述，以下正确的是()。

答案:部分背包问题的时间复杂度为O(nlogn)###部分背包问题使用贪心算法可以求得全局最优解###部分背包问题允许将一个物品的一部分装入背包()不能够使用贪心算法求解。

答案:0-1背包问题###图的m着色问题###n皇后问题马的遍历问题的剪枝条件为()。

答案:不能走出棋盘边界###每个点只经过一次在装载问题中，已知c为轮船的载重量，bestw是当前最优解，ew是当前扩展结点的重量，r是剩余集装箱的重量，w[i]是待装载集装箱的重量，当()时，需要将对应的子树剪掉。

答案:ew+w[i]>c###ew+r<=bestwPrim算法适合稠密图，其时间复杂度只与边的数目有关。

答案:错解决有10个圆盘的汉诺塔问题，至少需要移动圆盘1024次。

答案:错含有n个顶点的连通图的生成树含有n(n+1)/2条边。

答案:错用回溯法解决0-1背包问题的基本思想是从第1个物品开始逐个选择物品，当剩余容量装不下后续考虑的物品或者得不到更优解时，再通过回溯来修改先前的装入方案，直到求得全局最优解为止。

答案:对以下代码的时间复杂度为()。i=1;while(i<=n){i+=2;}

答案:O(n)小明的表哥为他推荐了一些学习计算机编程的小视频，这些视频的播放时间长短不完全相同。现在给定一段时间，为了能够快速计算出在这段时间内小明最多可以看多少个视频，可以使用()算法。

答案:贪心已知一只青蛙一次可以跳上1级台阶，也可以跳上2级。该青蛙跳上一个5级的台阶总共有()种跳法。

答案:8图的m着色问题可使用()算法求解。

答案:回溯输入数组(6,-1,5,4,-7)，它的最大子段和以及子段的起始位置和结束位置(位置均从1开始)分别是()、()和()。

答案:14,1,4函数f(n)=3nlogn^3+n+2的渐进表达式是（）。

答案:O(nlogn)马的遍历问题的剪枝函数：棋盘大小为m*n，A[][]数组用于记录马的行走过程。boolcheck(intx,inty){if(x>=1&&x<=n&&y>=1&&y<=m&&(!A[x][y]))____(1)___;else____(2)____;}

答案:(1)returntrue(2)returnfalse以深度优先方式搜索问题解的算法称为()。

答案:回溯法如果使用穷举法求解0-1背包问题，将产生（）种装物品的方案。

答案:2^n()描述算法形象直观，且易于理解。

答案:程序流程图4皇后问题的解的个数为()。

答案:2可使用()设计一个求取一个序列的最长递增子序列的高效算法。

答案:动态规划如果从最后一个物品开始装入背包，0-1背包问题的最优解为()。【n为物品数量，c为背包容量】

答案:m[1][c]以广度优先或以最小耗费方式搜索问题解的算法称为()。

答案:分支限界法在图的m着色问题中，如果有5个顶点，3种颜色，则解空间树为()。

答案:一棵6层（包括第一层）的3叉树关于二分查找的设计思想，以下说法正确的是()。

答案:如果key大于a[mid]，则在升序序列的后半部分继续查找###如果key等于a[mid]，则返回mid###如果key小于a[mid]，则在升序序列的前半部分继续查找###待查找元素key首先和最中间的值a[mid]进行比较分支限界法最常见的实现方式包括()。

答案:优先队列式分支限界法###队列式分支限界法关于Prim算法和Dijkstra算法，以下说法正确的是()。

答案:两个算法在不优化时的时间复杂度都为O(V^2)，V表示顶点的个数###两个算法都需要引入一个数组用于记录一个点是否被访问过###两个算法都是贪心算法的经典实例###两个算法都包含了松弛操作，在松弛时对相应的数据结构进行更新如果马的初始位置为(x,y)，在不考虑重复和出界的情况下，()是下一个可以到达的遍历位置。

答案:(x-2,y-1)###(x-2,y+1)###(x+2,y-1)###(x-1,y+2)()不是使用自然语言描述算法的优点。

答案:直观形象###格式规范###易于自动生成代码递归的应用场景包括()。

答案:采用的数据结构是递归的###问题的定义是递归的###问题的求解方法是递归的以下不等式正确的是()。

答案:O(logn)###O(nlogn)###O(n)下列关于动态规划算法与分治法的说法正确的是（）

答案:动态规划算法与分治法类似，基本思想是将待求解问题分解成若干个子问题###动态规划算法经分解得到的子问题往往不是独立的，有些子问题被重复计算多次###分治算法经分解得到的子问题往往是独立的能够使用贪心算法求解的问题需要具备的基本要素为()。

答案:最优子结构###贪心选择性质关于贪心算法，以下说法正确的是()。

答案:贪心算法在每一步选择中都采取最好或者最优（最有利）的选择策略###部分背包问题可以使用贪心算法求解以下表达式正确的是()。

答案:O(Cf(N))=O(f(N))###O(f)O(g)=O(fg)###O(f)+O(g)=O(f+g)###O(f)+O(g)=O(max(f,g))以下采用分治策略的算法包括()。

答案:快速排序###二分查找分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树，在分支限界法中，每一个活结点有多次机会成为扩展结点。

答案:错动态规划算法通过保存已解决子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

答案:对在最坏情况下，快速排序的效率仍然高于其他所有排序算法。

答案:错对于同一背包和相同的一组物品，作为部分背包问题求解得到的总价值一定大于等于作为0-1背包问题求解得到的总价值。

答案:对在解决活动安排问题时应首先对活动进行排序，排序的依据是按照活动开始时间降序排列。

答案:错在图的m着色问题中，当搜索的当前节点t<=N时，依次尝试m种颜色，调用剪枝函数check()进行判断。如果当前颜色可以使用，则进入下一层搜索；当搜索到叶子节点时（t>N），即输出一种着色方案。

答案:对使用贪心算法求解找硬币问题时，总能找到问题的最优解。

答案:错在使用回溯法求解0-1背包问题时，为了能够更加高效地进行剪枝，可以通过将剩余物品的价值进行求和的方法得到右子树的最优上界。

答案:错为了提高问题求解效率，有时候需要在某些递归算法中消除递归调用，使其转化为非递归算法。

答案:对对于有64片圆盘的汉诺塔问题，如果每移动一次圆盘需要1秒，则一小时以内可以完成全部圆盘的移动。

答案:错贪心算法中每次做出的贪心选择都是局部最优选择。

答案:对使用动态规划算法求解最长公共子序列问题，引入数组c[i][j]存储序列x[1..i]和y[1..j]的最长公共子序列的长度，则对于长度为m和n的两条序列，其最长公共子序列的长度为c[m][n]。

答案:对在对Dijkstra算法进行初始化时，如果两个顶点之间没有边，则它们之间的距离为无穷大。

答案:对二分查找算法是运用()的典型实例。

答案:分治策略如果斐波那契数列的第一项F(0)=1，第二项F(1)=1，则F(8)=___________。

答案:34以下算法中效率最优的算法是()。

答案:T(n)=T(n/2)+O(1)直接或间接地调用自身的算法称为()。

答案:递归如果从第一个物品开始装入背包，在能够装入的情况下，背包的最优价值m[i][j]=()。

答案:max{m[i-1][j],m[i-1][j-wi]+vi}函数f(n)=1+1/n^2的渐近表达式为()。

答案:O(1)在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是()。

答案:分支限界法代码填空【快速排序的分区函数：以第1个元素为基准元素】intswap(inta[],inti,intj){inttemp=a[i];a[i]=a[j];a[j]=temp;}intpartition(inta[],intp,intq){intx=a[p];inti=p,j;for(j=p+1;j<=q;j++){if(a[j]<=x){i++;______(1)________;}}_________(2)___________;returni;}

答案:(1)swap(a,i,j)(2)swap(a,p,i)函数n^2/10+2^n的渐进表达式为()。

答案:O(2^n)回溯法搜索状态空间树是按照()的顺序。

答案:深度优先遍历在装载问题中，如果右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量，则当()时，可将其右子树剪去。

答案:ew+r<=bestw关于回溯法和分支限界法，以下说法正确的是()。

答案:分支限界法通常用于求满足约束条件的一个解或特定意义下的最优解###在回溯法中，活结点的所有可行子结点均被遍历后才从栈中弹出###在分支限界法中，每个结点只有一次成为扩展结点的机会###回溯法通常用于求满足约束条件的所有解如果一个给定装载问题有解，则采用的装载策略为：首先将第一艘轮船尽可能装满；再将剩余的集装箱装上第二艘轮船。

答案:对优先队列式分支限界法将活结点表组织成一个优先队列，按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。

答案:对分支限界法采用的搜索策略是()。

答案:广度优先搜索队列具有()的性质。

答案:先进先出使用队列式分支限界法求解装载问题时，每次从队列Q中取出队首元素作为当前扩展结点。取队首元素后，判断当前Q是否为空。如Q非空，则将尾部标记-1加入Q，算法开始处理下一层的活结点。

答案:错根据活结点表的组织方式不同，分支限界法包括()等形式。

答案:队列式分支限界法###优先队列式分支限界法关于分支限界法的基本思想，下列描述正确的是()。

答案:每一个活结点只有一次机会成为扩展结点###一直持续到找到所求的解或活结点表为空时为止###从活结点表中取下一结点成为当前扩展结点，并重复结点扩展过程###那些导致不可行解或导致非最优解的子结点被舍弃，其余子结点被加入活结点表中###活结点一旦成为扩展结点，就一次性产生其所有子结点应用分支限界法的三个关键问题包括()。

答案:如何组织活结点表###如何设计合适的剪枝函数###如何确定最优解的解向量四皇后问题一共有2个可行解，八皇后问题一共有76个可行解。

答案:错在N皇后问题中，需要将棋盘当做一个二维数组来分析，对于该二维数组，以下说法正确的是()。

答案:对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相减的值相同。###对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相加的值相同。用m种颜色给n个顶点着色、且使一条边的两个顶点颜色不同，则对应的解空间树是一棵()。

答案:高为n的m叉树任何一张地图只用()种颜色就能使具有共同边界的国家着上不同的颜色。

答案:4使用回溯法求解0-1背包问题时，计算右子树上界的方法是通过贪心策略求得上界，即将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，此时得到的价值就是右子树中解的上界。

答案:对马的遍历问题能否有可行解，与()有关。

答案:棋盘大小###马的初始位置回溯法的主要用途包括求问题的所有解、求问题的最优解和求问题的任一解。

答案:对回溯法采用的搜索策略是()。

答案:深度优先搜索关于使用回溯法求解0-1背包问题，以下说法正确的是()。

答案:使用约束函数剪去不合理的左子树（装该物品）。###使用限界函数剪去得不到更优解的右子树（不装该物品）。回溯法中的剪枝函数包括()。

答案:限界函数###约束函数能够使用贪心算法求解的问题需具备的基本要素包括()。

答案:贪心选择性质###最优子结构性质在对Dijkstra算法进行初始化时，如果两个顶点之间没有边，则它们之间的距离为()。

答案:无穷大在求解部分背包问题时采用的贪心策略是()。

答案:选择单位重量下价值最大的物品Prim算法适合稀疏图，其时间复杂度只与边的数目有关。

答案:错使用贪心算法求解最优装载问题，其时间复杂度为()。

答案:O(nlogn)()能够使用贪心算法求解。

答案:单源最短路径问题###活动安排问题###最小生成树问题###部分背包问题###最优装载问题在解决活动安排问题时应首先对活动进行排序，排序的依据是()。

答案:按照活动结束时间升序排列Dijkstra算法可用于求解()。

答案:每对顶点间最短路径问题###单对顶点最短路径问题###单终点最短路径问题###单源最短路径问题下列关于贪心算法与动态规划算法说法正确的是()。

答案:贪心算法与动态规划算法求解的问题都具备最优子结构性质###贪心算法与动态规划算法的主要区别是贪心算法要求问题具有贪心选择性质0-1背包问题与部分背包问题的区别在于()。

答案:在0-1背包问题中，物品只有装入和不装入两种情况，而部分背包问题允许只装入物品的一部分###若用贪心算法解决0-1背包问题，只能得到近似最优解某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额分别为15,10,12,8（万元），投资收益分别为12,8,9,5（万元），投资总额为30万元，选择项目()可以使总收益最大。（不允许部分投资某个项目）

答案:B###D###C输入数组（-1,0,1,-2,3），它的最大子段和是()。

答案:3字符序列abcde与字符序列abdge的最长公共子序列长度为()，最长公共子串长度为()。

答案:4,2关于备忘录法，以下说法正确的是()。

答案:备忘录法为每个解过的子问题建立备忘录以备需要时查看，又称查表法。###备忘录法可以避免相同子问题的重复求解。###备忘录法的控制结构与直接使用递归方法的控制结构相同。使用动态规划算法求两条长度分别为m和n的序列的最长公共子序列，其时间复杂度为()。

答案:O(n*m)在使用动态规划算法求解0-1背包问题时，若m[i][j]=m[i+1][j-w[i]]+v[i]，说明第i个物品在剩余背包容量为j时可以装入，并且装入比不装入的背包总价值更大，装入后，背包剩余容量减少w[i]，价值增加v[i]。

答案:对序列（1，7，3，4，9，2，3）的最长递增子序列的长度为()。

答案:4使用动态规划算法求最大子段和的时间复杂度为()。

答案:O(n)使用穷举法求解最长递增子序列的时间复杂度为()。

答案:O(n*2^n)能够使用动态规划算法来求解的问题通常需要具备两个重要的性质，它们分别是()。

答案:最优子结构###重叠子问题在使用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分成大小相等的多个子问题的处理方法是行之有效的。

答案:对快速排序是对传统排序算法()的一种改进。

答案:冒泡排序在经典的汉诺塔问题中，如果有5个圆盘需要从A柱移至C柱，最少需要移动()步。

答案:31给定递归公式T(n)=4T(n/2)+O(n),由主定理可以得知T(n)=()。

答案:O(n^2)已知某楼房共20层，如果采用二分查找，请问最多猜()次就能猜出任意一个楼层。

答案:5已知f(1)=1，f(n)=f(n-1)+n，那么f(50)的作用是()。

答案:计算1到50的和。递归的优点包括()。

答案:可读性强###结构清晰###容易用数学归纳法来证明算法的正确性分治法能解决的问题一般具有（）等特征。

答案:最优子结构###分解出的子问题的解可以合并为原问题的解###子问题相互独立###该问题缩小到一定程度时可以容易地解决递归函数是指在一个函数体中出现直接或间接调用该函数自身的函数。

答案:对关于快速排序的时间复杂度，()是正确的。

答案:在平均情况下时间复杂度为O(nlogn)###在最坏情况下时间复杂度为O(n^2)###在最好情况下时间复杂度为O(nlogn)对于f(n)=n，下列说法正确的是（）。

答案:f(n)=O(n^3)###f(n)=O(n)###f(n)=O(n^2)程序是算法用某种程序设计语言的具体实现，程序需满足算法的所有性质。

答案:错如果存在正的常数C和自然数N0,使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)),即f(N)的阶不高于g(N）的阶。

答案:对一个算法的优劣由（）决定。

答案:时间复杂度###空间复杂度函数f(n)=20log3^n的渐进表达式是（）。

答案:O(n)使用伪代码描述算法具有（）等优点。

答案:易于转化为程序语言代码###简单易懂###容易修改算法通常具有（）的性质。

答案:输出：至少有一个输出###确定性：组成算法的每条指令清晰、无歧义###输入：有零个或多个输入###有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限算法是指解决问题的方法或过程，它包含一系列步骤，用来将输入数据转换成输出结果。

答案:对分析以下代码的时间复杂度：intfunc(intn){inti=1,k=0;while(i<=n){k++;i=i*2;}returnk;}

答案:O(logn)常用的描述算法的形式有（）。

答案:伪代码###程序流程图###自然语言为了得到装入集装箱的数量以及装入的总重量和集装箱编号，在使用贪心算法求解最优装载问题时，每成功装入一个集装箱，则()。

答案:更新轮船已装载总重量###装入集装箱总数加1###更新轮船的剩余重量###记录装载的集装箱编号()是回溯法的应用实例。

答案:n皇后问题###0-1背包问题###图的m着色问题关于最长公共子序列问题，以下说法正确的是()。

答案:如果两个序列的最后一个元素相同，则它们的最长公共子序列长度为去掉最后一个元素后，两个剩余序列的最长公共子序列长度加1###空序列和一条非空序列的最长公共子序列的长度为0###两个序列的最长公共子序列可能不唯一###两个序列的最长公共子序列包含了这两个序列前缀的最长公共子序列一个算法的优劣可以用()来衡量。

答案:时间复杂度###空间复杂度关于Prim算法中的数据结构，以下说法正确的是()。

答案:使用used[n]标记顶点是否被访问###使用数组lowcost[n]记录不在S中的顶点到S的最短距离###使用数组closeset[n]记录不在S中的顶点在S中的最近邻接点程序需要具备以下哪些性质？

答案:输出：至少有一个输出###确定性###输入：有零个或多个输入已知4个物品A、B、C、D的重量分别为[15,10,12,7]，价值分别为[50,20,40,40]，每一个物品均不能分解。现有一个容量为30的背包，选择物品()可以使得背包中物品的总价值最大。

答案:C###B###D关于活动安排问题，以下说法正确的是()。

答案:算法每次总是选择具有最早完成时间的相容活动加入集合中。###对于活动安排问题，贪心算法能求得的整体最优解，即它最终所确定的相容活动集合的规模最大。###活动安排问题的贪心选择意义在于使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。()属于搜索算法。

答案:回溯法###分支限界法在图的m着色问题中需要使用到的数据结构包括()。

答案:用一个二维数组以邻接矩阵的方式存储地图###用一个一维数组存储每一个点所着颜色能够使用分治法求解的问题通常具有的特征包括()。

答案:问题缩小到一定的规模可以直接求解###分解出的各个子问题相互独立###分解出的子问题的解可以合并为原问题的解###问题可以分解为若干个规模更小的相同类型的子问题关于Dijkstra算法中的数据结构，以下说法正确的是()。

答案:需要一个used[]数组用于记录一个点是否已访问过###需要一个dis[]数组用于保存源点到其他点的最短路径值###如果源点到某一个点i之间有一条边，则dis[i]的初始值为这条边的权重###如果源点到某一个点i没有直接的边相连，则dis[i]的初始值为无穷大在物品重量和背包容量都是正整数的情况下，0-1背包问题可以用()求解。

答案:动态规划算法###回溯法###穷举法关于Dijkstra算法，以下说法正确的是()。

答案:有向图和无向图都可以使用Dijkstra算法来求单源最短路径###Dijkstra算法既可以用于求解单源最短路径问题，也可以用于求解单终点最短路径问题###在Dijkstra算法中，通过松弛操作来更新源点到其他顶点的距离递归的基本要素包括()。

答案:递归表达式###递归结束条件使用贪心算法求解最优装载问题，其时间复杂度为O(n)。

答案:错使用递归对整数进行求和的速度比使用循环的速度更快。

答案:错动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

答案:对在计算最长公共子序列的长度时，为了减少空间需求可以使用滚动数组。给定两个序列，长度分别为m和n，可以将短的序列作为行，长的序列作为列，最后可将空间需求减至O(min(m,n))。

答案:对动态规划的基本步骤是先找出最优解的性质，并刻画其结构特征，然后递归地定义最优值，以自底向上的方式计算出最优值，最后根据计算最优值时得到的信息，构造最优解。

答案:对如果图中存在负权边，则不能使用Dijkstra算法来求源点到其他点之间的最短路径。

答案:对在Prim算法中，每次从不在集合S的点中选出一个点j使得其与S内的某点i的距离最短，则(i，j)就是生成树上的一条边，同时将j点加入S。

答案:对在马的遍历问题中，对于棋盘上任意一点A(x,y)，有八个扩展方向，可以用数组fx[8]={1,2,2,1,-1,-2,-2,-1},fy[8]={2,1,-1,-2,-2,-1,1,2}来模拟马走“日”时下标的变化过程。

答案:对快速排序算法的性能取决于划分的对称性，划分越对称，排序的效率越高。

答案:对Dijkstra算法采用了和Prim算法类似的松弛操作，松弛操作的目的是减少dis[i]的值，如果从源点s到达i有更优的路径则更新dis[i]。

答案:对解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法和分支限界法。

答案:对Dijkstra算法是一个按路径长度递增的次序产生最短路径的算法。

答案:对在最好情况下、最坏情况下、平均情况下的时间复杂度中，可操作性最好的且最有实际价值的，是最坏情况下的时间复杂度。

答案:错二分查找又称为折半查找，它是一种高效的查找方法，但是二分查找要求列表中的元素是有序的，是分治算法的典型实例之一。

答案:对队列Queue具有先进后出的性质。

答案:错对于一个二维数组而言，同一条右斜线上的坐标x和y之和为一个相同的数。

答案:错任何一张地图只用4种颜色就能使具有共同边界的国家着上不同的颜色。

答案:对如果不对顶点的选取过程进行优化，Dijkstra算法的时间复杂度为O(EV)。【V表示顶点的数量，E表示边的数量】

答案:错回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。

答案:对logn^5+n^1/2=O(n^1/2)

答案:对使用分治设计算法来求解问题时，通常在分解问题时要求子问题的规模尽量一致。

答案:对某个问题的最优解包含着其子问题的最优解，这种性质称为最优子结构性质。

答案:对使用分支限界法设计求解装载问题的算法时，在队列中增加一个-1作为层的尾部标记。

答案:对快速排序是对冒泡排序的一种改进，它通过分区函数将待排序数据分为两组，其中一组中的数据都比另一组中的数据大，再递归对两组中的数据分别进行快速排序。

答案:对对于有5种物品的0-1背包问题，其解空间数量为()。

答案:32()是动态规划算法的基本要素之一。

答案:子问题重叠性质给定5个集装箱，它们的重量分别是3,4,5,2,1，已知船的装载量为10，该船最多可装载的集装箱数量是()个。

答案:4使用回溯法解决0-1背包问题中，在计算右子树的最优上界时，采用了()思想。

答案:贪心通常以自底向上的方式求解最优解的算法是()。

答案:动态规划法使用回溯法求解0-1背包问题，限界函数（用于剪去一些不包含最优解的右子树）的时间复杂度为(