2022年Access基础知识点.pdf

《2022年Access基础知识点.pdf》由会员分享，可在线阅读，更多相关《2022年Access基础知识点.pdf（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 一 章 数 据 构 造 与 算 法 通 过 对 部 分 考 生 日 勺 调 查 以 及 对 近 年 真 题 的 总 结 分 析，笔 试 部 分 常 常 考 察 的 是 算 法 复 杂 度、数 据 构 造 的 概 念、栈、二 叉 树 的 遍 历、二 分 法 查 找，读 者 应 对 此 部 分 进 行 重 点 学 习。详 细 重 点 学 习 知 识 点：1.算 法 的 概 念、算 法 时 间 复 杂 度 及 空 间 复 杂 度 日 勺 概 念 2.数 据 构 造 的 定 义、数 据 逻 辑 构 造 及 物 理 构 造 的 定 义 3.栈 的 定 义 及 其 运 算、线 性 链 表 的 存 储

2、方 式 4.树 与 二 叉 树 日 勺 概 念、二 叉 树 的 基 本 性 质、完 全 二 叉 树 的 概 念、二 叉 树 日 勺 遍 历 5.二 分 查 找 法 6.冒 泡 排 序 法 1.1 算 法 考 点 1 算 法 的 基 本 概 念 考 试 链 接：考 点 1在 笔 试 考 试 中 考 核 的 几 率 为 3 0%,重 要 是 以 填 空 题 的 形 式 出 现，分 值 为 2分，此 考 点 为 识 记 内 容，读 者 还 应 当 理 解 算 法 中 对 数 据 的 基 本 运 算。计 算 机 解 题 的 过 程 实 际 上 是 在 实 行 某 种 算 法，这 种 算 法 称 为 计

3、 算 机 算 法。1.算 法 的 基 本 特 性：可 行 性、确 定 性、有 穷 性、拥 有 足 够 日 勺 情 报。2.算 法 的 基 本 要 素:(1)算 法 中 对 数 据 的 运 算 和 操 作 一 种 算 法 由 两 种 基 本 要 素 构 成：一 是 对 数 据 对 象 的 运 算 和 操 作；二 是 算 法 的 控 制 构 造。在 一 般 的 计 算 机 系 统 中，基 本 的 运 算 和 操 作 有 如 下 4类：算 术 运 算、逻 辑 运 算、关 系 运 算 和 数 据 传 播。(2)算 法 的 控 制 构 造：算 法 中 各 操 作 之 间 的 执 行 次 序 称 为 算

4、法 的 控 制 构 造。描 述 算 法 的 工 具 一 般 有 老 式 流 程 图、N-S构 造 化 流 程 图、算 法 描 述 语 言 等。一 种 算 法 一 般 都 可 以 用 次 序、选 择、循 环 3种 基 本 控 制 构 造 组 合 而 成。考 点 2 算 法 复 杂 度 考 试 链 接：考 点 2在 笔 试 考 试 中，是 一 种 常 常 考 察 的 内 容，在 笔 试 考 试 中 出 现 的 几 率 为 7 0%,重 要 是 以 选 择 口 勺 形 式 出 现，分 值 为 2分，此 考 点 为 重 点 识 记 内 容，读 者 还 应 当 识 记 算 法 时 间 复 杂 度 及 空

5、 间 复 杂 度 的 概 念。1.算 法 的 时 间 复 杂 度 算 法 的 时 间 复 杂 度 是 指 执 行 算 法 所 需 要 的 计 算 工 作 量。同 一 种 算 法 用 不 一 样 的 语 言 实 现，或 者 用 不 一 样 的 编 译 程 序 进 行 编 译，或 者 在 不 一 样 日 勺 计 算 机 上 运 行，效 率 均 不 一 样。这 表 明 使 用 绝 对 日 勺 时 间 单 位 衡 量 算 法 的 效 率 是 不 合 适 的。撇 开 这 些 与 计 算 机 硬 件、软 件 有 关 的 原 因，可 以 认 为 一 种 特 定 算 法 运行 工 作 量 的 大 小，只 依

6、赖 于 问 题 的 规 模(一 般 用 整 数 n表 达)，它 是 问 题 规 模 日 勺 函 数。即 算 法 日 勺 工 作 量=(n)2.算 法 日 勺 空 间 复 杂 度 算 法 的 空 间 复 杂 度 是 指 执 行 这 个 算 法 所 需 要 的 内 存 空 间。一 种 算 法 所 占 用 的 存 储 空 间 包 括 算 法 程 序 所 占 的 空 间、输 入 口 勺 初 始 数 据 所 占 日 勺 存 储 空 间 以 及 算 法 执 行 过 程 中 所 需 要 的 额 外 空 间。其 中 额 外 空 间 包 括 算 法 程 序 执 行 过 程 中 日 勺 工 作 单 元 以 及 某

7、 种 数 据 构 造 所 需 要 口 勺 附 加 存 储 空 间。假 如 额 外 空 间 量 相 对 于 问 题 规 模 来 说 是 常 数，则 称 该 算 法 是 原 地 工 作 日 勺。在 许 多 实 际 问 题 中，为 了 减 少 算 法 所 占 的 存 储 空 间，一 般 采 用 压 缩 存 储 技 术，以 便 尽 量 减 少 不 必 要 日 勺 额 外 空 间。疑 难 解 答：算 法 的 工 作 量 用 什 么 来 计 算？算 法 的 工 作 量 用 算 法 所 执 行 的 基 本 运 算 次 数 来 计 算，而 算 法 所 执 行 的 基 本 运 算 次 数 是 问 题 规 模 的

8、 函 数，即 算 法 日 勺 工 作 量 二 f(n),其 中 n是 问 题 日 勺 规 模。L2数 据 构 造 的 基 本 概 念 考 点 3 数 据 构 造 的 定 义 考 试 链 接：考 点 3在 笔 试 考 试 中，是 一 种 常 常 考 察 日 勺 内 容，在 笔 试 考 试 中 出 现 日 勺 几 率 为 7 0%,重 要 是 以 选 择 的 形 式 出 现，分 值 为 2分，此 考 点 为 识 记 内 容，读 者 还 应 当 识 记 数 据 的 逻 辑 构 造 和 存 储 构 造 的 概 念。数 据 构 造 作 为 计 算 机 日 勺 一 门 学 科，重 要 研 究 和 讨 论

9、如 下 三 个 方 面：(1)数 据 集 合 中 个 数 据 元 素 之 间 所 固 有 的 逻 辑 关 系，即 数 据 的 逻 辑 构 造；(2)在 对 数 据 元 素 进 行 处 理 时，各 数 据 元 素 在 计 算 机 中 日 勺 存 储 关 系，即 数 据 日 勺 存 储 构 造；(3)对 多 种 数 据 构 造 进 行 的 运 算。数 据：是 对 客 观 事 物 的 符 号 表 达，在 计 算 机 科 学 中 是 指 所 有 能 输 入 到 计 算 机 中 并 被 计 算 机 程 序 处 理 的 符 号 的 总 称。数 据 元 素：是 数 据 的 基 本 单 位，在 计 算 机 程

10、 序 中 一 般 作 为 一 种 整 体 进 行 考 虑 和 处 理。数 据 对 象：是 性 质 相 似 的 数 据 元 素 的 集 合，是 数 据 日 勺 一 种 子 集。数 据 的 逻 辑 构 造 是 对 数 据 元 素 之 间 的 逻 辑 关 系 的 描 述，它 可 以 用 一 种 数 据 元 素 的 集 合 和 定 义 在 此 集 合 中 的 若 干 关 系 来 表 达。数 据 的 逻 辑 构 造 有 两 个 要 素：一 是 数 据 元 素 日 勺 集 合，一 般 记 为 D;二 是 D上 日 勺 关 系，它 反 应 了 数 据 元 素 之 间 日 勺 前 后 件 关 系，一 般 记

11、为 R。一 种 数 据 构 造 可 以 表 到 达 B=(D,R)其 中 B表 达 数 据 构 造。为 了 反 应 D中 各 数 据 元 素 之 间 日 勺 前 后 件 关 系，一 般 用 二 元 组 来 表 达。数 据 口 勺 逻 辑 构 造 在 计 算 机 存 储 空 间 中 口 勺 寄 存 形 式 称 为 数 据 的 存 储 构 造(也 称 数 据 日 勺 物 理 构 造)。由 于 数 据 元 素 在 计 算 机 存 储 空 间 中 的 位 置 关 系 也 许 与 逻 辑 关 系 不 一 样，因 此，为 了 表 达 寄 存 在 计 算 机 存 储 空 间 中 的 各 数 据 元 素 之

12、间 的 逻 辑 关 系(即 前 后 件 关 系)，在 数 据 的 存 储 构 造 中，不 仅 要 寄 存 各 数 据 元 素 的 信 息，还 需 要 寄 存 各 数 据 元 素 之 间 的 前 后 件 关 系 的 信 息。一 种 数 据 的 逻 辑 构 造 根 据 需 要 可 以 表 到 达 多 种 存 储 构 造，常 用 的 存 储 构 造 有 次 序、链 接、索 引 等 存 储 构 造。而 采 用 不 一 样 的 存 储 构 造，其 数 据 处 理 的 效 率 是 不 一 样 的。因 此，在 进 行 数 据 处 理 时，选 择 合 适 的 存 储 构 造 是 很 重 要 的。考 点 4 线

13、 性 构 造 与 非 线 性 构 造 考 试 链 接：考 点 4在 笔 试 考 试 中，虽 然 说 不 是 考 试 常 常 考 察 口 勺 内 容，但 读 者 还 是 对 此 考 点 有 所 理 解，在 笔 试 考 试 中 出 现 口 勺 几 率 为 3 0%,重 要 是 以 填 空 题 出 现 的 形 式 出 现，分 值 为 2分，此 考 点 为 识 记 内 容。根 据 数 据 构 造 中 各 数 据 元 素 之 间 前 后 件 关 系 的 复 杂 程 度，一 般 将 数 据 构 造 分 为 两 大 类 型：线 性 构 造 与 非 线 性 构 造。假 如 一 种 非 空 日 勺 数 据 构

14、造 满 足 下 列 两 个 条 件：(1)有 且 只 有 一 种 根 结 点；(2)每 一 种 结 点 最 多 有 一 种 前 件，也 最 多 有 一 种 后 件。则 称 该 数 据 构 造 为 线 性 构 造。线 性 构 造 又 称 线 性 表。在 一 种 线 性 构 造 中 插 入 或 删 除 任 何 一 种 结 点 后 还 应 是 线 性 构 造。假 如 一 种 数 据 构 造 不 是 线 性 构 造，则 称 之 为 非 线 性 构 造。疑 难 解 答：空 的 数 据 构 造 是 线 性 构 造 还 是 非 线 性 构 造?一 种 空 的 数 据 构 造 究 竟 是 属 于 线 性 构

15、造 还 是 属 于 非 线 性 构 造，这 要 根 据 详 细 状 况 来 确 定。假 如 对 该 数 据 构 造 口 勺 算 法 是 按 线 性 构 造 的 规 则 来 处 理 曰 勺，则 属 于 线 性 构 造;否 则 属 于 非 线 性 构 造。1.3栈 及 线 性 链 表 考 点 5 栈 及 其 基 本 运 算 考 试 链 接：考 点 5在 笔 试 考 试 中，是 一 种 必 考 的 内 容，在 笔 试 考 试 中 出 现 口 勺 几 率 为 100%,重 要 是 以 选 择 口 勺 形 式 出 现，分 值 为 2分，此 考 点 为 重 点 掌 握 内 容，读 者 应 当 掌 握 栈

16、日 勺 运 算。1.栈 的 基 本 概 念 栈 是 限 定 只 在 一 端 进 行 插 入 与 删 除 的 线 性 表，一 般 称 插 入、删 除 的 这 一 端 为 栈 顶,另 一 端 为 栈 底。当 表 中 没 有 元 素 时 称 为 空 栈。栈 顶 元 素 总 是 后 被 插 入 日 勺 元 素，从 而 也 是 最 先 被 删 除 的 元 素；栈 底 元 素 总 是 最 先 被 插 入 的 元 素，从 而 也 是 最 终 才 能 被 删 除 的 元 素。栈 是 按 照 先 进 后 出 或 后 进 先 出 的 原 则 组 织 数 据 的。2.栈 的 次 序 存 储 及 其 运 算 用 一

17、维 数 组 S(1：m)作 为 栈 的 次 序 存 储 空 间，其 中 m为 最 大 容 量。在 栈 曰 勺 次 序 存 储 空 间 S(1：m)中，S(b o tto m)为 栈 底 元 素，S(t o p)为 栈 顶 元 素。top=0表 达 栈 空；top=m表 达 栈 满。栈 的 基 本 运 算 有 三 种：入 栈、退 栈 与 读 栈 顶 元 素。（1）入 栈 运 算：入 栈 运 算 是 指 在 栈 顶 位 置 插 入 一 种 新 元 素。首 先 将 栈 顶 指 针 加 一（即 top加 1）,然 后 将 新 元 素 插 入 到 栈 顶 指 针 指 向 的 位 置。当 栈 顶 指 针

18、已 经 指 向 存 储 空 间 的 最 终 一 种 位 置 时，阐 明 栈 空 间 已 满，不 也 许 再 进 行 入 栈 操 作。这 种 状 况 称 为 栈 上 溢 错 误。（2）退 栈 运 算：退 栈 是 指 取 出 栈 顶 元 素 并 赋 给 一 种 指 定 的 变 量。首 先 将 栈 顶 元 素（栈 顶 指 针 指 向 日 勺 元 素）赋 给 一 种 指 定 日 勺 变 量，然 后 将 栈 顶 指 针 减 一（即 top减 1）。当 栈 顶 指 针 为。时，阐 明 栈 空，不 可 进 行 退 栈 操 作。这 种 状 况 称 为 栈 的 下 溢 错 误。（3）读 栈 顶 元 素：读 栈

19、顶 元 素 是 指 将 栈 顶 元 素 赋 给 一 种 指 定 的 变 量。这 个 运 算 不 删 除 栈 顶 元 素，只 是 将 它 赋 给 一 种 变 量，因 此 栈 顶 指 针 不 会 变 化。当 栈 顶 指 针 为 0时，阐 明 栈 空，读 不 到 栈 顶 元 素。小 技 巧：栈 是 按 照“先 进 后 出 或 后 进 先 出 的 原 则 组 织 数 据，不 过 出 栈 方 式 有 多 种 选 择，在 考 题 中 常 常 考 察 多 种 不 一 样 日 勺 出 栈 方 式。考 点 6 线 性 链 表 的 基 本 概 念 考 试 链 接：考 点 6在 笔 试 考 试 中 出 现 日 勺

20、几 率 为 3 0%,重 要 是 以 选 择 口 勺 形 式 出 现，分 值 为 2分，此 考 点 为 识 记 内 容。重 点 识 记 结 点 时 构 成。在 链 式 存 储 方 式 中，规 定 每 个 结 点 由 两 部 分 构 成：一 部 分 用 于 寄 存 数 据 元 素 值，称 为 数 据 域，另 一 部 分 用 于 寄 存 指 针，称 为 指 针 域。其 中 指 针 用 于 指 向 该 结 点 口 勺 前 一 种 或 后 一 种 结 点（即 前 件 或 后 件）。链 式 存 储 方 式 既 可 用 于 表 达 线 性 构 造，也 可 用 于 表 达 非 线 性 构 造。(1)线 性

21、链 表 线 性 表 的 链 式 存 储 构 造 称 为 线 性 链 表。在 某 些 应 用 中，对 线 性 链 表 中 的 每 个 结 点 设 置 两 个 指 针，一 种 称 为 左 指 针，用 以 指 向 其 前 件 结 点；另 一 种 称 为 右 指 针，用 以 指 向 其 后 件 结 点。这 样 的 表 称 为 双 向 链 表。(2)带 链 的 栈 栈 也 是 线 性 表，也 可 以 采 用 链 式 存 储 构 造。带 链 的 栈 可 以 用 来 搜 集 计 算 机 存 储 空 间 中 所 有 空 闲 的 存 储 结 点，这 种 带 链 的 栈 称 为 可 运 用 栈。疑 难 解 答：在

22、 链 式 构 造 中，存 储 空 间 位 置 关 系 与 逻 辑 关 系 是 什 么？在 链 式 存 储 构 造 中，存 储 数 据 构 造 的 存 储 空 间 可 以 不 持 续，各 数 据 结 点 的 存 储 次 序 与 数 据 元 素 之 间 的 逻 辑 关 系 可 以 不 一 致，而 数 据 元 素 之 间 的 逻 辑 关 系 是 由 指 针 域 来 确 定 的。1.4树 与 二 叉 树 考 点 7 树 与 二 叉 树 及 其 基 本 性 质 考 试 链 接：考 点 7在 笔 试 考 试 中，是 一 种 必 考 的 内 容，在 笔 试 考 试 中 出 现 的 几 率 为 100%,重

23、要 是 以 选 择 日 勺 形 式 出 现，有 时 也 有 出 目 前 填 空 题 中，分 值 为 2分，此 考 点 为 重 点 掌 握 内 容。重 点 识 记 树 及 二 叉 树 的 性 质。误 区 警 示：满 二 叉 树 也 是 完 全 二 叉 树，而 完 全 二 叉 树 一 般 不 是 满 二 叉 树。应 当 注 意 两 者 的 区 别。1、树 的 基 本 概 念 树(tree)是 一 种 简 朴 的 非 线 性 构 造。在 树 构 造 中，每 一 种 结 点 只 有 一 种 前 件，称 为 父 结 点，没 有 前 件 的 结 点 只 有 一 种，称 为 树 的 根 结 点。每 一 种

24、结 点 可 以 有 多 种 后 件，它 们 称 为 该 结 点 的 子 结 点。没 有 后 件 的 结 点 称 为 叶 子 结 点。在 树 构 造 中，一 种 结 点 所 拥 有 的 后 件 个 数 称 为 该 结 点 的 度。叶 子 结 点 的 度 为。在 树 中，所 有 结 点 中 日 勺 最 大 的 度 称 为 树 的 度。2、二 叉 树 及 其 基 本 性 质(1)二 叉 树 日 勺 定 义 二 叉 树 是 一 种 很 有 用 的 非 线 性 构 造，具 有 如 下 两 个 特 点：非 空 二 叉 树 只 有 一 种 根 结 点；每 一 种 结 点 最 多 有 两 棵 子 树，且 分

25、别 称 为 该 结 点 口 勺 左 子 树 和 右 子 树。由 以 上 特 点 可 以 看 出，在 二 叉 树 中，每 一 种 结 点 的 度 最 大 为 2,即 所 有 子 树(左 子 树 或 右 子 树)也 均 为 二 叉 树，而 树 构 造 中 的 每 一 种 结 点 时 度 可 以 是 任 意 的。此 外,二 叉 树 中 口 勺 每 个 结 点 的 子 树 被 明 显 地 分 为 左 子 树 和 右 子 树。在 二 叉 树 中，一 种 结 点 可 以 只 有 左 子 树 而 没 有 右 子 树，也 可 以 只 有 右 子 树 而 没 有 左 子 树。当 一 种 结 点 既 没 有 左

26、子 树 也 没 有 右 子 树 时，该 结 点 即 为 叶 子 结 点。(2)二 叉 树 日 勺 基 本 性 质二 叉 树 具 有 如 下 几 种 性 质：性 质 1：在 二 叉 树 的 第 k层 上，最 多 有 2k-l(k l)个 结 点；性 质 2：深 度 为 m日 勺 二 叉 树 最 多 有 2m-l个 结 点；性 质 3:在 任 意 一 棵 二 叉 树 中，度 为。的 结 点(即 叶 子 结 点)总 是 比 度 为 2的 结 点 多 一 种。性 质 4：具 有 n个 结 点 口 勺 二 叉 树，其 深 度 至 少 为 lo&n+1,其 中 lo&n 表 达 取 1。理 n的 整 数

27、部 分。小 技 巧：在 二 叉 树 的 遍 历 中，无 论 是 前 序 遍 历，中 序 遍 历 还 是 后 序 遍 历，二 叉 树 日 勺 叶 子 结 点 的 先 后 次 序 都 是 不 变 日 勺 o3、满 二 叉 树 与 完 全 二 叉 树 满 二 叉 树 是 指 这 样 口 勺 一 种 二 叉 树：除 最 终 一 层 外，每 一 层 上 口 勺 所 有 结 点 均 有 两 个 子 结 点。在 满 二 叉 树 中，每 一 层 上 的 结 点 数 都 到 达 最 大 值，即 在 满 二 叉 树 的 第 k层 上 有 2k-l个 结 点，且 深 度 为 m日 勺 满 二 叉 树 有 2m-1

28、个 结 点。完 全 二 叉 树 是 指 这 样 的 二 叉 树：除 最 终 一 层 外，每 一 层 上 的 结 点 数 均 到 达 最 大 值;在 最 终 一 层 上 只 缺 乏 右 边 的 若 干 结 点。对 于 完 全 二 叉 树 来 说，叶 子 结 点 只 也 许 在 层 次 最 大 的 两 层 上 出 现：对 于 任 何 一 种 结 点，若 其 右 分 支 下 的 子 孙 结 点 时 最 大 层 次 为 P，则 其 左 分 支 下 的 子 孙 结 点 日 勺 最 大 层 次 或 为 P，或 为 p+1。完 全 二 叉 树 具 有 如 下 两 个 性 质:性 质 5:具 有 n个 结 点

29、 的 完 全 二 叉 树 的 深 度 为 lo&n+lo性 质 6:设 完 全 二 叉 树 共 有 n个 结 点。假 如 从 根 结 点 开 始，按 层 次(每 一 层 从 左 到 右)用 自 然 数 1,2,，n给 结 点 进 行 编 号，则 对 于 编 号 为 k(k=l,2,n)的 结 点 有 如 下 结 论：若 k=l,则 该 结 点 为 根 结 点，它 没 有 父 结 点；若 k l,则 该 结 点 的 父 结 点 编 号 为 INT(k/2)o 若 2 k W n,则 编 号 为 k的 结 点 的 左 子 结 点 编 号 为 2k；否 则 该 结 点 无 左 子 结 点(显 然 也

30、 没 有 右 子 结 点)。若 2 k+l n,则 编 号 为 k H勺 结 点 的 右 子 结 点 编 号 为 2 k+l；否 则 该 结 点 无 右 子 结 点。考 点 8 二 叉 树 日 勺 遍 历 考 试 链 接：考 点 8在 笔 试 考 试 中 考 核 几 率 为 3 0%,分 值 为 2分，读 者 应 当 纯 熟 掌 握 多 种 遍 历 的 详 细 算 法，能 由 两 种 遍 历 的 成 果 推 导 另 一 种 遍 历 的 成 果。在 遍 历 二 叉 树 的 过 程 中，一 般 先 遍 历 左 子 树，再 遍 历 右 子 树。在 先 左 后 右 口 勺 原 则 下，根 据 访 问

31、根 结 点 时 次 序，二 叉 树 日 勺 遍 历 分 为 三 类：前 序 遍 历、中 序 遍 历 和 后 序 遍 历。(1)前 序 遍 历：先 访 问 根 结 点、然 后 遍 历 左 子 树，最 终 遍 历 右 子 树；并 且，在 遍 历 左、右 子 树 时，仍 然 先 访 问 根 结 点，然 后 遍 历 左 子 树，最 终 遍 历 右 子 树。(2)中 序 遍 历：先 遍 历 左 子 树、然 后 访 问 根 结 点，最 终 遍 历 右 子 树；并 且，在遍 历 左、右 子 树 时，仍 然 先 遍 历 左 子 树，然 后 访 问 根 结 点，最 终 遍 历 右 子 树。(3)后 序 遍 历：

32、先 遍 历 左 子 树、然 后 遍 历 右 子 树，最 终 访 问 根 结 点；并 且，在 遍 历 左、右 子 树 时，仍 然 先 遍 历 左 子 树，然 后 遍 历 右 子 树，最 终 访 问 根 结 点。疑 难 解 答：树 与 二 叉 树 口 勺 不 一 样 之 处 是 什 么？在 二 叉 树 中，每 一 种 结 点 的 度 最 大 为 2,即 所 有 子 树(左 子 树 或 右 子 树)也 均 为 二 叉 树，而 树 构 造 中 日 勺 每 一 种 结 点 口 勺 度 可 以 是 任 意 日 勺。L5查 找 技 术 考 点 9 次 序 查 找 考 试 链 接：考 点 9在 笔 试 考 试

33、 中 考 核 几 率 在 30%,一 般 出 现 选 择 题 中，分 值 为 2分，读 者 应 当 详 细 掌 握 次 序 查 找 的 算 法。查 找 是 指 在 一 种 给 定 日 勺 数 据 构 造 中 查 找 某 个 指 定 日 勺 元 素。从 线 性 表 的 第 一 种 元 素 开 始，依 次 将 线 性 表 中 的 元 素 与 被 查 找 的 元 素 相 比 较，若 相 等 则 表 达 查 找 成 功；若 线 性 表 中 所 有 的 元 素 都 与 被 查 找 元 素 进 行 了 比 较 但 都 不 相 等，则 表 达 查 找 失 败。在 下 列 两 种 状 况 下 也 只 能 采

34、用 次 序 查 找：(1)假 如 线 性 表 为 无 序 表，则 不 管 是 次 序 存 储 构 造 还 是 链 式 存 储 构 造，只 能 用 次 序 查 找。(2)虽 然 是 有 序 线 性 表，假 如 采 用 链 式 存 储 构 造，也 只 能 用 次 序 查 找。考 点 1 0 二 分 法 查 找考 试 链 接：考 点 10在 笔 试 考 试 中 考 核 几 率 为 30%,一 般 出 现 填 空 题 中，分 值 为 2分，考 核 比 较 多 查 找 的 比 较 次 数，读 者 应 当 详 细 掌 握 二 分 查 找 法 的 算 法。二 分 法 只 合 用 于 次 序 存 储 的，按

35、非 递 减 排 列 的 有 序 表，其 措 施 如 下：设 有 序 线 性 表 的 长 度 为 n,被 查 找 的 元 素 为 i,(1)将 i与 线 性 表 口 勺 中 间 项 进 行 比 较；(2)若 i与 中 间 项 的 值 相 等，则 查 找 成 功；(3)若 i不 不 小 于 中 间 项，则 在 线 性 表 的 前 半 部 分 以 相 似 的 措 施 查 找；(4)若 i不 小 于 中 间 项，则 在 线 性 表 的 后 半 部 分 以 相 似 的 措 施 查 找。疑 难 解 答：二 分 查 找 法 合 用 于 哪 种 状 况？二 分 查 找 法 只 合 用 于 次 序 存 储 口

36、勺 有 序 表。在 此 所 说 的 有 序 表 是 指 线 性 表 中 的 元 素 按 值 非 递 减 排 列(即 从 小 到 大，但 容 许 相 邻 元 素 值 相 等)。这 个 过 程 一 直 进 行 到 查 找 成 功 或 子 表 长 度 为 0为 止。对 于 长 度 为 n的 有 序 线 性 表，在 最 坏 状 况 下，二 分 查 找 只 需 要 比 较 log2n次。1.6排 序 技 术 考 点 1 1 互 换 类 排 序 法 考 试 链 接：考 点 11属 于 比 较 难 的 内 容，一 般 以 选 择 题 的 形 式 考 察，考 核 几 率 为 3 0%,分 值 约 为 2分,读

37、 者 应 当 纯 熟 掌 握 几 种 排 序 算 法 的 基 本 过 程。冒 泡 排 序 法 和 迅 速 排 序 法 都 属 于 互 换 类 排 序 法。(1)冒 泡 排 序 法 首 先，从 表 头 开 始 往 后 扫 描 线 性 表，逐 次 比 较 相 邻 两 个 元 素 的 大 小，若 前 面 口 勺 元 素 不 小 于 背 面 日 勺 元 素，则 将 它 们 互 换，不 停 地 将 两 个 相 邻 元 素 中 日 勺 大 者 往 后 移 动，最 终 最 大 者 到 了 线 性 表 的 最 终。然 后，从 后 到 前 扫 描 剩 余 的 线 性 表，逐 次 比 较 相 邻 两 个 元 素

38、的 大 小，若 背 面 口 勺 元 素 不 不 小 于 前 面 的 元 素，则 将 它 们 互 换，不 停 地 将 两 个 相 邻 元 素 中 的 小 者 往 前 移 动,最 终 最 小 者 到 了 线 性 表 的 最 前 面。对 剩 余 日 勺 线 性 表 反 复 上 述 过 程，直 到 剩 余 的 线 性 表 变 空 为 止，此 时 已 经 排 好 序。在 最 坏 日 勺 状 况 下，冒 泡 排 序 需 要 比 较 次 数 为 n(n-1)/2。(2)迅 速 排 序 法 它 的 基 本 思 想 是：任 取 待 排 序 序 列 中 的 某 个 元 素 作 为 基 准(一 般 取 第 一 种

39、元 素)，通 过 一 趟 排 序，将 待 排 元 素 分 为 左 右 两 个 子 序 列，左 子 序 列 元 素 曰 勺 排 序 码 均 不 不 小 于 或 等 于 基 准 元 素 日 勺 排 序 码，右 子 序 列 的 排 序 码 则 不 小 于 基 准 元 素 的 排 序 码，然 后 分 别 对 两 个 子 序 列 继 续 进 行 排 序，直 至 整 个 序 列 有 序。疑 难 解 答：冒 泡 排 序 和 迅 速 排 序 的 平 均 执 行 时 间 分 别 是 多 少？冒 泡 排 序 法 的 平 均 执 行 时 间 是。(n2),而 迅 速 排 序 法 的 平 均 执 行 时 间 是 O(

40、nlO g2n)。第 二 章 程 序 设 计 基 础 通 过 对 部 分 考 生 的 调 查 以 及 对 近 年 真 题 的 总 结 分 析，笔 试 部 分 常 常 考 察 日 勺 是 构造 化 程 序 设 计 日 勺 原 则、面 向 对 象 措 施 口 勺 基 本 概 念，读 者 应 对 此 部 分 进 行 重 点 学 习。详 细 重 点 学 习 知 识 点：1.构 造 化 程 序 设 计 措 施 日 勺 四 个 原 则 2.对 象、类、消 息、继 承 口 勺 概 念、类 与 实 例 的 区 别 2.1构 造 化 程 序 设 计 考 点 1 构 造 化 程 序 设 计 日 勺 原 则 考 试

41、 链 接：考 点 1在 笔 试 考 试 中 出 现 日 勺 几 率 为 3 0%,重 要 是 以 选 择 题 的 形 式 出 现，分 值 为 2分，此 考 点 为 识 记 内 容，读 者 应 当 识 记 构 造 化 程 序 设 计 措 施 口 勺 四 个 重 要 原 则。20世 纪 70年 代 提 出 了 构 造 化 程 序 设 计”的 思 想 和 措 施。构 造 化 程 序 设 计 措 施 引 入 了 工 程 化 思 想 和 构 造 化 思 想，使 大 型 软 件 口 勺 开 发 和 编 程 得 到 了 极 大 的 改 善。构 造 化 程 序 设 计 措 施 的 重 要 原 则 为：自 顶

42、向 下、逐 渐 求 精、模 块 化 和 限 制 使 用 got。语 句。疑 难 解 答：怎 样 进 行 自 顶 向 下 设 计 措 施？程 序 设 计 时，应 先 考 虑 总 体，后 考 虑 细 节；先 考 虑 全 局 目 的，后 考 虑 局 部 目 日 勺；不 要 一 开 始 就 过 多 追 求 众 多 的 细 节，先 从 最 上 层 总 目 的 开 始 设 计，逐 渐 使 问 题 详 细 化。2.2面 向 对 象 的 程 序 设 计 考 点 2 面 向 对 象 措 施 的 基 本 概 念考 试 链 接：考 点 2在 笔 试 考 试 中，是 一 种 常 常 考 察 日 勺 内 容，在 笔 试

43、 考 试 中 出 现 的 几 率 为 7 0%,重 要 是 以 填 空 题 目 勺 形 式 出 现，分 值 为 2分，此 考 点 为 重 点 识 记 内 容，读 者 应 当 识 记 几 种 基 本 要 素 的 定 义、对 象 的 特 性 以 及 消 息、继 承、类 的 定 义。误 区 警 示：当 使 用 对 象 这 个 术 语 时，既 可 以 指 一 种 详 细 的 对 象，也 可 以 泛 指 一 般 口 勺 对 象，不 过 当 使 用 实 例 这 个 术 语 时，必 须 是 指 一 种 详 细 的 对 象。面 向 对 象 措 施 涵 盖 对 象 及 对 象 属 性 与 措 施、类、继 承、多

44、 态 性 几 种 基 本 要 素。(1)对 象 一 般 把 对 对 象 的 操 作 也 称 为 措 施 或 服 务。属 性 即 对 象 所 包 括 的 信 息，它 在 设 计 对 象 时 确 定，一 般 只 能 通 过 执 行 对 象 的 操 作 来 变 化。属 性 值 应 当 指 的 是 纯 粹 的 数 据 值，而 不 能 指 对 象。操 作 描 述 了 对 象 执 行 日 勺 功 能，若 通 过 信 息 的 传 递，还 可 认 为 其 他 对 象 使 用。对 象 具 有 如 下 特 性：标 识 惟 一 性、分 类 性、多 态 性、封 装 性、模 块 独 立 性。(2)类 和 实 例 类 是

45、 具 有 共 同 属 性、共 同 措 施 的 对 象 的 集 合。它 描 述 了 属 于 该 对 象 类 型 的 所 有 对 象 的 性 质，而 一 种 对 象 则 是 其 对 应 类 的 一 种 实 例。类 是 有 关 对 象 性 质 口 勺 描 述，它 同 对 象 同 样，包 括 一 组 数 据 属 性 和 在 数 据 上 口 勺 一 组 合 法 操 作。（3）消 息 消 息 是 实 例 之 间 传 递 的 信 息，它 祈 求 对 象 执 行 某 一 处 理 或 回 答 某 一 规 定 的 信 息，它 统 一 了 数 据 流 和 控 制 流。一 种 消 息 由 三 部 分 构 成：接 受

46、消 息 的 对 象 的 名 称、消 息 标 识 符（消 息 名）和 零 个 或 多 种 参 数。（4）继 承 广 义 地 说，继 承 是 指 可 以 直 接 获 得 已 经 有 的 性 质 和 特 性，而 不 必 反 复 定 义 它 们。继 承 分 为 单 继 承 与 多 重 继 承。单 继 承 是 指，一 种 类 只 容 许 有 一 种 父 类，即 类 等 级 为 树 形 构 造。多 重 继 承 是 指，一 种 类 容 许 有 多 种 父 类。（5）多 态 性 对 象 根 据 所 接 受 的 消 息 而 做 出 动 作，同 样 日 勺 消 息 被 不 一 样 的 对 象 接 受 时 可 导

47、致 完 全 不 一 样 的 行 动，该 现 象 称 为 多 态 性。疑 难 解 答：能 举 一 下 现 实 中 的 对 象 及 其 属 性 和 操 作 吗？一 辆 汽 车 是 一 种 对 象，它 包 括 了 汽 车 日 勺 属 性（如 颜 色、型 号 等）及 其 操 作（如 启 动、刹 车 等）。一 种 窗 口 是 对 象，它 包 括 了 窗 口 的 属 性（如 大 小、颜 色 等）及 其 操 作（如 打 开、关 闭 等）。第 三 章 软 件 工 程 基 础 通 过 对 部 分 考 生 日 勺 调 查 以 及 对 近 年 真 题 的 总 结 分 析，笔 试 部 分 常 常 考 察 口 勺 是

48、软 件 生 命 周 期、软 件 设 计 日 勺 基 本 原 理，软 件 测 试 日 勺 目 日 勺、软 件 调 试 日 勺 基 本 概 念，读 者应 对 此 部 分 进 行 重 点 学 习。详 细 重 点 学 习 知 识 点：1.软 件 的 概 念、软 件 生 命 周 期 日 勺 概 念 及 各 阶 段 所 包 括 的 活 动 2.概 要 设 计 与 详 细 设 计 的 概 念、模 块 独 立 性 及 其 度 量 日 勺 原 则、详 细 设 计 常 用 的 工 具 3.软 件 测 试 日 勺 目 日 勺、软 件 测 试 口 勺 4个 环 节、4.软 件 调 试 的 任 务 3.1软 件 工 程

49、 基 本 概 念 考 点 1 软 件 定 义 与 软 件 特 点 考 试 链 接：考 点 1在 笔 试 考 试 中，是 一 种 常 常 考 察 日 勺 内 容，考 核 口 勺 几 率 为 7 0%,重 要 是 以 选 择 题 的 形 式 出 现，分 值 为 2分，此 考 点 为 识 记 内 容，读 者 应 当 识 记 软 件 的 定 义，特 点 及 其 分 类。软 件 指 的 是 计 算 机 系 统 中 与 硬 件 互 相 依 存 的 另 一 部 分，包 括 程 序、数 据 和 有 关 文 档 日 勺 完 整 集 合。程 序 是 软 件 开 发 人 员 根 据 顾 客 需 求 开 发 的、用

50、程 序 设 计 语 言 描 述 的、适 合 计 算 机 执 行 的 指 令 序 列。数 据 是 使 程 序 能 正 常 操 纵 信 息 的 数 据 构 造。文 档 是 与 程 序 的 开 发、维 护 和 使 用 有 关 日 勺 图 文 资 料。可 见，软 件 由 两 部 分 构 成：(1)机 器 可 执 行 的 程 序 和 数 据；(2)机 器 不 可 执 行 的，与 软 件 开 发、运 行、维 护、使 用 等 有 关 的 文 档。软 件 日 勺 特 点：(1)软 件 是 逻 辑 实 体，而 不 是 物 理 实 体，具 有 抽 象 性；(2)没 有 明 显 日 勺 制 作 过 程，可 进 行