二级公共基础考点解析.pdf

《二级公共基础考点解析.pdf》由会员分享，可在线阅读，更多相关《二级公共基础考点解析.pdf（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 一 章 数 据 结 构 与 算 法(江 苏 大 学,袁 猛)2012.9.20经 过 对 部 分 考 生 的 调 查 以 及 对 近 年 真 题 的 总 结 分 析，笔 试 部 分 经 常 考 查 的 是 算 法 复 杂 度、数 据 结 构 的 概 念、栈、二 叉 树 的 遍 历、二 分 法 查 找，读 者 应 对 此 部 分 进 行 重 点 学 习。详 细 重 点 学 习 知 识 点：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表 示)，它 是 问 题 规 模 的 函 数。即 算 法 的 工 作 量=f(n)2.算 法 的 空 间 复 杂 度 算 法 的 空 间 复 杂 度 是 指 执 行 这 个 算 法 所 需 要 的 内 存 空 间。一 个 算 法 所 占 用 的 存 储 空 间 包 括 算 法 程 序 所 占 的 空 间、输 入 的 初 始 数 据 所 占 的 存 储 空 间 以 及 算 法 执 行 过 程 中 所 需 要 的 额 外 空 间。其 中 额 外 空 间 包 括 算 法 程 序 执 行 过 程 中 的 工 作 单 元 以 及 某 种 数 据 结 构 所

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

8、(n),其 中 n是 问 题 的 规 模。1.2数 据 结 构 的 基 本 概 念 考 点 3 数 据 结 构 的 定 义 考 试 链 接：考 点 3在 笔 试 考 试 中，是 一 个 经 常 考 查 的 内 容，在 笔 试 考 试 中 出 现 的 几 率 为 7 0%,主 要 是 以 选 择 的 形 式 出 现，分 值 为 2分，此 考 点 为 识 记 内 容，读 者 还 应 该 识，己 数 据 的 逻 辑 结 构 和 存 储 结 构 的 概 念.数 据 结 构 作 为 计 算 机 的 一 门 学 科，主 要 研 究 和 讨 论 以 下 三 个 方 面：(1)数 据 集 合 中 个 数 据

9、元 素 之 间 所 固 有 的 逻 辑 关 系，即 数 据 的 逻 辑 结 构；(2)在 对 数 据 元 素 进 行 处 理 时，各 数 据 元 素 在 计 算 机 中 的 存 储 关 系，即 数 据 的 存 储 结 构；(3)对 各 种 数 据 结 构 进 行 的 运 算。数 据：是 对 客 观 事 物 的 符 号 表 示，在 计 算 机 科 学 中 是 指 所 有 能 输 入 到 计 算 机 中 并 被 计 算 机 程 序 处 理 的 符 号 的 总 称。数 据 元 素：是 数 据 的 基 本 单 位，在 计 算 机 程 序 中 通 常 作 为 一 个 整 体 进 行 考 虑 和 处 理。

10、数 据 对 象：是 性 质 相 同 的 数 据 元 素 的 集 合，是 数 据 的 一 个 子 集。数 据 的 逻 辑 结 构 是 对 数 据 元 素 之 间 的 逻 辑 关 系 的 描 述，它 可 以 用 一 个 数 据 元 素 的 集 合 和 定 义 在 此 集 合 中 的 若 干 关 系 来 表 示。数 据 的 逻 辑 结 构 有 两 个 要 素：一 是 数 据 元 素 的 集 合，通 常 记 为 D；二 是 D 上 的 关 系，它 反 映 了 数 据 元 素 之 间 的 前 后 件 关 系，通 常 记 为 R。个 数 据 结 构 可 以 表 示 成 B=(D,R)其 中 B表 示 数

11、据 结 构。为 了 反 映 D 中 各 数 据 元 素 之 间 的 前 后 件 关 系，一 般 用 二 元 组 来 表 示。数 据 的 逻 辑 结 构 在 计 算 机 存 储 空 间 中 的 存 放 形 式 称 为 数 据 的 存 储 结 构(也 称 数 据 的 物 理 结 构)。由 于 数 据 元 素 在 计 算 机 存 储 空 间 中 的 位 置 关 系 可 能 与 逻 辑 关 系 不 同，因 此，为 了 表 示 存 放 在 计 算 机 存 储 空 间 中 的 各 数 据 元 素 之 间 的 逻 辑 关 系(即 前 后 件 关 系)，在 数 据 的 存 储 结 构 中，不 仅 要 存 放

12、各 数 据 元 素 的 信 息，还 需 要 存 放 各 数 据 元 素 之 间 的 前 后 件 关 系 的 信 息。种 数 据 的 逻 辑 结 构 根 据 需 要 可 以 表 示 成 多 种 存 储 结 构，常 用 的 存 储 结 构 有 顺 序、链 接、索 引 等 存 储 结 构。而 采 用 不 同 的 存 储 结 构，其 数 据 处 理 的 效 率 是 不 同 的。因 此，在 进 行 数 据 处 理 时，选 择 合 适 的 存 储 结 构 是 很 重 要 的。考 点 4 线 性 结 构 与 非 线 性 结 构 考 试 链 接：考 点 4在 笔 试 考 试 中，虽 然 说 不 是 考 试 经

13、 常 考 查 的 内 容，但 读 者 还 是 对 此 考 点 有 所 了 解，在 笔 试 考 试 中 出 现 的 几 率 为 30%,主 要 是 以 填 空 题 出 现 的 形 式 出 现，分 值 为 2分，此 考 点 为 识 记 内 容.根 据 数 据 结 构 中 各 数 据 元 素 之 间 前 后 件 关 系 的 复 杂 程 度，一 般 将 数 据 结 构 分 为 两 大 类 型：线 性 结 构 与 非 线 性 结 构。如 果 一 个 非 空 的 数 据 结 构 满 足 下 列 两 个 条 件：(1)有 且 只 有 一 个 根 结 点；(2)每 一 个 结 点 最 多 有 一 个 前 件，

14、也 最 多 有 一 个 后 件。则 称 该 数 据 结 构 为 线 性 结 构。线 性 结 构 又 称 线 性 表。在 一 个 线 性 结 构 中 插 入 或 删 除 任 何 一 个 结 点 后 还 应 是 线 性 结 构。如 果 一 个 数 据 结 构 不 是 线 性 结 构，则 称 之 为 非 线 性 结 构。疑 难 解 答：空 的 数 据 结 构 是 线 性 结 构 还 是 非 线 性 结 构？一 个 空 的 数 据 结 构 究 竟 是 属 于 线 性 结 构 还 是 属 非 线 性 结 构，这 要 根 据 具 体 情 况 来 确 定。如 果 对 该 数 据 结 构 的 算 法 是 按

15、线 性 结 构 的 规 则 来 处 理 的，则 属 于 线 性 结 构；否 则 属 于 非 线 性 结 构。1.3栈 及 线 性 链 表 考 点 5 栈 及 其 基 本 运 算 考 试 链 接：考 点 5在 笔 试 考 试 中，是 一 个 必 考 的 内 容，在 笔 试 考 试 中 出 现 的 几 率 为 100%,主 要 是 以 选 择 的 形 式 出 现，分 值 为 2分，此 考 点 为 重 点 掌 握 内 容，读 者 应 该 掌 握 栈 的 运 算.1.栈 的 基 本 概 念 栈 是 限 定 只 在 一 端 进 行 插 入 与 删 除 的 线 性 表，通 常 称 插 入、删 除 的 这

16、端 为 栈 顶，另 端 为 栈 底。当 表 中 没 有 元 素 时 称 为 空 栈。栈 顶 元 素 总 是 后 被 插 入 的 元 素，从 而 也 是 最 先 被 删 除 的 元 素；栈 底 元 素 总 是 最 先 被 插 入 的 元 素，从 而 也 是 最 后 才 能 被 删 除 的 元 素。栈 是 按 照 先 进 后 出 或 后 进 先 出”的 原 则 组 织 数 据 的。2.栈 的 顺 序 存 储 及 其 运 算 用 一 维 数 组 S（1：m）作 为 栈 的 顺 序 存 储 空 间，其 中 m 为 最 大 容 量。在 栈 的 顺 序 存 储 空 间 S（1：m）中，S（bottom）为

17、 栈 底 元 素，S（top）为 栈 顶 元 素。top=0表 示 栈 空;top=m表 示 栈 满。栈 的 基 本 运 算 有 三 种：入 栈、退 栈 与 读 栈 顶 元 素。（1）入 栈 运 算：入 栈 运 算 是 指 在 栈 顶 位 置 插 入 一 个 新 元 素。首 先 将 栈 顶 指 针 加 一（即 top加 1）,然 后 将 新 元 素 插 入 到 栈 顶 指 针 指 向 的 位 置。当 栈 顶 指 针 已 经 指 向 存 储 空 间 的 最 后 一 个 位 置 时，说 明 栈 空 间 已 满，不 可 能 再 进 行 入 栈 操 作。这 种 情 况 称 为 栈”上 溢 错 误。（2

18、）退 栈 运 算：退 栈 是 指 取 出 栈 顶 元 素 并 赋 给 一 个 指 定 的 变 量。首 先 将 栈 顶 元 素（栈 顶 指 针 指 向 的 元 素）赋 给 一 个 指 定 的 变 量，然 后 将 栈 顶 指 针 减 一（即 top减 1）。当 栈 顶 指 针 为 0时，说 明 栈 空，不 可 进 行 退 栈 操 作。这 种 情 况 称 为 栈 的 卜 溢 错 误。（3）读 栈 顶 元 素：读 栈 顶 元 素 是 指 将 栈 顶 元 素 赋 给 一 个 指 定 的 变 量。这 个 运 算 不 删 除 栈 顶 元 素，只 是 将 它 赋 给 一 个 变 量，因 此 栈 顶 指 针 不

19、 会 改 变。当 栈 顶 指 针 为 0时，说 明 栈 空，读 不 到 栈 顶 元 素。小 技 巧：栈 是 按 照“先 进 后 出 或 后 进 先 出”的 原 则 组 织 数 据，但 是 出 栈 方 式 有 多 种 选 择，在 考 题 中 经 常 考 查 各 种 不 同 的 出 栈 方 式。考 点 6 线 性 链 表 的 基 本 概 念 考 试 链 接：考 点 6在 笔 试 考 试 中 出 现 的 几 率 为 3 0%,主 要 是 以 选 择 的 形 式 出 现，分 值 为 2分，此 考 点 为 识 记 内 容。重 点 识 记 结 点 的 组 成.在 链 式 存 储 方 式 中，要 求 每 个

20、 结 点 由 两 部 分 组 成：一 部 分 用 于 存 放 数 据 元 素 值，称 为 数 据 域，另 一 部 分 用 于 存 放 指 针，称 为 指 针 域。其 中 指 针 用 于 指 向 该 结 点 的 前 一 个 或 后 一 个 结 点（即 前 件 或 后 件）。链 式 存 储 方 式 既 可 用 于 表 示 线 性 结 构，也 可 用 于 表 示 非 线 性 结 构。（1）线 性 链 表 线 性 表 的 链 式 存 储 结 构 称 为 线 性 链 表。在 某 些 应 用 中，对 线 性 链 表 中 的 每 个 结 点 设 置 两 个 指 针，一 个 称 为 左 指 针，用 以 指 向

21、 其 前 件 结 点；另 一 个 称 为 右 指 针，用 以 指 向 其 后 件 结 点。这 样 的 表 称 为 双 向 链 表。（2）带 链 的 栈 栈 也 是 线 性 表，也 可 以 采 用 链 式 存 储 结 构。带 链 的 栈 可 以 用 来 收 集 计 算 机 存 储 空 间 中 所 有 空 闲 的 存 储 结 点，这 种 带 链 的 栈 称 为 可 利 用 栈。疑 难 解 答：在 链 式 结 构 中，存 储 空 间 位 置 关 系 与 逻 辑 关 系 是 什 么？在 链 式 存 储 结 构 中，存 储 数 据 结 构 的 存 储 空 间 可 以 不 连 续，各 数 据 结 点 的

22、存 储 顺 序 与 数 据 元 素 之 间 的 逻 辑 关 系 可 以 不 一 致，而 数 据 元 素 之 间 的 逻 辑 关 系 是 由 指 针 域 来 确 定 的。1.4树 与 二 叉 树 考 点 7 树 与 二 叉 树 及 其 基 本 性 质 考 试 链 接：考 点 7在 笔 试 考 试 中，是 一 个 必 考 的 内 容，在 笔 试 考 试 中 出 现 的 几 率 为 100%,主 要 是 以 选 择 的 形 式 出 现，有 时 也 有 出 现 在 填 空 题 中，分 值 为 2分，此 考 点 为 重 点 掌 握 内 容。重 点 识 记 树 及 二 叉 树 的 性 质.误 区 警 示：

23、满 二 叉 树 也 是 完 全 二 叉 树，而 完 全 二 叉 树 一 般 不 是 满 二 叉 树.应 该 注 意 二 者 的 区 别。1、树 的 基 本 概 念 树(tr e e)是 一 种 简 单 的 非 线 性 结 构。在 树 结 构 中，卷 一 个 结 点 只 有 一 个 前 件，称 为 父 结 点，没 有 前 件 的 结 点 只 有 一 个，称 为 树 的 根 结 点。每 一 个 结 点 可 以 有 多 个 后 件，它 们 称 为 该 结 点 的 子 结 点。没 有 后 件 的 结 点 称 为 叶 子 结 点。在 树 结 构 中，一 个 结 点 所 拥 有 的 后 件 个 数 称 为

24、 该 结 点 的 度。叶 子 结 点 的 度 为 0。在 树 中，所 有 结 点 中 的 最 大 的 度 称 为 树 的 度。2、二 叉 树 及 其 基 本 性 质(1)二 叉 树 的 定 义 二 叉 树 是 一 种 很 有 用 的 非 线 性 结 构，具 有 以 下 两 个 特 点：非 空 二 叉 树 只 有 一 个 根 结 点；每 一 个 结 点 最 多 有 两 棵 子 树，且 分 别 称 为 该 结 点 的 左 子 树 和 右 子 树。由 以 上 特 点 可 以 看 出，在 二 叉 树 中，每 一 个 结 点 的 度 最 大 为 2,即 所 有 子 树(左 子 树 或 右 子 树)也 均

25、 为 二 叉 树，而 树 结 构 中 的 每 一 个 结 点 的 度 可 以 是 任 意 的。另 外，二 叉 树 中 的 每 个 结 点 的 子 树 被 明 显 地 分 为 左 子 树 和 右 子 树。在 二 叉 树 中，一 个 结 点 可 以 只 有 左 子 树 而 没 有 右 子 树，也 可 以 只 有 右 子 树 而 没 有 左 子 树。当 一 个 结 点 既 没 有 左 子 树 也 没 有 右 子 树 时，该 结 点 即 为 叶 子 结 点。(2)二 叉 树 的 基 本 性 质 二 叉 树 具 有 以 下 儿 个 性 质：性 质 1：在 二 叉 树 的 第 k层 上，最 多 有 2k-

26、l(k 2 l)个 结 点；性 质 2：深 度 为 m的 二 叉 树 最 多 有 2m-l个 结 点；性 质 3：在 任 意 一 棵 二 叉 树 中，度 为 0的 结 点(即 叶 子 结 点)总 是 比 度 为 2的 结 点 多 一 个。性 质 4：具 有 n个 结 点 的 二 叉 树，其 深 度 至 少 为 log2n+1,其 中 logzn 表 示 取 log2n的 整 数 部 分。小 技 巧：在 二 叉 树 的 遍 历 中，无 论 是 前 序 遍 历，中 序 遍 历 还 是 后 序 遍 历，.:叉 树 的 叶 子 结 点 的 先 后 顺 序 都 是 不 变 的。3、满 二 叉 树 与 完

27、 全 二 叉 树 满 二 叉 树 是 指 这 样 的 一 种 二 叉 树：除 最 后 一 层 外，每 一 层 上 的 所 有 结 点 都 有 两 个 子 结 点。在 满 二 叉 树 中，每 一 层 上 的 结 点 数 都 达 到 最 大 值，即 在 满 二 叉 树 的 第 k层 上 有 2k-l个 结 点，且 深 度 为 m的 满 二 叉 树 有 2m1个 结 点。完 全 二 叉 树 是 指 这 样 的 二 叉 树：除 最 后 一 层 外，每 层 上 的 结 点 数 均 达 到 最 大 值；在 最 后 一 层 上 只 缺 少 右 边 的 若 干 结 点。对 于 完 全 二 义 树 来 说，叶

28、子 结 点 只 可 能 在 层 次 最 大 的 两 层 上 出 现：对 于 任 何 一 个 结 点，若 其 右 分 支 下 的 子 孙 结 点 的 最 大 层 次 为 P，则 其 左 分 支 下 的 子 孙 结 点 的 最 大 层 次 或 为 p,或 为 p+1。完 全 二 叉 树 具 有 以 下 两 个 性 质：性 质 5:具 有 n个 结 点 的 完 全 二 义 树 的 深 度 为 logzn+1。性 质 6:设 完 全 二 叉 树 共 有 n个 结 点。如 果 从 根 结 点 开 始，按 层 次(每 一 层 从 左 到 右)用 自 然 数 1,2,，n给 结 点 进 行 编 号，则 对

29、于 编 号 为 k(k=l,2,，n)的 结 点 有 以 下 结 论：若 k=l,则 该 结 点 为 根 结 点，它 没 有 父 结 点；若 k l,则 该 结 点 的 父 结 点 编 号 为 INT(k/2)。若 2 k W n,则 编 号 为 k的 结 点 的 左 子 结 点 编 号 为 2k；否 则 该 结 点 无 左 子 结 点(显 然 也 没 有 右 子 结 点)。若 2k+lWn,则 编 号 为 k的 结 点 的 右 子 结 点 编 号 为 2k+l；否 则 该 结 点 无 右 子 结 点。考 点 8 二 叉 树 的 遍 历 考 试 链 接：考 点 8在 笔 试 考 试 中 考 核

30、 几 率 为 3 0%,分 值 为 2分，读 者 应 该 熟 练 掌 握 各 种 遍 历 的 具 体 算 法，能 由 两 种 遍 历 的 结 果 推 导 另 一 种 遍 历 的 结 果.在 遍 历 二 叉 树 的 过 程 中，一 般 先 遍 历 左 子 树，再 遍 历 右 子 树。在 先 左 后 右 的 原 则 下，根 据 访 问 根 结 点 的 次 序，二 叉 树 的 遍 历 分 为 三 类：前 序 遍 历、中 序 遍 历 和 后 序 遍 历。(1)前 序 遍 历：先 访 问 根 结 点、然 后 遍 历 左 子 树，最 后 遍 历 右 子 树；并 且，在 遍 历 左、右 子 树 时,仍 然

31、先 访 问 根 结 点，然 后 遍 历 左 子 树，最 后 遍 历 右 子 树。(2)中 序 遍 历：先 遍 历 左 子 树、然 后 访 问 根 结 点，最 后 遍 历 右 子 树；并 且，在 遍 历 左、右 子 树 时,仍 然 先 遍 历 左 子 树，然 后 访 问 根 结 点，最 后 遍 历 右 子 树。(3)后 序 遍 历：先 遍 历 左 子 树、然 后 遍 历 右 子 树，最 后 访 问 根 结 点；并 且，在 遍 历 左、右 子 树 时,仍 然 先 遍 历 左 子 树，然 后 遍 历 右 子 树，最 后 访 问 根 结 点。疑 难 解 答：树 与 二 叉 树 的 不 同 之 处 是

32、什 么？在 二 叉 树 中，每 一 个 结 点 的 度 最 大 为 2,即 所 有 子 树(左 子 树 或 右 子 树)也 均 为 二 叉 树，而 树 结 构 中 的 每 一 个 结 点 的 度 可 以 是 任 意 的。1.5查 找 技 术 考 点 9 顺 序 查 找 考 试 链 接：考 点 9在 笔 试 考 试 中 考 核 几 率 在 30%,一 般 出 现 选 择 题 中，分 值 为 2分，读 者 应 该 具 体 掌 握 顺 序 查 找 的 算 法.查 找 是 指 在 一 个 给 定 的 数 据 结 构 中 查 找 某 个 指 定 的 元 素。从 线 性 表 的 第 一 个 元 素 开 始

33、，依 次 将 线 性 表 中 的 元 素 与 被 查 找 的 元 素 相 比 较，若 相 等 则 表 示 查 找 成 功；若 线 性 表 中 所 有 的 元 素 都 与 被 查 找 元 素 进 行 了 比 较 但 都 不 相 等，则 表 示 查 找 失 败。在 下 列 两 种 情 况 下 也 只 能 采 用 顺 序 查 找：(1)如 果 线 性 表 为 无 序 表，则 不 管 是 顺 序 存 储 结 构 还 是 链 式 存 储 结 构，只 能 用 顺 序 查 找。(2)即 使 是 有 序 线 性 表，如 果 采 用 链 式 存 储 结 构，也 只 能 用 顺 序 查 找。考 点 1 0 二 分

34、 法 查 找 考 试 链 接：考 点 10在 笔 试 考 试 中 考 核 几 率 为 30%,一 般 出 现 填 空 题 中，分 值 为 2分，考 核 比 较 多 查 找 的 比 较 次 数，读 者 应 该 具 体 掌 握 二 分 查 找 法 的 算 法.二 分 法 只 适 用 于 顺 序 存 储 的，按 非 递 减 排 列 的 有 序 表，其 方 法 如 下：设 有 序 线 性 表 的 长 度 为 n,被 查 找 的 元 素 为 i,(1)将 i与 线 性 表 的 中 间 项 进 行 比 较；(2)若 i与 中 间 项 的 值 相 等，则 查 找 成 功；(3)若 i小 于 中 间 项，则

35、在 线 性 表 的 前 半 部 分 以 相 同 的 方 法 查 找；(4)若 i大 于 中 间 项，则 在 线 性 表 的 后 半 部 分 以 相 同 的 方 法 查 找。疑 难 解 答：二 分 查 找 法 适 用 于 哪 种 情 况？二 分 查 找 法 只 适 用 于 顺 序 存 储 的 有 序 表。在 此 所 说 的 有 序 表 是 指 线 性 表 中 的 元 素 按 值 非 递 减 排 列(即 从 小 到 大，但 允 许 相 邻 元 素 值 相 等)。这 个 过 程 一 直 进 行 到 查 找 成 功 或 子 表 长 度 为 0为 止。对 于 长 度 为 n的 有 序 线 性 表，在 最

36、 坏 情 况 下，二 分 查 找 只 需 要 比 较 log2n次。1.6排 序 技 术 考 点 1 1 交 换 类 排 序 法 考 试 链 接：考 点 11属 于 比 较 难 的 内 容，一 般 以 选 择 题 的 形 式 考 查，考 核 几 率 为 3 0%,分 值 约 为 2分，读 者 应 该 熟 练 掌 握 几 种 排 序 算 法 的 基 本 过 程.冒 泡 排 序 法 和 快 速 排 序 法 都 属 于 交 换 类 排 序 法。（1）冒 泡 排 序 法 首 先，从 表 头 开 始 往 后 扫 描 线 性 表，逐 次 比 较 相 邻 两 个 元 素 的 大 小，若 前 面 的 元 素

37、大 于 后 面 的 元 素,则 将 它 们 互 换，不 断 地 将 两 个 相 邻 元 素 中 的 大 者 往 后 移 动，最 后 最 大 者 到 了 线 性 表 的 最 后。然 后，从 后 到 前 扫 描 剩 下 的 线 性 表，逐 次 比 较 相 邻 两 个 元 素 的 大 小，若 后 面 的 元 素 小 于 前 面 的 元 素,则 将 它 们 互 换，不 断 地 将 两 个 相 邻 元 素 中 的 小 者 往 前 移 动，最 后 最 小 者 到 了 线 性 表 的 最 前 面。对 剩 下 的 线 性 表 重 复 上 述 过 程，直 到 剩 下 的 线 性 表 变 空 为 止，此 时 已

38、经 排 好 序。在 最 坏 的 情 况 下，冒 泡 排 序 需 要 比 较 次 数 为 n（n-1）/2。（2）快 速 排 序 法 它 的 基 本 思 想 是：任 取 待 排 序 序 列 中 的 某 个 元 素 作 为 基 准（一 般 取 第 一 个 元 素），通 过 一 趟 排 序，将 待 排 元 素 分 为 左 右 两 个 子 序 列，左 子 序 列 元 素 的 排 序 码 均 小 于 或 等 于 基 准 元 素 的 排 序 码，右 子 序 列 的 排 序 码 则 大 于 基 准 元 素 的 排 序 码，然 后 分 别 对 两 个 子 序 列 继 续 进 行 排 序，直 至 整 个 序 列

39、 有 序。疑 难 解 答：冒 泡 排 序 和 快 速 排 序 的 平 均 执 行 时 间 分 别 是 多 少？冒 泡 排 序 法 的 平 均 执 行 时 间 是 O（，），而 快 速 排 序 法 的 平 均 执 行 时 间 是 O（n lo g a）。1.7 例 题 详 解、选 择 题【例 1】算 法 的 时 间 复 杂 度 取 决 于。（考 点 2）A）问 题 的 规 模 B）待 处 理 的 数 据 的 初 态 C）问 题 的 难 度 D）A）和 B）解 析：算 法 的 时 间 复 杂 度 不 仅 与 问 题 的 规 模 有 关，在 同 一 个 问 题 规 模 下，而 且 与 输 入 数 据

40、 有 关。即 与 输 入 数 据 所 有 的 可 能 取 值 范 围、输 入 各 种 数 据 或 数 据 集 的 概 率 有 关。答 案：D）【例 2】在 数 据 结 构 中，从 逻 辑 上 可 以 把 数 据 结 构 分 成 o（考 点 3）A）内 部 结 构 和 外 部 结 构 B）线 性 结 构 和 非 线 性 结 构 C）紧 凑 结 构 和 非 紧 凑 结 构 D）动 态 结 构 和 静 态 结 构 解 析：逻 辑 结 构 反 映 数 据 元 素 之 间 的 逻 辑 关 系，线 性 结 构 表 示 数 据 元 素 之 间 为 对 一 的 关 系，非 线 性 结 构 表 示 数 据 元

41、素 之 间 为 一 对 多 或 者 多 对 的 关 系，所 以 答 案 为 B）。答 案：B）【例 3】以 下 不 是 栈 的 基 本 运 算。（考 点 5）A）判 断 栈 是 否 为 素 空 B）将 栈 置 为 空 栈 C）删 除 栈 顶 元 素 D）删 除 栈 底 元 素 解 析：栈 的 基 本 运 算 有：入 栈，出 栈（删 除 栈 顶 元 素），初 始 化、置 空、判 断 栈 是 否 为 空 或 满、提 取 栈 顶 元 素 等，对 栈 的 操 作 都 是 在 栈 顶 进 行 的。答 案：D）【例 4】链 表 不 具 备 的 特 点 是。（考 点 6）A）可 随 机 访 问 任 意 一

42、个 结 点 B）插 入 和 删 除 不 需 要 移 动 任 何 元 素 C）不 必 事 先 估 计 存 储 空 间 D）所 需 空 间 与 其 长 度 成 正 比解 析：顺 序 表 可 以 随 机 访 问 任 意 个 结 点，而 链 表 必 须 从 第 一 个 数 据 结 点 出 发，逐 一 查 找 每 个 结 点。所 以 答 案 为 A）。答 案：A）【例 5】已 知 某 二 叉 树 的 后 序 遍 历 序 列 是 D A C B E,中 序 遍 历 序 列 是 D E B A C,则 它 的 前 序 遍 历 序 列 是。（考 点 8）A）ACBED B）DEABCC）DECAB D）EDB

43、AC解 析：后 序 遍 历 的 顺 序 是“左 子 树 一 右 子 树 一 根 结 点”;中 序 遍 历 顺 序 是“左 子 树 一 根 结 点 一 右 子 树”;前 序 遍 历 顺 序 是 根 结 点 一 左 子 树 一 右 子 树 根 据 各 种 遍 历 算 法，不 难 得 出 前 序 遍 历 序 列 是 EDBAC。所 以 答 案 为 D）。答 案：D）【例 6】设 有 一 个 已 按 各 元 素 的 值 排 好 序 的 线 性 表（长 度 大 于 2）,对 给 定 的 值 k,分 别 用 顺 序 查 找 法 和 二 分 查 找 法 查 找 一 个 与 k相 等 的 元 素，比 较 的

44、次 数 分 别 是 s和 b,在 查 找 不 成 功 的 情 况 卜，s和 b的 关 系 是。（考 点 9）A）s=b B）sb C）s Llog2n+1。答 案：B）【例 7】在 快 速 排 序 过 程 中，每 次 划 分，将 被 划 分 的 表（或 子 表）分 成 左、右 两 个 子 表，考 虑 这 两 个 子 表，下 列 结 论 一 定 正 确 的 是。（考 点 11）A）左、右 两 个 子 表 都 已 各 自 排 好 序 B）左 边 子 表 中 的 元 素 都 不 大 于 右 边 子 表 中 的 元 素 C）左 边 子 表 的 长 度 小 于 右 边 子 表 的 长 度 D）左、右 两

45、 个 子 表 中 元 素 的 平 均 值 相 等 解 析：快 速 排 序 基 本 思 想 是：任 取 待 排 序 表 中 的 某 个 元 素 作 为 基 准（般 取 第 一 个 元 素），通 过 趟 排 序，将 待 排 元 素 分 为 左 右 两 个 子 表，左 子 表 元 素 的 排 序 码 均 小 于 或 等 于 基 准 元 素 的 排 序 码，右 子 表 的 排 序 码 则 大 于 基 准 元 素 的 排 序 码，然 后 分 别 对 两 个 子 表 继 续 进 行 排 序，直 至 整 个 表 有 序。答 案：B）二、填 空 题【例 1】问 题 处 理 方 案 的 正 确 而 完 整 的

46、描 述 称 为。（考 点 1）解 析：计 算 机 解 题 的 过 程 实 际 上 是 在 实 施 某 种 算 法，这 种 算 法 称 为 计 算 机 算 法。答 案：算 法【例 2】一 个 空 的 数 据 结 构 是 按 线 性 结 构 处 理 的，则 属 于 o（考 点 4）解 析：一 个 空 的 数 据 结 构 是 线 性 结 构 或 是 非 线 性 结 构，要 根 据 具 体 情 况 而 定。如 果 对 数 据 结 构 的 运 算 是 按 线 性 结 构 来 处 理 的，则 属 于 线 性 结 构，否 则 属 于 非 线 性 结 构。答 案：线 性 结 构【例 3】设 树 T 的 度 为

47、 4,其 中 度 为 1、2、3 和 4 的 结 点 的 个 数 分 别 为 4、2、1、1,则 T 中 叶 子 结 点 的 个 数 为。（考 点 7）解 析：根 据 树 的 性 质：树 的 结 点 数 等 于 所 有 结 点 的 度 与 对 应 的 结 点 个 数 乘 积 之 和 加 1。因 此 树 的 结 点 数 为 1 X 4+2 X 2+3 X 1+4 X 1+1=1 6。叶 子 结 点 数 目 等 于 树 结 点 总 数 减 去 度 不 为 0 的 结 点 数 之 和，即 16（4+2+1+1）=8。答 案：8【例 4】二 分 法 查 找 的 存 储 结 构 仅 限 于 且 是 有

48、序 的。（考 点 10）解 析：二 分 查 找，也 称 折 半 查 找，它 是 一 种 高 效 率 的 查 找 方 法。但 二 分 查 找 有 条 件 限 制：要 求 表 必 须 用 顺 序 存 储 结 构，且 表 中 元 素 必 须 按 关 键 字 有 序（升 序 或 降 序 均 可）。答 案：顺 序 存 储 结 构第 二 章 程 序 设 计 基 础 经 过 对 部 分 考 生 的 调 查 以 及 对 近 年 真 题 的 总 结 分 析，笔 试 部 分 经 常 考 查 的 是 结 构 化 程 序 设 计 的 原 则、面 向 对 象 方 法 的 基 本 概 念，读 者 应 对 此 部 分 进

49、行 重 点 学 习。详 细 重 点 学 习 知 识 点：1.结 构 化 程 序 设 计 方 法 的 四 个 原 则 2.对 象、类、消 息、继 承 的 概 念、类 与 实 例 的 区 别 2.1结 构 化 程 序 设 计 考 点 1 结 构 化 程 序 设 计 的 原 则 考 试 链 接：考 点 1在 笔 试 考 试 中 出 现 的 几 率 为 3 0%,主 要 是 以 选 择 题 的 形 式 出 现，分 值 为 2分，此 考 点 为 识 记 内 容，读 者 应 该 识 记 结 构 化 程 序 设 计 方 法 的 四 个 主 要 原 则.20世 纪 70年 代 提 出 了 结 构 化 程 序

50、设 计”的 思 想 和 方 法。结 构 化 程 序 设 计 方 法 引 入 了 工 程 化 思 想 和 结 构 化 思 想，使 大 型 软 件 的 开 发 和 编 程 得 到 了 极 大 的 改 善。结 构 化 程 序 设 计 方 法 的 主 要 原 则 为：自 顶 向 下、逐 步 求 精、模 块 化 和 限 制 使 用 got。语 句。疑 难 解 答：如 何 进 行 自 顶 向 下 设 计 方 法？程 序 设 计 时，应 先 考 虑 总 体，后 考 虑 细 节；先 考 虑 全 局 目 标，后 考 虑 局 部 目 标；不 要 一 开 始 就 过 多 追 求 众 多 的 细 节，先 从 最 上