算法分析与设计智慧树知到期末考试答案章节答案2024年黑龙江工程学院

算法分析与设计智慧树知到期末考试答案+章节答案2024年黑龙江工程学院（4）

答案:b+=p[i]/w[i]*cleft;（3）

答案:i++；（2）

答案:b+=p[i]；（1）

答案:cleft-=w[i]；对于快速排序算法，选取数组最左元素作为基准元。若数组元素严格递减，则算法的时间复杂度为（）。

答案:在霍尔划分中，若i为从左向右扫描指针，j是从右向左扫描指针，则划分结束的条件是（）。

答案:i＞=j采用最大效益优先搜索方式的算法是（）。

答案:分支界限法FIFO是（）的一种搜索方式。

答案:分支限界法最大效益优先是（）的一种搜索方式。

答案:分支界限法回溯法解旅行售货员问题时的解空间树是（）。

答案:排列树下面算法的时间复杂度为（

）。intmaxElement(inta[],intn){maxVal=a[0];for(i=1;imaxVal)maxVal=a[i];returnmaxVal;}

答案:O(n)

答案:（1）（3）二分搜索算法是用（）实现的算法。

答案:分治法不属于回溯法解题步骤的是（

）

答案:确定最优子结构的性质对于下列递归，说法正确的是（

）。intf(intx){if(x==0)return0;elsereturn2*f(x-1)+x*x;}

答案:满足递归基本原则之基准情形、不断推进及合成效益法则。广度优先是（）的一种搜索方式。

答案:分支界限算法下列算法中不能解决0/1背包问题的是()

答案:贪心法函数logn3的渐进表达式为（

）。

答案:logn若序列X={B，C，A，D，B，C，D}，Y={A，C，B，A，B，C，D}，则其最长公共子序列长度为（）。

答案:5对于如下算法，以下叙述正确的是（

）。intuniqueElement(inta[],intn){for(i=0;i答案:（1）（4）从时间上讲，Kruskal算法的时间复杂度为()

答案:O(eloge)

答案:4下面算法的时间复杂度为（

）。intbinary(intn){if(n==1)return1;elsereturnbinary(n/2)+1;}

答案:O(logn)下面程序的时间复杂度为（

）。x=1；for（i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x++；

答案:n3回溯法的算法框架按照问题的解空间可分为（

）算法框架。（1）排列树

（2）子集树

（3）深度优先生成树

（4）广度优先生成树

答案:（1）（2）以下不能使用分治法求解的是（）。

答案:0/1背包问题对于快速排序算法，选取数组最左元素作为基准元。若所有数组元素都相等，则算法的时间复杂度为（）。

答案:解决0/1背包问题时需要排序的方法是回溯法和（）。

答案:分支限界法下面说法关于算法与问题的说法错误的是（）。

答案:证明算法不正确，需要证明对任意实例算法都不能正确处理。队列式分支限界法以最小耗费优先的方式搜索解空间树。（）

答案:错分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，两者的搜索方式是相同的。（）

答案:错问题的两个要素是输入和实例。（）

答案:错求解问题的输入量，称为问题的规模。（）

答案:对MST是最小连通子图包含n个顶点和n-1条边（）

答案:对判断下面的二分搜索算法是否正确。intbinarySearch(inta[],constintx,intn){

if(n>0&&x>=a[0])

{

intleft=0;

intright=n-1;

while(left<right){

intmiddle=(left+right+1)/2;

if(x<a[middle]){

right=middle-1;

}

else{

left=middle;

}

}

if(x==a[left])

{

returnleft;

}

}

return-1;}

答案:对算法是一个语句集合，按照顺序执行语句，处理实例，得到正确答案。（）

答案:对给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题。（）

答案:错回溯法中，所有子结点都已经产生的结节称为死结点。（）

答案:错Kruskal算法的预处理是边权非递减排序。（）

答案:对回溯算法在生成解空间的任一结点时先判断该结点是否可能包含问题的解，如果肯定不包含则跳过对该结点为根的子树的搜索逐层向祖先结点回溯。（）

答案:对贪心算法总能找到最优解。（）

答案:错回溯法是一种既带系统性又带有跳跃性的搜索算法。（）

答案:对分支限界法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树

答案:广度优先优先队列式分支限界法通常用以下（）数据结构来实现。

答案:堆分支限界法的搜索策略是：在扩展结点处，先生成其（）儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。

答案:所有的判断：优先队列式分支限界法中，限界函数的选择将影响算法性能。（）

答案:对优先队列式分支限界法选取扩展结点的原则是（）。

答案:结点的优先级判断：分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，两者的求解目标是相同的。（）

答案:错判断：优先队列式分支限界为了加速搜索的进程，按照优先队列中规定的优先级，选取优先级最高的结点，成为当前扩展结点。（）

答案:对常见的两种分支限界法为（）

答案:队列式（FIFO）分支限界法与优先队列式分支限界法用分支限界法设计算法的步骤不包括：（

）

答案:定义最优子结构判断：旅行商问题中，分支限界法的目标是找出满足约束条件的所有解。（）

答案:错回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。

答案:深度优先判断：回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种走不通就掉头的思想作为其控制结构。（）

答案:对回溯法主要有迭代回溯法和（）回溯法两种编程实现方法。

答案:递归回溯法的效率不依赖于下列哪些因素（）

答案:确定解空间的时间关于回溯搜索法的介绍下面（）是不正确描述。

答案:回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径用回溯法求解子集树问题，子集树有2^n个叶结点，遍历该子集树的算法时间复杂度通常为（）

答案:O(2^n)旅行售货员问题的解空间树是（）。

答案:排列树回溯法的算法框架按照问题的解空间一般分为子集树算法框架与（）算法框架。

答案:排列树用回溯法解0/1背包问题时，该问题的解空间结构为（）结构。

答案:子集树下面哪种函数是回溯法中为避免无效搜索采取的策略（）

答案:剪枝函数背包问题的贪心算法所需的计算时间为()

答案:O(nlogn)采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为()

答案:O(nlogn)Kruskal算法按照权重的升序把边包含进来，以构造最小生成树,并使得这种包含不会产生回路。为了保证这种检查的效率，需要应用一种所谓的并查算法。（）

答案:对贪心算法一定能产生最优解。（）

答案:错Prim算法是一种为加权连通图构造最小生成树的贪心算法。（）

答案:对贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。（）

答案:对对于不含有负权重值的图，Dijkstral算法总能产生一个正确的解。（）

答案:对贪心算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须消耗的大量时间。（）

答案:对如果e是加权连通图中权重最小的边，它必定是图的每一棵最小生成树的边。()

答案:错下列算法中通常以自底向上的方式求解最优解的是()

答案:动态规划法备忘录法是（）的变形。

答案:动态规划一个问题使用动态规划算法的关键特征是（）。

答案:最优子结构性质下列是动态规划基本要素的是（）

答案:子问题重叠性质0-1背包问题实例的动态规划表中某一行值的序列总是非递减的（）。

答案:对下列算法通常以自底向上的方式求解的是（）。

答案:动态规划算法求解某一问题的算法是唯一的。

答案:错适合于用动态规划法求解的问题，经分解得到的子问题不是互相独立的。（）

答案:对动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。（）

答案:对动态规划算法是以空间换时间的时空权衡技术（）。

答案:对要计算矩阵连乘积A1A2A3A4A5A6，其中各矩阵维数分别为A1（30×35），A2（35×15），A3（15×5），A4（5×10），A5（10×20），A6（20×25）。使用动态规划算法，记录最优值的数组中，元素m[2][4]的值为（）。

答案:4375对于棋盘覆盖问题的分治算法，使用主定理进行算法分析时，k、m、d的值分别为（）。

答案:k=4，m=2，d=0二分查找有序表（2，8，13，24，33，41，52，58，63，100），若查找表中元素51，则其依次和表中元素（）进行比较，查找结果是失败。

答案:33，56，41，52递归算法的基本原则包括基准情形、不断推进、设计法则和合成效益法则。（）

答案:对采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（）。

答案:递归次数与每次划分后得到的分区处理顺序无关设当n＞1时，T（n）=27T（n/3）+O（n2），则此分治法的时间复杂度为（）。

答案:Θ(n3)设当n＞1时，T（n）=2T（n/2）+O（n），则此分治法的时间复杂度为（）。

答案:Θ（nlogn）直接或间接调用自身的算法称为递归算法。（）

答案:对下列选项中，不可能是快速排序第2趟排序结果的是（）。

答案:{3，2，5，4，7，6，9}适合于用分治法求解的问题，经分解得到的子问题可以不是互相独立的。（）

答案:错使用分治法解决的一个问题时，需要将一个大的问题分解成若干个子问题，这些子问题可以和原问题相同，也可以不同。（）

答案:错算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。（）

答案:对算法分析是（）

答案:对算法需要多少计算时间和存储空间作定量分析当m为24，n为60时，使用欧几里得算法求m和n的最大公约数，需要进行（）次除法运算。

答案:3次下面函数中增长率最低的是（）

答案:log2n计算机的资源最重要的是内存和运算资源。因而，算法的复杂性有时间和空间之分。（）

答案:对描述算法的基本方法有。（1）自然语言（2）流程图（3）伪代码（4）程序设计语言（）

答案:（1）(2)（3）(4)下面属于算法的特性有()。

答案:确定性：组成算法的每条指令是清晰，无歧义的。###输出：算法产生至少一个量作为输出。###有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。###输入：有0个或多个外部量作为算法的输入。时间复杂度是指算法最坏情况下的运行时间。（）