算法分析作业

算法分析练习题 一 算法分析练习题 一 一 选择题一 选择题 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 归并排序 D 0 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 原问题和子问题使用相同的方法解 2 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 从分治法的一般设计模式可以看出 用它设计出的程序一般是 递归算法 3 7 矩阵连乘问题的算法可由 动态规划 设计实现 8 动态规划算法的基本思想是将待求解问题分解成若干 子问题 先求解 子问题 然后从这些 子问题 的解得到原问题的 解 9 算法是由若干条指令组成的有穷序列 且要满足输入 输出 确定性和 有限性 四条性质 10 大整数乘积算法是用 分治法 来设计的 11 快速排序算法是基于 分治策略 的一种排序算法 12 动态规划算法的两个基本要素是 性质和 性质 13 任何可用计算机求解的问题所需的时间都与其 规模 有关 14 快速排序算法的性能取决于 划分的对称性 15 出自于 平衡子问题 的思想 通常分治法在分割原问题 形成若干子问 题时 这些子问题的规模都大致 相同 16 使用二分搜索算法在 n 个有序元素表中搜索一个特定元素 在最佳情况下 搜索的时间复杂性为 O 在最坏情况下 搜索的时间复杂性为 O logn 17 已知一个分治算法耗费的计算时间 T n T n 满足如下递归方程 222 21 nnOnT nO nT 解得此递归方可得 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 动态规划算法适用于解 具有某种最优性质 问题 4 26 最优子结构性质的含义是 问题的最优解包含其子问题的最优解 27 按照符号 O 的定义 O f O g 等于 O max f n g n 28 二分搜索技术是运用 分治 策略的典型例子 29 动态规划算法中 通常不同子问题的个数随问题规模呈 多项式 级增长 30 最优子结构性质 和 子问题重叠性质 是采用动态规划算法的两个基本 要素 三 算法填空三 算法填空 1 最大子段和 动态规划算法 int MaxSum int n int a int sum 0 b 0 sum 存储当前最大的存储当前最大的 b j b 存储存储 b j for int j 1 j0 b a j else b a i 一旦某个区段和为负 则从下一个位置累和一旦某个区段和为负 则从下一个位置累和 if b sum sum b return sum 2 快速排序 template void QuickSort Type a int p int r if p r int q Partition a p r QuickSort a p q 1 对左半段排序对左半段排序 QuickSort a q 1 r 对右半段排序对右半段排序 四 简答题四 简答题 1 写出下列复杂性函数的偏序关系 即按照渐进阶从低到高排序 23 23log log10 nnn nnnnnn 5 2 将所给定序列 a 1 n 分为长度相等的两段 a 1 n 2 和 a n 2 1 n 分别求 出这两段的最大子段和 则 a 1 n 的最大子段和有哪三种情形 3 3 请说明动态规划方法为什么需要最优子结构性质 请说明动态规划方法为什么需要最优子结构性质 最优子结构性质是指大问题的最优解包含子问题的最优解 动态规划方法是自 底向上计算各个子问题的最优解 即先计算子问题的最优解 然后再利用子问 题的最优解构造大问题的最优解 因此需要最优子结构 4 设计动态规划算法的主要步骤是怎么的 请简述 设计动态规划算法的主要步骤是怎么的 请简述 参考解答 1 找出最优解的性质 并刻划其结构特征 6 分 2 递归地定义最优值 3 以自底向上的方式计算出最优值 4 根据计算最优值时得到的信息 构造最优解 5 5 分治法所能解决的问题一般具有哪几个特征 请简述 分治法所能解决的问题一般具有哪几个特征 请简述 参考解答 1 该问题的规模缩小到一定的程度就可以容易地解决 6 分 2 该问题可以分解为若干个规模较小的相同问题 即该问题具有 最 优子结构性质 3 利用该问题分解出的子问题的解可以合并为该问题的解 4 原问题所分解出的各个子问题是相互独立的 即子问题之间不 包 含公共的子问题 6 6 算法的要特性是什么 算法的要特性是什么 参考解答 确定性 可实现性 输入 输出 有穷性 7 7 算法分析的目的是什么 算法分析的目的是什么 参考解答 分析算法占用计算机资源的情况 对算法做出比较和评价 设计出 额更好的算法 8 8 算法的时间复杂性与问题的什么因素相关 算法的时间复杂性与问题的什么因素相关 参考解答 算法的时间复杂性与问题的规模相关 是问题大小 n 的函数 9 9 算法的渐进时间复杂性的含义 算法的渐进时间复杂性的含义 参考解答 当问题的规模 n 趋向无穷大时 影响算法效率的重要因素是 T n 的数量级 而其他因素仅是使时间复杂度相差常数倍 因此可以用 T n 的数量 级 阶 评价算法 时间复杂度 T n 的数量级 阶 称为渐进时间复杂性 1010 简述渐进时间复杂性上界的定义 简述渐进时间复杂性上界的定义 参考解答 T n 是某算法的时间复杂性函数 f n 是一简单函数 存在正整数 6 No 和 C n No 有 T n f n 这种关系记作 T n O f n 1111 快速排序算法最坏情况下需要多少次比较运算 快速排序算法最坏情况下需要多少次比较运算 参考解答 最坏情况下快速排序退化成冒泡排序 需要比较 n2 次 1212 阐述归并排序的分治思路 阐述归并排序的分治思路 参考解答 讲数组一分为二 分别对每个集合单独排序 然后将已排序的两 个序列归并成一个含 n 个元素的分好类的序列 如果分割后子问题还很大 则继续分治 直到一个元素 1313 快速排序的基本思想是什么 快速排序的基本思想是什么 参考解答 快速排序的基本思想是在待排序的 N 个记录中任意取一个记录 把该记录放在最终位置后 数据序列被此记录分成两部分 所有关键字比该 记录关键字小的放在前一部分 所有比它大的放置在后一部分 并把该记录 排在这两部分的中间 这个过程称作一次快速排序 之后重复上述过程 直 到每一部分内只有一个记录为止 1414 分治法的基本思想是什么 分治法的基本思想是什么 将一个规模为 N 的问题分解为 K 个规模较小的子问题 这些子问题相互独立且与原问题性 质相同 求出子问题的解 就可得到原问题的解 即一种分目标完成程序算法 简单问题 可用二分法完成 1515 设计动态规划算法的主要步骤 设计动态规划算法的主要步骤 参考解答 1 找出最优解的性质 并刻划其结构特征 6 分 2 递归地定义最优值 3 以自底向上的方式计算出最优值 4 根据计算最优值时得到的信息 构造最优解 1616 分治法与动态规划法的异同分治法与动态规划法的异同 共同点 将待求解的问题分解成若干子问题 先求解子问题 然后再从这些子问题的解得到原问题 的解 不同点 1 适合于用动态规划法求解的问题 分解得到的各子问题往往不是相互独立的 而分治法中子问题相互独立 2 动态规划法用表保存已求解过的子问题的解 再次碰到同样的子问题时不必重新求解 而只需查询答案 故可获得多项式级时间复杂度 效率较高 而分治法中对于每次出现的子问题均求解 导致同样的子问题被反复求解 故产生指数增 长的时间复杂度 效率较低 1717 分治法所能解决的问题一般具有的几个特征 分治法所能解决的问题一般具有的几个特征 参考解答 1 该问题的规模缩小到一定的程度就可以容易地解决 6 分 7 2 该问题可以分解为若干个规模较小的相同问题 即该问题具有 最 优子结构性质 3 利用该问题分解出的子问题的解可以合并为该问题的解 4 原问题所分解出的各个子问题是相互独立的 即子问题之间不 包 含公共的子问题 五 算法设计题五 算法设计题 1 最长上升子序列问题 提示 此题可采用动态规划算法实现 对于给定的一个序列 我们可以得到一些递增 12 N a aa 11000N 上升的子序列 这里 比如 对于序列 1 12 iiiK aaa 12 1 K iiiN 7 3 5 9 4 8 有它的一些上升子序列 如 1 7 3 4 8 等等 这 些子序列中最长的长度是 4 比如子序列 1 3 5 8 你的任务 就是对于 给定的序列 求出最长上升子序列的长度 要求写出你设计的算法思想及递推 函数的公式表达 8 2 Gray 码构造问题 提示 此题可采用分治递归算法实现 问题描述 格雷码 是一个长度为的序列 满足 n 2 a 每个元素都是长度为 n 比特的串 b 序列中无相同元素 c 连续的两个元素恰好只有 1 个比特不同 例如 n 2 时 格雷码为 00 01 11 10 Gray 码是一种编码 这种编码可以避免在读取时 因各数据位时序上的差 异造成的误读 格雷码在工程上有广泛应用 但格雷码不便于运算 请你设计 一种构造方法 输入长度序列 n 输出格雷码 你只要做出一种构造方案即可 格雷码并不唯一 9 3 现在有 8 位运动员要进行网球循环赛 要设计一个满足以下要求的比赛日程 表 1 每个选手必须与其他选手各赛一次 2 每个选手一天只能赛一次 3 循环赛一共进行 n 1 天 请利用分治法的思想 给这 8 位运动员设计一个合理的比赛日程 4 对于矩阵连乘所需最少数乘次数问题 其递归关系式为 1 i k j 0 min 1 ikj ij m i j m i km kjpp pij 其中 m i j 为计