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

算法设计与分析（安徽理工大学）知到智慧树章节测试课后答案2024年秋安徽理工大学第一章单元测试

算法的重要特性()。

A:有穷性

B:能行性

C:确定性

D:输出

E:输入

答案:有穷性

；能行性

；确定性

；输出

；输入

语句returnsum(x,y);执行频度为1()

A:对B:错

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

A:错B:对

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

A:对B:错

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

A:

B:

C:

D:

答案:

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

A:错B:对

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

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

答案:无的渐进表达式=____

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

答案:无

第二章单元测试

递归程序每一次递归执行的语句都完全相同()

A:错B:对

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

A:线性递归B:非线性递归

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

A:对B:错

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

A:错B:对

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

A:对B:错

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

A:对B:错

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

A:

B:

C:

D:

答案:

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

A:错B:对

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

答案:无分析算法的时间复杂度，

写出T(n)的表达式____

答案:无

第三章单元测试

在求解矩阵乘法问题中使用分治策略改善了问题的时间复杂度。()

A:对B:错

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

A:错B:对

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

A:

B:

C:

D:

答案:

；

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

A:对B:错

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

A:对B:错

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

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

B:递归层次多

C:子问题规模太小

答案:元素在数组间频繁复制

；递归层次多

；子问题规模太小

数组link表示数组A(1:n)中元素的大小关系的链接信息表内容如下

link下标：12345678

值：64713080

表头指针p=5，则以p开头的数据顺序是()

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

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

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

答案:A(5)＜A(3)＜A(7)＜A(8)

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

A:错B:对

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

A:错B:对

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

A:对B:错

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

A:对B:错

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

A:对B:错

答案:错

第四章单元测试

贪心法的关键是首先选择一种度量标准，按照这个标准依次处理n个输入()

A:错B:对

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

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

B:物品重量wi从小到大

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

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

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

A:错B:对

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

A:错B:对

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

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

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

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

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

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

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

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

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

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

A:对B:错

答案:对已知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(1)=-4,其他P值不变

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

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

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

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

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

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

n个结点的无向图连通图的生成树的性质有()

A:无环

B:有n-1条边

C:连通

D:包含n个结点

答案:无环

；有n-1条边

；连通

；包含n个结点

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

A:对B:错

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

A:错B:对

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

A:错B:对

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

A:错B:对

答案:对

第五章单元测试

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

A:对B:错

答案:对

()

A:错B:对

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

A:对B:错

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

A:错B:对

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

A:对B:错

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

A:错B:对

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

A:错B:对

答案:对组成的序偶：(5,4)(3,6),由于占的背包容量:6>4,产生的效益值3<5,因此序偶(3,6)被支配，删除掉()

A:对B:错

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

A:错B:对

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

A:＜B,C,A＞

B:＜B,D,B,A＞

C:＜B,D,A,B＞

D:＜B,C,B,A＞

答案:＜B,C,B,A＞

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

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

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

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

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

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

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

A:错B:对

答案:对

第六章单元测试

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

A:FHIGEDBCA

B:FHIGDEABC

C:FHIGDEBCA

D:HIGFDEBCA

答案:FHIGDEBCA

算术表达式的后缀形式是()

A:

B:

C:

答案:

将寄存器的值存入存储单元的语句是()

A:

B:

C:

D:

答案:

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

A:错B:对

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

A:对B:错

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

A:先左子树，再右子树

B:先右子树，再左子树

答案:先右子树，再左子树

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

A:队列

B:堆栈

答案:堆栈

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

A:对B:错

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

A:对B:错

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

A:错B:对

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

A:对B:错

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

A:对B:错

答案:对

第七章单元测试

背包问题中,约束条件是显式约束条件。（）

A:对B:错

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

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

A:最大效益优先

B:广度优先

C:深度优先

D:最小耗费优先

答案:深度优先

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

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

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

C:x(i)＜x(k)

答案:x(i)均不等于x(k)

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

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

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

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

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

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

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

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

A:错B:对

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

A:

B:C:D:

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

A:对B:错

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

A:错B:对

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

A:对B:错

答案:对

第八章单元测试

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

A:对B:错

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

A:深度优先

B:LC检索C:LIFOD:FIFO

答案:深度优先

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

A:错B:对

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

A:分支限界法

B:回溯法C:贪心法D:动态规划

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