智慧树知到答案算法设计与分析最新答案

第三章 单元测试

1、单选题：
设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，若xm=yn则（ ）。
选项：
A:zk≠xm=yn，且zk是Xm-1和Yn-1的最长公共子序列。

B:zk=xm=yn，且zk是Xm-1和Yn-1的最长公共子序列。

C:zk≠xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。

D:zk=xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。

答案: 【
】

2、单选题：
当(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10)=(-1, 5, -2, 1, -7, -4, 2, 3, -1, 2)时，最大子段和为( ).
选项：
A:7
B:10
C:6
D:9

答案: 【】

3、单选题：
设有四个矩阵A,B,C,D,它们的维数分别是A=50*10, B=10*40, C=40*30, D=30*50,，则计算其乘积至少需要（ ）次乘法
选项：
A:87500

B:10500,
C:16000,
D:36000,
答案: 【】

4、多选题：
下面关于动态规划解题的步骤内容描述正确的是哪些？（ ）
选项：
A:计算最优值：以自顶往下的方法计算问题的最优值，也就是先求解规模较大的问题的最优值。

B:分析最优解的结构：将一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质。

C:构造最优解：根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造。

D:建立递归关系：建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到。

答案: 【
】

5、单选题：
问题用动态规划算法求解效率较高的原因？( )
选项：
A:最优子结构性质
B:子问题重叠性质
C:贪心选择性质
D:递归性质.

答案: 【】

6、单选题：
对0-1背包问题，n=5，c=12，w={3,7,5,4，4}，v={6,3, 5,4，6 }，则其最优解为（ ）
选项：
A:（1，0，1，0，1）

B:（0，1，0，1，1）
C:（0，1，1，1，1）
D:（1，1，1，1，1）

答案: 【

7、判断题：
一般来说解同一个问题，动态规划法的效率高于分治算法（ ）
选项：
A:错
B:对
答案: 【】

8、判断题：
图象的变位压缩存储采用数据头和数据存储的编码式存储方式，节省存储空间，实现压缩。（ ）
选项：
A:对
B:错
答案: 【】

第四章 单元测试

1、单选题：
在某通讯系统中用到了a，b，c，d，e，f 8个字符，字符频度（百分比）为 45， 13， 12，16，9，5则字符a的编码为( )：
选项：
A:1100

B:0
C:. 111
答案: 【】

2、单选题：
活动安排问题利用贪心法求解，则其复杂度为（ ）
选项：
A:O(n2)
B:O(logn)

C:O(nlogn)
D:O(n)
答案: 【】

3、判断题：
在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。( )
选项：
A:错
B:对
答案: 【】

4、判断题：
背包问题与0-1背包问题求解方法类似，都能用贪心法或动态规划方法得到最优解（ ）
选项：
A:错
B:对
答案: 【】

5、多选题：
有关分治法、贪心算法和动态规划算法的描述，正确的是（ ）
选项：
A:问题能用动态规划法解的不一定能用贪心算法解；

B:贪心算法和动态规划算法共同特征为最优子结构性质;

C:适用三种方法所解的问题都是可分解成子问题的；

D:用贪心法一定能用动态规划法，但是，动态规划法的效率一般高于贪心算法。

答案: 【
】

6、多选题：
下列哪些问题能适用贪心法高效求解？ （ ）
选项：
A:0-1背包问题
B:最小生成树问题

C:单源最短路径问题

D:哈夫曼编码问题
答案: 【】

第五章 单元测试

1、判断题：
使用回溯法求解0-1背包问题时，计算右子树上界的方法是通过贪心策略求得上界（ ）
选项：
A:对
B:错
答案: 【】

2、判断题：
适用回溯法解旅行售货员问题，只有当搜索到最后一个城市时，才能判断当前路径是否是该问题的一个解。（ ）
选项：
A:对
B:错
答案: 【

3、多选题：
下面关于用回溯法解题说法，正确的是( ).
选项：
A:在搜索过程中动态产生问题的解空间；

B:这种方法适用于解一些组合数相当大的问题。

C:显式地存储整个解空间 ；

D:解空间树有子集树与排列树两种;

答案: 【
】

4、多选题：
回溯法中的剪枝函数包括( )。
选项：
A:限界函数

B:约束函数

C:递归函数

D:随机数生成函数

答案: 【
】

5、多选题：
回溯法解题步骤,正确的是（ ）
选项：
A:确定最优子结构的性质;

B:以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索;

C:针对所给问题，定义问题的解空间;

D:确定易于搜索的解空间结构;

答案: 【
】

6、判断题：
四色定理是第一个主要由计算机证明的理论（ ）
选项：
A:对
B:错
答案: 【】

第六章 单元测试

1、单选题：
在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是( )。
选项：
A:回溯法和分支限界法

B:回溯法
C:回溯法求解子集树问题
D:分支限界法
答案: 【】

2、单选题：
分支限界法与回溯法的相同点是：都是一种在问题的（ ）中搜索问题解的算法。
选项：
A:二叉搜索树T
B:排列树T
C:子集树T
D:解空间树T

答案: 【
】

3、多选题：
优先队列式分支限界法解问题时，活结点表的组织形式可能是（ ）。
选项：
A:最小堆
B:数组

C:栈
D:最大堆
答案: 【】

4、判断题：
具有限界函数的广度优先生成搜索解空间树法称为回溯法。（ ）
选项：
A:对
B:错
答案: 【】

5、判断题：
旅行售货员问题的解空间树是一棵子集树。（ ）
选项：
A:错
B:对
答案: 【】