算法设计与分析（安徽理工大学）智慧树知到期末考试答案章节答案2024年安徽理工大学

算法设计与分析（安徽理工大学）智慧树知到期末考试答案+章节答案2024年安徽理工大学152欧拉回路问题简单来说就是一笔画问题，每个边经过且只经过一次，结点可能会多次经过（）

答案:对130每对结点间的最短路径问题可以看成，求n次单源点最短路问题（）

答案:对124Prim算法中，数组元素near[j]取值为0表示已经结点j已经选入到树中；不为0，表示与结点j相邻的最小成本边的另一个端点。（）

答案:对55从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。（）

答案:对69Kruscal算法生成最小生成树时只要边数小于n-1，加入的最小边不构成环即可（）

答案:对46二元比较树的外节点表示一次不成功的检索，一次不成功检索在一个外节点处结束（错）一次成功检索在一个内节点处结束（）

答案:对188宽度优先检索是把未检测的结点存入队列（）

答案:对187结点v的所有相邻结点都被访问了，则v是已检测的结点（）

答案:对78分治策略将问题划分为规模相当的子问题时，平均效率最高（）

答案:对179在对表达式不做任何化简以及不使用交换律、分配律、结合律的情况下，如果表达式树的右子树不是叶子就先处理右子树，在处理左子树。（）

答案:对39如果元素间比较和下标比较代价相当，考虑递归开销，用分治策略找最大最小元素并不比直接求解效率更高（）

答案:对193双连通图中是不含有关节点的连通图（）

答案:对37二分检索问题种，成功检索的平均检索次数=总次数/（n+1）（）

答案:错180一个算术表达式的左右子树均为非叶结点时，先处理左子树在处理右子树，最后处理根（）

答案:错157货郎担问题中，递推式g(1,S)表示从结点1出发经过集合S中的结点到达结点1的最短路径长度（）

答案:对191深度优先周游算法DFT，调用深度优先检索算法DFS的次数超过1次数则说明图是非连通图（）

答案:对83集合的树表示中，数组Parent(1)=-8表示元素1是一个集合对应的树的树根，元素值为-8（）

答案:错155货郎担问题实际是一个排列问题，求解时间复杂度为O(n!)()

答案:对151货郎担问题求解模型可以用于求解欧拉回路问题（）

答案:错174通过表达式的后缀序列建立表达式树，如果遇到运算符，建立一个结点存储该运算符，并出栈栈顶两个元素，并作为运算符的左右儿子。然后将新结点压入栈（）

答案:对167表达式树建立过程是首先确定中缀表达式中优先级最低的运算符作为树根，左右运算量分别形成根的左右子树，然后依次对左右运算量判断最低优先级的运算，直到确定一棵完整的树。（）

答案:对已知普通背包问题M=30，n=3p=(35,30,25,5),w=(35,30,25,5),该背包问题最优解解向量X=（）

答案:0,0,1,1###6/7,0,0,0###0,1,0,0###5/7,0,0,1集合合并时间上界是O(n)的集合表示法是()

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

()。

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

答案:剪枝函数集合的三种表示形式中，执行查找操作时间为O(1)的方法是()

答案:位向量表示法已知数据列表如下：-15，-6，0，7，9，21，98，101，查找元素0，需要比较几次中间元素（）

答案:3多段图决策问题，源点为1，汇点为12，二维数组D记录各阶段决策选择的结点。经过求解已知：D(3,6)=10,D(3,7)=10D(3,8)=10；D(2,2)=7,

D(2,3)=6,D(2,4)=8,

D(2,5)=8；D(1,1)=2。最优路径是()

答案:1，2，7，10，12

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

答案:动态规划法n=5作业1-5的效益值分别为（35，30，25，20，15），期限值分别为（2，1，2，3，1），使用FJS算法，最后集合的根和元素个数是（）

答案:1，4背包问题的贪心算法所需的计算时间为（）。

答案:O(nlogn)下列是动态规划算法基本要素的是（）。

答案:子问题重叠性质

答案:(i,j]

答案:L(5)＞=DFN(2)对于算术表达式a*(b-d),模型机B有2个寄存器，则最优表达式是（）

答案:loadb,R1/subR1,d,R1/loada,R2/mpyR2,R1,R1最长公共子序列算法利用的算法是（）。

答案:动态规划法13已知n个数据得列表，最坏情况比较次数（）

答案:logn已知背包M=20，n=4，p=(25，20，10，5)w=(25,20,10,5),背包问题最优效益值（）

答案:20

答案:后序遍历下面是贪心算法的基本要素的是（）。

答案:贪心选择性质164常见的算术表达式，运算符在中间两边是操作数，称为表达式的中缀形式（）

答案:对45不相交集合的树表示中，集合的查找算法Find，使用压缩规则的作用是减小树的高度，可以有效提高以后的查询效率（）

答案:对137求解最优二分检索树中，递推关系初值C(i,i)=0表示结点i被检索成本为0（）

答案:错137求解最优二分检索树中，递推关系C(i,i)=0表示结点检索成本为0（）

答案:错189宽度优先检索程序BFS中，已被访问结点w，visited(w)=1（）

答案:对129解决N个资金在M个项目中配置的问题，可以使用多段图问题建模求解。按照项目M的数量，多段图可以分为M+1个阶段，起点s（第一阶段）表示没有给任何项目分配任何资金，汇点t表示给M个项目分配N个资金。边(i,j)表示给第i个项目分配j个资金，结点(i,j)表示前i个项目分配了j个资金，0＜=j＜=N，除起点和汇点外，其余阶段含有n+1个结点.（）

答案:对172形成表达式的后缀序列时，遇到右括号弹出栈中所有内容（）

答案:错82二次取中间值方法可以确保划分的子问题规模均为n/2()

答案:错200判断图的关节点问题中，可以通过后序遍历方式求结点的L值()

答案:对61判断一个集合中的作业调度是否可行，只需要判断集合中作业的期限值按照非降序是否有违反期限的情况即可。（）

答案:对165逆波兰式是两操作数在前面，运算符在后面的表达式，又称表达式的后缀形式（）

答案:对206八皇后问题，两个皇后(x,y),(l,m)不在同一斜角线上约束条件可以用|x-l|=|y-m|表示（）

答案:对163逆后序遍历就是先序遍历（）

答案:错

答案:对145背包问题中，序偶(8,9)和序偶(7,7)来自两个不同的集合，根据支配规则，7＜9,7＜8,则序偶(7,7)被支配，所以合并过程中要删除序偶(7,7)()

答案:错121贪心法求解0/1背包问题一定不能得到最优解（）

答案:错72贪心法不能得到0/1背包问题的最优解（）

答案:错134检索成本最小的二分检索树高度一定是最小的（）

答案:错42主定理MasterMethod可以解决任何类型的递归式求解问题（）

答案:错132动态规划求解每对结点间最短路问题，通过决策路径上经过的最大结点编号从而限制各阶段的结点数量（）

答案:对156货郎担问题对应有向连通图的结点为1-n，从结点1开始，递推式g(2,Φ)从结点1到结点2的路径长度（）

答案:错

答案:对76求最大最小元素问题中，分治策略比直接求解策略更优（）

答案:错57快速排序算法的性能取决于划分的对称性，即子问题规模相当。（）

答案:对118普通背包问题要求解向量x的取值范围是[0，1]，即可以是0或1，也可以是分数；0/1背包问题解向量只能是0或1（）

答案:对74汉诺塔问题得递归求解使用的是线性递归（）

答案:对94分支限界法的求解目标是找出满足约束条件的一个解或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解（）

答案:错102适用动态规划算法解决问题应该具有最优原理和子问题重叠（）

答案:错0/1背包问题中，p3=5，w3=4，最末序偶(6,6)，已经推断x3=1，继续推测x2的值应该继续判断()

答案:PROCMERGESORT(low,high)iflow＜highthenmid=(low+high)/2CALLMERGESORT(low,mid)CALLMERGESORT(mid+1,high)CALL________________归并排序算法,空白处选择（）

答案:MERGE(low,mid,high)二分检索算法是利用（）实现的算法

答案:分治策略7个作业，期限值分别为：1，2，3，3，5，6，6；先考虑作业7，需要考虑的时间片是（）

答案:F(6)分支限界法解最大团问题时，活结点表的组织形式是（）。

答案:最大堆link数组link[1]-link[8],内容如下：64713080.Q表示ary数组中一个子序列的起始下标，Q=2，则子序列为（）

答案:ary[2]＜ary[4]＜ary[1]＜ary[6]

答案:快速分类算法i＜p则交换两个元素，元素列表如下：5,4,3,2,5,9,6,8,7，经过一次划分后列表是（）

答案:5,4,3,2,5,9,6,8,7算法partition中元素交换条件改为i＜=p，元素如下：15,14,13,12,15,19,16,18,17，经过一次划分后列表是（）

答案:12,14,13,15,15,19,16,18,17有元素列表如下：65798959758540。经一次划分后，元素列表是（）

答案:59406589758579递归表达式arysum(1,n)=arysum(1,n/2)+arysum(n/2+1,n)完成对数组求和，这种递归方式是（）

答案:非线性递归数组长度为n，对其执行一次划分过程，时间复杂度设为P(n)=（）

答案:O(n)select问题最好情况下时间复杂度（）

答案:O(nlogn)19在快速排序算法中，元素个数为n，一次划分的比较次数是（）

答案:n次元素列表如下：2212-5-81560173147，利用分治策略找最大最小元素，递归层数（）

答案:4PROCMERGESORT(low,high)iflow＜highthenmid=(low+high)/2CALLMERGESORT(low,mid)CALLCALLMERGE(low,mid,high)MERGE是两个子序列的合并算法，归并排序算法,空白处选择（）

答案:MERGESORT(mid+1,high)连续执行n次查找和合并集合的操作时间接近O(n)的方法是()

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

答案:回溯法二分检索算法对数组下标0-19的元素进行划分子问题，中间元素下标为（）

答案:9以深度优先方式系统搜索问题解的算法称为

()

答案:回溯算法17数组中元素如下：31201681751541891031576，归并算法递归层次为（）

答案:5广度优先是（）的一搜索方式。

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

答案:结点的优先级下列算法中不能解决0/1背包问题的是（）

答案:贪心法15谜问题中，Less(12)=5说明比牌12小并且位置在牌12之后的牌有5个。（）

答案:对下面不是分支界限法搜索方式的是（）。

答案:深度优先采用LC检索方式的算法是（）

答案:分支界限法如果x是答案结点，且效益值P是当前的最优解，则问题的界U更新为P，如果x不是答案结点则界等于P+ε，ε是个极小的正数。（）

答案:对LC检索一定可以找得到具有最小成本的答案结点()

答案:错分支限界法搜索结点的顺序是广度优先。（）

答案:对子集和数问题中，限界函数Bk(x(1)...x(k))取真的条件是（）

答案:已决策的前k个数据之和，加上剩余所有数据之和大于等于M###已决策的前k个数据之和加上第k+1个数小于等于M是回溯法搜索方式的是（）。

答案:深度优先对于给定问题的解空间树是唯一的()

答案:错背包问题的回溯算法所需的计算时间为（）

答案:树结构与所求问题的实例无关，结构不变的解空间树称为静态树()

答案:对以深度优先方式搜索问题的解的方法称为回溯法()

答案:对

答案:错皇后k可行的放置X(k)，已决策的前i个皇后的位置x(i),必须满足以下条件（）

答案:x(i)均不等于x(k)###x(i)-x(k)的绝对值不等于i-k的绝对值应用着色问题求解排考问题时，n门课程作为图的n个结点，有公共学生的课程，其对应结点用边连接，形成一个无向连通图。对该图求解着色问题，不同颜色数量即为需要排考的时间段数（）

答案:对结点u及其儿子x、y、z的信息如下：DFN(u)=5，L(x)=1,L(y)=2,L(z)=5,可以判断：结点u不是关节点。（）

答案:错算法ART(u,v)中，当对u(不是根结点)的邻接节点w递归访问结束后，就得到了L(w)的值。（）

答案:对当n＜MR(L)＜MR(R),其中n是机器的寄存器数量，应该先处理（）

答案:先右子树，再左子树删除无向连通图的一个结点及其相关联的边，形成了两个及以上的非空分图，这个结点称为关节点（）

答案:对

答案:已知一棵二元树的中序遍历序列：FDHGIBEAC，先序遍历序列为：ABDFGHIEC。其后序遍历序列为（）

答案:FHIGDEBCA

答案:深度优先检索DFS需要使用（）存储被访问但尚未被检测的结点

答案:堆栈机器模型A下生成最优代码规则，当右子树不是叶子的时候，要先对右子树进行递归处理，结果存入存储单元，再处理左子树，最后是根。（）

答案:对图采用邻接表或邻接矩阵存储方式，深度优先检索的时间复杂度不同（）

答案:对MR(T)的意思是表达式不使用store指令需要的最少的寄存器数量。()

答案:对深度优先数DFN，表示深度优先访问的顺序。DFN(1)=5表示结点1第5个被访问。（）

答案:对动态规划方法求解每对结点间的最短路问题要求图中不含有负环()

答案:对n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下()说法不正确？

答案:让水桶大的人先打水，可以使得每个人排队时间之和最小

答案:对

答案:对

答案:对动态规划求解问题的前提是最优化原理成立，求解问题的关键是找到递推关系式。()

答案:对已知序列X=＜A,B,C,B,D,A,B＞,Y=＜B,D,C,A,B,A＞，则序列X和Y的最长公共子序列是（）

答案:＜B,C,B,A＞二分检索树的左子树中的元素都小于根，右子树中的元素都大于根()

答案:对

答案:对最优二分检索树就是求解一个预期成本最小的二分检索树，决策过程主要是确定子树的根。()

答案:对函数g(i,s)表示由结点i开始，通过S中的所有结点，在结点1终止的一条最短路径长度()

答案:对K段图汇点t，cost(k-1,j)表示k-1阶段的结点j到t的权值，cost(i,j)表示i阶段的结点j到汇点t的最小成本。()

答案:对单源点最短路问题要求有向图中边的权值不能为负数。()

答案:对给定无向连通图的最小生成树是唯一的()

答案:错一个作业i是否可以插入到可行调度序列，要看能否找到一个可行的位置q，满足以下要求()

答案:位置q之后的作业的期限值都大于它们当前的位置###位置q之前的作业的期限值都小于等于当前作业i的期限值###位置q之后的作业的期限值都大于作业i的期限值.###作业i的期限值大于等于q+1Prim算法处理边的顺序是构成树的边中最小的边，剩余的边中权值最小的边不一定最先被选入生成树中。()

答案:对插入算法求带期限的作业调度问题最大的问题是作业的调度顺序不固定，需要不断移动作业的调动位置，用并查集求解该问题的思路是开始就确定作业的调度位置。()

答案:对证明贪心解就是最优解的思路是在不减少总效益值的情况下，替换解向量中不同元素，直到把最优解转化为贪心解。()

答案:对贪心法求解带有限期的作业调度问题，度量标准是总效益值，即按照效益值的从大到小的顺序处理作业。()

答案:对贪心法求解背包问题的最优度量标准是()

答案:单位效益值pi/wi的非增次序Kruscal算法处理边的顺序是全部边中权值从小到大的顺序，选择n-1条边，这个过程中要保证不形成环。()

答案:对已知F(0)=0,F(1)=0,F(2)=1,F(3)=3,F(4)=4,P(0)=1,P(1)=-3,P(2)=1,P(3)=-1,P(4)=-1正处理作业,2，它的期限值为3，以下判断正确的是()

答案:P(3)=1,P(1)=-4,其他P值不变###处理完作业2，F(3)-1=2,2所在集合的根是1，所以F(1)=F(3)=0###由于F(3)=3＞0，所以作业3可以调度，调度位置是时间片3[2,3]n个结点的无向图连通图的生成树的性质有()

答案:包含n个结点###无环###有n-1条边###连通贪心法的关键是首先选择一种度量标准，按照这个标准依次处理n个输入()

答案:对二次取中间值方法得到的划分元素可以划分成两个规模为n/2的子问题()

答案:错造成选择问题最坏情况的原因是，划分元素选择使得两个子问题规模悬殊()

答案:对数组link表示数组A(1:n)中元素的大小关系的链接信息表内容如下link下标：12345678值：64713080表头指针p=5，则以p开头的数据顺序是()

答案:A(5)＜A(3)＜A(7)＜A(8)大堆排序求解选择问题，首先确定出最大元素()

答案: