2024知到网课 算法设计与分析（安徽理工大学）智慧树答案

第一章 单元测试

1、多选题：算法的重要特性( )。
A:确定性

B:输入

C:能行性

D:有穷性

E:输出

正确答案:【确定性
;输入
;能行性
;有穷性
;输出
】

2、判断题：语句 return sum(x,y);执行频度为1 ( )
A:对
B:错
正确答案:【错】

3、判断题：的上界函数是 ( )
A:错
B:对
正确答案:【对】

4、判断题：算法时间复杂度为O(1)说明算法执行时间是单位时间( )
A:对
B:错
正确答案:【错】

5、单选题：集合的位向量表示法，合并集合操作的时间复杂度为( )
A:

B:

C:

D:

正确答案:【
】

6、判断题：带加权规则的Union算法中，Parent(1)=-8,Parent(2)=-4，1、2代表的集合合并后,集合的根是1,Parent(1)=-12,Parent(2)=1( )
A:对
B:错
正确答案:【对】

第二章 单元测试

1、判断题：递归程序每一次递归执行的语句都完全相同( )
A:错
B:对
正确答案:【错】

2、单选题：对数组ary[0:n-1]求和,采用如下递归方式：arysum(n)=ary[n-1]+arysum(n-1),递归方式是( )
A:线性递归
B:非线性递归

正确答案:【线性递归】

3、判断题：问题规模为的全排列问题，可以看作个规模为的全排列问题，因此时间复杂度为： ( )
A:错
B:对
正确答案:【对】

4、判断题：递归程序简洁明了，因此比非递归程序执行效率高( )
A:错
B:对
正确答案:【错】

5、判断题：Master Method适应于求解形式如T(n)=aT(n/b)+f(n)的递归关系式。其中 ，a表示子问题个数 ， n/b子问题规模，f(n)表示划分子问题或整合子问题解的时间。( )
A:对
B:错
正确答案:【对】

6、判断题：递归关系式：F(n)=F(n-1)+F(n-2)+1是二阶齐次常系数线性递归式。( )
A:对
B:错
正确答案:【错】

7、单选题：解形式为( )(p均为待定系数):
A:

B:

C:

D:

正确答案:【
】

8、判断题：求解非线性变系数递归关系式一个原则是“变换”，经过变换将其转换为线性常系数等常规可求的递归式。( )
A:错
B:对
正确答案:【对】

第三章 单元测试

1、判断题：在求解矩阵乘法问题中使用分治策略改善了问题的时间复杂度。 ( )
A:对
B:错
正确答案:【错】

2、判断题：问题规模为n的二分检索，不成功检索的情况有无数种( )
A:对
B:错
正确答案:【错】

3、多选题：二分检索平均时间复杂度是( )
A:

B:

C:

D:

正确答案:【
;
】

4、判断题：分治策略在求最大最小元素问题中的应用有助于改善时间复杂度( )
A:错
B:对
正确答案:【错】

5、判断题：插入排序算法的最好情况是初始序列从小到大排列(目标是从小到大)时间复杂度是 ( )
A:对
B:错
正确答案:【错】

6、多选题：归并排序MergeSort算法存在的问题是( )
A:元素在数组间频繁复制

B:子问题规模太小

C:递归层次多

正确答案:【元素在数组间频繁复制
;子问题规模太小
;递归层次多
】

7、单选题：数组link表示数组A(1:n)中元素的大小关系的链接信息表内容如下
link 下标：1 2 3 4 5 6 7 8
值： 6 4 7 1 3 0 8 0
表头指针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)
】

8、判断题：归并排序子问题是通过位置划分得到的，而快速排序的子问题是通过元素划分得到的( )
A:对
B:错
正确答案:【对】

9、判断题：规模为n的快速排序，第一次划分比较次数是n+1次。( )
A:对
B:错
正确答案:【对】

10、判断题：大堆排序求解选择问题，首先确定出最大元素( )
A:错
B:对
正确答案:【对】

11、判断题：造成选择问题最坏情况的原因是，划分元素选择使得两个子问题规模悬殊( )
A:对
B:错
正确答案:【对】

12、判断题：二次取中间值方法得到的划分元素可以划分成两个规模为n/2的子问题( )
A:对
B:错
正确答案:【错】

第四章 单元测试

1、判断题：贪心法的关键是首先选择一种度量标准，按照这个标准依次处理n个输入( )
A:对
B:错
正确答案:【对】

2、单选题：贪心法求解背包问题的最优度量标准是( )
A:目标函数效益值Pi从大到小

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

C:物品重量wi从小到大

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

3、判断题：证明贪心解就是最优解的思路是在不减少总效益值的情况下，替换解向量中不同元素，直到把最优解转化为贪心解。( )
A:对
B:错
正确答案:【对】

4、判断题：贪心法求解带有限期的作业调度问题，度量标准是总效益值，即按照效益值的从大到小的顺序处理作业。( )
A:对
B:错
正确答案:【对】

5、多选题：一个作业i是否可以插入到可行调度序列，要看能否找到一个可行的位置q，满足以下要求( )
A:位置q之后的作业的期限值都大于作业i的期限值.

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

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

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

正确答案:【位置q之后的作业的期限值都大于作业i的期限值.
;作业i的期限值大于等于q+1
;位置q之后的作业的期限值都大于它们当前的位置
;位置q之前的作业的期限值都小于等于当前作业i的期限值
】

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

7、多选题：已知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:P(3)=1,其他P值不变

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

D:由于F(3)=3＞0，所以作业3可以调度，调度位置是时间片3[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]
】

8、多选题：n个结点的无向图连通图的生成树的性质有( )
A:包含n个结点

B:无环

C:连通

D:有n-1条边

正确答案:【包含n个结点
;无环
;连通
;有n-1条边
】

9、判断题：Prim算法处理边的顺序是构成树的边中最小的边，剩余的边中权值最小的边不一定最先被选入生成树中。( )
A:对
B:错
正确答案:【对】

10、判断题：Kruscal算法处理边的顺序是全部边中权值从小到大的顺序，选择n-1条边，这个过程中要保证不形成环。( )
A:错
B:对
正确答案:【对】

11、判断题：给定无向连通图的最小生成树是唯一的 ( )
A:错
B:对
正确答案:【错】