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

第一章测试算法的重要特性()。

A:能行性

B:输出

C:有穷性

D:确定性

E:输入

答案:ABCDE语句returnsum(x,y);执行频度为1()

A:对

B:错

答案:B的上界函数是()

A:对

B:错

答案:A算法时间复杂度为O(1)说明算法执行时间是单位时间()

A:对

B:错

答案:B集合的位向量表示法，合并集合操作的时间复杂度为()

A:

B:

C:

D:

答案:A带加权规则的Union算法中，Parent(1)=-8,Parent(2)=-4，1、2代表的集合合并后,集合的根是1,Parent(1)=-12,Parent(2)=1()

A:对

B:错

答案:A写一个算法交换两个变量x、y的值不使用第三个变量。

答案:求下列函数的渐进表达式：;;;

答案:的渐进表达式=____

答案:按照渐进阶从低到高的顺序排列以下表达式：,,,,,,。

答案:第二章测试递归程序每一次递归执行的语句都完全相同()

A:对

B:错

答案:B对数组ary[0:n-1]求和,采用如下递归方式：arysum(n)=ary[n-1]+arysum(n-1),递归方式是()

A:线性递归

B:非线性递归

答案:A问题规模为的全排列问题，可以看作个规模为的全排列问题，因此时间复杂度为：()

A:错

B:对

答案:B递归程序简洁明了，因此比非递归程序执行效率高()

A:错

B:对

答案:AMasterMethod适应于求解形式如T(n)=aT(n/b)+f(n)的递归关系式。其中，a表示子问题个数，n/b子问题规模，f(n)表示划分子问题或整合子问题解的时间。()

A:对

B:错

答案:A递归关系式：F(n)=F(n-1)+F(n-2)+1是二阶齐次常系数线性递归式。()

A:错

B:对

答案:A解形式为()(p均为待定系数):

A:

B:

C:

D:

答案:C求解非线性变系数递归关系式一个原则是“变换”，经过变换将其转换为线性常系数等常规可求的递归式。()

A:对

B:错

答案:A用MasterMethod求解递归关系式：，上界是____

答案:分析算法的时间复杂度，写出T(n)的表达式____

答案:第三章测试在求解矩阵乘法问题中使用分治策略改善了问题的时间复杂度。()

A:对

B:错

答案:B问题规模为n的二分检索，不成功检索的情况有无数种()

A:错

B:对

答案:A二分检索平均时间复杂度是()

A:

B:

C:

D:

答案:BD分治策略在求最大最小元素问题中的应用有助于改善时间复杂度()

A:错

B:对

答案:A插入排序算法的最好情况是初始序列从小到大排列(目标是从小到大)时间复杂度是()

A:错

B:对

答案:A归并排序MergeSort算法存在的问题是()

A:递归层次多

B:子问题规模太小

C:元素在数组间频繁复制

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

A:A(5)＜A(3)＜A(7)＜A(8)＜A(0)

B:A(5)＜A(6)＜A(7)＜A(8)＜A(0)

C:A(5)＜A(3)＜A(7)＜A(8)

答案:C归并排序子问题是通过位置划分得到的，而快速排序的子问题是通过元素划分得到的()

A:对

B:错

答案:A规模为n的快速排序，第一次划分比较次数是n+1次。()

A:错

B:对

答案:B大堆排序求解选择问题，首先确定出最大元素()

A:对

B:错

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

A:错

B:对

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

A:对

B:错

答案:B第四章测试贪心法的关键是首先选择一种度量标准，按照这个标准依次处理n个输入()

A:错

B:对

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

A:目标函数效益值Pi从大到小

B:单位效益值pi/wi的非增次序

C:物品重量wi从小到大

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

A:对

B:错

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

A:对

B:错

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

A:作业i的期限值大于等于q+1

B:位置q之前的作业的期限值都小于等于当前作业i的期限值

C:位置q之后的作业的期限值都大于它们当前的位置

D:位置q之后的作业的期限值都大于作业i的期限值.

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

A:对

B:错

答案:A已知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，以下判断正确的是()

A:P(3)=1,其他P值不变

B:处理完作业2，F(3)-1=2,2所在集合的根是1，所以F(1)=F(3)=0

C:由于F(3)=3＞0，所以作业3可以调度，调度位置是时间片3[2,3]

D:P(3)=1,P(1)=-4,其他P值不变

答案:BCDn个结点的无向图连通图的生成树的性质有()

A:包含n个结点

B:有n-1条边

C:无环

D:连通

答案:ABCDPrim算法处理边的顺序是构成树的边中最小的边，剩余的边中权值最小的边不一定最先被选入生成树中。()

A:对

B:错

答案:AKruscal算法处理边的顺序是全部边中权值从小到大的顺序，选择n-1条边，这个过程中要保证不形成环。()

A:对

B:错

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

A:对

B:错

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

A:对

B:错

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

A:错

B:对

答案:B()

A:错

B:对

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

A:错

B:对

答案:B每对节点间最短路径问题，递推关系式从到的路径上最大编号的结点时。()

A:错

B:对

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

A:错

B:对

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

A:对

B:错

答案:Ai曲线的构造是将的曲线在X轴上右移i单位，然后上移个单位而得到。()

A:对

B:错

答案:A组成的序偶：(5,4)(3,6),由于占的背包容量:6>4,产生的效益值3

B:＜B,C,A＞

C:＜B,C,B,A＞

D:＜B,D,B,A＞

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

A:让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水

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

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

D:若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样

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

A:对

B:错

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

A:FHIGEDBCA

B:FHIGDEBCA

C:FHIGDEABC

D:HIGFDEBCA

答案:B算术表达式的后缀形式是()

A:

B:

C:

答案:C将寄存器的值存入存储单元的语句是()

A:

B:

C:

D:

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

A:错

B:对

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

A:对

B:错

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

A:先左子树，再右子树

B:先右子树，再左子树

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

A:堆栈

B:队列

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

A:错

B:对

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

A:错

B:对

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

A:对

B:错

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

A:对

B:错

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

A:对

B:错

答案:A第七章测试背包问题中,约束条件是显式约束条件。（）

A:错

B:对

答案:A0/1背包问题的显示约束条件是____

答案:是回溯法搜索方式的是（）。

A:广度优先

B:最小耗费优先

C:深度优先

D:最大效益优先

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

A:x(i)均不等于x(k)

B:x(i)-x(k)的绝对值不等于i-k的绝对值

C:x(i)＜x(k)

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

A:已决策的前k个数据之和加上第k+1个数大于M

B:已决策的前k个数据之和，加上剩余所有数据之和大于等于M

C:已决策的前k个数据之和加上第k+1个数小于等于M

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

A:错

B:对

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

A:

B:

C:

D:

答案:D对于给定问题的解空间树是唯一的()

A:对

B:错

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

A:对

B:错

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

A:对

B:错

答案:A第八章测试分支限界法搜索结点的顺序是广度优先。（）

A:对

B:错

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

A:FIFO

B:LC检索

C:深度优先

D:LIFO

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

A:错

B:对

答案:B下列算法中不能解决0/1背包问题的是（）

A:贪心法

B:分支限界法

C:动态规划

D:回溯法

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

A:错

B:对

答案:B采用LC检索