全国计算机等级考试--二级公共基础知识

《全国计算机等级考试--二级公共基础知识》由会员分享，可在线阅读，更多相关《全国计算机等级考试--二级公共基础知识（99页珍藏版）》请在装配图网上搜索。

1、 全 国 计 算 机 等 级 考 试二 级 公 共 基 础 知 识 第 一 章 数 据 结 构 与 算 法n 考 试 大 纲1. 算 法 的 基 本 概 念 ； 算 法 复 杂 度 的 概 念 和 意 义 （ 时 间 复 杂 度 与 空 间 复杂 度 ） 。2. 数 据 结 构 的 定 义 ； 数 据 的 逻 辑 结 构 与 存 储 结 构 ； 数 据 结 构 的 图 形 表示 ； 线 性 结 构 与 非 线 性 结 构 的 概 念 。3. 线 性 表 的 定 义 ； 线 性 表 的 顺 序 存 储 结 构 及 其 插 入 与 删 除 运 算 。4. 栈 和 队 列 的 定 义 ； 栈 和 队

2、 列 的 顺 序 存 储 结 构 及 其 基 本 运 算 。5. 线 性 单 链 表 、 双 向 链 表 与 循 环 链 表 的 结 构 及 其 基 本 运 算 。6. 树 的 基 本 概 念 ； 二 叉 树 的 定 义 及 其 存 储 结 构 ； 二 叉 树 的 前 序 、 中 序和 后 序 遍 历 。7. 顺 序 查 找 与 二 分 法 查 找 算 法 ； 基 本 排 序 算 法 （ 交 换 类 排 序 ， 选 择 类排 序 ， 插 入 类 排 序 ） 。 知 识 点 归 纳n 算 法 的 基 本 概 念n 所 谓 算 法 是 指 解 题 方 案 的 准 确 而 完 整 的 描 述 。 严

3、 格 来说 ， 一 个 算 法 必 须 具 有 以 下 五 个 主 要 特 征 ：n 有 穷 性n 确 定 性 n 可 行 性n 输 入n 输 出n 综 上 ， 所 谓 算 法 ， 是 一 组 严 格 定 义 运 算 顺 序 的 规 则 ，而 且 每 一 个 规 则 都 是 有 效 且 明 确 的 ， 此 顺 序 将 在 有 限的 次 数 终 止 。 算 法 的 基 本 概 念n 算 法 的 组 成 要 素n 算 法 中 对 数 据 的 运 算 和 操 作n 算 法 的 控 制 结 构n 算 法 设 计 基 本 方 法n 列 举 法n 归 纳 法 n 递 推n 递 归n 减 半 递 推n 回

4、溯 法 算 法 的 复 杂 度n 算 法 的 复 杂 度 可 分 为 时 间 复 杂 度 和 空 间 复 杂 度 ，是 衡 量 算 法 优 劣 的 量 度 。1.算 法 的 时 间 复 杂 度n 算 法 的 时 间 复 杂 度 是 指 执 行 算 法 所 需 要 的 工 作量 。 一 般 情 况 下 ， 算 法 中 的 基 本 操 作 重 复 执 行的 次 数 是 问 题 规 模 n的 某 个 函 数 f(n)。 算 法 的时 间 量 度 记 作 ： T(n)=O(f(n)， 表 示 随 问 题 规模 n的 增 大 ， 算 法 执 行 时 间 的 增 长 率 和 f(n)的增 长 率 相 同

5、， 称 为 算 法 的 (渐 进 )时 间 复 杂 度 。 算 法 的 复 杂 度n 何 估 算 算 法 的 时 间 复 杂 度 ？ 任 何 一 个 算 法 都 是 由 一 个 “ 控 制 结 构 ” 和 若 干 “ 原 操 作 ”组 成 的 ， 因 此 一 个 算 法 的 执 行 时 间 可 以 看 成 是 所 有 原 操 作 的 执行 时 间 之 和 ( 原 操 作 (i)的 执 行 次 数 原 操 作 (i)的 执 行 时 间 )则 算 法 的 执 行 时 间 与 所 有 原 操 作 的 执 行 次 数 之 和 成 正 比 。从 算 法 中 选 取 一 种 对 于 所 研 究 的 问 题

6、 来 说 是 基 本 操 作 的 原 操 作 ，以 该 基 本 操 作 在 算 法 中 重 复 执 行 的 次 数 作 为 算 法 时 间 复 杂 度 的依 据 。 这 种 衡 量 效 率 的 办 法 所 得 出 的 不 是 时 间 量 ， 而 是 一 种 增长 趋 势 的 量 度 。 它 与 软 硬 件 环 境 无 关 ， 只 暴 露 算 法 本 身 执 行 效率 的 优 劣 。 算 法 的 复 杂 度n 算 法 的 空 间 复 杂 度n 算 法 的 空 间 负 杂 度 是 指 执 行 这 个 算 法 所需 要 的 内 存 空 间 。 空 间 复 杂 度 作 为 算 法所 需 存 储 空 间

7、 的 量 度 ， 记 作 ：S(n)=O(g(n)， 其 中 n为 问 题 的 规 模 ， 表示 随 问 题 规 模 的 增 大 ， 算 法 运 行 所 需 存储 量 的 增 长 率 与 g(n)的 增 长 率 相 同 。 数 据 结 构n 利 用 计 算 机 进 行 数 据 处 理 是 计 算 机 应 用 的 一个 重 要 领 域 。 数 据 结 构 主 要 研 究 和 讨 论 以 下三 个 方 面 的 问 题 ：1. 数 据 集 合 中 各 数 据 元 素 之 间 的 逻 辑 关 系 ， 即数 据 的 逻 辑 结 构 。2. 在 对 数 据 进 行 处 理 时 ， 各 数 据 元 素 在

8、计 算 机中 的 存 储 关 系 ， 即 数 据 的 存 储 结 构 。 3. 对 各 种 数 据 结 构 进 行 的 运 算 。 数 据 的 逻 辑 结 构n 数 据 逻 辑 结 构 是 对 数 据元 素 之 间 存 在 的 逻 辑 关系 的 描 述 ， 它 可 以 用 一个 数 据 元 素 的 集 合 和 定义 在 此 集 合 上 的 若 干 关系 表 示 。 n 与 数 据 在 计 算 机 中 的 存储 位 置 无 关 ， 是 独 立 于计 算 机 的 。 数 据 的 存 储 结 构n 数 据 的 存 储 结 构 是 数 据 元 素 及 其 关 系 在 计 算 机 存 储 器 中的 表

9、示 。 存 储 结 构 的 主 要 内 容 是 指 在 存 储 空 间 中 使 用 一个 存 储 结 点 来 存 储 一 个 数 据 元 素 ， 在 存 储 空 间 中 建 立 各存 储 结 点 之 间 的 关 联 ， 来 表 示 数 据 元 素 之 间 的 逻 辑 关 系 。n 常 见 的 存 储 结 构 ： n 顺 序 存 储 结 构n 链 式 存 储 结 构n 索 引 存 储 结 构n 散 列 存 储 结 构 线 性 结 构 和 非 线 性 结 构线 性 结 构n 在 数 据 元 素 的 非 空 有 限 集 合 中 ， 线 性 结 构 的 逻 辑 特 征如 下 ：n 存 在 一 个 唯

10、一 的 被 称 为 “ 第 一 个 ” 的 数 据 元 素n 存 在 一 个 唯 一 的 被 称 为 “ 最 后 一 个 ” 的 数 据 元 素n 除 第 一 个 之 外 ， 集 合 中 的 每 个 数 据 元 素 均 有 且 只 有 一个 直 接 前 驱n 除 最 后 一 个 之 外 ， 集 合 中 的 每 个 数 据 元 素 均 有 且 只 有一 个 直 接 后 继非 线 性 结 构 n 非 线 性 结 构 的 逻 辑 特 征 是 ： 一 个 结 点 可 能 有 多 个 直 接前 驱 和 直 接 后 继 ， 树 和 图 都 属 于 非 线 性 结 构 。 线 性 表n 通 常 以 下 列

11、n 个 数 据 元 素 的 序 列 ” 表 示线 性 表 ： (a1,a2 ,.,ai ,.,an) n 序 列 中 数 据 元 素 的 个 数 n 定 义 为 线 性 表的 表 长 ； n=0 时 的 线 性 表 被 称 为 空 表 。称 i 为 ai在 线 性 表 中 的 位 序 。 线 性 表 的 顺 序 存 储n 线 性 表 的 顺 序 存 储 结 构 用 一 组 地 址 连 续 的 存 储 单 元 依 次 存 放 线性 表 中 的 数 据 元 素 ， 即 以 “ 存 储 位 置 相 邻 ” 表 示 “ 位 序 相 继 的两 个 数 据 元 素 之 间 的 前 驱 和 后 继 的 关

12、系 ， 并 以 表 中 第 一 个 元 素的 存 储 位 置 作 为 线 性 表 的 起 始 地 址 ， 称 作 线 性 表 的 基 地 址 。 所 有 数 据 元 素 的 存 储 位 置 均 可 由 第 一 个 数 据 元 素 的 存 储 位 置 得 到 ADR(a i) = ADR(a1) + (i-1) C 基 地 址 一 个 数 据 元 素 所 占 存 储 量 线 性 表 的 插 入 和 删 除 运 算n 插 入 运 算 是 指 在 线 性 表 的 某 个 指 定 位 置 增 加 一 个新 结 点 。n 一 般 情 况 下 ， 要 在 第 i(1 i n)个 元 素 之 前 插 入一

13、个 新 元 素 时 ， 首 先 要 从 最 后 一 个 元 素 开 始 ， 直到 第 i个 元 素 之 间 共 n-i+1个 元 素 依 次 向 后 移 动 一个 位 置 ， 然 后 将 新 元 素 插 入 到 第 i项 。n 删 除 运 算 是 指 撤 销 结 构 中 的 某 个 结 点 。 n 一 般 情 况 ， 要 删 除 第 i(1 i n)个 元 素 ， 要 从 第i+1个 元 素 开 始 ， 直 到 第 n个 元 素 ， 共 n-i个 元 素 依次 向 前 移 动 一 个 位 置 。 栈n 栈 是 限 定 仅 在 表 的 一 端 进 行 插 入 和 删 除 操 作 的 线 性 表

14、。 允 许 插 入 和删 除 的 一 端 称 为 栈 顶 ， 另 一 端 称 为 栈 底 。n 栈 顶 元 素 总 是 最 后 被 插 入 的 元 素 ， 从 而 也 是 最 先 被 删 除 的 元 素 ； 栈底 元 素 总 是 最 先 被 插 入 ， 也 是 最 后 被 删 除 的 元 素 。 因 此 ， 栈 是 一 种后 进 先 出 的 线 性 表 。n 通 常 用 指 针 top指 示 栈 顶 位 置 ， 用 指 针 bottom指 示 栈 底 位 置 。 栈 的 顺 序 存 储 及 运 算n 用 一 维 数 组 S(1:m)作 为 栈 的 顺 序 存 储 空 间 ， m为栈 的 最 大

15、 容 量 。 top=0表 示 栈 为 空 ， top=m表 示栈 满 。n 栈 的 操 作n 入 栈 ： 在 栈 顶 位 置 插 入 一 个 新 元 素 ， 栈 顶 指 针 top加1。 n 退 栈 ： 取 出 栈 顶 元 素 并 赋 值 给 一 个 指 定 的 变 量 ， 栈顶 指 针 top减 1。n 取 栈 顶 元 素 ： 将 栈 顶 元 素 的 值 赋 给 一 个 指 定 的 变 量 ，不 删 除 栈 顶 元 素 ， 栈 顶 指 针 不 变 。 队 列n 队 列 是 一 种 先 进 先 出 的 线 性 表 ， 它 只 允 许 在 表 的 一 端 插 入 元素 (队 尾 )， 在 另

16、一 端 删 除 元 素 (队 头 )。 通 常 定 义 头 指 针front指 向 队 头 元 素 的 前 一 个 位 置 ， 定 义 尾 指 针 rear指 向 队尾 元 素 的 位 置 。n 队 列 是 一 种 先 进 先 出 的 数 据 结 构 。n 向 队 尾 插 入 一 个 元 素 的 操 作 称 为 入 队 ， 从 队 头 删 除 一 个 元 素的 操 作 称 为 退 队 。 循 环 队 列n 将 队 列 存 储 空 间 的 最 后 一 个 位 置 绕 到 第 一 个 位 置 ， 形成 逻 辑 上 的 环 状 空 间 。n 循 环 队 列 初 始 状 态 为 空 ， 即 front

17、=rear=m。n 入 队 操 作 时 ， rear加 1， 若 rear=m+1， 则 置 rear=1；n 退 队 操 作 时 ， front加 1， 若 front=m+1， 则 置 front=1。n 在 循 环 队 列 为 空 或 为 满 时 ， 均 有 front=rear， 因 此 需要 设 置 标 志 s进 行 区 分 ， 定 义 s=0表 示 队 列 为 空 ， s=1表示 队 列 非 空 。 单 链 表n 线 性 表 的 链 式 存 储 结 构 的 特 点 是 用 一 组 任 意 的 存储 单 元 (可 以 连 续 ， 也 可 以 不 连 续 )存 储 线 性 表 的数 据

18、 元 素 ， 为 了 表 示 每 个 数 据 元 素 ai与 其 直 接 后 继元 素 ai+1之 间 的 逻 辑 关 系 ， 对 数 据 元 素 ai来 说 ， 除了 存 储 其 本 身 的 信 息 (数 据 域 )之 外 ， 还 需 要 存 储其 后 继 元 素 的 存 储 位 置 信 息 (指 针 域 )。n 指 针 域 中 存 储 的 信 息 称 为 指 针 或 链 ， N个 结 点 链 接成 一 个 链 表 ， 即 为 线 性 表 的 链 式 存 储 结 构 。 由 于结 点 中 只 包 含 一 个 指 针 域 ， 故 称 为 单 链 表 。 单 链 表n 通 常 以 单 链 表 中

19、 第 一 个 数 据 元 素 的 存 储 地 址作 为 作 为 单 链 表 的 地 址 ， 称 为 头 指 针 。 整 个链 表 的 存 储 必 须 从 头 指 针 开 始 (顺 序 存 取 )，头 指 针 指 示 链 表 中 第 一 个 结 点 的 存 储 位 置 。最 后 一 个 数 据 元 素 没 有 直 接 后 继 ， 其 指 针 域为 空 。 单 链 表 的 插 入 和 删 除 双 向 链 表 和 循 环 链 表n 在 双 向 链 表 中 的 结 点 包 含 两 个 指 针 域 ， 其 中 一 个 指 向 直 接 后 继 ， 另一 个 指 向 直 接 前 驱 。n 循 环 链 表 的

20、 特 点 是 表 中 最 后 一 个 结 点 的 指 针 域 指 向 第 一 个 结 点 ， 整个 链 表 成 为 一 个 由 链 指 针 相 链 接 的 环 。 据 此 ， 从 表 中 任 一 节 点 出 发均 可 找 到 表 中 其 它 结 点 。 在 循 环 链 表 中 增 加 了 一 个 表 头 结 点 ， 其 指针 域 指 向 第 一 个 元 素 结 点 ， 头 指 针 则 指 向 头 结 点 。HEAD HEAD HEAD 树 及 其 基 本 概 念n 树 是 一 种 简 单 的 非 线 性 结 构 ， 在 树中 ， 所 有 的 数 据 元 素 之 间 具 有 明 显的 层 次 性

21、 关 系 。n 树 是 (n 0)个 结 点 的 有 限 集 合 ， 在任 意 一 棵 非 空 树 中 ： (1)有 且 仅 有 一 个 特 定 的 结 点 称 为 根结 点 。 (2)当 n1时 ， 其 余 的 结 点 可 分 为 m个互 不 相 交 的 子 集 T 1,T2,Tm， 其 中每 个 有 限 子 集 本 身 又 是 一 棵 树 ， 并且 称 为 根 的 子 树 。n 集 合 为 空 的 树 简 称 为 空 树 ； 树 中 的元 素 称 为 结 点 。 树 的 主 要 术 语n 结 点 的 度 ： 结 点 拥 有 的 子 树 数 。n 叶 节 点 (终 端 结 点 )： 度 为

22、0的 结 点 。n 双 亲 、 孩 子 和 兄 弟 ： 结 点 的 子 树 的 根 节 点 称 为该 结 点 的 孩 子 ， 该 结 点 称 为 孩 子 结 点 的 双 亲 结点 。 同 一 个 双 亲 结 点 的 孩 子 互 称 为 兄 弟 。n 层 次 ： 结 点 的 层 次 从 根 开 始 定 义 ， 根 为 第 一 层 ，根 的 孩 子 为 第 二 层 。 n 深 度 ： 树 中 结 点 的 最 大 层 次 称 为 树 的 深 度 或 高度 。 二 叉 树n 二 叉 树 是 n(n 0)个 数 据 元 素 的有 限 集 ， 它 或 为 空 集 ,或 者 含 有唯 一 的 称 为 根 的

23、 元 素 ， 且 其 余 元素 分 成 两 个 互 不 相 交 的 子 集 ， 每个 子 集 自 身 也 是 一 棵 二 叉 树 ， 分别 称 为 根 的 左 子 树 和 右 子 树 。 n 二 叉 树 是 另 一 种 树 型 结 构 ， 其 特点 是 每 个 结 点 至 多 有 两 棵 子 树 ，并 且 二 叉 树 的 子 树 有 左 右 之 分 ，其 顺 序 不 能 任 意 颠 倒 。 二 叉 树 的 基 本 性 质n 性 质 1 在 二 叉 树 的 第 i层 上 至 多 有 2i-1个 结 点（ i 1）n 性 质 2 深 度 为 k的 二 叉 树 至 多 有 2k -1个 结 点（ k

24、 1）n 性 质 3 对 任 何 一 棵 二 叉 树 T， 如 果 其 终 端 结 点 数 为n0， 度 为 2的 结 点 数 为 n2 ， 则 ： n0 =n2+1n 性 质 4 具 有 n个 结 点 的 二 叉 树 ， 其 深 度 至 少 为log2n +1 满 二 叉 树 和 完 全 二 叉 树n 满 二 叉 树 除 最 后 一 层 外 ， 每 一 层 上 的 所 有 结 点 都 有 两 个 子 节 点 ， 也 就是 说 每 一 层 上 的 结 点 数 都 达 到 最 大 值 ， 即 在 满 二 叉 树 的 第 k层 上 有 2k-1个 结 点 ， 且 深 度 为 m的 满 二 叉 树

25、有 2m-1个 结 点 。n 完 全 二 叉 树 除 最 后 一 层 外 ， 每 一 层 上 的 结 点 数 均 达 到 最 大 值 ， 在 最 后一 层 上 只 缺 少 右 边 的 若 干 结 点 。 具 有 n个 结 点 的 完 全 二 叉 树 ， 其 深 度 为log2n +1。n 从 以 上 定 义 可 知 ， 满 二 叉 树 也 是 完 全 二 叉 树 ， 反 之 则 不 然 。满 二 叉 树 最 大 层 的 结 点均 向 左 靠 齐 完 全 二 叉 树 AD CB E F 二 叉 树 的 基 本 性 质性 质 5 如 果 对 一 棵 有 n 个 结 点 的 完 全 二 叉 树 （

26、其 深 度 为log2n +1） 的 结 点 按 层 序 （ 从 第 1层 到 第 log2n +1 层 ， 每层 从 左 到 右 ） 从 1起 开 始 编 号 ， 则 对 任 一 编 号 为 i 的 结 点(1 i n)， 则 : (1) 如 果 i=1， 则 编 号 为 i 的 结 点 是 二 叉 树 的 根 ， 无 双 亲 ；如 果 i1， 则 其 双 亲 结 点 parent(i)的 编 号 是 i/2。 (2) 如 果 2in， 则 编 号 为 i 的 结 点 无 左 孩 子 （ 编 号 为 i 的 结 点 为 叶 子 结 点 ） ； 否 则 其 左 孩 子 结 点 lChild(i

27、) 的 编 号是 2i 。 (3) 如 果 2i+1n， 则 编 号 为 i 的 结 点 无 右 孩 子 ； 否 则 其 右孩 子 结 点 rChild(i) 的 编 号 是 结 点 2i+1。 二 叉 树 的 链 式 存 储 结 构n 在 二 叉 树 的 链 式 存 储 结 构 中 ， 每 个 结 点 设 置 三 个 域 ，即 数 据 域 ， 左 指 针 域 和 右 指 针 域 ， 两 个 指 针 域 分 别存 储 左 右 子 树 根 节 点 的 存 储 位 置 ， 即 指 针 。L(i) V(i) R(i)Lchild value Rchild 二 叉 树 的 链 式 存 储 结 构 二

28、叉 树 的 遍 历n 二 叉 树 的 遍 历 指 不 重 复 地 访 问 二 叉 树 的 所 有 结 点 。 从 二 叉 树 的 结构 定 义 得 知 ， 二 叉 树 是 由 根 结 点 、 左 子 树 和 右 子 树 三 部 分构 成 ， 则 遍 历 二 叉 树 的 操 作 可 分 解 为 访 问 根 结 点 、 遍 历 左 子 树和 遍 历 右 子 树 三 个 子 操 作 ， 并 且 由 二 叉 树 的 递 归 定 义 可 知 ， 遍历 左 子 树 和 遍 历 右 子 树 可 如 同 遍 历 二 叉 树 一 样 递 归 进 行 。 先 序 遍 历 二 叉 树 中 序 遍 历 二 叉 树 后

29、 序 遍 历 二 叉 树若 二 叉 树 为 空 ， 则 空 操 作 ； 否 则(1) 访 问 根 结 点 ；(2) 先 序 遍 历 左 子 树 ；(3) 先 序 遍 历 右 子 树 。 若 二 叉 树 为 空 ， 则 空 操 作 ；否 则(1) 中 序 遍 历 左 子 树 ；(2) 访 问 根 结 点 ；(3) 中 序 遍 历 右 子 树 。 若 二 叉 树 为 空 ， 则 空 操 作 ；否 则(1) 后 序 遍 历 左 子 树 ；(2) 后 序 遍 历 右 子 树 ；(3) 访 问 根 结 点 。 二 叉 树 的 遍 历先 序 遍 历 ： ABDEGHCFIJ中 序 遍 历 ： DBGEHA

30、CIJF后 序 遍 历 ： DGHEBJIFCA 查 找n 查 找 是 指 在 一 个 给 定 的 数 据 结 构 中 查 找 某 个 指 定 的 元 素 。n 顺 序 查 找n 顺 序 查 找 一 般 是 指 在 线 性 表 中 查 找 指 定 元 素 ， 基 本 方 法 如下 ： 从 线 性 表 的 第 一 个 元 素 开 始 ， 依 次 将 线 性 表 中 的 元 素与 被 查 找 元 素 进 行 比 较 ， 若 相 等 则 表 示 找 到 ， 即 查 找 成 功 ；若 线 性 表 中 的 所 有 元 素 与 被 查 找 元 素 都 不 相 等 ， 则 查 找 失败 。 n 如 果 线

31、性 表 为 无 序 表 ， 即 表 中 元 素 的 排 列 是 无 序 的 ， 则 不管 线 性 表 采 用 顺 序 存 储 还 是 链 式 存 储 ， 都 必 须 使 用 顺 序 查找 。n 如 果 线 性 表 有 序 ， 但 采 用 链 式 存 储 结 构 ， 则 也 必 须 使 用 顺序 查 找 。 查 找n 二 分 查 找 (折 半 查 找 )n 二 分 查 找 法 只 适 用 于 顺 序 存 储 的 有 序 表 。 先 确 定待 查 目 标 元 素 所 在 范 围 (区 间 )， 然 后 逐 步 缩 小 范围 直 至 找 到 该 元 素 ， 或 者 当 查 找 区 间 缩 小 到 0

32、也没 有 找 到 目 标 元 素 为 止 。n 查 找 过 程 中 ， 给 定 值 首 先 和 处 于 待 查 区 间 中 间位 置 的 关 键 字 进 行 比 较 ， 若 相 等 ， 则 查 找 成 功 ，否 则 将 查 找 区 间 缩 小 到 前 半 个 区 间 或 后 半个 区 间 之 后 继 续 进 行 查 找 。 折 半 查 找二 分 查 找 排 序n 排 序 是 指 将 一 个 无 序 序 列 整 理 成 按 值 递 增 或 递减 (本 章 均 采 用 递 增 规 则 )的 有 序 序 列 。n 排 序 可 以 在 各 种 不 同 的 存 储 结 构 上 实 现 ， 本 章所 介

33、绍 的 算 法 以 顺 序 存 储 的 线 性 表 为 排 序 对 象 ，在 程 序 设 计 语 言 中 就 是 一 维 数 组 。n 排 序 的 算 法 种 类 很 多 ， 主 要 包 括 交 换 类 排 序 、插 入 类 排 序 、 选 择 类 排 序 等 。 交 换 类 排 序n 冒 泡 排 序n 基 本 思 想 ： 从 表 头 开 始 扫 描 线 性 表 ， 在 扫 描 的 过 程 中 依 次 比 较相 邻 两 个 元 素 的 大 小 ， 若 前 面 的 元 素 大 于 后 面 的 元 素 ， 则 交 换它 们 的 位 置 。 显 然 ， 在 扫 描 过 程 中 ， 不 断 地 将 将

34、 相 邻 元 素 间 较大 的 向 后 移 动 ， 最 后 将 线 性 表 中 最 大 的 元 素 移 到 表 尾 。n 然 后 ， 从 后 向 前 扫 描 剩 下 的 线 性 表 ， 同 样 在 扫 描 的 过 程 中 依 次比 较 相 邻 两 个 元 素 的 大 小 ， 若 后 面 的 元 素 小 于 前 面 的 元 素 ， 则交 换 位 置 。 在 扫 描 过 程 中 ， 不 断 地 将 将 相 邻 元 素 间 较 小 的 向 前移 动 ， 最 后 将 线 性 表 中 最 小 的 元 素 移 到 表 头 。 n 对 剩 下 的 线 性 表 重 复 上 述 过 程 ， 直 到 剩 余 线

35、性 表 为 空 为 止 ， 此时 线 性 表 变 为 有 序 。 冒 泡 排 序 示 例第 一 遍 (从 前 向 后 )第 一 遍 (从 后 向 前 )第 二 遍 (从 前 向 后 )第 二 遍 (从 后 向 前 ) 快 速 排 序n 基 本 思 想 ： 从 线 性 表 中 选 取 一 个 元 素 ， 设 为 T， 将 线 性 表 后 面小 于 T的 元 素 移 动 到 前 面 ， 将 前 面 大 于 T的 元 素 移 动 到 后 面 ，将 线 性 表 分 为 两 个 部 分 (子 表 )， T放 到 分 界 线 的 位 置 ， 这 个 过程 称 为 线 性 表 的 分 割 ， 通 过 一 次

36、 分 割 ， 就 以 T为 分 界 将 线 性 表分 为 两 个 子 表 ， 前 面 的 子 表 中 的 所 有 元 素 均 不 大 于 T， 而 后 面子 表 中 的 元 素 均 不 小 于 T。 按 照 上 述 原 则 对 子 表 继 续 进 行 分 割 ，直 到 子 表 为 空 ， 则 整 个 线 性 表 有 序 。 快 速 排 序n 操 作 步 骤 ：n 首 先 ， 在 表 的 第 一 个 元 素 、 最 后 一 个 元 素 和 中 间 元 素 中 选取 一 个 中 值 ， 设 为 P(k)， 并 将 P(k)赋 值 给 T， 再 将 表 中 的第 一 个 元 素 移 到 P(k) 的

37、 位 置 。 设 两 个 指 针 i， j分 别 指 向表 的 起 始 和 最 后 位 置 ， 反 复 操 作 以 下 两 步 ： 将 j逐 渐 减 小 ， 并 逐 次 比 较 P(j)和 T， 直 到 发 现 一 个 P(j)T为 止 ，并 将 P(i)移 到 P(j)的 位 置 上 。 n 上 述 两 步 操 作 交 替 进 行 ， 直 到 i和 j指 向 同 一 个 位 置 ， 再 将T移 动 到 P(i)的 位 置 上 ， 完 成 一 次 分 割 。 31 68 45 90 23 39 54 12 87 7631暂 存 枢 轴 记 录 T：low highhighhigh1212 lo

38、w68 68highhighhigh2323low45 45highhigh3131快 速 排 序 的 一 次 分 割 过 程31 插 入 类 排 序n 简 单 插 入 排 序n 基 本 思 想 ： 将 待 排 序 列 表 分 成 两 部 分 ：已 排 序 部 分 和 未 排 序 部 分 。 每 次 扫 描 将未 排 序 列 表 中 的 第 一 个 元 素 取 出 并 插 入到 已 排 序 列 表 中 的 合 适 位 置 。 包 含 n个 元素 的 列 表 最 多 需 要 n-1次 扫 描 。 简 单 插 入 排 序 示 例原 始 序 列第 1趟第 2趟 第 3趟第 4趟第 5趟 希 尔 排

39、序n 基 本 思 想 ： 将 整 个 无 序 序 列 分 割 成 若 干 个 小 的子 序 列 分 别 进 行 插 入 排 序 。n 子 序 列 的 分 割 方 法 ： 将 相 隔 某 个 增 量 h的 元 素构 成 一 个 子 序 列 ， 在 排 序 过 程 中 ， 逐 次 减 小 这个 增 量 ， 最 后 当 h减 到 1时 ， 进 行 一 次 插 入 排 序 ，排 序 完 成 。 n 增 量 序 列 一 般 取 ht=n/2k(k=1,2log2n) 希 尔 排 序h=6h=1h=3完 成 选 择 类 排 序n 简 单 选 择 排 序n 基 本 思 想 ： 将 待 排 序 列 表 分 成

40、 两 部 分 ： 已 排 序部 分 和 未 排 序 部 分 。 找 到 未 排 序 部 分 中 的 最 小元 素 并 把 它 和 未 排 序 部 分 中 的 第 一 个 元 素 进 行交 换 。 经 过 一 次 选 择 和 交 换 ， 列 表 中 已 排 序 部分 增 加 一 个 元 素 ， 未 排 序 部 分 减 少 一 个 元 素 。每 次 把 一 个 元 素 从 未 排 序 部 分 移 动 到 已 排 序 部分 称 为 完 成 一 次 分 类 扫 描 或 称 为 一 趟 排 序 。 n 一 个 包 含 n个 元 素 的 列 表 需 要 进 行 n-1次 扫 描 完成 排 序 。 简 单

41、选 择 排 序 示 例原 始 序 列第 1趟第 2趟 第 3趟第 4趟第 5趟 第 二 章 程 序 设 计 基 础n 考 试 大 纲n 1. 程 序 设 计 方 法 与 风 格 。2. 结 构 化 程 序 设 计 。3. 面 向 对 象 的 程 序 设 计 方 法 ， 对 象 ， 方法 ， 属 性 及 继 承 与 多 态 性 。 知 识 点 归 纳n 程 序 设 计 方 法n 程 序 设 计 是 一 门 技 术 ， 需 要 相 应 的 理 论 、 方 法和 工 具 来 支 持 。 就 程 序 设 计 方 法 和 技 术 的 发 展而 言 ， 主 要 经 历 了 结 构 化 的 程 序 设 计

42、和 面 向 对象 的 程 序 设 计 阶 段 。n 在 程 序 设 计 中 ， 通 常 采 用 “ 自 顶 向 下 ， 逐 步 求精 ” 的 方 法 ， 即 把 一 个 模 块 的 功 能 逐 步 分 解 ，细 化 为 一 系 列 具 体 的 步 骤 ， 进 而 转 换 成 一 系 列用 某 种 程 序 设 计 语 言 编 写 的 程 序 。 程 序 设 计 风 格n 除 了 程 序 设 计 设 计 方 法 和 技 术 之 外 ， 程序 风 格 也 是 非 常 重 要 的 。 良 好 的 程 序 设计 风 格 概 括 起 来 包 括 以 下 及 格 方 面 ：n 源 程 序 文 档 化n 数

43、据 说 明 的 方 法 n 语 句 的 结 构n 输 入 和 输 出 程 序 设 计 风 格n 源 程 序 文 档 化n 标 识 符 的 命 名n 程 序 的 注 释n 序 言 性 注 释 n 功 能 性 注 释n 程 序 的 视 觉 组 织n 数 据 的 说 明n 数 据 说 明 的 次 序 应 该 规 范 化n 说 明 语 句 中 变 量 的 安 排 有 序 化n 使 用 注 释 说 明 复 杂 的 数 据 结 构 程 序 设 计 风 格n 语 句 结 构n 在 一 行 内 只 写 一 条 语 句n 程 序 编 写 应 优 先 考 虑 清 晰 性n 除 非 对 效 率 有 特 殊 要 求

44、， 程 序 编 写 要 做 到 清 晰 第 一 ， 效 率 第 二n 首 先 要 保 证 程 序 正 确 ， 然 后 才 要 求 提 高 速 度n 避 免 使 用 临 时 变 量 而 使 程 序 的 可 读 性 下 降 n 避 免 不 必 要 的 转 移n 尽 可 能 使 用 库 函 数n 避 免 使 用 复 杂 的 条 件 语 句n 尽 量 减 少 使 用 “ 否 定 ” 条 件 的 条 件 语 句n 数 据 结 构 要 有 利 于 程 序 的 简 化n 要 模 块 化 ， 使 模 块 功 能 尽 可 能 单 一 化n 利 用 信 息 隐 蔽 ， 确 保 每 一 个 模 块 的 独 立 性n

45、 从 数 据 出 发 构 造 程 序n 不 要 修 补 不 好 的 程 序 ， 要 重 写 编 写 程 序 设 计 风 格n 输 入 和 输 出n 对 所 有 输 入 数 据 检 验 合 法 性n 检 查 输 入 项 的 各 种 重 要 组 合 的 合 法 性n 输 入 格 式 要 简 单 ， 以 使 输 入 的 步 骤 和 操 作 尽 可 能 简 单n 输 入 数 据 时 ， 应 允 许 使 用 自 由 格 式n 应 允 许 缺 省 值 n 输 入 一 批 数 据 时 ， 最 好 使 用 输 入 结 束 标 志n 在 以 交 互 式 输 入 /输 出 方 式 进 行 输 入 时 ， 要 在

46、屏 幕 上 使 用 提 示符 明 确 提 示 输 入 的 请 求 ， 同 时 在 数 据 输 入 结 束 时 ， 应 在 屏 幕上 给 出 状 态 信 息n 当 程 序 设 计 语 言 对 输 入 格 式 有 严 格 要 求 时 ， 应 保 持 输 入 格 式与 输 入 语 句 的 一 致 性 ； 给 所 有 的 输 出 加 注 释 ， 并 设 计 输 出 报表 格 式 。 结 构 化 程 序 设 计n 结 构 化 程 序 设 计 的 原 则n 自 顶 向 下 。 程 序 设 计 时 ， 应 先 考 虑 总 体 ， 后 考 虑 细 节 ；先 考 虑 全 局 目 标 ， 后 考 虑 局 部 目

47、标 。 不 要 一 开 始 就 过多 追 求 细 节 ， 先 从 最 上 层 总 目 标 开 始 设 计 ， 逐 步 使 问题 具 体 化 。n 逐 步 求 精 。 对 复 杂 的 问 题 ， 应 设 计 一 些 子 目 标 过 渡 ，逐 步 细 化 。n 模 块 化 。 一 个 复 杂 问 题 肯 定 是 有 若 干 简 单 问 题 构 成 。模 块 化 是 把 程 序 要 解 决 的 总 目 标 分 解 为 分 目 标 ， 再 进一 步 分 解 为 具 体 的 小 目 标 ， 每 个 小 目 标 成 为 一 个 模 块 。 n 严 格 限 制 GOTO语 句 的 使 用 。 结 构 化 程

48、 序 设 计 的 基 本 结 构 和 特 点n 程 序 由 一 些 基 本 结 构 组 成 ， 任 何 一 个 程 序 都 可以 用 三 种 基 本 控 制 结 构 组 成 ： 顺 序 结 构 、 选 择结 构 和 循 环 结 构 ， 并 且 具 有 如 下 特 点 ： 单 入 口 、单 出 口 、 结 构 中 无 死 循 环 ， 程 序 中 三 种 基 本 控制 结 构 之 间 形 成 顺 序 执 行 关 系 。n 一 个 大 型 程 序 应 按 功 能 分 割 成 一 些 模 块 ， 并 把这 些 模 块 按 层 次 关 系 进 行 组 织 。 n 在 程 序 设 计 时 应 采 用 自

49、顶 向 下 、 逐 步 细 化 的 实施 方 法 。 面 向 对 象 程 序 设 计n 面 向 对 象 方 法 的 基 本 概 念1.对 象 、 类 和 属 性 在 面 向 对 象 程 序 设 计 中 ， 对 象 是 程 序 的 基 本 单 位 。 对象 可 以 表 示 客 观 世 界 中 的 任 何 实 体 ， 是 对 问 题 域 中 某 个实 体 的 抽 象 。 每 个 对 象 可 以 用 它 本 身 的 一 组 属 性 和 它 可以 执 行 的 一 组 操 作 来 定 义 。 类 是 对 一 组 具 有 共 同 属 性 和相 似 行 为 的 对 象 的 一 种 抽 象 ， 描 述 了 属

50、 于 该 类 的 所 有 对象 的 性 质 。2.方 法 方 法 有 称 为 操 作 或 服 务 ， 它 描 述 了 对 象 执 行 的 功 能 ，若 通 过 消 息 传 递 ， 还 可 为 其 他 对 象 使 用 。 面 向 对 象 方 法 的 基 本 概 念3.继 承 ： 继 承 是 对 象 方 法 的 一 个 重 要 特 征 。 指 一 个 类 (子 类 )直 接 使 用 另 一 个类 (父 类 )的 所 有 属 性 和 方 法 。 它 可 以 减 少 相 似 类 的 重 复 说 明 ， 从 而 体 现 一 般性 和 特 殊 性 的 原 则 。4.多 态 性 ： 多 态 性 可 以 用

51、“ 一 个 对 外 界 面 ， 多 个 内 部 实 现 ” 来 表 示 。 可 以 通过 方 法 重 载 和 方 法 重 写 来 实 现 多 态 。 重 载 指 一 个 类 中 可 以 有 多 个 具 有 相 同 名称 的 方 法 ， 由 传 递 给 它 们 的 不 同 个 数 和 类 型 的 参 数 来 决 定 执 行 那 个 方 法 。 重写 指 子 类 可 以 重 新 实 现 父 类 的 某 些 方 法 ， 使 其 具 有 自 己 的 特 征 。 多 态 性 机 制增 加 了 面 向 对 象 软 件 系 统 的 灵 活 性 ， 提 高 了 软 件 的 可 重 用 性 和 可 扩 充 性

52、。5.消 息 ： 面 向 对 象 系 统 中 的 对 象 之 间 是 通 过 消 息 机 制 彼 此 相 互 合 作 的 ， 消 息是 一 个 对 象 与 另 一 个 对 象 之 间 传 递 的 信 息 ， 它 请 求 对 象 执 行 某 一 处 理 或 回 答某 一 要 求 的 信 息 。 面 向 对 象 程 序 设 计 的 特 点n 按 照 人 的 思 维 方 式 对 客 观 世 界 进 行 抽 象n 稳 定 性 好n 可 重 用 性 好n 易 于 开 发 大 型 软 件n 可 维 护 性 好 第 三 章 软 件 工 程 基 础n 考 试 大 纲n 1. 软 件 工 程 基 本 概 念 ，

53、 软 件 生 命 周 期 的 概 念 ，软 件 工 具 与 软 件 开 发 环 境 。2. 结 构 化 分 析 方 法 ， 数 据 流 图 ， 数 据 字 典 ， 软件 需 求 规 格 说 明 书 。3. 结 构 化 设 计 方 法 ， 总 体 设 计 与 详 细 设 计 。4. 软 件 测 试 的 方 法 ， 白 盒 测 试 与 黑 盒 测 试 ， 测试 用 例 设 计 ， 软 件 测 试 的 实 施 ， 单 元 测 试 、 集成 测 试 和 系 统 测 试 。5. 程 序 的 调 试 ， 静 态 调 试 与 动 态 调 试 。 知 识 点 归 纳n 软 件 定 义 和 特 点n 计 算 机

54、 软 件 式 计 算 机 系 统 中 与 硬 件 相 互 依 存 的另 一 部 分 ， 是 包 括 程 序 、 数 据 及 相 关 文 档 的 完整 集 合 。 计 算 机 软 件 具 有 如 下 特 点 ：n 软 件 是 一 种 逻 辑 实 体 ， 具 有 抽 象 性n 软 件 生 产 没 有 明 显 的 制 造 过 程n 软 件 在 运 行 、 使 用 期 间 不 存 在 磨 损 、 老 化 问 题n 软 件 的 开 发 、 运 行 对 计 算 机 系 统 具 有 依 赖 性 n 软 件 复 杂 性 高 ， 成 本 昂 贵n 软 件 开 发 涉 及 诸 多 社 会 因 素 软 件 危 机n

55、 所 谓 软 件 危 机 是 指 在 计 算 机 软 件 开 发 和 维 护 过程 中 所 遇 到 的 一 系 列 严 重 问 题 ， 包 括 ：n 软 件 需 求 的 增 长 得 不 到 满 足n 软 件 开 发 成 本 和 进 度 无 法 控 制n 软 件 质 量 难 以 保 证n 软 件 不 可 维 护 或 可 维 护 性 低n 软 件 成 本 不 断 提 高 n 软 件 开 发 生 产 率 的 提 高 赶 不 上 硬 件 的 发 展 和 应用 需 求 的 增 长 。 软 件 工 程n 为 了 消 除 软 件 危 机 ， 提 出 了 软 件 工 程 学 。软 件 工 程 是 应 用 于

56、计 算 机 软 件 定 义 、 开发 和 维 护 的 一 整 套 方 法 、 工 具 、 文 档 、实 践 标 准 和 工 序 。n 软 件 工 程 的 三 要 素n 方 法 n 工 具n 过 程 软 件 工 程 过 程n 软 件 工 程 过 程 是 把 输 入 转 化 为 输 出 的 一 组 彼 此 相 关 的资 源 和 活 动 。 它 包 括 两 方 面 含 义 ：n 1. 软 件 工 程 过 程 是 指 为 获 得 软 件 产 品 ， 在 软 件 工 具 支持 下 由 软 件 工 程 师 完 成 的 一 系 列 工 程 活 动 。 通 常 包 括四 种 基 本 活 动 ：n P(Plan

57、)： 软 件 规 格 说 明 n D(Do)： 软 件 开 发n C(Check)： 软 件 确 认n A(Action)： 软 件 演 进n 2.从 软 件 开 发 的 观 点 看 ， 软 件 工 程 过 程 是 使 用 适 当 的资 源 ， 为 开 发 软 件 进 行 的 一 组 开 发 活 动 ， 在 活 动 结 束时 将 输 入 (用 户 需 求 )转 化 为 输 出 (软 件 产 品 )。 软 件 生 命 周 期n 软 件 从 提 出 、 实 现 、 使 用 、 维 护 到 停 止 使用 的 过 程 称 为 软 件 的 生 命 周 期 。 一 般 包 括以 下 几 个 阶 段 ：n

58、可 行 性 研 究 与 计 划 制 定n 需 求 分 析 n 软 件 设 计n 软 件 实 现n 软 件 测 试n 运 行 和 维 护 软 件 工 程 目 标 与 原 则n 软 件 工 程 的 目 标 是 在 给 定 成 本 、 进 度 的 前 提 下 ， 开 发出 具 有 有 效 性 、 可 靠 性 、 可 理 解 性 、 可 维 护 性 、 可 重用 性 、 可 适 应 性 、 可 移 植 性 、 可 追 踪 性 和 可 互 操 作 性且 满 足 用 户 需 求 的 软 件 产 品 。n 为 达 到 上 述 目 标 ， 在 软 件 开 发 的 过 程 中 ， 必 须 遵 循 软件 工 程

59、的 基 本 原 则 ： n 抽 象n 信 息 隐 蔽n 模 块 化n 局 部 化n 确 定 性n 一 致 性n 完 备 性n 可 验 证 性 软 件 开 发 工 具 与 软 件 开 发 环 境n 软 件 开 发 工 具 对 过 程 和 方 法 提 供 自 动 或 半 自动 的 支 持 。 当 这 些 工 具 被 集 成 起 来 使 得 一 个工 具 产 生 的 信 息 可 以 被 另 外 一 个 工 具 使 用 时 ，一 个 支 持 软 件 开 发 的 系 统 就 建 立 起 来 了 ， 称为 计 算 机 辅 助 软 件 工 程 (CASE)。 CASE集 成 了软 件 、 硬 件 和 一 个

60、 软 件 工 程 数 据 库 (包 含 了 有关 分 析 、 设 计 、 程 序 构 造 和 测 试 的 重 要 信 息 )从 而 创 建 了 一 个 软 件 开 发 环 境 。 结 构 化 分 析 方 法n 结 构 化 分 析 方 法 大 多 使 用 自 顶 向 下 、 逐 层 分 解 的 系 统 分析 方 法 来 定 义 系 统 需 求 。 在 结 构 化 分 析 的 基 础 上 ， 完 成系 统 的 规 格 说 明 ， 建 立 系 统 的 一 个 自 顶 向 下 的 任 务 分 析模 型 。 结 构 化 分 析 方 法 是 一 种 建 模 技 术 ， 模 型 的 核 心 是数 据 辞 典

61、 ， 它 描 述 了 所 有 在 目 标 系 统 中 使 用 和 生 成 的 数据 对 象 。 结 构 化 分 析 常 用 的 工 具 ： n 数 据 流 图 (DFD):描 述 数 据 在 系 统 中 如 何 被 传 送 或 变 换 以 及描 述 如 何 对 数 据 流 进 行 变 换 的 功 能 ， 用 于 功 能 建 模 。n 数 据 字 典n 判 定 树n 判 定 表 数 据 流 图n 数 据 流 图 是 描 述 数 据 处 理 过 程 的 工 具 ， 它 从 数据 传 递 和 加 工 的 角 度 ， 来 刻 画 数 据 流 从 输 入 系统 到 从 系 统 输 入 的 移 动 变 换

62、 过 程 。n 数 据 流 图 的 基 本 元 素n 外 部 实 体 n 数 据 流n 处 理 (加 工 )n 数 据 存 储 数 据 字 典n 数 据 字 典 是 关 于 数 据 的 信 息 的 集 合 ， 对数 据 流 图 中 的 各 个 元 素 进 行 完 整 的 定 义和 说 明 。 数 据 流 图 和 数 据 字 典 共 同 构 成系 统 的 逻 辑 模 型 。n 数 据 字 典 通 常 包 含 的 信 息 有 ： 名 称 、 别名 、 何 处 使 用 、 如 何 使 用 、 内 容 描 述 以及 补 充 信 息 等 。 软 件 需 求n 软 件 需 求 包 括 ： 功 能 需 求

63、、 性 能 需 求 、环 境 需 求 、 可 靠 性 需 求 、 安 全 保 密 需 求 、用 户 界 面 需 求 、 资 源 使 用 需 求 、 成 本 消耗 需 求 、 开 发 进 度 需 求 等 。n 需 求 分 析 应 交 付 的 主 要 文 档 是 软 件 需 求规 格 说 明 书 (SRS)。 结 构 化 设 计n 结 构 化 设 计 就 是 采 用 最 佳 的 可 能 方 法 设 计 系 统 的 各 个组 成 部 分 以 及 个 成 分 之 间 的 内 部 联 系 的 技 术 。 也 就 是说 ， 结 构 化 设 计 是 这 样 一 个 过 程 ： 它 决 定 用 哪 些 方 法

64、把 哪 些 部 分 联 系 起 来 ， 才 能 解 决 好 某 个 具 体 的 有 清 楚定 义 的 问 题 。 从 工 程 管 理 的 角 度 看 ， 软 件 设 计 分 两 步完 成 ：n 1.概 要 设 计 ， 即 总 体 设 计 。 将 软 件 需 求 转 化 为 数 据 结构 和 软 件 的 系 统 结 构 。 常 用 的 软 件 结 构 设 计 工 具 是 结构 图 (Structure Chart)。 n 2.详 细 设 计 ： 即 过 程 设 计 。 通 过 对 结 构 表 示 进 行 细 化 ，得 到 软 件 详 细 的 数 据 结 构 和 算 法 。 过 程 设 计 常 用

65、 的 工具 有 ： 程 序 流 程 图 、 N-S图 、 PAD图 、 过 程 设 计 语 言PDL(伪 码 )。 软 件 测 试n 定 义 ：n 使 用 人 工 或 自 动 手 段 来 运 行 或 测 定 某 个 系 统 的 过 程 ，其 目 的 在 于 检 验 它 是 否 满 足 规 定 的 需 求 或 弄 清 预 期 结果 与 实 际 结 果 之 间 的 差 别 。n 软 件 测 试 是 为 了 发 现 错 误 而 执 行 程 序 的 过 程 。n 一 个 好 的 测 试 用 例 是 指 可 能 找 到 迄 今 为 止 尚 未 发 现 的错 误 的 用 例 。 n 一 个 成 功 的 测

66、 试 是 发 现 了 至 今 尚 未 发 现 的 错 误 的 测 试 。n 测 试 不 能 表 明 软 件 中 不 存 在 错 误 ， 它 只 能 说 明 软 件 中存 在 错 误 。 测 试 技 术 与 方 法 综 述n 从 是 否 需 要 执 行 被 测 试 软 件 的 角 度 ， 可 将 测 试分 为 静 态 测 试 和 动 态 测 试 。n 静 态 测 试 主 要 包 括 代 码 检 查 、 静 态 结 构 分 析 、代 码 质 量 度 量 等 。n 动 态 测 试 是 基 于 计 算 机 的 测 试 ， 是 为 了 发 现 错误 而 执 行 程 序 的 过 程 ， 或 者 说 ， 是 根 据 软 件 开发 的 各 个 阶 段 的 规 格 说 明 和 程 序 的 内 部 结 构 而精 心 设 计 的 一 批 测 试 用 例 ， 并 利 用 这 些 测 试 用例 去 运 行 程 序 ， 以 发 现 程 序 错 误 的 过 程 。 测 试 技 术 与 方 法 综 述n 按 照 功 能 划 分 ， 可 将 软 件 测 试 分 为 黑 盒 测 试 和 白 盒 测试 。n 黑 盒 测 试