理科计算机主干基础课.doc
2页
1理 科 计 算 机 主 干 基 础 课《 算 法 与 数 据 结 构 》 教 学 大 纲1999 年 7 月 20 日 一 、 课 程 目 的 和 要 求 ：《 算 法 与 数 据 结 构 》 是 理 科 非 计 算 机 专 业 的 一 门 重 要 的 计 算 机 必 修 课 ， 是一 门 理 论 和 实 际 紧 密 结 合 的 课 程 本 课 的 主 要 目 的 是 使 学 生 较 全 面 地 理 解 算 法和 数 据 结 构 的 概 念 、 掌 握 各 种 数 据 结 构 与 算 法 的 实 现 方 式 ， 比 较 不 同 数 据 结 构和 算 法 的 特 点 通 过 学 习 ， 使 学 生 能 够 提 高 用 计 算 机 解 决 实 际 问 题 的 能 力 三 ， 先 修 课本 课 程 要 求 学 生 已 学 过 “计 算 概 论 ”课 程 ， 掌 握 了 程 序 设 计 语 言 C 的 基 本知 识 ， 并 且 有 了 一 些 使 用 C 语 言 进 行 程 序 设 计 的 实 际 经 验 四 ， 知 识 单 元 和 学 时 安 排1 绪 论 (3 学 时 )算 法 的 概 念 ， 算 法 的 分 析数 据 结 构 的 概 念 、 数 据 结 构 的 分 类本 课 程 要 讨 论 的 基 本 问 题2 线 性 表 （ 6 学 时 ）线 性 表 结 构 ，线 性 表 的 顺 序 存 储 实 现 （ 顺 序 表 ） ，线 性 表 的 链 接 实 现 （ 链 接 表 ） ，线 性 表 的 应 用3 字 符 串 *（ 4 学 时 ）字 符 串 ，字 符 串 的 基 本 操 作 ，模 式 匹 配 问 题 ，字 符 串 的 应 用4 堆 栈 与 队 列 （ 5 学 时 ）堆 栈 的 概 念 ， 堆 栈 的 实 现 ， 堆 栈 的 应 用 ，队 列 的 概 念 ， 队 列 的 实 现 ， 队 列 的 应 用5.树 与 二 叉 树 (6 学 时 )树 结 构 的 概 念 ， 树 的 逻 辑 结 构二 叉 树 的 概 念 ， 完 全 二 叉 树 与 满 二 叉 树树 、 树 林 和 二 叉 树 的 相 互 转 换树 和 二 叉 树 的 实 现树 和 二 叉 树 的 各 种 遍 历 算 法Huffman 树 的 概 念 及 应 用6 检 索 与 字 典 （ 8 学 时 ）2检 索 问 题 与 字 典静 态 字 典 与 动 态 字 典顺 序 检 索 ， 二 分 检 索分 块 检 索 *，最 佳 二 叉 排 序 树 *散 列 表 、 散 列 函 数 的 基 本 概 念 ， 散 列 函 数 的 选 择 ， 碰 撞 的 处 理 方 法 ，基 于 属 性 的 检 索 方 法 *， 倒 排 表 与 多 重 表 *。
平 衡 二 叉 排 序 树 *， B 树 与 B+树 *7 排 序 (4 学 时 )排 序 的 基 本 概 念选 择 排 序 ， 插 入 排 序 、 冒 泡 排 序 、 快 速 排 序Shell 排 序 *、 堆 排 序 *、 归 并 排 序 *、 基 数 排 序 *各 种 排 序 算 法 的 复 杂 性 分 析8 图 结 构 (6 学 时 )图 的 基 本 概 念 及 有 关 术 语图 的 存 储 表 示 法图 遍 历 、最 小 生 成 树最 短 路 径拓 扑 排 序 *关 键 路 径 *9 算 法 分 析 与 设 计 *（ 2-3 学 时 ）10 稀 疏 矩 阵 和 广 义 表 *(2-3 学 时 )稀 疏 矩 阵 的 存 储广 义 表 的 基 本 概 念五 、 上 机 实 践1. 在 课 程 的 前 12 周 ， 学 生 应 当 完 成 一 批 程 序 设 计 作 业 ， 主 要 内 容 为 一 些 典型 数 据 结 构 的 实 现 和 应 用 2. 课 程 最 后 6 周 时 间 ， 每 个 学 生 必 须 独 立 完 成 一 个 较 大 的 程 序 实 习 ， 写 出 相应 的 实 习 报 告 。
（ 报 告 内 容 应 当 包 括 ： 对 问 题 的 分 析 ， 主 要 设 计 思 想 ， 实 现 方法 ， 采 用 的 数 据 结 构 ， 算 法 及 其 分 析 ， 调 试 报 告 等 ）六 、 主 要 参 考 教 材《 算 法 与 数 据 结 构 –C 语 言 描 述 》 ， 张 乃 孝 等 ， 北 京 大 学 教 材 科 ， 2000.8《 数 据 结 构 》 ， 许 卓 群 张 乃 孝 杨 冬 青 唐 世 渭 ， 高 等 教 育 出 版 社 1987《 数 据 结 构 基 础 》 ， 张 乃 孝 等 ， 北 京 大 学 出 版 社 1991《 数 据 结 构 —C++与 面 向 对 象 程 序 设 计 》 ， 张 乃 孝 裘 宗 燕 高 教 出 版 社 1998《 数 据 结 构 》 （ C 语 言 版 ） ， 严 蔚 敏 吴 伟 民 ， 清 华 大 学 出 版 社 1996。
