第三章单元测试
- 设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，若xm=yn则（ ）。
- 当(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10)=(-1, 5, -2, 1, -7, -4, 2, 3, -1, 2)时，最大子段和为( ).
- 设有四个矩阵A,B,C,D,它们的维数分别是A=50*10, B=10*40, C=40*30, D=30*50,，则计算其乘积至少需要（ ）次乘法
- 下面关于动态规划解题的步骤内容描述正确的是哪些？（ ）
- 问题用动态规划算法求解效率较高的原因？( )
- 对0-1背包问题，n=5，c=12，w={3,7,5,4，4}，v={6,3, 5,4，6 }，则其最优解为（ ）
- 一般来说解同一个问题，动态规划法的效率高于分治算法（ ）
- 图象的变位压缩存储采用数据头和数据存储的编码式存储方式，节省存储空间，实现压缩。（ ）
A:zk≠xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。
B:zk≠xm=yn，且zk是Xm-1和Yn-1的最长公共子序列。
C:zk=xm=yn，且zk是Xm-1和Yn-1的最长公共子序列。
D:zk=xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。
答案:zk=xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。
A:10 B:6 C:9
D:7
A:87500
B:10500, C:16000, D:36000,
A:建立递归关系：建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到。
B:构造最优解：根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造。
C:计算最优值：以自顶往下的方法计算问题的最优值，也就是先求解规模较大的问题的最优值。
D:分析最优解的结构：将一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质。
A:贪心选择性质 B:最优子结构性质 C:子问题重叠性质 D:递归性质.
A:（0，1，0，1，1） B:（1，0，1，0，1）
C:（1，1，1，1，1）
D:（0，1，1，1，1）
A:错 B:对
A:错 B:对
温馨提示支付 ￥3.00 元后可查看付费内容,请先翻页预览!
