算法分析作业

1、D 、定义最）。D回溯法D回溯法回溯法D回溯法D回溯法D、算法分析练习题（一）、选择题1、二分搜索算法是利用（A ）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（A ）。A、找出最优解的性质B、构造最优解C、算出最优解优解3下列算法中通常以自底向上的方式求解最优解的是（BA、备忘录法B动态规划法C、贪心法4、衡量一个算法好坏的标准是（ C ）。A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短5、以下不可以使用分治法求解的是（ D ）。A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1 背包问题6. 实现循环赛日程表利用的算法是

2、（A）。A、分治策略B、动态规划法C、贪心法7. 备忘录方法是那种算法的变形。 （ B ）A、分治法 B动态规划法C、贪心法D8最长公共子序列算法利用的算法是（B）。A、分支界限法 B动态规划法C贪心法9实现棋盘覆盖算法利用的算法是（A）。A、分治法B动态规划法C、贪心法10、矩阵连乘问题的算法可由（B）设计实现A、分支界限算法B、动态规划算法C、贪心算法回溯算法11、Strassen 矩阵乘法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法12、使用分治法求解不需要满足的条件是（ A ）。A 子问题必须是一样的B 子问题不能够重复C子问题的解可以合并D原问题和子问题使用

3、相同的方法解 13、下列算法中不能解决0/1背包问题的是（A ）A贪心法B动态规划C回溯法D分支限界法14 实现合并排序利用的算法是（A、分治策略B、动态规划法C、贪心法回溯法15下列是动态规划算法基本要素的是（A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质16.下列算法中通常以自底向下的方式求解最优解的是（A、分治法B、动态规划法C、贪心法回溯法17、合并排序算法是利用（。实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法18 实现大整数的乘法是利用的算法（A、贪心法B、动态规划法C、分治策略回溯法19. 实现最大子段和利用的算法是（A、分治策略B、动态规划法C、贪心法

4、回溯法20. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B）A、重叠子问题B最优子结构性质C贪心选择性质D定义最优解21. 实现最长公共子序列利用的算法是（B）A、分治策略B、动态规划法C、贪心法D回溯法二、填空题1、算法的复杂性有 时间复杂性和 空间复杂性之分。2、 程序是算法用某种程序设计语言的具体实现。3、 算法的“确定性”指的是组成算法的每条指令 是清晰的，无歧义的。4、矩阵连乘问题的算法可由动态规划 设计实现。5、 算法是指解决问题的一种方法或一个过程6从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法 。7、 矩阵连乘问题的算法可由动态规划设计实现。8

5、、动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解 子问题，然后从这些 子问题的解得到原问题的解。9、算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。10、 大整数乘积算法是用分治法来设计的。11、快速排序算法是基于 分治策略 的一种排序算法。12、动态规划算法的两个基本要素是. 性质和性质。13、任何可用计算机求解的问题所需的时间都与其规模 有关。14、快速排序算法的性能取决于划分的对称性 o15、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致 相同。16、使用二分搜索算法在n个有序元素表中搜索一个特定元

6、素，在最佳情况下，搜索的时间复杂性为0(),在最坏情况下，搜索的时间复杂性为0( logn )o17、已知一个分治算法耗费的计算时间 T(n)，T(n)满足如下递归方程：0( 1)n c 2T(n)二笛(n/2)+0(n) n Z 2解得此递归方可得T(n)= 0 (nlogn)。18、 动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过 的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。19、递归的二分查找算法在divide阶段所花的时间是 0(1)，conquer阶段所花的时间是T( n/2)，

7、算法的时间复杂度是0( log n)。20、 用动态规划算法计算矩阵连乘问题的最优值所花的时间是0(n3)，子问题空间大小是 0(n2)。21、一个算法的优劣可以用(时间复杂度)与(空间复杂度)与来衡量。22、 直接或间接地调用自身的算法称为(递归算法)。23、记号在算法复杂性的表示法中表示(渐进确界或紧致界)。24、在分治法中，使子问题规模大致相等的做法是出自一种(平衡子问题)的思 想。25、动态规划算法适用于解(具有某种最优性质)问题26、最优子结构性质的含义是（问题的最优解包含其子问题的最优解） 。27、 按照符号 0 的定义 O（f）+O（g）等于 O（maxf（n）,g（n）。28、

8、二分搜索技术是运用（分治）策略的典型例子。29、动态规划算法中，通常不同子问题的个数随问题规模呈（多项式）级增长。30、（最优子结构性质）和（子问题重叠性质）是采用动态规划算法的两个基本 要素。三、算法填空1. 最大子段和：动态规划算法int MaxSum(int n, int a|)int sum=0, b=0 ；/sum 存储当前最大的 bj, b 存储 bjfor(int j=1 ； j0)b+=ai:else b=ai ;/ 一旦某个区段和为负，则从下一个位置累和if (bsum) sum=b:return sum ；2快速排序templatevclass Typevoid Quick

9、Sort (Type a, int p, int r)if (pr) int q=Partition(a,p,r);Quicksort( a. p，q-1); 对左半段排序QuickSort(a.q+1.r); / 对右半段排序四、简答题1、写出下列复杂性函数的偏序关系(即按照渐进阶从低到高排序)：2n3nlog n n! n log n n2 nn 103参石解答皐 ioYY2 Y3 Y”！ Y于2、将所给定序列a1:n分为长度相等的两段a1:n/2和an/2+1:n，分别求 出这两段的最大子段和，则 a1:n 的最大子段和有哪三种情形？3、请说明动态规划方法为什么需要最优子结构性质。 最优

10、子结构性质是指大问题的最优解包含子问题的最优解。 动态规划方法是自 底向上计算各个子问题的最优解， 即先计算子问题的最优解， 然后再利用子问题 的最优解构造大问题的最优解，因此需要最优子结构4、设计动态规划算法的主要步骤是怎么的？请简述。参考 解答：（1）找出最优解 的性质， 并刻划 其结构特 征。（6 分 ）（ 2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。5、分治法所能解决的问题一般具有哪几个特征？请简述。参考解答： （ 1）该问题的规模缩小到一定的程度就可以容易地解决；（6分 ）（ 2）该问题可以分解为若干个规模较小的相同问题，即

11、该问题具有最优子结构性质 ;（ 3） 利用该问题分解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独立的，即子问 题之间不包 含公共的子问题。6、算法的要特性是什么？ 参考解答：确定性、可实现性、输入、输出、有穷性7、算法分析的目的是什么？参考解答： 分析算法占用计算机资源的情况， 对算法做出比较和评价， 设计出额 更好的算法。8、算法的时间复杂性与问题的什么因素相关？ 参考解答：算法的时间复杂性与问题的规模相关，是问题大小 n 的函数。9、算法的渐进时间复杂性的含义？参考解答：当问题的规模 n 趋向无穷大时，影响算法效率的重要因素是 T（n） 的数量级，而其他因素

12、仅是使时间复杂度相差常数倍，因此可以用 T（n） 的数量 级（阶）评价算法。时间复杂度T（n）的数量级（阶）称为渐进时间复杂性。 10 简述渐进时间复杂性上界的定义。参考解答： T（n） 是某算法的时间复杂性函数， f（n） 是一简单函数，存在正整数No和 C, nNo,有 T(n)vf(n)，这种关系记作 T(n)=O(f(n)11快速排序算法最坏情况下需要多少次比较运算？参考解答：最坏情况下快速排序退化成冒泡排序，需要比较n2次。12阐述归并排序的分治思路。参考解答：讲数组一分为二，分别对每个集合单独排序，然后将已排序的两 个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，

13、 则继续分治，直到一个元素。13快速排序的基本思想是什么。参考解答：快速排序的基本思想是在待排序的 N个记录中任意取一个记录， 把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该 记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录 排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直 到每一部分内只有一个记录为止。14分治法的基本思想是什么？将一个规模为 N的问题分解为 K个规模较小的子问题，这些子问题相互独立且与原问题性 质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。15设计动态规划算法的主要步骤？

14、参考解答：（1）找出最优解的性质，并刻划其结构特征。（6 分）（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。16分治法与动态规划法的异同共同点：将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。不同点：1、 适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的； 而分治法中子问题 相互独立。2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，

15、 故产生指数增长的时间复杂度，效率较低。17分治法所能解决的问题一般具有的几个特征？参考解答：（1）该问题的规模缩小到一定的程度就可以容易地解决；（6分）（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最 优子结构性质；(3)禾U用该问题分解出的子问题的解可以合并为该问题的解；(4)原问题所分解出的各个子问题是相互独立的，即子问 题之间不包 含公共的子问题。五、算法设计题1. 【最长上升子序列问题】一一提示：此题可采用动态规划算法实现对于给定的一个序列(ai,a2,|(,aN)，仁N乞1000。我们可以得到一些递增上升的子序列(ai1,ai2jl|,aiK)，这里1乞h : i?：

16、丨1(: “乞N。比如，对于序列(1, 7,3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8) 等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8)。你的任务：就是对于给定的 序列，求出最长上升子序列的长度。要求写出你设计的算法思想及递推函数的公 式表达。.券考解答：设/晁示：从左向右担描过龟克到以巩可元素结尾的序列，获得的 長益上升子序列的长度*且干序列也含a)=+ 当应四 a 叫畀;1 吒 j11 r 1； Vj(l= J即,/(0是从/，7(2)到f(i-l)中找最尢的个值,再加1.或者就 是I主要是看iii这金元素能否加入到之胡已鮭

17、?划寻的聂长上升子序列”如果能如 入*是之前已获得的最长上升子序刊艮度打一：如果不能加入，就取这最后一个元素 作为一令单独子序列，悅度为仁養.疳所要求的整牛序列的最长公共子序列长:度为max (f (i): 1=il时，格雷码的长厘为才，即共有旷个码序列。此时，瞬问題一分为二，即上半部分和下半部分上半部分最高位设为0.下半部分竟高位设为U剰下且-1位 的辂雷码的掏造采用递归的思路匸3. 现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程 表：（1）每个选手必须与其他选手各赛一次；（2）每个选手一天只能赛一次；（3）循环赛一共进行n - 1天。请利用分治法的思想，给这8位运动员设

18、计一个合理的比赛日程。123421433412432156786587785r 68765567865817856876512342143r 341243214. 对于矩阵连乘所需最少数乘次数问题，其递归关系式为:f0i = jmi,j mkinmi,k mk 1,j pyPkPj i ： j i空:j其中mi , j为计算矩阵连乘AiAj所需的最少数乘次数，p“为矩阵Ai的行,p为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为：AA2AA50x10104040x3030x5P 0汉 P 1P 1 汇 P 2P 2 汉 P 3P 3代 P 4请根据以上的递归关系，计算出矩阵连乘积A AAA所

19、需要的最少数乘次数。r创 11十凰24+ 毘吗刊=0 + 8000十56 10- 5 =10500西14 = min J 曲12 +阳34+ 20000 + 6000 + 50 - 40. 5 = 36000.创 13 +国4 + A A A = 27000 + 0 + 50 30* 5 = 34500= 105005. 有这样一类特殊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背包问题，应如何选择放进去的物品，才

20、能使到放进背包的 物品总价值最大，能获得的最大总价值多少？參考辭客；因为该01背包问题比较特球.恰好重董越軽的畅品价位赵离*所以优 先取重量轻的物品放进背赳口最终可以把重量分别为2. 3* 4. 5的三个物品就进背包， 得到的价值和为15 # 8 # 6斗4二33,为最大值亠6. 归并排序算法对下列实例排序，写出算法执行过程。A=(48,12,61,3,5,19,32,7)48a 12, 61,348, 1261,312, 483,613, 12, 4& 615, 19, 32,75, 1032, 75, 197,325, 7, 323,3, 1,12, 19 32, 48,617. 规则证明

21、：O(f(n)+O(g(n) = O(maxf(n),g(n)*对于任意離n) = 0(劇,存在正常数q和自然数力 使得对所有尬nv 有S)MG/(n)。类似地，对于任意a(n) = O(g(n),存在正常数和自然数4 使得对 所有eg 有S)兰* 令c=maxq, qb n3 =1113x(,逼，ft(n)= m日刈/tn),g(n)则对所有的nnr有巒m +側罚二內(4Q十9() q2 max/(n) ,g(n)=2c3h(n)-O(maxnJs(/j) 8. 给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元 素x,返回其在数组中的位置，如果未找到返回-1。写出二分

22、搜索的算法，并分析其时间复杂度。L. I snip ltileinL Birun ySearch (Type 怪. const Typci. x, ini n)在X, iJx时返回其在数组巾的fi!遣，否则雄回-1Ini Left=V； ini riffht=n-l;While lBft=right) int middle-(lefi+righcJ/S;il (x=amiddle) return middle； if (x)amid.dle_) left-niiddlBl: else righL-iuiddle-1;Re turn -1; 时间直杂性为0(1 ogn)9. 利用分治算法写出合并

23、排序的算法，并分析其时间复杂度L void MergeSortfType aT int left, int right)讦(kftcright) 少冇2个元素int i=(lcft+nght)/2;取中点 mcrgeSrt(u7 Icfr, i); mcrgeSort(at i+l, right);meige(a, b, left, i, right); /洽并到数组 b copy(斗 b, kftT right)；夂制A数纟H a算法在最坏悄况下的时间ft杂度为O(nlogn) rA Ji aai ir办公室卫生管理制度一、主要内容与适用范围1 本制度规定了办公室卫生管理的工作内容和要求及检查与考核。2 此管理制度适用于本公司所有办公室卫生的管理二、定义 1 公共区域：包括办公室走道、会议室、卫生间，每天由行政文员进行清扫；2个人区域：包括个人办公桌及办公区域由各部门工作人员每天自行清扫。1. 公共区域环境卫生应做到以下几点：1) 保持公共区域及个人区域地面干净清洁、无污物、污水