算法设计与分析答案2023

第三章测试

1.设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，若xm=yn则（ ）。
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的最长公共子序列。

答案:A
2.当(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10)=(-1, 5, -2, 1, -7, -4, 2, 3, -1, 2)时，最大子段和为( ).
A:7 B:9
C:10 D:6 3.设有四个矩阵A,B,C,D,它们的维数分别是A=50*10, B=10*40, C=40*30, D=30*50,，则计算其乘积至少需要（ ）次乘法
A:10500, B:87500
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，1，1，1，1）
B:（0，1，1，1，1） C:（1，0，1，0，1）
D:（0，1，0，1，1） 7.一般来说解同一个问题，动态规划法的效率高于分治算法（ ）
A:对 B:错 8.图象的变位压缩存储采用数据头和数据存储的编码式存储方式，节省存储空间，实现压缩。（ ）
A:对 B:错