算法分析作业

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

2、法是（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、使用分治法求解不需要

3、满足的条件是（ 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、合并排序算法是利用

4、（ 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、

5、程序是 算法 用某种程序设计语言的具体实现。3、算法的 “确定性 ”指的是组成算法的每条 指令 是清晰的，无歧义的。4.矩阵连乘问题的算法可由 动态规划 设计实现。 5、算法是指 解决问题的 一种方法 或 一个过程 。6、从分治法的一般设计模式可以看出，用它设计 出的程序一般是 递归算法 。 7、矩阵连乘问题的 算法可由 动态规划 设计实现。 8. 动态规划算法 的基本思想是将待求解问题分解成若干 子问题 ， 先求解 子问题 ，然后从这些 子问题 的解得 到原问题的 解。 9.算法是由若干条指令组成的有穷 序列，且要满足输入、 输出 、 确定性和 有 限性 四条性质。 10、大整数乘积算法是用

6、 分治 法 来设计的。 11.快速排序算法是基于 分治策略的一种排序算法。12.动态规划算法的两个基本要素 是. 性质和 性质。13.任何可用计算机求解的 问题所需的时间都与其规模 有关。14.快速排序算法的性能取决于 划分的对称性。15、出自于平 衡子问题”的思想，通常分治法在分割原问题，形成 若干子问题时，这些子问题的规模都大致相同 16、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为0()，在最坏情况下，搜索的时间复杂性为0 (logn )。17、已知一个分治算法耗费的计算时间T(n)， T(n)满足如下递归方程：n 20(1) T(n) 2T(n/

7、2) O(n)n 2解得此递归方可得T(n)= 0( nlogn )。18、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法自底向上”的填充方向，而是 自顶向下”的递归方向， 为每个解过的子问题建立了备忘录以备需要时查看， 同样也可避免相同子问题的重复求解。递归的二分查找算法在divide阶段所花的时间是0(1)，conquer阶段19、所花的时间是T(n/2)，算法的时间复杂度是 0( log n)。20、用动态规划算法计算矩阵连乘问题的最优值所花的时间是O(n3)，子问题空间大小是0(n2)。 21、一个算法的优劣可以用（时间复杂度）与（空间复杂度）与来衡 量。22、直接或

8、间接地调用自身的算法称为（递归 算法）。23、记号在算法复杂性的表示法中表示（渐进确界或紧致界）。24、在分治法中，使子问题 规模大致相等的做法是出自一种（平衡子问题）的 思想。25、动态规划算法适用于解（具有某种最优 性质）问题。26、最优子结构性质的含义是（问题的最优解包含其子问题的最优解）。27、按照符号0的定义O（f）+O（g等于O（maxf（n）,g（n） 28、二分搜索技术是运用（分治）策略的典型例子。29、动态规划算法中，通常不同子问题的个数随问题规模呈（多项式）级增长。30、（最优子结构性质）和（子问题重叠性质）是采用动态规划算法的两个基本要素。三、算法填空1最大子段和：动态规

9、划算法 int MaxSum（int n, int a） int sum=0, b=0 /sum 存储当前最大的 bj, b 存储 bj for（int j=1； jv=n； j+） if（b0）b+=aj；else b=ai ；/ 一旦某个区段和为负，则从下一个位置累和if （bsum）sum=b ； return sum 2快 速排序 templatevclass Typevoid Quicksort （Type a, int p, int r） if （p No,有T(n)vf(n)这种关 系记作 T(n)=O(f(n)。11 快速排序算法最坏情况下需要多少次比较运算？ 参考解答： 最坏

10、情况下快速排序退化成冒泡排序，需要比较 n2 次。 12 阐 述归并排序的分治思路。 参考解答：讲数组一分为二，分别对 每个集合单独排序，然后将已排序的两个序列归并成一个含 n 个元素的分好类的序列。如果分割后子问题还很大，则继续分 治，直到一个元素。 13 快速排序的基本思想是什么。 参考 解答：快速排序的基本思想是在待排序的 N 个记录中任意取一 个记录，把该记录放在最终位置后，数据序列被此记录分成两 部分。所有关键字比该记录关键字小的放在前一部分，所有比 它大的放置在后一部分，并把该记录排在这两部分的中间，这 个过程称作一次快速排序。之后重复上述过程，直到每一部分 内只有一个记录为止。

11、14 分治法的基本思想是什么？ 将一个 规模为 N 的问题分解为 K 个规模较小的子问题，这些子问题相 互独立且与原问题性 质相同。求出子问题的解，就可得到原问 题的解。即一种分目标完成程序算法，简单问题可 用二分法 完成。15 设计动态规划算法的主要步骤？ 参考解答：(1)找出 最优解的性质，并刻划其结构特征。 (6 分 )( 2)递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。16分治法与动态规划法的异同 共同点：将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的 解。 不同点：1、适合于用动态规划法 求解的

12、问题，分解得到的各子问题往往不是 相互独立的；而分治法中子问题 相互独立。2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。17分治法所能解决的问题一般具有的几个特征？参考解答：（1）该问题的规模缩小到一定的程度就可以容易地解决；（6分）（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分 解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独

13、立的，即子问题 之间不包 含公共的子问题。五、算法设计题1.【最长上升子序列问题】一一提示：此题可采用动态规划算 法实现对于给定的一个序列，。我们可以得到一些递增 （a,a, ,a）l N 100012N上升的子序列，这里。比如， 对于序列（1,9, 4, 8)，有它的一些上升子序列，如 (1, 7), (3, 4, 8)等等。 这些子序列中最长的长度是 4，比如子序列 (1, 3, 5, 8)。 你的任务：就是对于给定的序列，求出最长上升子序列 的长度。要求写出你设计的算法思想及递推函数的公式 表达。 .2.【 Gray 码构造问题】 提示：此题可采用分治 递归算法实现 n 问题描述： “格

14、雷码 ”是一个长度为的 序列，满足：2 (a)每个元素都是长度为 n比特的 串(b)序列中无相同元素(c)连续的两个元素恰好只有 1 个比特不同 例如： n=2 时，格雷码为 00， 01， 11， 10。 Gray 码是一种编码，这种编码可以避 免在读取时，因各数据位时序上的差异造成的误读。 格雷码在工程上有广泛应用。但格雷码不便于运算， 请你设计一种构造方法，输入长度序列n，输出格雷码(你只要做出一种构造方案即可，格雷码并不唯 一)。3.现在有 8 位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程表： ( 1) 每个 选手必须与其他选手各赛一次；( 2) 每个选手一天只能赛一次；

15、(3)循环赛一共进行n -1天。请利 用分治法的思想，给这 8 位运动员设计一个合理的比 赛日程。4.对于矩阵连乘所需最少数乘次数问题，其递归关系式为：Oi jmi,jminmi,k帥 1，j PPPH j i 调 i k j 其中 mi, j为计算矩阵连乘Ai,Aj所需的最少数乘次数，p为矩阵Ai的行，i-1为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为：P AA A A12弭 504040 3叫0 5p pp pp p p p01 1223 强请根据以上的递归关系，计算出矩阵连乘积 AAAA所需要的最少数乘次数。 1234 5.有这样一类特殊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背包问