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

第三章 单元测试

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)

答案:

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从小到大

答案:

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

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

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

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

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

D:位置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]

答案:

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

B:无环

C:连通

D:有n-1条边

答案:

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

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

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

12、判断题：
单源点最短路问题要求有向图中边的权值不能为负数。( )
选项：
A:对
B:错
答案:

第五章 单元测试

1、判断题：
动态规划求解问题的前提是最优化原理成立，求解问题的关键是找到递推关系式。( )
选项：
A:对
B:错
答案:

2、判断题：

( )
选项：
A:错
B:对
答案:

3、判断题：
K段图汇点t，cost(k-1,j)表示k-1阶段的结点j到t的权值，cost(i,j)表示i阶段的结点j到汇点t的最小成本。( )
选项：
A:错
B:对
答案:

4、判断题：
每对节点间最短路径问题，递推关系式从到的路径上最大编号的结点时。 ( )
选项：
A:错
B:对
答案:

5、判断题：
二分检索树的左子树中的元素都小于根，右子树中的元素都大于根 ( )
选项：
A:对
B:错
答案:

6、判断题：
最优二分检索树就是求解一个预期成本最小的二分检索树，决策过程主要是确定子树的根。 ( )
选项：
A:错
B:对
答案:

7、判断题：
i曲线的构造是将的曲线在X轴上右移i单位，然后上移个单位而得到。( )
选项：
A:错
B:对
答案:

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

9、判断题：
函数g(i,s)表示由结点i开始，通过S中的所有结点，在结点1终止的一条最短路径长度( )
选项：
A:对
B:错
答案:

10、单选题：
已知序列X=＜A,B,C,B,D,A,B＞,Y=＜B,D,C,A,B,A＞，则序列X和Y的最长公共子序列是（ ）
选项：
A:＜B,C,B,A＞

B:＜B,D,A,B＞

C:＜B,C,A＞

D:＜B,D,B,A＞

答案:

11、单选题：
n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下 ( ) 说法不正确？
选项：
A:让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水

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

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

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

答案:

12、判断题：
动态规划方法求解每对结点间的最短路问题要求图中不含有负环( )
选项：
A:对
B:错
答案:

第六章 单元测试

1、单选题：
已知一棵二元树的中序遍历序列：FDHGIBEAC，先序遍历序列为：ABDFGHIEC。其后序遍历序列为（ ）
选项：
A:FHIGDEBCA

B:FHIGDEABC

C:FHIGEDBCA

D:HIGFDEBCA

答案:

2、单选题：
算术表达式 的后缀形式是( )
选项：
A:

B:

C:

答案:

3、单选题：
将寄存器的值存入存储单元的语句是( )
选项：
A:

B:

C:

D:

答案:

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

5、判断题：
MR(T)的意思是表达式不使用store指令需要的最少的寄存器数量。 ( )
选项：
A:对
B:错
答案:

6、单选题：
当n＜MR(L)＜MR(R),其中n是机器的寄存器数量，应该先处理（ ）
选项：
A:先左子树，再右子树

B:先右子树，再左子树

答案:

7、单选题：
深度优先检索DFS需要使用（ ）存储被访问但尚未被检测的结点
选项：
A:堆栈

B:队列

答案:

8、判断题：
图采用邻接表或邻接矩阵存储方式，深度优先检索的时间复杂度不同（ ）
选项：
A:错
B:对
答案:

9、判断题：
删除无向连通图的一个结点及其相关联的边，形成了两个及以上的非空分图，这个结点称为关节点（ ）
选项：
A:对
B:错
答案:

10、判断题：
深度优先数DFN，表示深度优先访问的顺序。DFN(1)=5表示结点1第5个被访问。（ ）
选项：
A:错
B:对
答案:

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

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

第七章 单元测试

1、判断题：
背包问题中,约束条件是显式约束条件。（ ）
选项：
A:错
B:对
答案:

2、单选题：
是回溯法搜索方式的是（ ）。
选项：
A:广度优先

B:最小耗费优先

C:最大效益优先

D:深度优先

答案:

3、多选题：
皇后k可行的放置X(k)，已决策的前i个皇后的位置x(i),必须满足以下条件（ ）
选项：
A:x(i)-x(k)的绝对值不等于i-k的绝对值

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

C:x(i)＜x(k)

答案:

4、多选题：
子集和数问题中，限界函数Bk(x(1)…x(k))取真的条件是（ ）
选项：
A:已决策的前k个数据之和加上第k+1个数大于M

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

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

答案:

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

6、单选题：

背包问题的回溯算法所需的计算时间为（ ） 
选项：
A:
B:
C:

D:
答案:

7、判断题：
对于给定问题的解空间树是唯一的 ( )
选项：
A:对
B:错
答案:

8、判断题：
以深度优先方式搜索问题的解的方法称为回溯法 ( )
选项：
A:错
B:对
答案:

9、判断题：
树结构与所求问题的实例无关，结构不变的解空间树称为静态树 ( )
选项：
A:对
B:错
答案:

第八章 单元测试

1、判断题：
分支限界法搜索结点的顺序是广度优先。（ ）
选项：
A:错
B:对
答案:

2、单选题：
下面不是分支界限法搜索方式的是（ ）。
选项：
A:深度优先

B:宽度优先
C:后进先出优先
D:最小耗费优先
答案:

3、判断题：
15谜问题中，Less(12)=5说明比牌12小并且位置在牌12之后的牌有5个。（ ）
选项：
A:错
B:对
答案:

4、单选题：
下列算法中不能解决0/1背包问题的是（ ）
选项：
A:回溯法
B:动态规划
C:分支限界法

D:贪心法
答案:

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

6、单选题：
采用LC检索方式的算法是（ ）  
选项：
A:回溯法

B:贪心法
C:动态规划法
D:分支界限法
答案:

7、判断题：
LC检索一定可以找得到具有最小成本的答案结点( )
选项：
A:错
B:对
答案: