4 算 法 复 杂 度 主 要 包 括 时 间 复 杂 度 和 [ ] 复 杂 度 [2006.9] 1.2 数 据 结 构 与 算 法 数 据 结 构 作 为 计 算 机 的 一 门 学 科, 主 要 研 究 以 下 三 个 方 面 的 问 题 : a. 数 据 集 合 中 各 数 据 元 素 之

Transcription

1 1 算 法 1.1 算 法 的 基 本 概 念 1. 算 法 的 概 念 ( 必 记 ): 算 法 是 指 解 题 方 案 的 准 确 而 完 整 的 描 述 分 析 : 要 用 计 算 机 实 现 某 一 任 务 时, 先 应 设 计 出 一 整 套 解 决 问 题 的 指 导 方 案, 然 后 具 体 实 现 整 套 的 指 导 方 案 称 之 为 算 法, 而 具 体 的 实 现 称 之 为 程 序 并 且 在 设 计 指 导 方 案 时, 可 不 用 过 多 考 虑 到 实 现 程 序 的 具 体 细 节 ( 即 可 以 一 点 点 的 理 想 化 ), 但 在 程 序 实 现 时, 必 须 受 到 具 体 环 境 的 约 束 ( 现 实 不 同 于 理 想 ) 结 论 : 算 法 不 等 于 程 序, 也 不 等 于 计 算 方 法, 程 序 的 编 制 不 可 能 优 于 算 法 的 设 计 2. 算 法 的 基 本 特 征 ( 必 记 ): a. 可 行 性 : 由 于 算 法 总 是 在 某 个 特 定 的 计 算 工 具 上 实 现 并 执 行 的, 因 而 受 到 计 算 工 具 的 限 制, 所 以 在 设 计 算 法 时, 要 考 虑 到 设 计 的 算 法 是 否 是 可 性 的 b. 确 定 性 : 算 法 中 的 每 一 个 步 骤 都 必 须 是 有 明 确 定 义 的, 不 允 许 有 模 棱 两 可 的 解 释, 也 不 允 许 有 多 义 性 c. 有 穷 性 : 算 法 必 须 能 在 有 限 的 时 间 内 做 完, 即 算 法 必 须 能 在 执 行 有 限 个 步 骤 之 后 终 止 d. 拥 有 足 够 的 情 报 : 算 法 有 相 应 的 初 始 数 据 3. 算 法 的 基 本 要 素 : 一 个 算 法 通 常 由 两 个 基 本 要 素 所 组 成 : 一 是 对 数 据 对 象 的 运 算 和 操 作, 二 是 算 法 的 控 制 结 构 基 本 运 算 和 操 作 分 为 四 类 : a. 算 术 运 算 : ( 加 减 乘 除 等 运 算 ) b. 逻 辑 运 算 : ( 与 或 非 等 运 算 ) c. 关 系 运 算 : ( 大 于 小 于 等 于 不 等 于 等 运 算 ) d. 数 据 传 输 : ( 赋 值 输 入 输 出 等 操 作 ) 算 法 的 控 制 结 构 : 算 法 中 各 操 作 之 间 的 执 行 顺 序 称 之 为 算 法 的 控 制 结 构 一 个 算 法 一 般 都 可 以 用 顺 序 选 择 循 环 三 种 基 本 控 制 结 构 组 合 而 成 注 意 : 一 个 计 算 机 系 统 能 执 行 的 所 有 指 令 的 集 合, 称 为 该 计 算 机 系 统 的 指 令 系 统 4. 算 法 设 计 基 本 方 法 : 列 举 法 归 纳 法 递 推 递 归 减 半 递 推 技 术 回 溯 法 1.2 算 法 的 复 杂 度 ( 必 记 ) 算 法 的 复 杂 度 主 要 包 括 时 间 复 杂 度 和 空 间 复 杂 度 1. 算 法 的 时 间 复 杂 度 : 是 指 执 行 算 法 所 需 要 的 计 算 工 作 量, 是 由 算 法 所 执 行 的 基 本 运 算 次 数 来 度 量 可 用 平 均 性 态 和 最 坏 情 况 两 种 分 析 方 法 其 中 平 均 性 态 分 析 是 指 用 各 种 特 定 输 入 下 的 基 本 运 算 次 数 的 加 权 平 均 值 来 度 量 算 法 的 工 作 量 ; 而 最 坏 情 况 分 析 是 指 在 所 有 特 定 输 入 下 的 基 本 运 算 次 数 据 的 最 大 次 数 2. 算 法 的 空 间 复 杂 度 : 一 个 算 法 的 空 间 复 杂 度, 是 指 执 行 这 个 算 法 所 需 要 的 内 存 空 间 包 含 有 三 部 分 所 组 成 : 算 法 程 序 所 占 的 空 间 + 输 入 的 初 始 数 据 所 占 的 存 储 空 间 + 算 法 执 行 过 程 中 所 需 要 的 额 外 空 间 1 算 法 具 有 五 个 特 性, 以 下 选 项 中 不 属 于 算 法 特 性 的 是 ( ) [2005.4] A) 有 穷 性 B) 简 洁 性 C) 可 行 性 D) 确 定 性 2 问 题 处 理 方 案 的 正 确 而 完 整 的 描 述 称 为 [2005.4] 3 下 列 叙 述 中 正 确 的 是 [2006.9] A) 一 个 算 法 的 空 间 复 杂 度 大, 则 其 时 间 复 杂 度 也 必 定 大 B) 一 个 算 法 的 空 间 复 杂 度 大, 则 其 时 间 复 杂 度 必 定 小 C) 一 个 算 法 的 时 间 复 杂 度 大, 则 其 空 间 可 复 杂 度 必 定 小 D) 上 述 三 种 说 法 都 不 对 第 1 页, 共 26 页

2 4 算 法 复 杂 度 主 要 包 括 时 间 复 杂 度 和 [ ] 复 杂 度 [2006.9] 1.2 数 据 结 构 与 算 法 数 据 结 构 作 为 计 算 机 的 一 门 学 科, 主 要 研 究 以 下 三 个 方 面 的 问 题 : a. 数 据 集 合 中 各 数 据 元 素 之 间 所 固 有 的 逻 辑 关 系, 即 数 据 的 逻 辑 结 构 ; b. 在 对 数 据 进 行 处 理 时, 各 数 据 元 素 在 计 算 机 中 的 存 储 关 系, 即 数 据 的 存 储 结 构 ; c. 对 各 种 数 据 结 构 进 行 的 运 算 注 意 : 讨 论 以 上 问 题 主 要 目 的 是 为 了 提 高 数 据 处 理 的 效 率 提 高 效 率 包 括 两 个 方 面 : 一 是 提 高 数 据 处 理 的 速 度, 二 是 节 省 在 数 据 处 理 过 程 中 所 占 用 的 计 算 机 存 储 空 间 2.1 什 么 是 数 据 结 构 简 单 地 说, 数 据 结 构 是 指 相 互 有 关 联 的 数 据 元 素 的 集 合 而 数 据 元 素 之 间 的 关 联 通 常 是 指 其 前 后 件 关 系 ( 即 先 后 顺 序 关 系 ), 如 春 夏 秋 冬 之 间 的 先 后 顺 序 关 系 因 此, 一 个 数 据 结 构 应 包 含 以 下 两 方 面 的 信 息 :a. 表 示 数 据 元 素 的 信 息 ; b. 表 示 各 数 据 元 素 之 间 的 前 后 件 关 系 1. 数 据 的 逻 辑 结 构 所 谓 数 据 的 逻 辑 结 构, 是 指 反 映 数 据 元 素 之 间 逻 辑 关 系 的 数 据 结 构 注 意 : 这 种 逻 辑 关 系 仅 指 元 素 之 间 的 固 有 的 一 个 先 后 顺 序 关 系, 而 与 它 们 在 计 算 机 中 的 存 储 顺 序 无 关 2. 数 据 的 存 储 结 构 数 据 的 存 储 结 构 的 概 念 : 数 据 的 逻 辑 结 构 在 计 算 机 存 储 空 间 中 的 存 放 形 式 ( 也 称 数 据 的 物 理 结 构 ) 注 意 : a 数 据 元 素 在 计 算 机 中 存 储 空 间 中 的 位 置 关 系 可 以 与 它 们 的 逻 辑 关 系 相 同, 也 可 以 不 相 同 b 数 据 的 存 储 结 构 有 顺 序 链 接 索 引 等 c 数 据 元 素 采 用 不 同 的 存 储 结 构, 其 数 据 处 理 的 效 率 是 不 同 的 2.2 数 据 结 构 的 图 形 表 示 一 般 用 一 个 中 间 标 有 元 素 值 的 方 框 表 示 一 个 数 据 元 素, 用 一 条 有 向 线 段 从 前 件 结 点 指 向 后 件 结 点 春 夏 秋 冬 儿 子 父 亲 女 儿 在 数 据 结 构 中, 没 有 前 件 的 结 点 成 为 根 结 点 ( 如 上 图 中 的 春 与 父 亲 ); 没 有 后 件 的 结 点 称 为 终 端 结 点 ( 也 称 为 叶 子 结 点, 如 上 图 中 的 冬 与 儿 子 和 女 儿 ) 注 意 : 在 进 行 处 理 时, 一 个 数 据 结 构 中 的 元 素 结 点 可 能 是 在 动 态 变 化 的 这 种 变 化 可 能 是 元 素 结 点 的 个 数 发 生 变 化, 也 可 以 是 元 素 结 点 的 先 后 顺 序 发 生 变 化 2.3 线 性 结 构 与 非 线 性 结 构 空 的 数 据 结 构 是 : 一 个 数 据 元 素 都 没 有 的 数 据 结 构 根 据 数 据 结 构 中 各 数 据 元 素 之 间 前 后 件 关 系 的 复 杂 程 度, 可 将 数 据 结 构 分 为 二 大 类 : 线 性 结 构 和 非 线 性 结 构 一 个 非 空 的 数 据 结 构 满 足 下 列 两 个 条 件, 则 为 线 性 结 构, 线 性 结 构 又 称 为 线 性 表 a. 有 且 只 有 一 个 根 结 点 ; b. 每 一 个 结 点 最 多 有 一 个 前 件, 也 最 多 有 一 个 后 件 在 上 图 中, 左 边 的 是 线 性 结 构, 而 右 边 的 是 非 线 性 结 构 注 意 : 线 性 结 构 与 非 线 性 结 构 都 可 以 是 空 的 数 据 结 构 一 个 空 的 数 据 结 构 究 竟 属 于 线 性 结 构 还 是 属 于 非 线 性 结 构, 要 根 据 具 体 情 况 来 确 定 如 果 对 该 数 据 结 构 的 运 算 是 按 线 性 结 构 的 规 则 来 处 理 的, 则 属 于 线 性 结 构 ; 否 则 属 于 非 线 性 结 构 1 数 据 的 存 储 结 构 是 指 ( )[2005.4] A) 存 储 在 外 存 中 的 数 据 B) 数 据 所 占 的 存 储 空 间 量 C) 数 据 在 计 算 机 中 的 顺 序 存 储 方 式 D) 数 据 的 逻 辑 结 构 中 计 算 机 中 的 表 示 2 下 列 叙 述 中 正 确 的 是 ( )[2005.9] A) 一 个 逻 辑 数 据 结 构 只 能 有 一 种 存 储 结 构 第 2 页, 共 26 页

3 B) 数 据 的 逻 辑 结 构 属 于 线 性 结 构, 存 储 结 构 属 于 非 线 性 结 构 C) 一 个 逻 辑 数 据 结 构 可 以 有 多 种 存 储 结 构, 且 各 种 存 储 结 构 不 影 响 数 据 处 理 的 效 率 D) 一 个 逻 辑 数 据 结 构 可 以 有 多 种 存 储 结 构, 且 各 种 存 储 结 构 影 响 数 据 处 理 的 效 率 1.3 线 性 表 及 其 顺 序 存 储 结 构 3.1 线 性 表 的 基 本 概 念 非 空 线 性 表 的 结 构 特 征 如 下 : a. 有 且 只 有 一 个 根 结 点, 它 无 前 件 ; b. 有 且 只 有 一 个 终 端 结 点, 它 无 后 件 ; c. 除 根 结 点 与 终 端 结 点 外, 其 他 所 有 结 点 有 且 只 有 一 个 前 件, 也 有 且 只 有 一 个 后 件 春 夏 秋 冬 线 性 表 中 结 点 的 个 数 n 称 为 线 性 表 的 长 度 当 n=0 时, 称 为 空 表 3.2 线 性 表 的 顺 序 存 储 结 构 线 性 表 的 顺 序 存 储 结 构 具 有 以 下 两 个 基 本 特 点 : a. 线 性 表 中 所 有 元 素 所 占 的 存 储 空 间 是 连 续 的 ; b. 线 性 表 中 各 数 据 元 素 在 存 储 空 间 中 是 按 逻 辑 顺 序 依 次 存 放 的 注 意 : 在 线 性 表 的 顺 序 存 储 结 构 中, 其 前 后 件 两 个 元 素 在 存 储 空 间 中 是 紧 邻 的, 且 前 件 元 素 一 定 在 后 件 元 素 的 前 面 在 线 性 表 的 顺 序 存 储 结 构 中, 如 第 一 个 元 素 的 地 址 为 ADR(a1), 每 个 元 素 占 用 的 存 储 空 间 大 小 为 k 个 字 节, 则 线 性 表 中 第 i 个 元 素 的 存 储 地 址 为 :ADR(a1)+(i-1)*k 春 夏 秋 冬 春 夏 秋 冬 3.3 顺 序 表 的 插 入 运 算 在 线 性 表 的 顺 序 存 储 结 构 中, 当 插 入 元 素 时, 插 入 点 后 的 元 素 都 要 向 后 移 动 一 位, 以 让 出 一 个 存 储 空 间 在 平 均 情 况 下, 要 在 线 性 表 中 插 入 一 个 新 元 素, 需 要 移 动 表 中 一 半 的 元 素 因 此, 在 线 性 表 顺 序 存 储 的 情 况 下, 要 插 入 一 个 新 元 素, 其 效 率 是 很 低 的 3.4 顺 序 表 的 删 除 运 算 在 线 性 表 的 顺 序 存 储 结 构 中, 当 删 除 元 素 时, 删 除 点 后 的 元 素 都 要 向 前 移 动 一 位, 以 保 证 元 素 都 是 相 邻 存 储 的 在 平 均 情 况 下, 要 在 线 性 表 中 删 除 一 个 元 素, 需 要 移 动 表 中 一 半 的 元 素 因 此, 在 线 性 表 顺 序 存 储 的 情 况 下, 要 删 除 一 个 元 素, 其 效 率 是 很 低 的 1.4 栈 和 队 列 4.1 栈 及 其 基 本 运 算 1. 什 么 是 栈 栈 是 一 种 特 殊 的 线 性 表 栈 是 限 定 在 一 端 进 行 插 入 与 删 除 的 线 性 表, 允 许 插 入 与 删 除 的 一 端 称 为 栈 顶, 不 允 许 插 入 与 删 除 的 一 端 称 为 栈 底 栈 按 照 " 先 进 后 出 " (FILO) 或 " 后 进 先 出 " (LIFO) 组 织 数 据, 栈 具 有 记 忆 作 用 用 top 表 示 栈 顶 位 置, 用 botton 表 示 栈 底 第 3 页, 共 26 页

4 2. 栈 的 顺 序 存 储 及 其 运 算 栈 的 基 本 运 算 有 三 种 :. 入 栈 运 算 退 栈 运 算 和. 读 栈 顶 元 素 4.2 队 列 及 其 基 本 运 算 1. 什 么 是 队 列 队 列 是 允 许 在 一 端 进 行 插 入 而 在 另 一 端 进 行 删 除 的 特 殊 的 线 性 表 允 许 插 入 的 一 端 称 为 队 尾, 允 许 删 除 的 一 端 称 为 排 头 ( 或 队 头 ) 队 列 又 称 为 " 先 进 先 出 "(FIFO) 或 " 后 进 后 出 "(LILO) 的 线 性 表, 它 体 现 了 " 先 来 先 服 务 " 的 原 则 往 队 列 的 队 尾 插 入 一 个 元 素 称 为 入 队 运 算, 从 队 列 的 排 头 删 除 一 个 元 素 称 为 退 队 运 算 2. 循 环 队 列 及 其 运 算 所 谓 循 环 队 列, 就 是 将 队 列 存 储 空 间 的 最 后 一 个 位 置 绕 到 第 一 个 位 置, 形 成 逻 辑 上 的 环 状 空 间, 供 队 列 循 环 使 用 队 列 空 和 队 列 满 的 条 件 如 下 : 队 列 空 的 条 件 为 s=0 ; 队 列 满 的 条 件 为 s=1 且 front=rear. 循 环 队 列 主 要 有 两 种 基 本 运 算 : 入 队 运 算 和 退 队 运 算 a. 入 队 运 算 : 在 循 环 队 列 的 队 尾 加 入 一 个 新 元 素, 首 先 将 队 尾 指 针 进 一 ( 即 rear=rear+1), 并 当 rear=m+1 时 置 rear=1; 然 后 将 新 元 素 插 入 到 队 尾 指 针 指 向 的 位 置 注 意 : 当 循 环 队 列 非 空 (s=1) 且 队 尾 指 针 等 于 排 头 指 针 时, 说 明 循 环 队 列 已 满, 不 能 进 行 入 队 运 算, 这 种 情 况 称 为 " 上 溢 " b. 退 队 运 算 : 指 在 循 环 队 列 的 排 头 位 置 退 出 一 个 元 素 并 赋 给 指 定 的 变 量 首 先 将 排 头 指 针 进 一 ( 即 front=front+1), 并 当 front=m+1 时 置 front=1; 然 后 将 排 头 指 针 指 向 的 元 素 赋 给 指 定 的 变 量 注 意 : 当 循 环 队 列 为 空 (s=0) 时, 不 能 进 行 退 队 运 算, 这 种 情 况 称 为 " 下 溢 " 1 下 列 关 于 栈 的 描 述 中 错 误 的 是 ( )[2005.4] A) 栈 是 先 进 后 出 的 线 性 表 B) 栈 只 能 顺 序 存 储 C) 栈 具 有 记 忆 作 用 D) 对 栈 的 插 入 与 删 除 操 作 中, 不 需 要 改 变 栈 底 指 针 2 按 照 " 后 进 先 出 " 原 则 组 织 数 据 的 数 据 结 构 是 ( )[2006.4] A) 队 列 B) 栈 C) 双 向 链 表 D) 二 叉 树 3 列 关 于 栈 的 描 述 正 确 的 是 ( )[2005.9] A) 在 栈 中 只 能 插 入 元 素 而 不 能 删 除 元 素 B) 在 栈 中 只 能 删 除 元 素 而 不 能 插 入 元 素 C) 栈 是 特 殊 的 线 性 表, 只 能 在 一 端 插 入 或 删 除 元 素 D) 栈 是 特 殊 的 线 性 表, 只 能 在 一 端 插 入 元 素, 而 在 另 一 端 删 除 元 素 第 4 页, 共 26 页

5 4 数 据 结 构 分 为 逻 辑 结 构 和 存 储 结 构, 循 环 队 列 属 于 结 构 [2005.9] 5 按 先 进 后 出 原 则 组 织 数 据 的 数 据 结 构 是 [2006.9] 1.5 线 性 链 表 5.1 线 性 链 表 的 基 本 概 念 1. 链 式 存 储 在 顺 序 存 储 方 式 中 所 有 的 数 据 元 素 在 内 存 中 是 相 邻 存 放 的, 从 而 造 成 了 在 插 入 与 删 除 数 据 元 素 时, 需 要 大 量 移 动 相 应 的 数 据 元 素 为 了 解 决 这 种 问 题, 可 以 将 每 个 数 据 元 素 存 储 在 内 存 中 不 相 邻 的 不 同 位 置, 并 利 用 上 一 个 数 据 元 素 在 存 有 数 据 的 同 时, 也 存 放 下 一 个 数 据 元 素 所 在 的 位 置 地 址 ( 称 为 一 个 存 储 单 元, 即 结 点 ), 以 便 查 找 这 就 是 链 式 存 储 方 式 在 链 式 存 储 方 式 中, 要 求 每 个 结 点 由 两 部 分 组 成 : 一 部 分 用 于 存 放 数 据 元 素 值, 称 为 数 据 域 ; 另 一 部 分 用 于 存 放 地 址, 称 为 指 针 域 其 中 指 针 用 于 指 向 该 结 点 的 前 一 个 或 后 一 个 结 点 ( 即 前 件 或 后 件 ) 注 意 :a 在 链 式 存 储 结 构 中, 存 储 数 据 结 构 的 存 储 空 间 可 以 不 连 续, 各 数 据 结 点 的 存 储 顺 序 与 数 据 元 素 之 间 的 头 结 点 开 始 结 点 终 端 结 点 head a 1 a 2 a n 逻 辑 关 系 可 以 不 一 致, 而 数 据 元 素 之 间 的 逻 辑 关 系 是 由 指 针 域 来 确 定 的 b 链 式 存 储 方 式 既 可 以 用 于 表 示 线 性 结 构, 也 可 以 用 于 表 示 非 线 性 结 构 在 用 链 式 结 构 表 示 较 复 杂 的 非 线 性 结 构 时, 其 指 针 域 的 个 数 要 多 一 些 2. 线 性 链 表 线 性 表 的 链 式 存 储 结 构 称 为 线 性 链 表 如 果 结 点 中 有 两 个 指 针, 一 个 用 于 指 向 前 一 个 结 点, 而 另 一 上 用 于 指 向 后 一 个 结 点, 则 称 之 为 双 向 链 表 头 结 点 开 始 结 点 终 端 结 点 dhead a 1 a 2 a n 3. 带 链 的 栈 : 栈 的 链 式 存 储 结 构 称 为 带 链 的 栈 4. 带 链 的 队 列 : 队 列 的 链 式 存 储 结 构 称 为 带 链 的 队 列 5.2 线 性 链 表 的 基 本 运 算 : 查 找 插 入 删 除 1 下 列 对 于 线 性 链 表 的 描 述 中 正 确 的 是 ( )[2005.4] A) 存 储 空 间 不 一 定 是 连 续, 且 各 元 素 的 存 储 顺 序 是 任 意 的 B) 存 储 空 间 不 一 定 是 连 续, 且 前 件 元 素 一 定 存 储 在 后 件 元 素 的 前 面 C) 存 储 空 间 必 须 连 续, 且 前 件 元 素 一 定 存 储 在 后 件 元 素 的 前 面 D) 存 储 空 间 必 须 连 续, 且 各 元 素 的 存 储 顺 序 是 任 意 的 2 下 列 叙 述 中 正 确 的 是 ( )[2006.4] A) 线 性 链 表 是 线 性 表 的 链 式 存 储 结 构 B) 栈 与 队 列 是 非 线 性 结 构 C) 双 向 链 表 是 非 线 性 结 构 D) 只 有 根 结 点 的 二 叉 树 是 线 性 结 构 3 数 据 结 构 分 为 线 性 结 构 和 非 线 性 结 构, 带 链 的 队 列 属 于 [2006.9] 1.6 树 与 二 叉 树 6.1 树 的 基 本 概 念 树 是 一 种 简 单 的 非 线 性 结 构, 所 有 元 素 之 间 具 有 明 显 的 层 次 特 性 a. 在 树 结 构 中, 每 一 个 结 点 只 有 一 个 前 件, 称 为 父 结 点, 没 有 前 件 的 结 点 只 有 一 个, 称 为 树 的 根 结 点, 简 称 为 树 的 根 b. 在 树 结 构 中, 一 个 结 点 所 拥 有 的 后 件 个 数 称 为 该 结 点 的 度 ; 在 树 中, 所 有 结 点 中 的 最 大 的 度 称 为 树 的 度 c. 树 具 有 明 显 的 层 次 关 系, 即 树 是 一 种 层 次 结 构 d. 数 的 最 大 层 次 称 为 树 的 深 度 第 5 页, 共 26 页

6 E f. 在 树 中, 叶 子 结 点 没 有 子 树 B F 6.2 二 叉 树 及 其 基 本 性 质 1. 什 么 是 二 叉 树 : 二 叉 树 是 一 种 很 有 用 的 非 线 性 结 构 二 叉 树 具 有 以 下 两 个 特 点 : a. 非 空 二 叉 树 只 有 一 个 根 结 点 ; b. 每 一 个 结 点 最 多 有 两 棵 子 树, 且 分 别 称 为 该 结 点 的 左 子 树 与 右 子 树 由 以 上 特 点 可 以 看 出, 在 二 叉 树 中, 每 一 个 结 点 的 度 最 大 为 2 2. 二 叉 树 的 基 本 性 质 :( 重 要 ) A a. 在 二 叉 树 的 第 k 层 上, 最 多 有 2 k-1 (k>=1) 个 结 点 b. 深 度 为 m 的 二 叉 树 最 多 有 2 m -1 个 结 点 深 度 为 m 的 二 叉 树 是 指 二 叉 树 共 有 m 层 c. 在 任 意 一 棵 二 叉 树 中, 度 为 0 的 结 点 ( 即 叶 子 结 点 ) 总 是 比 深 度 为 2 的 结 点 多 一 个 d. 具 有 n 个 结 点 的 二 叉 树, 其 深 度 至 少 为 [log 2 n ]+1, 其 中 [log 2 n ] 表 示 取 log 2 n 的 整 数 部 分 3. 满 二 叉 树 与 完 全 二 叉 树 C G J 满 二 叉 树 与 完 全 二 叉 树 是 两 种 特 殊 形 态 的 二 叉 树 a. 满 二 叉 树 : 除 最 后 一 层 外, 每 一 层 上 的 所 有 结 点 都 有 两 个 子 结 点 这 就 是 说, 在 满 二 叉 树 中, 每 一 层 上 的 结 点 数 都 达 到 最 大 值, 即 在 满 二 叉 树 的 第 k 层 上 有 2k-1 个 结 点, 且 深 度 为 m 的 满 二 叉 树 有 2m-1 个 结 点 b. 完 全 二 叉 树 : 除 最 后 一 层 外, 每 一 层 上 的 结 点 数 均 达 到 最 大 值 ; 在 最 后 一 层 上 只 缺 少 右 边 的 若 干 结 点 注 意 : 满 二 叉 树 也 是 完 全 二 叉 树, 而 完 全 二 叉 树 一 般 不 是 满 二 叉 树 完 全 二 叉 树 还 具 有 以 下 性 质 : H K 树 形 表 示 法 D a. 具 有 n 个 结 点 的 完 全 二 叉 树 的 深 度 为 log 2 n ] +1 I L M 如 左 图 中, 1 A 为 根 结 点 ; 2 E F J H K L M 为 叶 子 结 点 3 树 中 A I 都 有 3 个 子 结 点, 故 树 的 度 为 3 4 整 个 树 中, 总 共 分 为 4 层, 故 树 的 深 度 为 4 二 叉 树 A 第 四 层 中, 最 多 有 =2 3 =8 个 结 点 B 树 的 深 度 为 4, 最 多 有 2 4-1=16-1=15 个 结 点 C 度 为 0 的 结 点 有 8 个, 度 为 2 的 结 点 有 7 个 完 全 二 叉 树 满 二 叉 树 非 满 二 叉 树 6.3 二 叉 树 的 存 储 结 构 在 计 算 机 中, 二 叉 树 通 常 采 用 链 式 存 储 结 构 6.4 二 叉 树 的 遍 历 :( 重 要 ) 在 先 左 后 右 的 原 则 下, 根 据 访 问 根 结 点 的 次 序, 二 叉 树 的 遍 历 可 以 分 为 三 种 : 前 序 遍 历 中 序 遍 历 后 序 遍 第 6 页, 共 26 页

7 历 a. 前 序 遍 历 : 首 先 访 问 根 结 点, 然 后 遍 历 左 子 树, 最 后 遍 历 右 子 树 b. 中 序 遍 历 : 首 先 遍 历 左 子 树, 然 后 访 问 根 结 点, 最 后 遍 历 右 子 树 c. 后 序 遍 历 : 首 先 遍 历 左 子 树, 然 后 遍 历 右 子 树, 最 后 访 问 根 结 点 F 1 5 F F 9 C 2 E 6 2 C 6 E C 4 E 8 A 3 D 4 G 7 1 A 4 D 8 G A 1 D 3 G 7 B 5 H 8 P 9 3 B 7 H 9 P B 2 H 5 P 6 前 序 :FCADBEGHP 中 序 :ACBDFEHGP 后 序 :ABDCHPGEF 注 意 : 在 树 结 构 中, 每 一 个 结 点 都 代 表 一 棵 子 树 前 序 遍 历 中 一 定 以 根 结 点 开 头, 后 序 遍 历 一 定 以 根 结 点 结 尾, 而 中 序 遍 历 中, 根 结 点 前 面 的 为 树 的 左 子 树, 而 其 后 面 的 为 树 的 右 子 树 1 在 深 度 为 7 的 满 二 叉 树 中, 叶 子 结 点 的 个 数 为 ()[2006.4] A)32 B)31 C)64 D)63 2 对 下 图 1 所 示 二 叉 树 图 1 图 2 进 行 中 序 遍 历 的 结 果 是 [2006.9] A)ACBDFEG B)ACBDFGE C)ABDCGEF D)FCADBEG 3 对 如 下 图 2 所 示 二 叉 树, 进 行 后 序 遍 历 的 结 果 为 ()[2006.4] A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA 4 某 二 叉 树 中, 度 为 2 的 结 点 有 18 个, 则 该 二 叉 树 中 有 个 叶 子 结 点 [2005.4] 5 一 棵 二 叉 树 第 六 层 ( 根 结 点 为 第 一 层 ) 的 结 点 数 最 多 为 个 [2005.9] 1.7 查 找 技 术 7.1 顺 序 查 找 : 顺 序 查 找 的 方 法 是 : 用 被 查 元 素 与 线 性 表 中 的 元 素 逐 一 比 较, 直 到 找 出 相 等 的 元 素, 则 查 找 成 功 ; 或 者 找 遍 所 有 元 素 都 不 相 等, 则 查 找 失 败 顺 序 查 找 的 优 点 : 对 线 性 表 的 元 素 的 逻 辑 次 序 无 要 求 ( 不 必 对 元 素 进 行 排 序 ), 对 线 性 表 的 存 储 结 构 无 要 求 ( 顺 序 存 储 链 接 存 储 皆 可 ) 顺 序 查 找 的 效 率 很 低, 但 在 以 下 情 况 下, 只 能 采 用 顺 序 查 找 : a. 如 果 线 性 表 为 无 序 表, 则 不 管 是 顺 序 存 储 结 构 还 是 链 式 存 储 结 构, 都 只 能 用 顺 序 查 找 b. 即 使 是 有 序 线 性 表, 如 果 采 用 链 式 存 储 结 构, 也 只 能 用 顺 序 查 找 7.2 二 分 法 查 找 : 第 7 页, 共 26 页

8 二 分 法 查 找 是 一 种 效 率 较 高 的 线 性 表 查 找 方 法 要 进 行 二 分 法 查 找, 则 线 性 表 结 点 必 须 是 排 好 序 的, 且 线 性 表 以 顺 序 方 式 存 储 二 分 法 查 找 的 方 法 : 首 先 用 要 查 找 的 元 素 值 与 线 性 表 中 间 位 置 的 元 素 值 相 比 较, 这 个 中 间 结 点 把 线 性 表 分 成 了 两 个 子 表, 比 较 相 等 则 查 找 完 成, 不 等 则 根 据 比 较 结 果 确 定 下 一 步 的 查 找 应 在 哪 一 个 子 表 中 进 行, 如 此 进 行 下 去, 直 到 找 到 满 足 条 件 的 结 点, 或 者 确 定 表 中 没 有 这 样 的 结 点 对 于 二 分 法 查 找 的 缺 点 是 线 性 表 排 序 需 花 费 时 间, 顺 序 方 式 存 储 的 插 入 删 除 不 便 注 意 : 对 于 长 度 为 n 的 有 序 线 性 表, 在 最 坏 的 情 况 下, 二 分 查 找 只 需 要 比 较 比 较 [log 2 n] 次, 而 顺 序 查 找 需 要 比 较 n 次 二 分 查 找 的 效 率 要 比 顺 序 查 找 高 得 多 1 在 长 度 为 64 的 有 序 线 性 表 中 进 行 顺 序 查 找, 最 坏 情 况 下 需 要 比 较 的 次 数 为 ( )[2006.9] A)63 B)64 C)6 D)7 2 下 列 数 据 结 构 中, 能 用 二 分 法 进 行 查 找 的 是 ( )[2005.9] A) 顺 序 存 储 的 有 序 线 性 表 B) 线 性 链 表 C) 二 叉 链 表 D) 有 序 线 性 链 表 3 对 长 度 为 n 的 线 性 表 进 行 顺 序 查 找, 在 最 坏 情 况 下 所 需 要 的 比 较 次 数 为 ( )[2005.4] A)log 2 n B) n/2 C) n D) n 排 序 技 术 ( 记 住 每 种 排 序 的 比 较 次 数 ) 排 序 是 指 将 一 个 无 序 序 列 整 理 成 按 值 非 递 减 顺 序 排 列 的 有 序 序 列 8.1 交 换 类 排 序 法 交 换 类 排 序 的 基 本 思 想 : 两 两 比 较 待 排 序 线 性 表 的 元 素 值, 并 对 不 满 足 顺 序 要 求 的 元 素 进 行 位 置 交 换, 直 到 全 部 满 足 为 止. 1 冒 泡 排 序 法 将 相 邻 的 元 素 进 行 两 两 比 较, 若 为 逆 序 则 进 行 交 换 将 线 性 表 照 此 方 法 从 头 到 尾 处 理 一 遍 称 作 一 趟 起 泡, 一 趟 起 泡 的 效 果 是 将 元 素 值 最 大 的 记 录 交 换 到 了 最 后 的 位 置, 即 该 线 性 表 的 最 终 位 置 若 某 一 趟 起 泡 过 程 中 没 有 发 生 任 何 交 换, 则 排 序 过 程 结 束 在 最 坏 情 况 下, 需 要 的 比 较 N(N-1)/2 次 2 快 速 排 序 法 快 速 排 序 又 称 分 区 交 换 排 序, 是 对 冒 泡 排 序 的 一 种 改 进 其 基 本 方 法 是 : 在 待 排 序 线 性 表 中 任 取 一 个 元 素, 以 它 为 基 准 用 交 换 的 方 法 将 所 有 的 元 素 分 成 两 部 分, 元 素 值 比 它 小 的 在 一 个 部 分, 元 素 值 比 它 大 的 在 另 一 个 部 分 再 分 别 对 两 个 部 分 实 施 上 述 过 程, 一 直 重 复 到 排 序 完 成 在 最 坏 的 情 况 下 与 冒 泡 排 序 相 当, 然 而 快 速 排 序 的 平 均 执 行 时 间 为 O(nlog 2n ) 8.2 插 入 类 排 序 法 插 入 排 序 的 基 本 思 想 是 : 每 步 将 一 个 待 排 序 元 素 按 其 元 素 值 的 大 小 插 入 到 前 面 已 排 序 的 元 素 中 的 适 当 位 置 上, 直 到 全 部 记 录 插 入 完 为 止 1 简 单 插 入 排 序 它 是 指 将 无 序 序 列 中 的 各 元 素 依 次 插 入 到 已 经 有 序 的 线 性 表 中 在 最 坏 情 况 下 比 较 需 要 N(N-1)/2 次 2 希 尔 排 序 法 希 尔 排 序 的 基 本 思 想 是 把 元 素 按 下 标 的 一 定 增 量 分 组, 对 每 组 元 素 使 用 插 入 排 序, 随 增 量 的 逐 渐 减 小, 所 分 成 的 组 包 含 的 记 录 越 来 越 多, 到 增 量 的 值 减 小 到 1 时, 整 个 数 据 合 成 一 组, 构 成 一 组 有 序 元 素, 故 其 属 于 插 入 排 序 方 法 在 最 坏 情 况 下 需 要 的 比 较 O(n 1.5 ) 次 8.3 选 择 类 排 序 法 选 择 排 序 的 基 本 思 想 是 : 每 次 从 待 排 序 的 元 素 中 选 出 元 素 值 最 小 ( 或 最 大 ) 的 记 录, 顺 序 放 在 已 排 序 的 记 录 第 8 页, 共 26 页

9 序 列 的 最 后, 直 到 全 部 排 完 1 简 单 选 择 排 序 对 线 性 表 进 行 n-1 趟 扫 描, 第 i 趟 扫 描 从 剩 下 的 n-i+1 个 记 录 中 选 出 元 素 值 最 小 的 记 录, 与 第 i 个 记 录 交 换 最 坏 情 况 下 需 要 比 较 N(N-1)/2 次 2 堆 排 序 堆 排 序 的 基 本 思 想 是 : 对 待 排 序 的 线 性 表, 首 先 把 它 们 按 堆 的 定 义 排 成 一 个 序 列 ( 称 为 建 堆 ), 这 就 找 到 了 最 小 的 元 素, 然 后 将 最 小 的 元 素 取 出, 用 剩 下 的 元 素 再 建 堆, 便 得 到 次 最 小 的 的 元 素, 如 此 反 复 进 行, 直 到 将 全 部 元 素 排 好 序 为 止 在 最 坏 怀 况 下 需 要 比 较 O(nlog 2 n ) 次 8.4 总 结 假 设 线 性 表 的 长 度 为 n, 在 最 坏 的 情 况 下 进 行 比 较 的 次 数 : 1 交 换 类 排 序 法 2 插 入 类 排 序 法 3 选 择 类 排 序 法 1 冒 泡 排 序 法 : n(n-1)/2 2 快 速 排 序 法 : n(n-1)/2 3 简 单 插 入 排 序 法 : n(n-1)/2 4 希 尔 排 序 法 : O(n 1.5 ) 5 简 单 选 择 排 序 法 : n(n-1)/2 6 堆 排 序 法 : O(nlog 2n ) 1 对 于 长 度 为 n 的 线 性 表, 在 最 坏 情 况 下, 下 列 各 排 序 法 所 对 应 的 比 较 次 数 中 正 确 的 是 (_)[2005.4] A) 冒 泡 排 序 为 n/2 B) 冒 泡 排 序 为 n C) 快 速 排 序 为 n D) 快 速 排 序 为 n(n-1)/2 2 对 长 度 为 10 的 线 性 表 进 行 冒 泡 排 序, 最 坏 情 况 下 需 要 比 较 的 次 数 为 [2006.4] 总 复 习 图 : 数 据 结 构 与 算 法 算 法 数 据 结 构 定 义 : 是 指 解 题 方 案 的 准 确 而 完 整 的 描 述 特 征 : 是 可 行 性 确 定 性 有 穷 性 和 拥 有 足 够 的 情 报 复 杂 度 : 包 括 时 间 复 杂 度 和 空 间 复 杂 度 数 据 的 逻 辑 结 构 数 据 的 存 储 结 构 线 性 结 构 非 线 性 结 构 顺 序 存 储 链 式 存 储 顺 序 存 储 : 栈 与 队 列 链 式 存 储 : 链 表 双 向 链 表 带 链 的 栈 带 链 的 队 列 1.9 精 典 模 拟 题 数 据 的 运 算 排 序 : 交 换 类 插 入 类 和 选 择 类 查 找 : 顺 序 查 找 二 分 查 找 插 入 与 删 除 一. 选 择 题 1. 算 法 的 时 间 复 杂 度 是 指 A. 执 行 算 法 程 序 所 需 要 的 时 间 B. 算 法 程 序 的 长 度 C. 算 法 执 行 过 程 中 所 需 要 的 基 本 运 算 次 数 D. 算 法 程 序 中 的 指 令 条 数 2. 算 法 的 空 间 复 杂 度 是 指 A. 算 法 程 序 的 长 度 B. 算 法 程 序 中 的 指 令 条 数 第 9 页, 共 26 页

10 C. 算 法 程 序 所 占 的 存 储 空 间 D. 算 法 执 行 过 程 中 所 需 要 的 存 储 空 间 3. 下 面 叙 述 正 确 的 是 A. 算 法 的 执 行 效 率 与 数 据 的 存 储 结 构 无 关 B. 算 法 的 空 间 复 杂 度 是 指 算 法 程 序 中 指 令 ( 或 语 句 ) 的 条 数 C. 算 法 的 有 穷 性 是 指 算 法 必 须 能 在 执 行 有 限 个 步 骤 之 后 终 止 D. 以 上 三 种 描 述 都 不 对 4. 在 计 算 机 中, 算 法 是 指 A. 查 询 方 法 B. 加 工 方 法 C. 解 题 方 案 的 准 确 而 完 整 的 描 述 D. 排 序 方 法 5. 算 法 一 般 都 可 以 用 哪 几 种 控 制 结 构 组 合 而 成 A. 循 环 分 支 递 归 B. 顺 序 循 环 嵌 套 C. 循 环 递 归 选 择 D. 顺 序 选 择 循 环 6. 算 法 分 析 的 目 的 是 (D) A. 找 出 数 据 结 构 的 合 理 性 B. 找 出 算 法 中 输 入 和 输 出 之 间 的 关 系 C. 分 析 算 法 的 易 懂 性 和 可 靠 性 D. 分 析 算 法 的 效 率 以 求 改 进 7. 下 列 列 关 于 算 法 的 叙 述 中, 正 确 的 是 A. 算 法 是 解 决 问 题 的 实 现 程 序 B. 算 法 是 解 决 问 题 的 计 算 方 法 C. 程 序 的 实 现 可 以 优 于 算 法 的 设 计 D. 算 法 的 基 本 特 征 是 可 行 性 确 定 性 有 穷 性 和 拥 有 足 够 的 情 报 8. 下 列 叙 述 中 正 确 的 是 A) 线 性 表 是 线 性 结 构 B) 栈 与 队 列 是 非 线 性 结 构 C) 线 性 链 表 是 非 线 性 结 构 D) 二 叉 树 是 线 性 结 构 9. 数 据 的 存 储 结 构 是 指 A) 数 据 所 占 的 存 储 空 间 量 B) 数 据 的 逻 辑 结 构 在 计 算 机 中 的 表 示 C) 数 据 在 计 算 机 中 的 顺 序 存 储 方 式 D) 存 储 在 外 存 中 的 数 据 10. 下 列 关 于 队 列 的 叙 述 中 正 确 的 是 A) 在 队 列 中 只 能 插 入 数 据 B) 在 队 列 中 只 能 删 除 数 据 C) 队 列 是 先 进 先 出 的 线 性 表 D) 队 列 是 先 进 后 出 的 线 性 表 11. 下 列 关 于 栈 的 叙 述 中 正 确 的 是 A) 在 栈 中 只 能 插 入 数 据 B) 在 栈 中 只 能 删 除 数 据 C) 栈 是 先 进 先 出 的 线 性 表 D) 栈 是 先 进 后 出 的 线 性 表 12. 以 下 数 据 结 构 中 不 属 于 线 性 数 据 结 构 的 是 A. 队 列 B. 线 性 表 C. 二 叉 树 D. 栈 13. 数 据 的 存 储 结 构 是 指 A. 数 据 所 占 的 存 储 空 间 量 B. 数 据 的 逻 辑 结 构 在 计 算 机 中 的 表 示 C. 数 据 在 计 算 机 中 的 顺 序 存 储 方 式 D. 存 储 在 外 存 中 的 数 据 14. 栈 和 队 列 的 共 同 点 是 A. 都 是 先 进 后 出 B. 都 是 先 进 先 出 C. 只 允 许 在 端 点 处 插 入 和 删 除 元 素 D. 没 有 共 同 点 15. 用 链 表 表 示 线 性 表 的 优 点 是 A. 便 于 插 入 和 删 除 操 作 B. 数 据 元 素 的 物 理 顺 序 与 逻 辑 顺 序 相 同 C. 花 费 的 存 储 空 间 较 顺 序 存 储 少 D. 便 于 随 机 存 取 16. 链 表 不 具 有 的 特 点 是 A) 不 必 事 先 估 计 存 储 空 间 B) 可 随 机 访 问 任 一 元 素 C) 插 入 删 除 不 需 要 移 动 元 素 D) 所 需 空 间 与 线 性 表 长 度 成 正 比 17. 如 果 进 栈 序 列 为 e1,e2,e3,e4, 则 可 能 的 出 栈 序 列 是 A)e3,e1,e4,e2 B)e2,e4,e3,e1 C)e3,e4,e1,e2 D) 任 意 顺 序 18. 设 有 下 列 二 叉 树 : 第 10 页, 共 26 页

11 A B C D E F 对 此 二 叉 树 中 序 遍 历 的 结 果 为 A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA 19. 在 深 度 为 5 的 满 二 叉 树 中, 叶 子 结 点 的 个 数 为 A)32 B)31 C)16 D) 设 树 T 的 度 为 4, 其 中 度 为 1,2,3,4 的 结 点 个 数 分 别 为 4,2,1,1 则 T 树 中 叶 子 结 点 数 为 A)8 B)7 C)6 D)5 21. 在 一 棵 二 叉 树 上 第 5 层 的 结 点 数 最 多 是 A. 8 B. 16 C. 32 D 设 一 棵 完 全 二 叉 树 共 有 699 个 结 点, 则 在 该 二 叉 树 中 的 叶 子 结 点 数 为 A. 349 B. 350 C. 255 D 在 深 度 为 5 的 满 二 叉 树 中, 结 点 的 个 数 为 A. 32 B. 31 C. 16 D 已 知 二 叉 树 后 序 遍 历 序 列 是 dabec, 中 序 遍 历 序 列 是 debac, 它 的 前 序 遍 历 序 列 是 A. cedba B. acbed C. decab D. deabc 25. 已 知 二 叉 树 前 序 遍 历 序 列 deabc, 是 后 序 遍 历 序 列 是 dabec, 中 序 遍 历 序 列 是 A)debac B)decab C)deabc D)cedba 26. 已 知 一 棵 二 叉 树 前 序 遍 历 和 中 序 遍 历 分 别 为 ABDEGCFH 和 DBGEACHF, 则 该 二 叉 树 的 后 序 遍 历 为 A)GEDHFBCA B)DGEBHFCA C)ABCDEFGH D)ACBFEDHG 27. 树 是 结 点 的 集 合, 它 的 根 结 点 数 目 是 A) 有 且 只 有 1 B)1 或 多 于 1 C)0 或 1 D) 至 少 线 性 表 若 采 用 链 式 存 储 结 构 时, 要 求 内 存 中 可 用 存 储 单 元 的 地 址 A) 必 须 是 连 续 的 B) 部 分 地 址 必 须 是 连 续 的 C) 一 定 是 不 连 续 的 D) 连 续 不 连 续 都 可 以 29. 下 列 叙 述 中, 错 误 的 是 A) 数 据 的 存 储 结 构 与 数 据 处 理 的 效 率 密 切 相 关 B) 数 据 的 存 储 结 构 与 数 据 处 理 的 效 率 无 关 C) 数 据 的 存 储 结 构 在 计 算 机 中 所 占 的 空 间 不 一 定 是 连 续 的 D) 一 种 数 据 的 逻 辑 结 构 可 以 有 多 种 存 储 结 构 30. 对 于 长 度 为 n 的 线 性 表, 在 最 坏 情 况 下, 下 列 各 排 序 法 所 对 应 的 比 较 次 数 中 正 确 的 是 A) 冒 泡 排 序 为 n/2 B) 冒 泡 排 序 为 n C) 快 速 排 序 为 n D) 快 速 排 序 为 n(n-1)/2 正 确 答 案 : 1-5:C D C C D 6-10:D D A B C 11-15:D C B C A 16-20:B B B C A 21-25:B B B D A 26-30:B A D B D 二. 填 空 题 1. 在 计 算 机 中, 算 法 是 指 解 题 方 案 的 准 确 而 完 整 的 描 述 2. 算 法 的 时 间 复 杂 度 是 指 算 法 执 行 过 程 中 所 需 要 的 基 本 运 算 次 数 3. 算 法 的 空 间 复 杂 度 是 指 执 行 过 程 中 所 需 要 的 存 储 空 间 4. 算 法 分 析 的 目 的 是 分 析 算 法 的 效 率 以 求 改 进 5. 算 法 的 基 本 特 征 是 可 行 性 确 定 性 有 穷 性 和 拥 有 足 够 的 情 报 6. 算 法 的 复 杂 度 主 要 包 括 时 间 复 杂 度 和 空 间 复 杂 度 7. 一 个 计 算 机 系 统 能 执 行 的 所 有 指 令 的 集 合, 称 为 该 计 算 机 系 统 的 指 令 系 统 8. 栈 的 基 本 运 算 有 三 种 : 入 栈 退 栈 和 读 栈 顶 元 素 9. 队 列 主 要 有 两 种 基 本 运 算 : 入 队 运 算 与 退 队 运 算 第 11 页, 共 26 页

12 10. 数 据 结 构 包 括 数 据 的 逻 辑 结 构 数 据 的 存 储 结 构 以 及 对 数 据 的 操 作 运 算 11. 数 据 的 逻 辑 结 构 在 计 算 机 存 储 空 间 中 的 存 放 形 式 称 为 数 据 的 存 储 结 构 或 物 理 结 构 12. 顺 序 存 储 方 法 是 把 逻 辑 上 相 邻 的 结 点 存 储 在 物 理 位 置 相 邻 的 存 储 单 元 中 13. 在 一 个 容 量 为 15 的 循 环 队 列 中, 若 头 指 针 front=6, 尾 指 针 rear=9, 则 该 循 环 队 列 中 共 有 个 元 素 14. 设 一 棵 完 全 二 叉 树 共 有 700 个 结 点, 则 在 该 二 叉 树 中 有 个 叶 子 结 点 15. 设 一 棵 二 叉 树 的 中 序 遍 历 结 果 为 DBEAFC, 前 序 遍 历 结 果 为 ABDECF, 则 后 序 遍 历 结 果 为 16. 在 先 左 后 右 的 原 则 下, 根 据 访 问 根 结 点 的 次 序, 二 叉 树 的 遍 历 可 以 分 为 三 种 : 前 序 遍 历 中 序 遍 历 和 后 序 遍 历 17. 在 最 坏 的 情 况 下, 冒 泡 排 序 的 时 间 复 杂 度 为 18. 在 最 坏 情 况 下, 堆 排 序 需 要 比 较 的 次 数 为 19. 在 长 度 为 n 的 有 序 线 性 表 中 进 行 二 分 查 找 最 坏 的 情 况 下, 需 要 的 比 较 次 数 为 20. 对 于 输 入 为 N 个 数 进 行 快 速 排 序 算 法 的 平 均 时 间 复 杂 度 是 2 程 序 设 计 基 础 2.1 程 序 设 计 设 计 方 法 和 风 格 程 序 的 整 体 风 格 应 该 强 调 简 单 和 清 晰, 程 序 必 须 是 可 以 理 解 的 著 名 的 清 晰 第 一, 效 率 第 二 的 论 点 已 成 为 当 今 主 导 的 程 序 设 计 风 格 要 形 成 良 好 的 程 序 设 计 风 格, 主 要 应 注 重 和 考 虑 以 下 因 素 : 1 源 程 序 文 档 化 2 数 据 说 明 的 方 法 3. 语 句 的 结 构 4 输 入 和 输 出 2.2 结 构 化 程 序 设 计 结 构 化 程 序 设 计 的 原 则 结 构 化 程 序 设 计 方 法 的 主 要 原 则 包 括 :( 重 要 ) 1. 自 顶 向 下 : 程 序 设 计 时, 应 先 考 虑 总 体, 后 考 虑 细 节 ; 先 考 虑 全 局 目 标, 后 考 虑 局 部 目 标 不 要 一 开 始 就 过 多 追 求 众 多 的 细 节, 先 从 最 上 层 总 目 标 开 始 设 计, 逐 步 使 问 题 具 体 化 2. 逐 步 求 精 : 对 复 杂 问 题, 应 设 计 一 些 子 目 标 作 过 渡, 逐 步 细 化 3. 模 块 化 : 一 个 复 杂 问 题, 肯 定 是 由 若 干 稍 简 单 的 问 题 构 成 模 块 化 是 把 程 序 要 解 决 的 总 目 标 分 解 为 分 目 标, 再 进 一 步 分 解 为 具 体 的 小 目 标, 把 每 个 小 目 标 称 为 模 块 4. 限 制 使 用 goto 语 句 结 构 化 程 序 的 基 本 结 构 与 特 点 结 构 化 程 序 的 基 本 结 构 为 顺 序 结 构 选 择 结 构 和 重 复 结 构 三 种 2.3 面 向 对 象 的 程 序 设 计 关 于 面 向 对 象 方 法 面 向 对 象 方 法 的 优 点 :( 重 要 ) 1 与 人 类 习 怪 的 思 维 方 法 一 致 2 稳 定 性 好 3 可 重 用 性 好 4 易 于 开 发 大 型 软 件 产 品 5 可 维 护 性 好 面 向 对 象 方 法 的 基 本 概 念 : 用 辩 证 唯 物 的 认 识 论 来 认 识 世 界 1. 对 象 : 对 象 是 面 向 对 象 方 法 中 最 基 本 的 概 念, 可 以 用 来 表 示 客 观 世 界 中 的 任 何 实 体, 对 象 是 实 体 的 抽 象 面 向 对 象 的 程 序 设 计 方 法 中 的 对 象 是 系 统 中 用 来 描 述 客 观 事 物 的 一 个 实 体, 是 构 成 系 统 的 一 个 基 本 单 位, 由 一 组 表 示 其 静 态 特 征 的 属 性 和 它 可 执 行 的 一 组 操 作 组 成 对 象 的 基 本 特 征 如 下 : a. 标 识 惟 一 性 : 可 通 过 内 在 本 质 来 区 分 b. 分 类 性 : 可 以 将 具 有 相 同 属 性 和 操 作 的 对 象 抽 象 成 类 第 12 页, 共 26 页

13 改 变 c. 多 态 性 : 指 同 一 个 操 作 可 以 是 不 同 对 象 的 行 为 d. 封 装 性 : 从 外 面 不 能 直 接 使 用 对 象 的 处 理 能 力, 也 不 能 直 接 修 改 内 部 状 态, 对 象 的 内 部 状 态 只 能 由 其 自 身 e. 模 块 独 立 性 好 2. 类 和 实 例 将 属 性 操 作 相 似 的 对 象 归 为 类 类 是 具 有 共 同 属 性 共 同 方 法 的 对 象 的 集 合 所 以, 类 是 对 象 的 抽 象, 它 描 述 了 属 于 该 对 象 类 型 的 所 有 对 象 的 性 质 而 一 个 对 象 则 是 其 对 应 类 的 一 个 实 例 3. 消 息 : 对 象 间 的 这 种 相 互 合 作 需 要 一 个 机 制 协 助 进 行, 这 样 的 机 制 称 为 消 息 消 息 是 一 个 实 例 与 另 一 个 实 例 之 间 传 递 的 信 息 4. 继 承 : 继 承 是 指 能 够 直 接 获 得 已 有 的 性 质 和 特 征, 而 不 必 重 复 定 义 他 们 继 承 是 使 用 已 有 的 类 定 义 作 为 基 础 建 立 新 类 的 定 义 技 术, 以 使 新 类 自 动 拥 有 旧 类 的 所 有 特 征 5. 多 态 性 : 多 态 性 是 指 同 样 的 消 息 被 不 同 的 对 象 接 受 时 可 导 致 完 全 不 同 的 行 动 的 现 象 1 下 列 选 项 不 符 合 良 好 程 序 设 计 风 格 的 是 ()[2006.9] A) 源 程 序 要 文 档 化 B) 数 据 说 明 的 次 序 要 规 范 化 C) 避 免 滥 用 goto 语 句 D) 模 块 设 主 地 要 保 证 高 耦 合 高 内 聚 2 下 列 选 项 中 不 属 于 结 构 化 程 序 设 计 方 法 的 是 ()[2006.4] A) 自 顶 向 下 B) 逐 步 求 精 C) 模 块 化 D) 可 复 用 3 在 面 向 对 象 的 方 法 中, 类 的 实 例 称 为 [2005.4] 4 在 面 向 对 象 方 法 中, 描 述 的 是 具 有 相 似 属 性 与 操 作 的 一 组 对 象 [2006.4] 2.4 精 典 模 拟 题 一. 选 择 题 1. 结 构 化 程 序 设 计 主 要 强 调 的 是 A) 程 序 的 规 模 B) 程 序 的 易 读 性 C) 程 序 的 执 行 效 率 D) 程 序 的 可 移 植 性 2. 对 建 立 良 好 的 程 序 设 计 风 格, 下 列 描 述 正 确 的 是 A) 程 序 应 简 单 清 晰 可 读 性 好 B) 符 号 名 的 命 名 只 要 符 合 语 法 C) 充 分 考 虑 程 序 的 执 行 效 率 D) 程 序 的 注 释 可 有 可 无 3. 在 面 向 对 象 方 法 中, 一 个 对 象 请 求 另 一 个 对 象 为 其 服 务 的 方 式 是 通 过 发 送 A) 调 用 语 句 B) 命 令 C) 口 令 D) 消 息 4. 信 息 隐 蔽 的 概 念 与 下 述 哪 一 种 概 念 直 接 相 关? A) 软 件 结 构 定 义 B) 模 块 独 立 性 C) 模 块 类 型 划 分 D) 模 块 耦 合 度 5. 下 面 对 对 象 概 念 描 述 错 误 的 是 A) 任 何 对 象 都 必 须 有 继 承 性 B) 对 象 是 属 性 和 方 法 的 封 装 体 C) 对 象 间 的 通 讯 靠 消 息 传 递 D) 操 作 是 对 象 的 动 态 属 性 6. 下 面 描 述 中, 符 合 结 构 化 程 序 设 计 风 格 的 是 A. 使 用 顺 序 选 择 和 重 复 ( 循 环 ) 三 种 基 本 控 制 结 构 表 示 程 序 的 控 制 逻 辑 B. 模 块 只 有 一 个 入 口, 可 以 有 多 个 出 口 C. 注 重 提 高 程 序 的 执 行 效 率 D. 不 使 用 goto 语 句 7. 下 面 概 念 中, 不 属 于 面 向 对 象 方 法 的 是 (D) 第 13 页, 共 26 页

14 A. 对 象 B. 继 承 C. 类 D. 过 程 调 用 8. 面 向 对 象 的 设 计 方 法 与 传 统 的 的 面 向 过 程 的 方 法 有 本 质 不 同, 它 的 基 本 原 理 是 A. 模 拟 现 实 世 界 中 不 同 事 物 之 间 的 联 系 B. 强 调 模 拟 现 实 世 界 中 的 算 法 而 不 强 调 概 念 C. 使 用 现 实 世 界 的 概 念 抽 象 地 思 考 问 题 从 而 自 然 地 解 决 问 题 D. 鼓 励 开 发 者 在 软 件 开 发 的 绝 大 部 分 中 都 用 实 际 领 域 的 概 念 去 思 考 9. 在 设 计 程 序 时, 应 采 纳 的 原 则 之 一 是 A. 程 序 结 构 应 有 助 于 读 者 理 解 B. 不 限 制 goto 语 句 的 使 用 C. 减 少 或 取 消 注 解 行 D. 程 序 越 短 越 好 10. 结 构 化 程 序 设 计 的 3 种 结 构 是 A) 顺 序 结 构 选 择 结 构 转 移 结 构 B) 分 支 结 构 等 价 结 构 循 环 结 构 C) 多 分 支 结 构 赋 值 结 构 等 价 结 构 D) 顺 序 结 构 选 择 结 构 循 环 结 构 正 确 答 案 :1-5:B A D B A 6-10:A D C A D 二. 填 空 题 1. 结 构 化 程 序 设 计 的 三 种 基 本 逻 辑 结 构 为 顺 序 选 择 和 2. 源 程 序 文 档 化 要 求 程 序 应 加 注 释 注 释 一 般 分 为 序 言 性 注 释 和 3. 在 面 向 对 象 方 法 中, 信 息 隐 蔽 是 通 过 对 象 的 性 来 实 现 的 4. 类 是 一 个 支 持 集 成 的 抽 象 数 据 类 型, 而 对 象 是 类 的 5. 在 面 向 对 象 方 法 中, 类 之 间 共 享 属 性 和 操 作 的 机 制 称 为 6. 结 构 化 程 序 设 计 方 法 的 主 要 原 则 可 以 概 括 为 自 顶 向 下 逐 步 求 精 模 块 化 和 限 制 使 用 goto 语 句 7. 面 向 对 象 的 程 序 设 计 方 法 中 涉 及 的 对 象 是 系 统 中 用 来 描 述 客 观 事 物 的 一 个 实 体 8. 一 个 类 可 以 从 直 接 或 间 接 的 祖 先 中 继 承 所 有 属 性 和 方 法 采 用 这 个 方 法 提 高 了 软 件 的 可 重 用 性 9. 面 向 对 象 的 模 型 中, 最 基 本 的 概 念 是 对 象 和 类 10. 在 面 向 对 象 的 程 序 设 计 中, 类 描 述 的 是 具 有 相 似 性 质 的 一 组 3 软 件 工 程 基 础 软 件 定 义 与 软 件 特 点 计 算 机 软 件 : 是 计 算 机 系 统 中 与 硬 件 相 互 依 存 的 另 一 部 分, 是 包 括 程 序 数 据 及 相 关 文 档 的 完 整 集 合 软 件 的 特 点 : a. 软 件 是 一 种 逻 辑 实 体, 不 是 物 理 实 体, 具 有 抽 象 性 ; b. 软 件 的 生 产 与 硬 件 不 同, 它 没 有 明 显 的 制 作 过 程 ; c. 软 件 在 运 行 使 用 期 间 不 存 在 磨 损 老 化 问 题 ; d. 软 件 的 开 发 运 行 对 计 算 机 系 统 有 依 赖 性, 受 计 算 机 系 统 的 限 制, 这 导 致 软 件 移 植 的 问 题 e. 软 件 复 杂 性 高, 成 本 昂 贵 ; f. 软 件 开 发 涉 及 诸 多 的 社 会 因 素 软 件 危 机 与 软 件 工 程 软 件 危 机 归 结 为 成 本 质 量 生 产 率 等 问 题 软 件 工 程 的 主 要 思 想 是 强 调 在 软 件 开 发 过 程 中 需 要 应 用 工 程 化 原 则, 即 将 软 件 产 品 看 作 是 一 个 工 程 产 品 来 处 理 软 件 工 程 包 括 3 个 要 素, 即 方 法 工 具 和 过 程 软 件 工 程 过 程 与 软 件 生 命 周 期 :( 重 要 ) 1 软 件 工 程 过 程 包 含 4 种 基 本 活 动 : a.p(plan) 软 件 规 格 说 明 规 定 软 件 的 功 能 及 其 运 行 时 的 限 制 b.d(do) 软 件 开 发 产 生 满 足 规 格 说 明 的 软 件 c.c(check) 软 件 确 认 确 认 软 件 能 够 满 足 客 户 提 出 的 要 求 d.a(action) 软 件 演 进 为 满 足 客 户 的 变 更 要 求, 软 件 必 须 在 使 用 的 过 程 中 演 进 2 软 件 生 命 周 期 : 软 件 生 命 周 期 分 为 软 件 定 义 软 件 开 发 及 软 件 运 行 维 护 三 个 阶 段 其 中 软 件 定 义 阶 段 包 含 有 : 可 行 性 研 究 第 14 页, 共 26 页

15 需 求 分 析 两 步 ; 软 件 开 发 阶 段 包 含 有 : 概 要 设 计 详 细 设 计 实 现 和 测 试 ; 软 件 运 行 维 护 阶 段 包 含 有 : 使 用 维 护 和 退 役 软 件 工 程 的 目 标 与 原 则 1. 软 件 工 程 的 目 标 软 件 工 程 的 目 标 是 : 考 试 出 现 时, 只 要 是 达 到 用 最 小 的 人 力 物 力 财 力 和 时 间 而 得 到 最 好 质 时 产 品 的 都 是 基 于 软 件 工 程 的 目 标, 软 件 工 程 的 理 论 和 技 术 性 研 究 的 内 容 主 要 包 括 : 软 件 开 发 技 术 和 软 件 工 程 管 理 2. 软 件 工 程 的 原 则 包 括 : 抽 象 信 息 隐 蔽 模 块 化 局 部 化 确 定 性 一 致 性 完 备 性 和 可 验 证 性 软 件 开 发 工 具 与 软 件 开 发 环 境 软 件 开 发 环 境 或 称 软 件 工 程 环 境 是 全 面 支 持 软 件 开 发 全 过 程 的 软 件 工 具 集 合 1 下 列 描 述 中 正 确 的 是 (2005 年 4 月 选 择 题 第 8 题 ) A) 程 序 就 是 软 件 B) 软 件 开 发 不 受 计 算 机 系 统 的 限 制 C) 软 件 既 是 逻 辑 实 体, 又 是 物 理 实 体 D) 软 件 是 程 序 数 据 与 相 关 文 档 的 集 合 2 下 列 描 述 中 正 确 的 是 (2005 年 9 月 选 择 题 第 5 题 ) A) 软 件 工 程 只 是 解 决 软 件 项 目 的 管 理 问 题 B) 软 件 工 程 主 要 解 决 软 件 产 品 的 生 产 率 问 题 C) 软 件 工 程 的 主 要 思 想 是 强 调 在 软 件 开 发 过 程 中 需 要 应 用 工 程 化 原 则 D) 软 件 工 程 只 是 解 决 软 件 开 发 中 的 技 术 问 题 3 下 列 叙 述 中 正 确 的 是 (2005 年 9 月 选 择 题 第 7 题 ) A) 软 件 交 付 使 用 后 还 需 要 进 行 维 护 B) 软 件 一 旦 交 付 使 用 就 不 需 要 再 进 行 维 护 C) 软 件 交 付 使 用 后 其 生 命 周 期 就 结 束 D) 软 件 维 护 是 修 复 程 序 中 被 破 坏 的 指 令 4 下 列 选 项 中 不 属 于 软 件 生 命 周 期 开 发 阶 段 任 务 的 是 (2006 年 9 月 选 择 题 第 3 题 ) A) 软 件 测 试 B) 概 要 设 计 C) 软 件 维 护 D) 详 细 设 计 3.2 结 构 化 分 析 方 法 结 构 化 方 法 包 括 已 经 形 成 了 配 套 的 结 构 化 分 析 方 法 结 构 化 设 计 方 法 和 结 构 化 变 成 方 法, 其 核 心 和 基 础 是 结 构 化 程 序 设 计 理 论 需 求 分 析 与 需 求 分 析 方 法 1. 需 求 分 析 : 确 定 做 什 么? 需 求 分 析 阶 段 的 工 作, 可 以 概 括 为 四 个 方 面 :( 重 要 ) a. 需 求 获 取 b. 需 求 分 析 c. 编 写 需 求 规 格 说 明 书 d. 需 求 评 审 2. 需 求 分 析 方 法 包 括 : 结 构 化 分 析 方 法 和 面 向 对 象 的 分 析 方 法 结 构 化 分 析 方 法 1. 关 于 结 构 化 分 析 方 法 结 构 化 分 析 方 法 的 实 质 是 着 眼 于 数 据 流, 自 顶 向 下, 逐 层 分 解, 建 立 系 统 的 处 理 流 程, 以 数 据 流 图 和 数 据 字 典 为 主 要 工 具, 建 立 系 统 的 逻 辑 模 型 2. 结 构 化 分 析 的 常 用 工 具 ( 重 要 ) a. 数 据 流 图 (DFD): 描 述 数 据 处 理 过 程 的 工 具, 是 需 求 理 解 的 逻 辑 模 型 的 图 形 表 示, 它 直 接 支 持 系 统 的 功 能 建 模 b. 数 据 字 典 (DD): 是 结 构 化 分 析 方 法 的 核 心 是 对 所 有 与 系 统 相 关 的 数 据 元 素 的 一 个 有 组 织 的 列 表, 以 及 精 确 的 严 格 的 定 义, 使 得 用 户 和 系 统 分 析 员 对 于 输 入 输 出 存 储 成 分 和 中 间 计 算 结 果 有 共 同 的 理 解 c. 判 定 树 d. 判 定 表 第 15 页, 共 26 页

16 3.2.3 软 件 需 求 规 格 说 明 书 ( 重 要 ) 软 件 需 求 规 格 说 明 书 是 需 求 分 析 阶 段 的 最 后 成 果, 是 软 件 开 发 中 的 重 要 文 档 之 一 3.3 结 构 化 设 计 方 法 软 件 设 计 的 基 本 概 念 1. 软 件 设 计 的 基 础 : 从 技 术 观 点 来 看, 软 件 设 计 包 括 软 件 结 构 设 计 数 据 设 计 接 口 设 计 过 程 设 计 从 工 程 管 理 角 度 来 看, 软 件 设 计 分 两 步 完 成 : 概 要 设 计 和 详 细 设 计 软 件 设 计 的 一 般 过 程 是 : 软 件 设 计 是 一 个 迭 代 的 过 程 ; 先 进 行 高 层 次 的 结 构 设 计, 后 进 行 低 层 次 的 过 程 设 计 ; 穿 插 进 行 数 据 设 计 和 接 口 设 计 2. 软 件 设 计 的 基 本 原 理 :( 重 要 ) a. 抽 象 b. 模 块 化 c. 信 息 隐 蔽 d. 模 块 独 立 性 注 意 : 模 块 独 立 性 是 指 每 个 模 块 只 完 成 系 统 要 求 的 独 立 的 子 功 能, 并 且 与 其 他 模 块 的 联 系 最 少 且 接 口 简 单, 通 常 使 用 耦 合 性 和 内 聚 性 来 衡 量 其 中 内 聚 性 是 指 一 个 模 块 内 部 各 个 元 素 间 彼 此 结 合 的 紧 密 程 序 的 度 量 ; 耦 合 性 是 指 模 块 间 互 相 连 接 的 紧 密 程 序 的 问 题 一 般 较 优 秀 的 软 件 设 计, 应 尽 量 做 到 高 内 聚, 低 耦 合, 即 减 弱 模 块 之 间 的 耦 合 性 和 提 高 模 块 内 的 内 聚 性, 有 利 于 提 高 模 块 的 独 立 性 概 要 设 计 模 块 1. 概 要 设 计 的 任 务 :( 重 要 ) a. 设 计 软 件 系 统 结 构 b. 数 据 结 构 及 数 据 库 设 计 数 据 信 息 c. 编 写 概 要 设 计 文 档 d. 概 要 设 计 文 档 评 审 控 制 信 息 2. 软 件 结 构 设 计 工 具 是 结 构 图 (SC):( 重 要 ) 结 构 图 用 来 描 述 系 统 的 层 次 和 分 块 结 构 关 系, 能 反 映 整 个 系 统 的 功 能 实 现 及 及 模 块 与 模 块 之 间 的 联 系 与 通 迅 包 含 有 四 种 模 块 类 型 : 传 入 模 块 传 出 模 块 变 换 模 块 和 协 调 模 块 结 构 图 中 的 基 本 符 号 : a 模 块 用 一 个 矩 形 表 示, 矩 形 内 注 明 模 块 的 功 能 和 名 字 ; b 箭 头 表 示 模 块 间 的 调 用 关 系 在 结 构 图 中 还 可 以 用 带 注 释 的 箭 头 表 示 模 块 调 用 过 程 中 来 回 传 递 的 信 息 c 带 实 心 圆 的 箭 头 表 示 传 递 的 是 控 制 信 息, 用 带 空 心 圆 的 箭 头 表 示 传 递 的 是 数 据 结 构 图 中 的 基 本 概 念 : a 深 度 : 程 序 结 构 的 层 次 数 称 为 结 构 的 深 度 结 构 的 深 度 在 一 定 意 义 上 反 映 了 程 序 结 构 的 规 模 和 复 杂 程 度 b 上 级 模 块 从 属 模 块 : 上 下 两 层 模 块 a 和 b, 且 有 a 调 用 b, 则 a 是 上 级 模 块,b 是 从 属 模 块 c 宽 度 : 层 次 结 构 中 同 一 层 模 块 的 最 大 模 块 个 数 称 为 结 构 的 宽 度 d 扇 入 : 扇 入 则 定 义 为 调 用 ( 或 控 制 ) 一 个 给 定 模 块 的 模 块 个 数 e 扇 出 : 扇 出 表 示 一 个 模 块 直 接 调 用 ( 或 控 制 ) 的 其 他 模 块 数 目 f 原 子 模 块 : 树 中 位 于 叶 子 结 点 的 模 块 深 度 3 B A 扇 出 3 C 扇 入 2 E D F 上 级 模 块 下 级 模 块 宽 度 3 3. 设 计 的 准 则 1 提 高 模 块 独 立 性 3 深 度 宽 度 扇 入 和 扇 出 适 当 5 应 减 少 模 块 的 接 口 和 界 面 的 复 杂 性 7 设 计 功 能 可 预 测 的 模 块 详 细 设 计 2 模 块 规 模 适 中 4 使 模 块 的 作 用 域 在 该 模 块 的 控 制 域 中 6 设 计 成 单 入 口 单 出 口 的 模 块 第 16 页, 共 26 页

17 1. 详 细 设 计 的 任 务 : 是 为 软 件 结 构 图 中 的 每 一 个 模 块 确 定 实 现 算 法 和 局 部 数 据 结 构, 用 某 种 选 定 的 表 达 工 具 表 示 算 法 和 数 据 结 构 的 细 节 2. 常 见 的 过 程 设 计 工 具 有 :( 重 要 ) 图 形 工 具 : 程 序 流 程 图,N-S,PAD,HIPO 表 格 工 具 : 判 定 表 语 言 工 具 :PDL( 伪 码 ) 1 为 了 使 模 块 尽 可 能 独 立, 要 求 (2005 年 4 月 选 择 题 第 7 题 ) A) 模 块 的 内 聚 程 度 要 尽 量 高, 且 各 模 块 间 的 耦 合 程 序 要 尽 量 强 B) 模 块 的 内 聚 程 度 要 尽 量 高, 且 各 模 块 间 的 耦 合 程 序 要 尽 量 弱 C) 模 块 的 内 聚 程 度 要 尽 量 低, 且 各 模 块 间 的 耦 合 程 序 要 尽 量 弱 D) 模 块 的 内 聚 程 度 要 尽 量 低, 且 各 模 块 间 的 耦 合 程 序 要 尽 量 强 1 在 软 件 设 计 中, 不 属 于 过 程 设 计 工 具 的 是 (2005 年 9 月 选 择 题 第 6 题 ) A) PDL( 过 程 设 计 语 言 ) B) PAD 图 C) N-S 图 D) DFD 图 2 两 个 或 两 个 以 上 模 块 之 间 关 联 的 紧 密 程 度 称 为 (2006 年 4 月 选 择 题 第 2 题 ) A) 耦 合 度 B) 内 聚 度 C) 复 杂 度 D) 数 据 传 输 特 性 3 从 工 程 管 理 角 度, 软 件 设 计 一 般 分 为 两 步 完 成, 它 们 是 (2006 年 9 月 选 择 题 第 2 题 ) A) 概 要 设 计 与 详 细 设 计 B) 数 据 设 计 与 接 口 设 计 C) 软 件 结 构 设 计 与 数 据 设 计 D) 过 程 设 计 与 数 据 设 计 4 下 列 软 件 系 统 结 构 图,(2006 年 9 月 选 择 题 第 1 题 ) A B C D 的 宽 度 为 软 件 测 试 E F 软 件 测 试 的 目 的 ( 重 要 ) 使 用 人 工 或 自 动 手 段 来 运 行 或 测 定 某 个 系 统 的 过 程, 其 目 的 在 于 检 验 它 是 否 满 足 规 定 的 需 求 或 是 弄 清 预 期 结 果 与 实 际 结 果 之 间 的 差 别 软 件 测 试 是 为 了 发 现 错 误 而 执 行 程 序 的 过 程 软 件 测 试 的 准 则 1 所 有 的 测 试 都 应 追 溯 到 需 求 2 严 格 执 行 测 试 计 划, 排 除 测 试 的 随 意 性 3 充 分 注 意 测 试 中 的 群 集 现 象 4 程 序 员 应 避 免 检 查 自 己 的 程 序 5 穷 举 测 试 不 可 能 6 妥 善 保 存 测 试 计 划 测 试 用 例 出 错 统 计 和 最 终 分 析 报 告 软 件 测 试 技 术 与 方 法 综 述 若 从 是 否 需 要 执 行 被 测 软 件 的 角 度, 可 以 分 为 静 态 测 试 和 动 态 测 试 方 法 若 按 照 功 能 划 分 可 以 分 为 白 盒 测 试 和 黑 盒 测 试 方 法 1. 静 态 测 试 与 动 态 测 试 静 态 测 试 不 实 际 运 行 软 件, 主 要 通 过 人 工 进 行 静 态 测 试 包 括 代 码 检 查 静 态 结 构 分 析 代 码 质 量 度 量 等 动 态 测 试 是 基 于 计 算 机 的 测 试, 是 为 了 发 现 错 误 而 执 行 程 序 的 过 程 2. 白 盒 测 试 方 法 与 测 试 用 例 设 计 白 盒 测 试 是 根 据 软 件 产 品 的 内 部 工 作 过 程, 检 查 内 部 成 分, 以 确 认 每 种 内 部 操 作 符 合 设 计 规 格 要 求 白 盒 测 第 17 页, 共 26 页

18 试 是 在 程 序 内 部 进 行, 主 要 用 于 完 成 软 件 内 部 操 作 的 验 证 白 盒 测 试 的 基 本 原 则 是 : 保 证 所 测 模 块 中 每 一 独 立 路 径 至 少 执 行 一 次 ; 保 证 所 测 模 块 所 有 判 断 的 每 一 分 支 最 少 执 行 一 次, 保 证 所 测 模 块 每 一 循 环 都 在 边 界 条 件 和 一 般 条 件 下 至 少 各 执 行 一 次, 验 证 所 有 数 据 结 构 的 有 效 性 3. 黑 盒 测 试 方 法 与 测 试 用 例 设 计 黑 盒 测 试 是 对 软 件 已 经 实 现 的 功 能 是 否 满 足 需 求 进 行 测 试 和 验 证 黑 盒 测 试 主 要 诊 断 功 能 不 对 或 遗 漏 界 面 错 误 数 据 结 构 或 外 部 数 据 库 访 问 错 误 性 能 错 误 初 始 化 和 终 止 条 件 错 软 件 测 试 的 实 施 ( 重 要 ) 软 件 测 试 一 般 按 4 个 步 骤 进 行, 即 单 元 测 试 集 成 测 试 验 收 测 试 ( 确 认 测 试 ) 和 系 统 测 试 其 中, 单 元 测 试 的 目 的 是 发 现 各 模 块 内 部 可 能 存 在 的 各 种 错 误 ; 集 成 测 试 的 目 的 是 发 现 与 接 口 有 关 的 错 误 ; 确 认 测 试 的 目 的 是 验 证 软 件 的 功 能 和 性 能 及 其 它 特 征 是 否 满 足 了 需 求 规 则 说 明 中 确 定 的 各 种 需 求 ; 系 统 测 试 的 目 的 是 在 真 实 的 系 统 工 作 环 境 下 检 验 软 件 是 否 能 与 系 统 正 确 连 接, 发 现 软 件 与 系 统 需 求 不 一 致 的 地 方 1 下 列 对 于 软 件 测 试 的 描 述 中 正 确 的 是 (2005 年 4 月 选 择 题 第 6 题 ) A) 软 件 测 试 的 目 的 是 证 明 程 序 是 否 正 确 B) 软 件 测 试 的 目 的 是 使 程 序 运 行 结 果 正 确 C) 软 件 测 试 的 目 的 是 尽 可 能 地 发 现 程 序 中 的 错 误 D) 软 件 测 试 的 目 的 是 使 程 序 符 合 结 构 化 原 则 2 下 列 叙 述 中 正 确 的 是 (2005 年 9 月 选 择 题 第 1 题 ) A) 程 序 设 计 就 是 编 制 程 序 B) 程 序 的 测 试 必 须 由 程 序 员 自 己 去 完 成 C) 程 序 经 调 试 改 错 后 还 应 进 行 再 测 试 D) 程 序 经 调 试 改 错 后 不 必 进 行 再 测 试 3 在 进 行 模 块 测 试 时, 要 为 每 个 被 测 试 的 模 块 另 外 设 计 两 类 模 块 : 驱 动 模 块 和 承 接 模 块 ( 桩 模 块 ) 其 中 3 的 作 用 是 将 测 试 数 据 传 送 给 被 测 试 的 模 块, 并 显 示 被 测 试 模 块 所 产 生 的 结 果 (2005 年 9 月 填 空 题 第 3 题 ) 4 程 序 测 试 分 为 静 态 分 析 和 动 态 测 试 其 中 4 是 指 不 执 行 程 序, 而 只 是 对 程 序 文 本 进 行 检 查, 通 过 阅 读 和 讨 论, 分 析 和 发 现 程 序 中 的 错 误 (2006 年 4 月 填 空 题 第 4 题 ) 3.5 程 序 的 调 试 基 本 概 念 ( 重 要 ) 程 序 调 试 的 任 务 是 : 诊 断 和 改 正 程 序 中 的 错 误 它 与 软 件 测 试 不 同, 软 件 测 试 是 尽 可 能 多 的 发 现 软 件 中 的 错 误 先 要 发 现 软 件 中 的 错 误, 然 后 借 助 于 一 定 的 调 试 工 具 去 执 行 找 出 软 件 错 误 的 具 体 位 置 软 件 测 试 贯 穿 整 个 软 件 生 命 期, 调 试 主 要 在 开 发 阶 段 1. 程 序 调 试 的 基 本 步 骤 : a. 错 误 定 位 b. 修 改 设 计 和 代 码, 以 排 除 错 误 c. 进 行 回 归 测 试, 防 止 引 进 新 的 错 误 软 件 调 试 方 法 调 试 的 关 键 在 于 推 断 程 序 内 部 的 错 误 位 置 及 原 因 从 是 否 跟 踪 和 执 行 程 序 的 角 度, 类 似 于 软 件 测 试, 软 件 调 试 可 以 分 为 静 态 调 试 和 动 态 调 试 静 态 调 试 主 要 是 指 通 过 人 的 思 维 来 分 析 源 程 序 代 码 和 排 错, 是 主 要 的 调 试 手 段, 而 动 态 调 试 是 辅 助 静 态 调 试 的 主 要 的 调 试 方 法 可 以 采 用 : 强 行 排 错 法 回 溯 法 原 因 排 除 法 1 诊 断 和 改 正 程 序 中 错 误 的 工 作 通 常 称 为 3 (2005 年 4 月 填 空 题 第 3 题 ) 2 下 列 叙 述 中 正 确 的 是 (2006 年 4 月 选 择 题 第 3 题 ) A) 软 件 测 试 应 该 由 程 序 开 发 者 来 完 成 B) 程 序 经 调 试 后 一 般 不 需 要 再 测 试 C) 软 件 维 护 只 包 括 对 程 序 代 码 的 维 护 D) 以 上 三 种 说 法 都 不 对 第 18 页, 共 26 页

19 3 2 的 任 务 是 诊 断 和 改 正 程 序 中 的 错 误 (2006 年 9 月 选 择 题 第 2 题 ) 3.6 精 典 模 拟 题 一. 选 择 题 1. 在 软 件 生 命 周 期 中, 能 准 确 地 确 定 软 件 系 统 必 须 做 什 么 和 必 须 具 备 那 些 功 能 的 阶 段 是 A) 概 要 设 计 B) 详 细 设 计 C) 可 行 性 分 析 D) 需 求 分 析 2. 下 面 不 属 于 软 件 工 程 的 3 个 要 素 的 是 A) 工 具 B) 过 程 C) 方 法 D) 环 境 3. 在 结 构 化 方 法 中, 软 件 功 能 分 解 属 于 下 列 软 件 开 发 中 的 阶 段 是 A) 详 细 设 计 B) 需 求 分 析 C) 总 体 设 计 D) 编 程 调 试 4. 软 件 开 发 的 结 构 化 生 命 周 期 方 法 将 软 件 生 命 周 期 划 分 成 A. 定 义 开 发 运 行 维 护 B. 设 计 阶 段 编 程 阶 段 测 试 阶 段 C. 总 体 设 计 详 细 设 计 编 程 调 试 D. 需 求 分 析 功 能 定 义 系 统 设 计 5. 检 查 软 件 产 品 是 否 符 合 需 求 定 义 的 过 程 为 A) 确 认 测 试 B) 集 成 测 试 C) 系 统 测 试 D) 单 元 测 试 6. 数 据 流 图 用 于 抽 象 描 述 一 个 软 件 的 逻 辑 模 型, 数 据 流 图 由 一 些 特 定 的 图 符 构 成 下 列 图 符 名 标 识 的 图 符 不 属 于 数 据 流 图 合 法 图 符 的 是 A) 控 制 流 B) 加 工 C) 数 据 存 储 D) 源 和 潭 7. 下 面 不 属 于 软 件 设 计 原 则 的 是 A) 抽 象 B) 模 块 化 C) 自 底 向 上 D) 信 息 隐 蔽 8. 程 序 流 程 图 (PFD) 中 的 箭 头 代 表 的 是 A) 数 据 流 B) 控 制 流 C) 调 用 关 系 D) 组 成 关 系 9. 下 列 工 具 中 为 需 求 分 析 常 用 工 具 的 是 A)PAD B)PFD C)N-S D)DFD 10. 软 件 调 试 的 目 的 是 A) 发 现 错 误 B) 改 正 错 误 C) 改 善 软 件 的 性 能 D) 挖 掘 软 件 的 潜 能 11. 软 件 需 求 分 析 阶 段 的 工 作, 可 以 分 为 四 个 方 面 : 需 求 获 取, 需 求 分 析, 编 写 需 求 规 格 说 明 书, 以 及 A) 阶 段 性 报 告 B) 需 求 评 审 C) 总 结 D) 都 不 正 确 12. 在 结 构 化 方 法 中, 用 数 据 流 程 图 (DFD) 作 为 描 述 工 具 的 软 件 开 发 阶 段 是 A. 可 行 性 分 析 B. 需 求 分 析 C. 详 细 设 计 D. 程 序 编 码 13. 在 软 件 开 发 中, 下 面 任 务 不 属 于 设 计 阶 段 的 是 A. 数 据 结 构 设 计 B. 给 出 系 统 模 块 结 构 C. 定 义 模 块 算 法 D. 定 义 需 求 并 建 立 系 统 模 型 14. 下 列 不 属 于 软 件 调 试 技 术 的 是 A. 强 行 排 错 法 B. 集 成 测 试 法 C. 回 溯 法 D. 原 因 排 除 法 15. 下 列 叙 述 中, 不 属 于 软 件 需 求 规 格 说 明 书 的 作 用 的 是 A. 便 于 用 户 开 发 人 员 进 行 理 解 和 交 流 B. 反 映 出 用 户 问 题 的 结 构, 可 以 作 为 软 件 开 发 工 作 的 基 础 和 依 据 C. 作 为 确 认 测 试 和 验 收 的 依 据 D. 便 于 开 发 人 员 进 行 需 求 分 析 16. 软 件 设 计 包 括 软 件 的 结 构 数 据 接 口 和 过 程 设 计, 其 中 软 件 的 过 程 设 计 是 指 A. 模 块 间 的 关 系 B. 系 统 结 构 部 件 转 换 成 软 件 的 过 程 描 述 C. 软 件 层 次 结 构 D. 软 件 开 发 过 程 17. 需 求 分 析 阶 段 的 任 务 是 确 定 A. 软 件 开 发 方 法 B. 软 件 开 发 工 具 C. 软 件 开 发 费 用 D. 软 件 系 统 功 能 18. 下 列 不 属 于 结 构 化 分 析 的 常 用 工 具 的 是 A. 数 据 流 图 B. 数 据 字 典 C. 判 定 树 D. PAD 图 19. 在 软 件 工 程 中, 白 箱 测 试 法 可 用 于 测 试 程 序 的 内 部 结 构 此 方 法 将 程 序 看 做 是 A. 循 环 的 集 合 B. 地 址 的 集 合 C. 路 径 的 集 合 D. 目 标 的 集 合 第 19 页, 共 26 页

20 20. 为 了 提 高 测 试 的 效 率, 应 该 A) 随 机 选 取 测 试 数 据 B) 取 一 切 可 能 的 输 入 数 据 作 为 测 试 数 据 C) 在 完 成 编 码 以 后 制 定 软 件 的 测 试 计 划 D) 集 中 对 付 那 些 错 误 群 集 的 程 序 正 确 答 案 :1-5:D D C A A 6-10:A C B D B 11-15:B B D B D 16-20:B D D C D 二. 填 空 题 1. 软 件 是 程 序 数 据 和 的 集 合 2.Jackson 方 法 是 一 种 面 向 的 结 构 化 方 法 3. 软 件 工 程 研 究 的 内 容 主 要 包 括 技 术 和 软 件 工 程 管 理 4. 数 据 流 图 的 类 型 有 和 事 务 型 5. 软 件 开 发 环 境 是 全 面 支 持 软 件 开 发 全 过 程 的 集 合 6. 若 按 功 能 划 分, 软 件 测 试 的 方 法 通 常 分 为 白 盒 测 试 方 法 和 黑 盒 测 试 方 法 7. 软 件 的 调 试 方 法 主 要 有 : 强 行 排 错 法 回 溯 法 和 原 因 排 除 法 8. 软 件 的 需 求 分 析 阶 段 的 工 作, 可 以 概 括 为 四 个 方 面 : 需 求 获 取 需 求 分 析 编 写 需 求 规 格 说 明 书 和 需 求 评 审 9. 软 件 工 程 研 究 的 内 容 主 要 包 括 : 软 件 开 发 技 术 和 软 件 工 程 管 理 10. 耦 合 和 内 聚 是 评 价 模 块 独 立 性 的 两 个 主 要 标 准, 其 中 反 映 了 模 块 内 各 成 分 之 间 的 联 系 4.1 数 据 库 系 统 的 基 本 概 念.1.1 数 据 数 据 库 数 据 库 管 理 系 统 1. 数 据 : 是 指 描 述 事 物 的 符 号 记 录 2. 数 据 库 : 是 存 储 在 计 算 机 存 储 设 备 中 的 结 构 化 的 相 关 数 据 的 集 合 注 意 两 点 : 其 一 是 数 据 库 不 仅 包 括 描 述 事 物 的 数 据 本 身, 而 且 包 括 相 关 事 物 之 间 的 关 系 其 二 是 数 据 库 中 的 数 据 具 有 集 成 与 共 享 的 特 点, 即 数 据 库 集 中 了 各 种 应 用 的 数 据, 进 行 统 一 的 构 造 与 存 储, 而 使 它 们 可 被 不 同 应 用 程 序 所 使 用 简 称 为 DB(Database) 3. 数 据 库 管 理 系 统 : 是 指 位 于 用 户 与 操 作 系 统 之 间 的 方 便 用 户 管 理 与 组 织 数 据 库 的 一 种 数 据 库 管 理 软 件 简 称 为 DBMS(Database Management System) 4. 数 据 库 应 用 系 统 : 是 指 在 数 据 库 系 统 资 源 的 基 础 上 针 对 某 一 类 应 用 而 开 发 出 来 的 应 用 软 件 如 大 家 都 熟 悉 的 教 务 管 理 系 统 5. 数 据 库 系 统 : 由 数 据 库 数 据 库 管 理 系 统 数 据 库 管 理 员 硬 件 平 台 和 软 件 平 台 5 个 部 分 所 组 成 简 称 为 DBS(Database System) 注 意 : 人 们 一 般 所 说 的 数 据 库 是 指 数 据 库 系 统 数 据 库 系 统 的 发 展 数 据 管 理 发 展 至 今 已 经 历 了 三 个 阶 段 : 人 工 管 理 阶 段 文 件 系 统 阶 段 和 数 据 库 系 统 阶 段 1. 文 件 系 统 阶 段 : 它 提 供 了 简 单 的 数 据 共 享 与 数 据 管 理 能 力, 但 是 它 无 法 提 供 完 整 的 统 一 的 管 理 和 数 据 共 享 能 力, 可 以 把 它 看 成 数 据 库 系 统 的 雏 形, 而 不 是 真 正 的 数 据 库 系 统 2. 层 次 数 据 库 与 网 状 数 据 库 系 统 阶 段 : 是 真 正 的 数 据 库 系 统, 但 脱 胎 于 文 件 系 统, 受 文 件 的 物 理 影 响 较 大 3. 关 系 数 据 库 系 统 阶 段 : 当 前 的 主 流 数 据 库, 系 统 结 构 简 单, 使 用 方 便, 逻 辑 性 强 物 理 性 少 数 据 库 系 统 的 基 本 特 点 ( 重 要 ) 1. 数 据 的 集 成 性 2. 数 据 的 高 共 享 性 与 低 冗 余 性 3. 数 据 独 立 性 4. 数 据 统 一 管 理 与 控 制 注 意 :( 重 要 ) 数 据 的 独 立 性 是 指 数 据 与 程 序 间 的 互 不 依 赖 性, 即 数 据 库 中 的 数 据 独 立 于 应 用 程 序 而 不 依 赖 于 应 用 程 序, 也 就 是 数 据 的 逻 辑 结 构 存 储 结 构 与 存 取 方 式 的 改 变 不 会 影 响 应 用 程 序 数 据 独 立 性 一 般 分 为 物 理 独 立 性 与 逻 辑 独 立 性 两 级 物 理 独 立 性 : 物 理 结 构 ( 包 括 存 储 结 构 存 取 方 式 等 ) 的 改 变, 如 存 储 设 备 的 更 换 物 理 存 储 的 更 换 存 取 方 式 改 变 不 影 响 数 据 库 的 逻 辑 结 构, 从 而 不 引 起 应 用 程 序 的 变 化 逻 辑 独 立 性 : 数 据 库 总 体 逻 辑 结 构 的 改 变, 如 修 改 数 据 模 式 增 加 新 的 数 据 类 型, 改 变 数 据 间 联 系 等, 不 需 要 相 应 修 改 应 用 程 序 数 据 库 系 统 的 内 部 结 构 体 系 数 据 库 系 统 在 其 内 部 具 有 三 级 模 式 及 二 级 映 射, 三 级 模 式 分 别 是 概 念 级 模 式 内 部 级 模 式 与 外 部 级 模 式, 二 第 20 页, 共 26 页

21 级 映 射 则 分 别 是 概 念 级 到 内 部 级 的 映 射 以 及 外 部 级 到 概 念 级 的 映 射 1. 数 据 库 系 统 的 三 级 模 式 外 模 式 : 也 称 子 模 式 或 用 户 模 式, 它 是 用 户 的 数 据 视 图, 也 就 是 用 户 所 见 到 的 数 据 模 式, 它 由 概 念 模 式 推 导 而 出 概 念 模 式 : 是 数 据 库 系 统 中 全 局 数 据 逻 辑 结 构 的 描 述, 是 全 体 用 户 公 共 数 据 视 图 内 模 式 : 又 称 物 理 模 式, 它 给 出 了 数 据 库 物 理 存 储 结 构 与 物 理 存 取 方 法 2. 数 据 库 系 统 的 两 级 映 射 : 是 概 念 级 到 内 部 级 的 映 射 以 及 外 部 级 到 概 念 级 的 映 射 注 意 : 三 级 模 式 与 两 级 映 射 的 引 入, 主 要 是 实 现 数 据 的 独 立 性 内 模 式 与 概 念 模 式 间 的 映 射, 是 达 到 物 理 独 立 性 ; 而 概 念 模 式 与 外 模 式 间 的 映 射, 是 达 到 逻 辑 独 立 性 应 用 程 序 外 模 式 概 念 模 式 内 模 式 数 据 库 应 用 程 序 外 模 式 外 模 式 / 概 念 模 式 映 射 概 念 模 式 / 内 模 式 映 射 1 数 据 库 独 立 性 是 数 据 库 技 术 的 重 要 特 点 之 一, 所 谓 数 据 独 立 性 是 指 (2005 年 4 月 选 择 题 第 9 题 ) A) 数 据 与 程 序 独 立 存 放 B) 不 同 的 数 据 被 存 放 在 不 同 的 文 件 中 C) 不 同 的 数 据 只 能 被 对 应 的 应 用 程 序 所 使 用 D) 以 上 三 种 说 法 都 不 对 2 数 据 库 设 计 的 根 本 目 标 是 要 解 决 (2005 年 9 月 选 择 题 第 8 题 ) A) 数 据 共 享 问 题 B) 数 据 安 全 问 题 C) 大 量 数 据 存 储 问 题 D) 简 化 数 据 维 护 3 数 据 库 系 统 的 核 心 是 (2005 年 9 月 选 择 题 第 10 题 ) A) 数 据 模 型 B) 数 据 库 管 理 系 统 C) 数 据 库 D) 数 据 库 管 理 员 4 据 管 理 技 术 发 展 过 程 经 过 人 工 管 理 文 件 系 统 和 数 据 库 系 统 三 个 阶 段, 其 中 数 据 独 立 性 最 高 的 阶 段 是 1 (2005 年 9 月 填 空 题 第 1 题 ) 5 数 据 独 立 性 分 为 逻 辑 独 立 性 与 物 理 独 立 性 当 数 据 的 存 储 结 构 改 变 时, 其 逻 辑 结 构 可 以 不 变, 因 此, 基 于 逻 辑 结 构 的 应 用 程 序 不 必 修 改, 称 为 5 (2006 年 4 月 填 空 题 第 5 题 ) 6 在 数 据 库 系 统 中, 用 户 所 见 的 数 据 模 式 为 (2006 年 9 月 选 择 题 第 4 题 ) A) 概 念 模 式 B) 外 模 式 C) 内 模 式 D) 物 理 模 式 7 数 据 库 技 术 的 根 本 目 标 是 要 解 决 数 据 的 (2006 年 9 月 选 择 题 第 9 题 ) A) 存 储 问 题 B) 共 享 问 题 C) 安 全 问 题 D) 保 护 问 题 4.2 数 据 模 型 数 据 模 型 的 基 本 概 念 数 据 库 应 用 系 统 就 是 将 现 实 世 界 映 射 到 计 算 机 中 的 结 果 为 了 简 化 这 个 映 射 过 程, 引 入 了 数 据 模 型 数 据 模 型 是 从 现 实 世 界 到 计 算 机 世 界 的 一 个 中 间 层 次, 其 不 仅 能 方 便 地 描 述 数 据 本 身, 而 且 能 正 确 地 反 映 出 数 据 之 间 存 在 的 整 体 逻 辑 关 系 数 据 模 型 : 是 数 据 特 征 的 抽 象, 它 从 抽 象 层 次 上 描 述 了 系 统 的 静 态 特 征 动 态 行 为 和 约 束 条 件, 为 数 据 库 系 统 的 信 息 表 示 与 操 作 提 供 一 个 抽 象 的 框 架 数 据 模 型 所 描 述 的 内 容 有 三 个 部 分 : 数 据 结 构 数 据 操 作 与 数 据 约 束 数 据 模 型 按 不 同 的 应 用 层 次 分 成 三 种 类 型 : 概 念 数 据 模 型 逻 辑 数 据 模 型 物 理 数 据 模 型 其 中, 概 念 数 据 模 型 简 称 概 念 模 型, 它 是 一 种 面 向 客 观 世 界 面 向 用 户 的 模 型, 与 具 体 的 数 据 库 系 统 无 关, 与 具 体 的 计 算 机 平 台 无 关, 如 E-R 模 型 ; 逻 辑 数 据 模 型 又 称 数 据 模 型, 它 是 一 种 面 向 数 据 库 系 统 的 模 型, 着 重 于 在 数 据 库 系 统 一 级 的 实 现, 如 层 次 模 型 网 状 模 型 和 关 系 模 型 ; 物 理 数 据 模 型 : 又 称 物 理 模 型, 它 是 一 种 面 向 计 算 机 物 理 表 示 的 模 型, 它 给 出 了 数 据 模 型 在 计 算 机 上 物 理 结 构 的 表 示 第 21 页, 共 26 页

22 4.2.2 E-R 模 型 ( 属 于 概 念 数 据 模 型 ) ( 重 要 ) 1.E-R 模 型 的 基 本 概 念 E-R 模 型 将 现 实 世 界 中 的 要 求 转 化 成 实 体 联 系 和 属 性 等 几 个 基 本 概 念 a. 实 体 : 是 现 实 世 界 中 的 事 物 的 抽 象, 是 概 念 世 界 中 的 基 本 单 位, 是 客 观 存 在 又 能 相 互 区 别 的 事 物 b. 属 性 : 是 事 物 的 特 征 c. 联 系 : 是 指 现 实 世 界 中 事 物 间 的 关 联 实 体 之 间 的 对 应 关 系 称 之 为 联 系, 反 映 了 现 实 世 界 事 物 之 间 的 相 互 关 联 通 常 分 为 : a 一 对 一 联 系 : 如 居 民 信 息 与 户 口 信 息 即 一 个 居 民 信 息 对 应 着 一 个 户 口 信 息, 并 且 一 个 户 口 信 息 也 只 对 应 着 一 个 居 民 信 息 居 民 信 息 1 1 户 口 信 息 b 一 对 多 联 系 或 多 对 一 联 系 : 注 意 两 个 实 体 前 后 的 顺 序 关 系 一 对 多 联 系 : 如 班 级 信 息 与 学 生 信 息 即 一 个 班 级 对 应 着 多 个 学 生, 并 且 一 个 学 生 只 对 应 一 个 班 级 1 多 班 级 信 息 学 生 信 息 多 对 一 联 系 : 如 学 生 信 息 与 班 级 信 息 即 一 个 学 生 对 应 一 个 班 级, 但 一 个 班 级 却 可 对 应 多 个 学 生 多 1 学 生 信 息 班 级 信 息 c 多 对 多 联 系 : 如 学 生 信 息 与 课 程 信 息 即 一 个 学 生 可 以 选 修 多 门 课 程, 并 且 一 门 课 程 可 被 多 个 学 生 选 修 多 多 课 程 信 息 学 生 信 息 2.E-R 模 型 三 个 基 本 概 念 之 间 的 联 接 关 系 a 实 体 是 概 念 世 界 中 的 基 本 单 位, 属 性 依 附 于 实 体, 它 本 身 并 不 构 成 独 立 单 位 b 一 个 实 体 可 以 有 若 干 个 属 性, 实 体 以 及 它 的 所 有 属 性 构 成 了 实 体 的 一 个 完 整 描 述 c 属 性 有 属 性 域, 每 个 实 体 可 取 属 性 域 内 的 值 d 一 个 实 体 的 所 有 属 性 取 值 组 成 了 一 个 值 集 叫 元 组 3.E-R 模 型 的 图 示 法 a. 实 体 集 表 示 法 : 使 用 矩 形 表 示 实 体 集 b. 属 性 表 示 法 : 使 用 椭 圆 形 表 示 属 性 c. 联 系 表 示 法 : 使 用 菱 形 表 示 属 性 如 教 学 管 理 系 统 的 E-R 图 为 : 学 号 姓 名 专 业 成 绩 编 号 名 称 学 分 学 生 选 课 课 程 层 次 模 型 ( 属 于 逻 辑 数 据 模 型 ) 层 次 模 型 的 基 本 结 构 是 树 形 结 构 网 状 模 型 ( 属 于 逻 辑 数 据 模 型 ) 网 状 模 型 是 一 个 不 加 任 何 条 件 限 制 的 无 向 图 关 系 模 型 ( 属 于 逻 辑 数 据 模 型 ) 1. 关 系 的 数 据 结 构 : 关 系 模 型 采 用 二 维 表 来 表 示, 简 称 表 二 维 表 由 表 框 架 及 表 的 元 组 组 成 一 个 二 维 表 就 是 一 个 关 系 2. 关 系 中 的 数 据 约 束 包 括 : a. 实 体 完 整 性 约 束 : 约 束 关 系 的 主 键 中 属 性 值 不 能 为 空 值 ; 第 22 页, 共 26 页

23 b. 参 照 完 整 性 约 束 : 是 关 系 之 间 的 基 本 约 束 ; c. 用 户 定 义 的 完 整 性 约 束 : 它 反 映 了 具 体 应 用 中 数 据 的 语 义 要 求 1 用 树 形 结 构 表 示 实 体 之 间 联 系 的 模 型 是 (2005 年 4 月 选 择 题 第 10 题 ) A) 关 系 模 型 B) 网 状 模 型 C) 层 次 模 型 D) 以 上 三 个 都 是 2 在 E-R 图 中, 用 来 表 示 实 体 的 图 形 是 (2006 年 4 月 选 择 题 第 9 题 ) A) 矩 形 B) 椭 圆 形 C) 菱 形 D) 三 角 形 3 一 个 关 系 表 的 行 称 为 3 (2006 年 9 月 填 空 题 第 3 题 ) 4.3 关 系 代 数 1 传 统 的 集 合 运 算 : R3 对 于 两 个 元 组 结 构 相 同 的 关 系, 可 对 他 们 进 行 并 差 和 交 集 合 运 算 设 置 有 关 系 R1 和 R2, 运 算 后 的 结 果 为 a 并 集 运 算 : 是 由 属 于 这 两 个 关 系 的 元 组 组 成 的 集 合 记 为 R3=R1 R2 R1 R2 R3= R1 R2 R2 学 号 姓 名 学 号 姓 名 学 号 姓 名 1001 张 三 2001 李 四 1001 张 三 2001 王 五 2001 李 四 2001 王 五 b 交 集 运 算 : 是 由 既 属 于 R1 同 时 又 属 于 R2 的 元 组 组 成 的 集 合 记 为 R3=R1 R2 R1 R2 R3= R1 R2 R2 学 号 姓 名 学 号 姓 名 学 号 姓 名 1001 张 三 2001 李 四 2001 王 五 3001 王 五 3001 王 五 c 差 集 运 算 : 是 由 属 于 R1 但 不 属 于 R2 的 元 组 组 成 的 集 合 记 为 R3=R1-R2 R1 R2 R3= R1-R2 学 号 姓 名 学 号 姓 名 学 号 姓 名 1001 张 三 2001 李 四 1001 张 三 3001 王 五 3001 王 五 2 专 门 的 关 系 运 算 : a 选 择 运 算 : 从 关 系 中 找 出 满 足 给 定 条 件 的 元 组 的 操 作 如 从 教 师 表 中 找 出 所 有 职 称 为 教 授 有 教 师 b 投 影 运 算 : 从 关 系 模 式 中 指 定 若 干 属 性 组 成 新 的 关 系 如 从 教 师 表 中 查 询 教 师 信 息, 并 显 示 编 号 姓 名 职 称 三 个 字 段 注 意 : 经 过 投 影 运 算 可 以 得 到 一 个 新 的 关 系, 其 关 系 模 式 所 包 含 的 属 性 个 数 往 往 比 原 关 系 少, 或 者 属 性 的 排 列 顺 序 不 同 c 笛 卡 尔 积 运 算 : 是 将 两 个 关 系 (R S) 合 并 成 一 个 大 的 关 系 (T) 大 关 系 T 的 列 数 是 关 系 R 和 关 系 S 的 列 数 共 同 所 组 成 的, 其 行 数 是 R 中 的 行 数 与 S 中 的 行 数 的 乘 积 记 为 :T=R S R S T=R S 学 号 姓 名 课 程 成 绩 学 号 学 号 姓 名 课 程 成 绩 学 号 1001 张 三 C 张 三 C 李 四 C 张 三 C C 张 三 C 李 四 C 李 四 C 李 四 C d 除 运 算 : 是 笛 卡 尔 积 的 逆 运 算, 考 试 的 可 能 性 小 记 法 为 :T/R=S 或 T R=S e 自 然 联 接 : 是 在 笛 卡 尔 积 运 算 的 基 础 上, 得 到 指 定 两 个 字 段 的 值 相 等 的 元 组 记 法 为 :T=R S 第 23 页, 共 26 页

24 R S T=R S,R. 学 号 =S. 学 号 学 号 姓 名 课 程 成 绩 学 号 学 号 姓 名 课 程 成 绩 学 号 1001 张 三 C 张 三 C 李 四 C C 李 四 C 设 有 如 下 关 系 表 :(2005 年 9 月 选 择 题 第 9 题 ) R S T A B C A B C A B C 则 下 列 操 作 中 正 确 的 是 A) T=R S B) T=R S C) T=R S D) T=R/S 2 设 有 如 三 个 关 系 表 (2006 年 9 月 选 择 题 第 6 题 ) R A m n S B C 1 3 T A B C m 1 3 n 1 3 下 列 操 作 中 正 确 的 是 A)T=R S B)T=R S C)T=R S D)T=R/S 4.4 数 据 库 设 计 与 管 理 数 据 库 设 计 是 数 据 库 应 用 的 核 心 数 据 库 设 计 概 述 数 据 库 设 计 一 般 采 用 生 命 周 期 法, 即 将 整 个 数 据 库 应 用 系 统 的 开 发 分 解 成 目 标 独 立 的 若 干 阶 段 : 需 求 分 析 概 念 设 计 逻 辑 设 计 物 理 设 计 其 中 需 求 分 析 得 到 需 求 说 明 书 概 念 设 计 得 到 概 念 数 据 模 型 逻 辑 设 计 得 到 逻 辑 数 据 模 型 物 理 设 计 得 到 数 据 库 内 模 式 数 据 库 设 计 的 需 求 分 析 分 析 和 表 达 用 户 的 需 求, 经 常 采 用 的 方 法 有 结 构 化 分 析 方 法 和 面 向 对 象 的 方 法 结 构 化 分 析 方 法 用 自 顶 向 下 逐 层 分 解 的 方 式 分 析 系 统 对 数 据 库 设 计 来 讲, 数 据 字 典 是 进 行 详 细 的 数 据 收 集 和 数 据 分 析 所 获 得 的 主 要 结 果 数 据 字 典 是 各 类 数 据 描 述 的 集 合, 它 通 常 包 括 5 个 部 分 1 数 据 项, 是 数 据 的 最 小 单 位 ;2 数 据 结 构, 是 若 干 数 据 项 有 意 义 的 集 合 ;3 数 据 流, 可 以 是 数 据 项, 也 可 以 是 数 据 结 构, 表 示 某 一 处 理 过 程 的 输 入 或 输 出 ;4 数 据 存 储, 处 理 过 程 中 存 取 的 数 据, 常 常 是 手 工 凭 证 手 工 文 挡 或 计 算 机 文 件 ;5 处 理 过 程 数 据 库 概 念 设 计 数 据 库 概 念 设 计 的 目 的 是 分 析 数 据 内 在 语 义 关 系, 在 此 的 基 础 上 建 立 一 个 数 据 的 抽 象 模 型 设 计 的 方 法 有 两 种 : a 集 中 式 模 式 设 计 法 ( 适 用 于 小 型 或 并 不 复 杂 的 单 位 或 部 门 ); b 视 图 集 成 设 计 法 其 设 计 过 程 分 为 三 步 : 选 择 局 部 应 用 视 图 设 计 视 图 集 成 数 据 库 的 逻 辑 设 计 关 系 视 图 的 作 用 有 以 下 几 点 : 1. 提 供 数 据 逻 辑 独 立 性 ; 2. 能 适 应 用 户 对 数 据 的 不 同 需 求 ; 3. 有 一 定 数 据 保 密 功 能 数 据 库 的 物 理 设 计 第 24 页, 共 26 页

25 数 据 库 物 理 设 计 的 主 要 目 标 是 对 数 据 库 内 部 物 理 结 构 作 调 整 并 选 择 合 理 的 存 取 路 径, 以 提 高 数 据 库 访 问 速 度 及 有 效 利 用 存 储 空 间 数 据 库 管 理 数 据 库 管 理 的 内 容 : 1. 数 据 库 的 建 立 ;2. 数 据 库 的 调 整 ;3. 数 据 库 的 重 组 ;4. 数 据 库 安 全 性 控 制 与 完 整 性 控 制 ;5. 数 据 库 的 故 障 校 复 ;6. 数 据 库 监 控 1 数 据 库 设 计 的 四 个 阶 段 是 : 需 求 分 析 概 念 设 计 逻 辑 设 计 和 (2006 年 9 月 选 择 题 第 5 题 ) A) 编 码 设 计 B) 测 试 阶 段 C) 运 行 阶 段 D) 物 理 设 计 4.5 精 典 模 拟 题 1. 在 数 据 库 管 理 技 术 的 发 展 过 程 中, 经 历 了 人 工 管 理 阶 段 文 件 系 统 阶 段 和 数 据 库 系 统 阶 段 其 中 数 据 独 立 性 最 高 的 是 A) 数 据 库 系 统 B) 文 件 系 统 C) 人 工 管 理 D) 数 据 项 管 理 2. 下 述 关 于 数 据 库 系 统 的 叙 述 中 正 确 的 是 A) 数 据 库 系 统 减 少 了 数 据 冗 余 B) 数 据 库 系 统 避 免 了 一 切 冗 余 C) 数 据 库 系 统 中 的 数 据 的 一 致 性 是 指 数 据 类 型 一 致 D) 数 据 库 系 统 比 文 件 系 统 能 管 理 更 多 的 数 据 3. 数 据 库 系 统 的 核 心 是 A) 数 据 库 B) 数 据 库 管 理 系 统 C) 数 据 模 型 D) 软 件 工 具 4. 用 树 形 结 构 来 表 示 实 体 之 间 联 系 的 模 型 称 为 A) 关 系 模 型 B) 层 次 模 型 C) 网 状 模 型 D) 数 据 模 型 5. 关 系 表 中 的 每 一 横 行 称 为 一 个 A) 元 组 B) 字 段 C) 属 性 D) 码 6. 关 系 数 据 库 管 理 系 统 能 实 现 的 专 门 关 系 运 算 包 A) 排 序 索 引 统 计 B) 选 择 投 影 连 接 C) 关 联 更 新 排 序 D) 显 示 打 印 制 表 7. 在 关 系 数 据 库 中, 用 来 表 示 实 体 之 间 联 系 的 是 A) 树 结 构 B) 网 结 构 C) 线 性 表 D) 二 维 表 8. 数 据 库 设 计 包 括 两 个 方 面 的 设 计 内 容, 它 们 是 A) 概 念 设 计 和 逻 辑 设 计 B) 模 式 设 计 和 内 模 式 设 计 C) 内 模 式 设 计 和 物 理 设 计 D) 结 构 特 性 设 计 和 行 为 特 性 设 计 9. 将 E-R 图 转 换 到 关 系 模 式 时, 实 体 和 联 系 都 可 以 表 示 成 A) 属 性 B) 关 系 C) 键 D) 域 10. 下 列 叙 述 中 正 确 的 是 (C) A. 数 据 库 是 一 个 独 立 的 系 统, 不 需 要 操 作 系 统 的 支 持 B. 数 据 库 设 计 是 指 设 计 数 据 库 管 理 系 统 C. 数 据 库 技 术 的 根 本 目 标 是 要 解 决 数 据 共 享 的 问 题 D. 数 据 库 系 统 中, 数 据 的 物 理 结 构 必 须 与 逻 辑 结 构 一 致 11. 下 列 模 式 中, 能 够 给 出 数 据 库 物 理 存 储 结 构 与 物 理 存 取 方 法 的 是 A. 内 模 式 B. 外 模 式 C. 概 念 模 式 D. 逻 辑 模 式 12. 数 据 结 构 中, 与 所 使 用 的 计 算 机 无 关 的 是 数 据 的 A. 存 储 结 构 B. 物 理 结 构 C. 逻 辑 结 构 D. 物 理 和 存 储 结 构 13. 在 数 据 管 理 技 术 发 展 过 程 中, 文 件 系 统 与 数 据 库 系 统 的 主 要 区 别 是 数 据 库 系 统 具 有 A. 数 据 无 冗 余 B. 数 据 可 共 享 C. 专 门 的 数 据 管 理 软 件 D. 特 定 的 数 据 模 型 14. 下 列 说 法 中, 不 属 于 数 据 模 型 所 描 述 的 内 容 的 是 A. 数 据 结 构 B. 数 据 操 作 C. 数 据 查 询 D. 数 据 约 束 第 25 页, 共 26 页

26 15. 下 列 有 关 数 据 库 的 描 述, 正 确 的 是 A) 数 据 处 理 是 将 信 息 转 化 为 数 据 的 过 程 B) 数 据 的 物 理 独 立 性 是 指 当 数 据 的 逻 辑 结 构 改 变 时, 数 据 的 存 储 结 构 不 变 C) 关 系 中 的 每 一 列 称 为 元 组, 一 个 元 组 就 是 一 个 字 段 D) 如 果 一 个 关 系 中 的 属 性 或 属 性 组 并 非 该 关 系 的 关 键 字, 但 它 是 另 一 个 关 系 的 关 键 字, 则 称 其 为 本 关 系 的 外 关 键 字 正 确 答 案 :1-5: A A B B A 6-10: B D A B C 11-15: A C D C D 二. 填 空 题 1. 一 个 项 目 具 有 一 个 项 目 主 管, 一 个 项 目 主 管 可 管 理 多 个 项 目, 则 实 体 项 目 主 管 与 实 体 项 目 的 联 系 属 于 的 联 系 2. 数 据 独 立 性 分 为 逻 辑 独 立 性 与 物 理 独 立 性 当 数 据 的 存 储 结 构 改 变 时, 其 逻 辑 结 构 可 以 不 变, 因 此, 基 于 逻 辑 结 构 的 应 用 程 序 不 必 修 改, 称 为 3. 在 关 系 模 型 中, 把 数 据 看 成 一 个 二 维 表, 每 一 个 二 维 表 称 为 一 个 4. 关 系 数 据 库 管 理 系 统 能 实 现 的 专 门 关 系 运 算 包 括 选 择 连 接 和 投 影 5. 数 据 字 典 是 各 类 数 据 描 述 的 集 合, 它 通 常 包 括 5 个 部 分, 即 数 据 项 数 据 结 构 数 据 流 数 据 存 储 和 处 理 过 程 6. 关 系 模 型 的 完 整 性 规 则 是 对 关 系 的 某 种 约 束 条 件, 包 括 实 体 完 整 性 参 照 完 整 性 和 自 定 义 完 整 性 7. 数 据 模 型 按 不 同 的 应 用 层 次 分 为 三 种 类 型, 它 们 是 概 念 数 据 模 型 逻 辑 数 据 模 型 和 物 理 数 据 模 型 8. 关 系 模 型 的 数 据 操 纵 即 是 建 立 在 关 系 上 的 数 据 操 纵, 一 般 有 查 询 增 加 删 除 和 修 改 四 种 操 作 9. 数 据 库 保 护 分 为 : 安 全 性 控 制 完 整 性 控 制 并 发 性 控 制 和 数 据 的 恢 复 10. 数 据 库 管 理 系 统 常 见 的 数 据 模 型 有 层 次 模 型 网 状 模 型 和 关 系 模 型 三 种 第 26 页, 共 26 页