算 法 设 计 与 分 析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). 试设 计 一 个 有 效 算 法 ， 对 任 给 的 两 个 字 符 串 A 和 B,计 算 出 它 们 的 编 辑 距 离 d(A ， B) 。（ 16 分 ）7 、 试 用 回 溯 法 解 决 下 列 整 数 变 换 问 题 ： 关 于 整数 的 变 换 和 定 义 如 下 ： . 对 于 给 定 的 两 个 整 数 和 ，要 求 用 最 少 的 变 换 和 变 换 次 数 将 变 为 。 （ 16 分 )1 、 ⑴ 证 明 ： 令 F(n)=O （ f ） ， 则 存 在 自 然 数n1、c1,使得对任意的自然数n≥n1，有 :F （ n ） ≤ c1f(n ） … … … … … … … … …...
