算 法 设 计 与 分 析1 、 （ 1 ） 证 明 ： O （ f)+O（ g)=O （ f+g) （ 7 分 ）（ 2 ） 求 下 列 函 数 的 渐 近 表 达 式 ： （ 6 分 ）① 3n2+10n；② 21+1/n；2 、 对 于 下 列 各 组 函 数 f （ n ） 和 g(n) ， 确 定f(n)=O（g（n）)或f(n)=Ω(g(n)）或f(n ） =θ （ g （ n） ) ， 并 简 述 理 由
（ 15 分 ）(1 ）（ 2 ）(3 ）3 、 试 用 分 治 法 对 数 组 A ［ n ］ 实 现 快 速 排 序
（ 13 分 ）4 、 试 用 动 态 规 划 算 法 实 现 最 长 公 共 子 序 列 问 题
（ 15 分 )5 、 试 用 贪 心 算 法 求 解 汽 车 加 油 问 题 ： 已 知 一 辆汽 车 加 满 油 后 可 行 驶 n 公 里 ， 而 旅 途 中 有 若 干 个加 油 站
试 设 计 一 个 有 效 算 法 , 指 出 应 在 哪 些 加油 站 停 靠 加 油 ， 使 加 油 次 数 最 少
（ 12 分 )6 、 试 用 动 态 规 划 算 法 实 现 下 列 问 题 : 设 A 和 B是两 个 字 符 串
我 们 要 用 最 少 的 字 符 操 作 , 将 字 符 串A 转 换 为 字 符 串 B， 这 里 所 说 的 字 符 操 作 包 括 ：(1 ） 删 除 一 个 字 符
(2 ） 插 入 一 个 字 符
（ 3) 将 一 个 字 符 改 为 另 一 个 字 符
将 字 符 串 A 变 换 为 字 符 串 B所 用 的 最 少 字 符 操 作数 称 为 字 符 串 A 到 B的 编 辑 距 离 ， 记 为 d（ A,B)
试设 计 一 个 有 效 算 法 ， 对 任 给 的 两 个
