数 据 结 构 考 研 大 纲 与 考 试 范 围 解 析 清 航 教 育 校 长 清 航 教 学 研 究 中 心 主 任 殷 人 昆 一. 考 研 试 题 范 围 分 析 虽 然 2011 年 计 算 机 专 业 考 研 大 纲 在 知 识 点 上 看 没 有 变 化, 历 年 考 试 的 出 题 范 围 基 本 上 没 有 超 出 大 纲 但 由 于 大 纲 中 知 识 点 列 举 不 很 详 细, 从 深 度 上 到 底 达 到 什 么 程 度, 试 题 的 重 点 到 底 在 哪 里, 很 多 人 心 中 没 有 数 因 此, 只 能 通 过 分 析 历 年 的 试 题 才 可 略 知 一 二 下 表 是 对 2009 年 和 2010 年 数 据 结 构 考 试 出 题 范 围 的 一 个 对 比 2009 年 2010 年 1. 队 列 的 应 用 : 缓 冲 区 1. 进 栈 与 出 栈 序 列 2. 栈 与 队 列 的 特 性 和 进 栈 / 出 栈 序 列 2. 限 制 一 端 输 出 的 双 端 队 列 的 出 队 序 列 3. 二 叉 树 前 序 中 序 后 序 层 次 序 遍 3. 前 序 中 序 后 序 层 次 序 线 索 二 叉 树 历 方 式 的 表 示 4. 二 叉 树 的 性 质 和 完 全 二 叉 树 的 性 质 4. 平 衡 二 叉 树 的 插 入 和 平 衡 化 旋 转 5. 平 衡 二 叉 树 的 定 义 5. m 叉 树 叶 结 点 的 计 算 6. 森 林 的 二 叉 树 表 示 6. Huffman 树 的 定 义 和 特 点 7. 无 向 连 通 图 的 定 义 顶 点 与 边 的 关 系 7. 无 向 连 通 图 和 多 重 连 通 图 8. m 阶 B 树 的 定 义 8. 拓 扑 排 序 序 列 9. 堆 的 定 义 插 入 和 重 新 形 成 堆 的 调 整 9. 折 半 查 找 的 性 能 分 析 方 法 10. 几 种 排 序 方 法 10. 快 速 排 序 递 归 次 数 11. 几 种 排 序 方 法 在 选 择 填 空 题 部 分, 各 主 要 知 识 点 分 布 如 下 表 所 示 2009 年 2010 年 栈 队 列 与 双 端 队 列 2 2 树 与 二 叉 树 森 林 4 4 图 1 2 查 找 1 1 排 序 2 2 在 综 合 应 用 题 方 面, 主 要 知 识 点 的 分 布 如 下 表 所 示 2009 年 2010 年 41. 求 解 图 的 最 短 路 径 41. 散 列 表 构 造 数 据 存 储 及 性 能 分 析 42. 算 法 设 计 : 在 单 链 表 中 遍 历 求 倒 数 42. 算 法 设 计 : 将 一 维 数 组 中 所 有 元 素 循 第 k 个 结 点 位 置 环 左 移 p 位 从 近 两 年 的 试 题 范 围 的 对 比 中, 可 以 发 现 其 中 的 互 补 性 以 2010 年 的 试 题 为 例, 选 择 填 空 题 的 知 识 点 涉 及 5 章, 其 中 以 树 与 二 叉 树 这 一 章 的 分 量 最 重, 以 查 找 这 一 章 的 分 量 最 轻 而 在 综 合 应 用 题 中 恰 恰 填 补 了 空 白, 一 道 题 压 在 了 查 找 这 一 章, 一 道 算 法 题 压 在 了 线 性 表 这 一 章, 该 章 在 选 择 填 空 题 中 一 道 题 也 没 有 2009 年 的 情 况 类 似 从 此 我 们 得 到 第 一 个 结 论 : 考 试 大 纲 的 每 一 部 分 都 可 能 出 题, 而 且 从 份 量 上 来 看, 是 一 视 同 仁 的, 只 有 树 与 二 叉 树 这 一 章 题 的 数 量 会 多 一 些 从 考 试 的 难 度 来 看,2009 年 是 第 一 次 联 考, 试 题 的 难 度 低 一 些, 基 本 是 难 度 低 的 题 但 2010 年 试 题 的 难 度 高 了 一 些, 特 别 是 双 端 队 列 多 重 连 通 图 海 豚 算 法 等, 在 多 数 学 校 不 会 讲 到 的 或 不 做 要 求 的, 也 赫 然 出 现 在 试 卷 中 从 此 我 们 得 出 第 二 个 结 论 : 考 试 清 航 教 育 您 成 功 的 基 石! 1
大 纲 虽 然 列 出 了 考 试 范 围, 实 际 上 很 多 边 边 角 角 都 要 注 意, 押 题 是 害 人 的, 要 立 足 于 扎 扎 实 实 理 解 和 掌 握 好 主 要 的 知 识 点 二. 风 险 和 机 遇 有 些 考 生 在 考 试 结 束 之 后 给 我 打 电 话, 说 : 我 辛 辛 苦 苦 地 把 严 老 师 习 题 集 中 的 题 都 做 了, 可 使 还 是 没 考 好! 我 们 在 批 改 报 考 各 个 学 校 的 考 生 的 试 卷 时 也 是 遗 憾 多 于 惊 喜, 有 些 试 题 所 涉 及 的 知 识 点 明 明 在 课 堂 上 都 讲 过, 为 什 么 很 多 考 生 还 是 弄 得 一 团 浆 糊? 机 遇 对 所 有 的 人 都 是 存 在 的, 关 键 在 于 如 何 把 握 分 析 很 多 考 生 的 试 卷 答 案, 我 认 为 问 题 发 生 在 考 生 个 人 可 能 的 原 因 如 下 1. 有 些 考 生 对 知 识 点 的 掌 握 不 深 入 例 如 2010 年 41 题 计 算 散 列 表 的 大 小, 回 答 得 完 全 不 着 调, 不 知 如 何 计 算 2. 有 些 考 生 虽 然 看 了 一 些 书, 也 做 了 不 少 练 习 然 而 可 能 是 复 习 的 内 容 太 陈 旧, 或 者 某 些 问 题 以 前 的 教 材 没 有 涉 及 到, 导 致 复 习 面 狭 窄 例 如, 多 重 连 通 图 的 概 念, 一 些 考 生 连 题 都 看 不 懂, 无 从 下 手 3. 有 些 考 生 复 习 功 夫 不 够, 把 希 望 寄 托 在 押 题 上, 许 多 最 基 本 的 知 识 都 不 会 例 如, 线 索 二 叉 树 都 不 知 道, 甚 至 散 列 表 都 不 会 做, 画 了 一 个 很 长 的 表 要 知 道, 这 些 可 是 老 师 上 课 讲 过 的 东 西, 也 是 许 多 习 题 集 里 常 有 的 东 西 4. 有 些 考 生 考 试 审 题 不 仔 细, 一 看 会 做, 急 急 忙 忙 写 出 答 案, 信 心 满 满, 以 为 能 得 高 分, 下 来 一 对 答 案 就 傻 了 眼 例 如,2009 年 第 5 题, 问 一 棵 完 全 二 叉 树 在 第 6 层 有 8 个 叶 结 点, 这 棵 完 全 二 叉 树 最 多 有 多 少 结 点? 有 的 考 生 一 看, 这 还 不 容 易, 高 兴 起 来 就 漏 掉 了 题 目 中 还 有 最 多 的 提 法, 恰 恰 供 选 择 的 答 案 中 有 一 个 选 项, 正 是 不 考 虑 最 多 情 况 的 计 算 结 果, 有 些 考 生 立 刻 就 选 定 了 这 个 选 项, 当 然 就 丢 分 了 5. 有 些 考 生 进 考 场 后 太 紧 张, 心 情 不 能 放 松, 影 响 了 正 常 发 挥 本 来 会 答 的 也 想 不 起 来 了 有 位 考 生 考 完 见 了 我 直 拍 脑 袋, 说 : 考 前 不 知 复 习 多 少 遍, 考 试 时 不 知 怎 的 就 是 想 不 起 来! 总 之, 考 不 好 的 原 因 有 主 观 的, 有 客 观 的, 也 有 心 理 上 的 这 些 都 可 以 视 为 风 险 我 们 应 正 视 这 些 风 险, 研 究 应 对 这 些 风 险 的 策 略, 才 能 很 好 地 备 考, 打 好 考 研 这 一 大 的 战 斗 三. 复 习 建 议 学 生 在 初 学 时 往 往 感 到 数 据 结 构 课 程 内 容 多 面 授 容 易 接 受, 但 自 学 难 度 大, 特 别 是 在 编 写 小 程 序 时 常 常 无 从 着 手 为 以 有 限 的 时 间 和 精 力 学 好 这 门 课 程 应 当 注 意 以 下 几 点, 有 助 于 改 善 自 学 效 果 1. 在 学 习 本 课 程 之 初, 必 须 注 意 复 习 在 用 C/C++ 语 言 编 写 小 程 序 时 的 语 法 规 则 和 方 法 为 本 课 程 的 学 习 打 下 基 础 C 语 言 与 Pascal 语 言 一 样, 是 一 种 面 向 过 程 的 语 言 C 程 序 结 构 的 特 点 是 遵 循 输 入 - 处 理 - 输 出 的 模 式 来 解 决 问 题 C++ 保 留 了 C 的 面 向 过 程 编 程 的 成 分 但 引 入 了 面 向 对 象 的 成 分, 在 复 习 C/C++ 语 言 时, 要 注 意 : (1) 函 数 的 概 念 和 相 关 问 题 包 括 函 数 类 型, 函 数 特 征, 函 数 参 数 的 传 递 特 别 注 意 传 值 参 数 和 引 用 参 数 在 使 用 上 的 区 别 还 有 函 数 的 不 同 返 回 值 类 型 间 的 区 别 (2) 函 数 中 局 部 变 量 的 作 用 域, 它 的 创 建 和 回 收 的 有 效 范 围 特 别 注 意 在 函 数 中 对 局 部 变 量 的 任 何 改 变, 因 在 退 出 函 数 过 程 时 局 部 变 量 被 释 放 而 不 能 当 作 函 数 返 回 值 返 回 (3) 类 型 ( 或 类 ) 的 定 义 方 式 使 用 C 定 义 结 构 的 复 杂 性 远 低 于 C++ 或 Java, 但 要 注 意 C 指 针 的 使 用 所 带 来 的 复 杂 性 (4) 在 C/C++ 中 的 动 态 存 储 分 配 和 动 态 存 储 回 收 方 式 (5) 程 序 中 定 义 的 变 量 或 类 的 实 例 必 须 在 使 用 前 初 始 化, 特 别 是 用 指 针 动 态 定 义 的 结 构 清 航 教 育 您 成 功 的 基 石! 2
或 数 组, 必 须 在 使 用 前 为 它 们 分 配 存 储 空 间, 并 在 动 态 分 配 后 判 断 这 次 分 配 是 否 成 功 只 有 动 态 分 配 成 功 才 能 继 续 程 序 中 要 做 的 事 情, 但 别 忘 了 赋 初 值 (6) 在 C/C++ 中 的 输 入 / 输 出 文 件 的 定 义 和 使 用 特 别 注 意 文 件 的 连 接 文 件 的 打 开 与 关 闭 文 件 模 式 的 作 用 2. 在 备 考 时 首 要 任 务 是 选 好 教 材 和 辅 导 书 教 材 不 一 定 采 用 某 些 所 谓 权 威 的 教 材, 因 为 可 能 在 内 容 上 不 够 全 面, 在 阐 述 上 不 够 深 入, 不 能 反 映 较 新 的 发 展 在 C 语 言 版 的 教 材 方 面, 我 个 人 比 较 倾 向 于 选 北 京 大 学 张 乃 孝 的 算 法 与 数 据 结 构 ( 高 教 版 ) 西 北 大 学 耿 国 华 的 数 据 结 构 ( 高 教 版 ) 南 京 邮 电 大 学 陈 慧 南 的 数 据 结 构 ( 高 教 版 ) 清 华 大 学 朱 明 芳 和 吴 及 的 数 据 结 构 与 算 法 ( 清 华 版 ) 辅 导 书 可 选 用 的 较 多, 它 的 作 用 在 于 提 供 考 研 的 指 导 和 相 关 可 利 用 的 习 题 3. 在 复 习 数 据 结 构 时, 要 注 意 知 识 体 系 数 据 结 构 课 程 中 的 知 识 本 身 具 有 良 好 的 结 构 性 从 总 体 上 来 说, 课 程 的 主 要 内 容 是 围 绕 着 数 组 线 性 表 栈 和 队 列 树 与 二 叉 树 图 集 合 与 查 找 结 构 等 常 用 的 数 据 结 构 和 查 找 排 序 等 常 用 算 法 来 组 织 的 其 中 有 些 结 构 是 面 向 应 用 的, 有 些 结 构 是 面 向 实 现 的 在 复 习 中 要 注 意 这 两 个 层 次 以 及 它 们 之 间 的 联 系 4. 注 意 比 较 在 复 习 中 应 当 注 意 从 横 向 和 纵 向 进 行 对 比 以 加 深 理 解 纵 向 对 比 将 一 种 结 构 与 它 的 各 种 不 同 的 实 现 加 以 比 较, 或 从 一 般 / 特 殊 的 角 度 整 体 / 部 分 的 角 度 实 参 / 形 参 的 角 度 建 立 相 关 类 型 的 变 量 之 间 的 联 系 ; 横 向 对 比 包 括 具 有 相 同 逻 辑 结 构 的 不 同 数 据 结 构 ( 如 线 性 表 栈 队 列 和 串 ) 的 比 较, 具 有 相 同 功 能 的 不 同 算 法 的 比 较 等 5. 注 意 复 习 和 重 读 有 些 内 容 在 初 读 时 难 以 透 彻 理 解 或 熟 练 掌 握, 或 者 看 起 来 似 乎 明 白 了, 但 用 的 时 候 容 易 犯 晕 在 继 续 学 习 的 过 程 中 如 遇 到 或 用 到 有 关 内 容 时, 应 当 及 时 复 习 或 重 读, 这 往 往 能 够 化 难 为 易, 温 故 知 新 6. 注 意 循 序 渐 进 在 进 入 具 体 内 容 复 习 之 初, 首 先 领 会 基 本 概 念 基 本 思 想, 这 一 点 极 为 重 要 特 别 是 在 阅 读 算 法 之 前, 一 定 要 先 弄 清 其 基 本 思 想 基 本 步 骤, 这 将 大 大 降 低 理 解 算 法 的 难 度 如 果 读 懂 了 算 法 而 不 知 其 基 本 思 想, 仍 不 算 是 真 懂 可 以 通 过 事 例 学 习 以 加 深 理 解 7. 注 意 练 习 习 题 练 习 是 课 程 的 基 本 要 求 之 一 只 看 书 不 做 题, 不 可 能 真 正 学 会 有 关 知 识, 更 不 能 达 到 技 能 培 养 的 目 的 另 一 方 面, 做 题 也 是 自 我 检 查 的 重 要 手 段 此 外, 在 做 算 法 设 计 型 的 习 题 时, 应 优 先 考 虑 数 据 结 构 的 定 义, 可 以 直 接 使 用 以 前 定 义 的 数 据 类 型 和 相 应 的 操 作, 综 合 已 学 过 的 知 识, 以 提 高 编 程 的 能 力 8. 算 法 思 路 的 理 解 算 法 及 其 思 想 评 价 是 本 课 程 的 重 点 之 一, 在 课 文 中 占 了 相 当 大 的 比 例 在 学 习 每 一 个 算 法 时, 建 议 首 先 理 解 问 题 的 要 求, 在 此 基 础 上 利 用 一 个 事 例 来 模 拟 问 题 的 求 解, 自 己 试 着 构 思 一 下 解 题 的 思 路, 能 够 写 出 来 更 好 然 后 再 阅 读 算 法, 在 读 懂 之 后, 不 要 急 于 往 下 进 行, 而 应 停 下 来 思 考 下 列 问 题 : 该 算 法 从 逻 辑 上 可 以 划 分 为 哪 几 个 部 分 ( 步 骤 )? 每 一 部 分 的 功 能 是 什 么? 这 一 功 能 又 是 如 何 实 现 的? 能 否 有 别 的 方 法 实 现? 各 部 分 之 间 的 关 系 如 何? 如 果 问 题 的 要 求 有 所 不 同, 应 当 如 何 修 改 算 法? 将 思 考 的 结 果 记 载 下 来, 在 复 习 时 会 有 很 大 帮 助 另 外, 这 样 的 分 析 也 是 灵 活 运 用 所 学 知 识 的 关 键 9. 努 力 培 养 算 法 设 计 的 能 力 清 航 教 育 您 成 功 的 基 石! 3
在 课 程 复 习 中 最 令 学 习 者 感 到 吃 力 的 是 设 计 和 编 写 算 法 算 法 设 计 水 平 是 软 件 设 计 的 基 础 要 提 高 算 法 的 设 计 水 平, 首 先 需 要 掌 握 问 题 要 求 的 基 本 内 容, 通 过 反 复 体 会 和 练 习 来 实 现 通 常 需 要 根 据 具 体 问 题 的 要 求, 选 择 合 适 的 数 据 结 构, 设 计 有 效 的 算 法 有 条 件 的 学 生 应 当 在 机 器 上 多 做 练 习 10. 在 复 习 完 每 一 章 节 后, 要 及 时 地 进 行 总 结, 用 简 短 的 文 字 记 录 这 部 分 的 内 容, 尽 可 能 用 自 己 的 话 复 述 一 遍 在 本 课 程 全 部 学 完 后 应 对 本 课 程 进 行 全 面 系 统 的 复 习 和 总 结, 认 真 做 模 拟 试 卷 在 进 行 总 复 习 时, 可 通 过 对 比 各 种 数 据 结 构 的 异 同 和 他 们 之 间 的 相 互 关 系, 加 深 对 各 种 数 据 结 构 的 理 解 在 复 习 时, 可 以 按 所 记 录 的 要 点 反 向 地 进 行, 即 依 据 要 点 找 出 其 具 体 内 容 按 这 样 的 方 法 进 行, 也 许 还 能 够 节 省 时 间, 提 高 学 习 效 果 最 后 应 当 强 调 的 是, 学 习 方 法 主 要 靠 自 己 摸 索, 多 总 结, 多 思 考, 勤 上 机, 勤 交 流, 是 把 数 据 结 构 这 门 课 程 真 正 学 好 的 关 键 四. 考 试 指 导 数 据 结 构 考 试 可 能 的 题 型 有 以 下 2 种 : (1) 选 择 填 空 题 : 给 出 一 些 有 关 数 据 结 构 性 质 特 点 及 一 些 简 单 算 法 性 能 的 不 完 全 叙 述, 要 求 学 生 从 题 后 给 出 的 供 选 择 的 答 案 中 选 择 合 适 的 答 案, 补 足 这 些 叙 述 (2) 综 合 应 用 题 : 又 有 2 种 题 型 : 简 答 题 : 应 用 作 图 方 法 简 单 计 算 或 证 明 方 法, 使 用 给 定 数 据 建 立 或 操 作 一 些 数 据 结 构, 或 判 断 某 些 算 法 的 正 误 编 程 题 : 给 出 算 法 设 计 要 求, 编 制 出 部 分 算 法 程 序, 用 来 考 察 几 个 知 识 点 的 综 合 应 用 下 面 根 据 各 种 题 型 举 例 分 析, 说 明 解 题 方 法 及 考 试 时 的 注 意 事 项 例 题 1 单 项 选 择 题 以 下 关 于 图 的 遍 历 的 说 法 中 不 正 确 的 是 ( ) A. 遍 历 图 的 过 程 实 质 上 是 对 每 个 顶 点 查 找 其 邻 接 顶 点 的 过 程 B. 深 度 优 先 搜 索 和 广 度 优 先 搜 索 对 无 向 图 和 有 向 图 都 适 用 C. 深 度 优 先 搜 索 和 广 度 优 先 搜 索 访 问 顶 点 的 顺 序 不 同, 它 们 的 时 间 复 杂 度 也 不 同 D. 深 度 优 先 搜 索 需 要 使 用 一 个 递 归 栈, 广 度 优 先 搜 索 需 要 使 用 一 个 辅 助 队 列 答 案 C 解 析 采 用 排 除 法 解 答 深 度 优 先 搜 索 和 广 度 优 先 搜 索 都 是 从 某 个 顶 点 出 发, 访 问 它 的 没 有 访 问 过 的 邻 接 顶 点, 一 直 搜 素 下 去, 选 项 A 正 确 这 两 种 搜 索 对 无 向 图 和 有 向 图 都 适 用, 选 项 B 正 确 深 度 优 先 搜 索 是 一 个 递 归 的 过 程, 需 要 一 个 递 归 栈, 广 度 优 先 搜 索 是 一 个 分 层 访 问 的 过 程 而 非 递 归 过 程, 需 要 用 队 列 逐 层 保 存 结 点, 选 项 D 正 确 最 后 剩 下 选 项 C, 不 对 原 因 是 若 两 个 算 法 都 用 邻 接 表 存 储 图 时, 它 们 的 时 间 复 杂 度 相 同, 都 是 O(n+e) 其 中 n 是 顶 点 数,e 是 边 数 例 题 2 单 项 选 择 题 若 设 S 是 一 个 已 有 10 个 元 素 的 顺 序 栈, 栈 中 元 素 依 次 是 A1, A2,, A10, 栈 顶 在 A10 Q 是 一 个 已 有 10 个 元 素 的 循 环 队 列, 队 列 中 元 素 依 次 是 B1, B2,, B10, 队 头 是 B1 如 果 想 要 把 栈 S 中 元 素 全 部 移 入 队 列 Q, 且 使 得 队 列 中 的 元 素 依 次 排 列 为 B 1, A 1, B 2, A 2,, B 10, A 10, 需 要 执 行 的 栈 和 队 列 的 操 作 的 次 数 为 ( ) A.100 B.1000 C.145 D.290 答 案 A 清 航 教 育 您 成 功 的 基 石! 4
解 析 不 需 要 使 用 排 除 法, 可 做 具 体 计 算 如 果 想 在 队 列 中 得 到 B1, A1, B2, A2, B10, A10, 需 首 先 把 栈 中 的 元 素 逆 置 为 A 10, A 9,, A 1, 再 从 队 列 和 栈 中 交 替 退 出 B 1, A 1,, B 10, A 10 并 存 入 队 列 即 可 为 逆 置 栈 中 元 素, 可 将 它 们 按 A10, A9,, A1 退 栈, 并 进 队 ; 再 从 队 列 中 按 A10, A9,, A1 顺 序 退 出 并 进 栈 就 可 以 了 操 作 步 骤 如 下 : (1) 栈 中 10 个 元 素 退 栈, 再 进 队 栈 空, 队 列 中 有 B 1, B 2,, B 10, A 10, A 9,, A 1 (2) 队 列 中 前 10 个 元 素 出 队, 再 进 队, 后 续 10 个 元 素 出 队, 再 进 栈 栈 中 有 10 个 元 素, 依 次 为 A10, A9,, A1, 队 列 中 有 10 个 元 素, 依 次 为 B1, B2,, B10 (3) 队 列 和 栈 中 元 素 轮 替 出 队 出 栈, 再 进 队 队 列 中 元 素 依 次 为 B 1, A 1, B 2, A 2,, B 10, A 10 总 共 有 20+40+40 = 100 次 栈 和 队 列 的 操 作 短 评 此 类 题 主 要 是 考 核 学 生 对 基 本 知 识 的 掌 握 程 度, 涉 及 范 围 较 广 所 有 各 章 内 容 都 可 能 牵 涉 到 主 要 考 查 对 各 种 数 据 结 构 的 定 义 特 点 性 质 ( 包 括 公 式 计 算 ) 主 要 操 作 的 性 能 分 析 ( 包 括 算 法 中 多 趟 执 行 时 每 一 趟 的 通 项 公 式 ), 因 此 要 求 复 习 时 必 须 仔 细 看 书 不 提 倡 死 记 硬 背, 但 要 学 会 推 导 另 外, 对 待 每 一 道 题, 特 别 涉 及 计 算 和 作 图 的 题 目, 一 定 要 在 草 稿 纸 上 试 做, 切 忌 轻 敌 其 实 所 谓 粗 心 就 是 轻 敌 的 结 果 例 题 3 综 合 应 用 题 设 一 段 正 文 由 字 符 集 {A, B, C, D, E, F } 中 的 字 母 组 成, 这 6 个 字 母 在 正 文 中 出 现 的 次 数 分 别 为 {16, 20, 24, 6, 5, 29 } (1) 为 这 5 个 字 母 设 计 Huffman 编 码 (2) 设 每 个 字 节 由 8 个 二 进 制 位 组 成, 试 计 算 按 (1) 所 得 Huffman 编 码 存 储 这 段 正 文, 总 共 需 要 多 少 个 字 节? (3) 若 这 段 正 文 开 始 部 分 的 二 进 制 编 码 序 列 为 0110110010011011000, 请 按 (1) 所 得 Huffman 编 码, 将 其 译 为 正 文 参 考 答 案 (1) 首 先 画 出 Hffman 编 码 树, 如 图 : 100 44 56 字 母 A B C D E F 编 码 101 00 01 1001 1000 20 24 27 11 29 11 16 5 6 (2) 问 题 归 结 于 求 此 Huffman 树 的 带 权 路 径 长 度 WPL = 3*16+2*20+2*24+4*6+4*5+2*29 = 238(bits) 共 需 字 节 数 = 238/8 = 29.75( 字 节 ) (3) 二 进 制 编 码 序 列 01 101 1001 01 01 1000 转 换 成 正 文 为 CADBFCE 短 评 此 类 题 要 求 对 各 章 中 许 多 细 节 比 较 清 楚 事 实 上, 数 据 结 构 课 程 中 讲 到 的 许 多 数 据 结 构 的 细 节 是 最 基 础 的 知 识, 将 这 些 内 容 理 解 透 彻 了, 以 后 学 生 在 自 主 开 发 软 件 时 将 会 得 到 回 报 的 在 解 答 此 类 题 时, 不 要 立 即 提 笔 就 答, 应 当 把 题 看 完, 回 忆 课 程 相 关 知 识 点 和 解 决 问 题 的 思 路, 如 果 做 过 类 似 的 题 目, 就 更 好 了 例 题 4 综 合 应 用 题 如 果 一 棵 二 叉 树 采 用 二 叉 链 表 存 储, 试 设 计 一 个 算 法 查 找 并 返 回 其 后 序 序 列 中 的 第 一 个 结 点 的 地 址, 要 求 既 不 用 递 归 也 不 用 栈 参 考 答 案 既 不 用 递 归 也 不 用 栈 查 找 二 叉 树 的 后 序 序 列 的 第 一 个 结 点 是 可 行 算 法 的 主 要 想 法 是, 如 果 二 叉 树 非 空, 可 从 根 结 点 出 发, 沿 左 子 女 链 一 直 走 到 底, 如 果 最 后 到 达 的 清 航 教 育 您 成 功 的 基 石! 5
结 点 的 右 指 针 为 空, 则 该 结 点 即 为 其 后 序 序 列 的 第 一 个 结 点 ; 如 果 该 结 点 的 右 指 针 非 空, 则 对 该 结 点 的 右 子 树 施 行 同 样 的 操 作 算 法 的 描 述 如 下 BiTNode * postfirst ( BiTNode *T ) { BiTNode *p = T; while ( p!= NULL ) { while ( p->lchild!= NULL ) p = p->lchild; if ( p->rchild == NULL ) return p; else p = p->rchild; } return NULL; }; 短 评 编 写 算 法 的 题 可 能 是 学 生 比 较 棘 手 的 问 题, 特 别 是 在 考 试 这 样 一 个 氛 围, 时 间 又 短 促, 想 编 出 一 个 好 算 法 不 太 容 易 一 个 建 议 是 首 先 仔 细 阅 读 试 题, 了 解 它 到 底 要 你 干 什 么 然 后 用 一 个 简 单 的 例 子 走 一 下, 总 结 每 一 步 向 下 走 用 什 么 语 句, 再 做 归 纳 也 可 以 按 照 结 构 化 程 序 设 计 的 方 法, 先 搭 框 架, 再 根 据 例 子 填 入 细 节 总 之, 要 想 又 快 又 好 地 编 写 出 算 法, 还 要 靠 平 时 的 基 本 训 练, 多 做 题, 自 主 做 题, 各 种 题 型 都 见 过 了, 考 试 时 自 然 文 思 泉 涌, 笔 下 就 流 畅 了 五. 结 束 语 数 据 结 构 课 程 是 一 门 知 识 性 实 践 性 都 很 强 的 课 程 数 据 结 构 及 算 法 编 写 与 分 析 都 是 不 容 易 的 学 好 它 需 要 付 出 极 大 的 劳 动, 在 平 时 勤 学 多 练 如 果 有 碰 运 气 或 取 巧 的 想 法, 十 有 八 九 通 不 过 考 试 只 有 基 础 打 扎 实, 考 试 才 能 顺 利 过 关 就 怕 平 时 不 看 书, 不 做 作 业 或 抄 别 人 的 作 业, 到 考 试 时 照 样 不 会, 自 然 一 次 次 通 不 过 了 最 后, 祝 愿 考 生 们 通 过 自 己 的 勤 奋 努 力, 取 得 优 良 的 成 绩 清 航 教 育 您 成 功 的 基 石! 6