算法分析作业_第1页
算法分析作业_第2页
算法分析作业_第3页
算法分析作业_第4页
算法分析作业_第5页
已阅读5页,还剩5页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

算法分析作业算法分析作业算法分析作业xxx公司算法分析作业文件编号:文件日期:修订次数:第1.0次更改批准审核制定方案设计,管理制度算法分析练习题(一)一、选择题1、二分搜索算法是利用(

A

)实现的算法。A、分治策略

B、动态规划法

C、贪心法

D、回溯法2、下列不是动态规划算法基本步骤的是(

A

)。A、找出最优解的性质

B、构造最优解

C、算出最优解

D、定义最优解3.下列算法中通常以自底向上的方式求解最优解的是(

B

)。A、备忘录法 B、动态规划法 C、贪心法 D、回溯法4、衡量一个算法好坏的标准是(C)。

A运行速度快B占用空间少C时间复杂度低D代码短

5、以下不可以使用分治法求解的是(D)。

A棋盘覆盖问题B选择问题C归并排序D0/1背包问题

6.实现循环赛日程表利用的算法是(

A

)。A、分治策略 B、动态规划法 C、贪心法 D、回溯法7.备忘录方法是那种算法的变形。(B)A、分治法 B、动态规划法 C、贪心法 D、回溯法8.最长公共子序列算法利用的算法是(

B

)。A、分支界限法 B、动态规划法 C、贪心法 D、回溯法9.实现棋盘覆盖算法利用的算法是(

A

)。A、分治法 B、动态规划法 C、贪心法 D、回溯法10.矩阵连乘问题的算法可由(

B)设计实现。A、分支界限算法

B、动态规划算法

C、贪心算法

D、回溯算法11、Strassen矩阵乘法是利用(

A

)实现的算法。A、分治策略

B、动态规划法

C、贪心法

D、回溯法12、使用分治法求解不需要满足的条件是(A)。

A子问题必须是一样的

B子问题不能够重复

C子问题的解可以合并

D原问题和子问题使用相同的方法解

13、下列算法中不能解决0/1背包问题的是(A)

A贪心法B动态规划C回溯法D分支限界法

14.实现合并排序利用的算法是(

A

)。A、分治策略 B、动态规划法 C、贪心法 D、回溯法15.下列是动态规划算法基本要素的是(

D

)。A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质16.下列算法中通常以自底向下的方式求解最优解的是(

B

)。A、分治法 B、动态规划法 C、贪心法 D、回溯法17、合并排序算法是利用(

A

)实现的算法。A、分治策略

B、动态规划法

C、贪心法

D、回溯法18.实现大整数的乘法是利用的算法(

C

)。A、贪心法 B、动态规划法 C、分治策略 D、回溯法19.实现最大子段和利用的算法是(

B

)。A、分治策略 B、动态规划法 C、贪心法 D、回溯法20.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的(

B

)。A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解21.实现最长公共子序列利用的算法是(

B

)。A、分治策略 B、动态规划法 C、贪心法 D、回溯法二、填空题1.算法的复杂性有时间复杂性和空间复杂性之分。2、程序是

算法

用某种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条指令是清晰的,无歧义的。4.矩阵连乘问题的算法可由动态规划设计实现。5、算法是指解决问题的一种方法或一个过程。6、从分治法的一般设计模式可以看出,用它设计出的程序一般是递归算法。7、矩阵连乘问题的算法可由动态规划设计实现。8.动态规划算法的基本思想是将待求解问题分解成若干子问题,先求解子问题,然后从这些子问题的解得到原问题的解。9.算法是由若干条指令组成的有穷序列,且要满足输入、输出、确定性和有限性四条性质。10、大整数乘积算法是用分治法来设计的。11.快速排序算法是基于分治策略的一种排序算法。12.动态规划算法的两个基本要素是.性质和性质。13.任何可用计算机求解的问题所需的时间都与其规模有关。14.快速排序算法的性能取决于划分的对称性。15、出自于“平衡子问题”的思想,通常分治法在分割原问题,形成若干子问题时,这些子问题的规模都大致相同。16、使用二分搜索算法在n个有序元素表中搜索一个特定元素,在最佳情况下,搜索的时间复杂性为O(),在最坏情况下,搜索的时间复杂性为O(logn)。17、已知一个分治算法耗费的计算时间T(n),T(n)满足如下递归方程:解得此递归方可得T(n)=O(

nlogn)。18、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向,而是“自顶向下”的递归方向,为每个解过的子问题建立了备忘录以备需要时查看,同样也可避免相同子问题的重复求解。19、递归的二分查找算法在divide阶段所花的时间是O(1),conquer阶段所花的时间是

T(n/2)

,算法的时间复杂度是O(

log

n)。20、用动态规划算法计算矩阵连乘问题的最优值所花的时间是O(n3),子问题空间大小是

O(n2)

。21、一个算法的优劣可以用(时间复杂度)与(空间复杂度)与来衡量。22、直接或间接地调用自身的算法称为(递归算法)。23、记号在算法复杂性的表示法中表示(渐进确界或紧致界)。24、在分治法中,使子问题规模大致相等的做法是出自一种(平衡子问题)的思想。25、动态规划算法适用于解(具有某种最优性质)问题。26、最优子结构性质的含义是(问题的最优解包含其子问题的最优解)。27、按照符号O的定义O(f)+O(g)等于O(max{f(n),g(n)})。28、二分搜索技术是运用(分治)策略的典型例子。29、动态规划算法中,通常不同子问题的个数随问题规模呈(多项式)级增长。30、(最优子结构性质)和(子问题重叠性质)是采用动态规划算法的两个基本要素。三、算法填空1.最大子段和:动态规划算法intMaxSum(intn,inta[]){intsum=0,b=0;速排序template<classType>voidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);最长上升子序列问题】——提示:此题可采用动态规划算法实现对于给定的一个序列,。我们可以得到一些递增上升的子序列,这里。比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等等。这些子序列中最长的长度是4,比如子序列(1,3,5,8)。你的任务:就是对于给定的序列,求出最长上升子序列的长度。要求写出你设计的算法思想及递推函数的公式表达。.2.【Gray码构造问题】——提示:此题可采用分治递归算法实现问题描述:“格雷码”是一个长度为的序列,满足:(a)每个元素都是长度为n比特的串(b)序列中无相同元素(c)连续的两个元素恰好只有1个比特不同例如:n=2时,格雷码为{00,01,11,10}。Gray码是一种编码,这种编码可以避免在读取时,因各数据位时序上的差异造成的误读。格雷码在工程上有广泛应用。但格雷码不便于运算,请你设计一种构造方法,输入长度序列n,输出格雷码(你只要做出一种构造方案即可,格雷码并不唯一)。3.现在有8位运动员要进行网球循环赛,要设计一个满足以下要求的比赛日程表:每个选手必须与其他选手各赛一次;每个选手一天只能赛一次;循环赛一共进行n–1天。请利用分治法的思想,给这8位运动员设计一个合理的比赛日程。4.对于矩阵连乘所需最少数乘次数问题,其递归关系式为:其中m[i,j]为计算矩阵连乘Ai…Aj所需的最少数乘次数,pi-1为矩阵Ai的行,为矩阵Ai的列。现有四个矩阵,其中各矩阵维数分别为:A1A2A3A4501010404030305p0p1p1p2p2p3p3p4请根据以上的递归关系,计算出矩阵连乘积A1A25.有这样一类特殊0-1背包问题:可选物品重量越轻的物品价值越高。n=6,c=20,P=(4,8,15,1,6,3),W=(5,3,2,10,4,8)。其中n为物品个数,c为背包载重量,P表示物品的价值,W表示物品的重量。请问对于此0-1背包问题,应如何选择放进去的物品,才能使到放进背包的物品总价值最大,能获得的最大总价值多少6.归

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论