算法设计分析 ( 第1次 )

第一项任务一、多项选择题(这个主要问题60分，20个项目，每个项目3分)1.设m I，j为计算矩阵链所需的最小乘法数.j，则矩阵链A1所需的最小乘法数n.n是()。A.m0，nB.m1，n-1C.m1，n 1D.m1，n2.二进制搜索算法基于()设计。A.分配定律B.动态规划方法C.贪婪法则D.穷举定律3.直接或间接调用自己的算法称为()。A.贪婪算法B.递归算法C.迭代算法D.动态规划算法4.算法分析的两个主要方面是()。A.空间复杂性和时间复杂性B.正确性和简单性C.可读性和文档5.以下关于最优子结构的陈述是不正确的()。原问题的最优解包括子问题的最优解原问题的最优解是基于子问题的最优解原问题的最优解取决于子问题的最优解通过合并子问题的非最优解，得到原问题的最优解6.当n越来越大时，在下列函数中，最快的增长率应该是()A.y=100nB.y=log100nC.y=D.y=7.用于实现合并排序的算法是()。A.分治策略B.动态规划方法C.贪婪法则D.追溯方法8.算法的时间复杂度是指()A.执行算法程序所需的时间B.算法程序的长度C.执行算法所需的基本操作数D.算法程序中的指令数9.在活动安排的问题中，下列关于活动A和B的描述中哪一个是相容的()？A.活动a在活动b开始之前开始B.活动a在活动b结束之前开始C.活动a在活动b开始之前结束D.活动a在活动b开始后开始10.衡量算法质量的标准是()。A.快速运行速度B.小足迹C.低时间复杂度D.短码11.在最长公共子序列问题中，如果具有ci，j的最长公共子序列的长度定义为X1.I和Y1.定义了长度为m的X序列和长度为n的Y序列的最长公共子序列的长度为()。A.c0，0B.c1，1C.c1，mD.cm，n12.下面关于贪婪算法，不正确的说法是()。A.用于解决优化问题在当前视图中总是选择最好的选项。C.期望通过局部最优达到全局最优。要解决的问题可能不满足最优子结构特性13.将一个由P行和Q列组成的矩形乘以一个由Q行和R列组成的矩形需要多少次？()A.p x rB.q2C.p x q x rD.q314.在最佳二叉搜索树问题中，考虑如下的BST:如果要搜索k3，总共需要进行多少次比较()。A.1B.两次C.三次D.4次15.JAVA程序主要有以下两种类型()A.应用程序和APPLET应用程序和理论程序B.系统程序和应用C.系统和理论程序D.d .系统程序和APPLET应用16.如赫奇曼树所示，字符S的编码是()。A.1010B.1110C.1111D.01017.动态规划要解决的问题必须满足最优子结构和()性质。A.没有后遗症B.无效性C.重叠的子问题D.递归18.对于N个元素的排序问题。当n=2时，只要进行()比较，就可以排列顺序A.3B.2C.1D.419.二进制搜索算法的基本思想是将N个元素分成两个数目大致相同的部分，然后将n/2与X: if()进行比较，然后只在数组a的左半部分继续搜索XA.xan/2B.x=n/2C.xan/2D.x=n/220.memo方法的递归方法是()A.自上而下B.从右到左C.上上下下D.从下到上2.对错(这个主题40分，20个项目，每个项目2分)1.赫奇曼编码的目的是用更少的比特流表达更多的信息。()2.两个序列中最长的公共子序列可以帮助评估两个序列的相似性。()3.算法是一组糟糕的规则。()4.扩大问题规模的有效方法是增加算法的计算复杂度。()5.合并排序算法是渐近最优的吗？()6.快速排序是一种基于贪婪策略的算法()。7.在最坏的情况下，二进制搜索方法使用O(log n)时间来完成搜索任务。()8.快速排序方法基于分治策略。()9.基于三数除法的快速排序的最差时间复杂度优于基本快速排序()10.递归算法在解决问题时通常非常简洁，而且效率很高？()11.最坏情况下的时间复杂度与平均时间复杂度相同。()12.计算机只能运行在有限步骤内终止的算法。()