资源描述
大 连 海 事 大 学 硕 士 研 究 生 入 学 考 试 大 纲考 试 科 目 ： 数 据 结 构试 卷 满 分 及 考 试 时 间 :试 卷 满 分 为 100 分 ， 考 试 时 间 为 120 分 钟 。一 、 绪 论考 试 内 容基 本 概 念 抽 象 数 据 类 型 的 表 示 与 实 现 算 法 和 算 法 分 析考 试 要 求 ：1. 了 解 数 据 结 构 的 基 本 概 念 ；2. 理 解 数 据 的 逻 辑 结 构 和 存 储 结 构 的 概 念 及 其 相 互 关 系 ；3. 了 解 算 法 的 五 个 要 素 ；4. 掌 握 计 算 语 句 的 频 度 和 时 间 、 空 间 复 杂 度 的 方 法 。二 、 线 性 表考 试 内 容线 性 表 的 类 型 定 义 线 性 表 的 顺 序 表 示 和 实 现 线 性 表 的 链 式 表 示 和 实 现考 试 要 求1 理 解 线 性 表 的 逻 辑 结 构 和 特 性 ， 熟 练 掌 握 线 性 表 的 两 类 存 储 结 构 ： 顺 序 存 储结 构 和 链 式 存 储 结 构 ；2 熟 练 掌 握 线 性 表 在 顺 序 存 储 结 构 上 实 现 查 找 、 插 入 和 删 除 等 基 本 运 算的 算 法 ；3 熟 练 掌 握 在 各 种 链 表 结 构 中 实 现 线 性 表 运 算 的 算 法 ；4 从 时 间 和 空 间 复 杂 度 的 角 度 分 析 比 较 线 性 表 两 种 存 储 结 构 的 不 同 特 点 。三 、 栈 和 队 列考 试 内 容栈 栈 的 应 用 栈 与 递 归 的 实 现 队 列考 试 要 求1 理 解 栈 和 队 列 两 种 数 据 结 构 的 概 念 和 特 点 ；2 熟 练 掌 握 在 顺 序 和 链 式 两 种 存 储 结 构 上 完 成 栈 的 基 本 运 算 ；3 熟 练 掌 握 链 式 队 列 和 循 环 队 列 的 基 本 操 作 ；4. 掌 握 利 用 栈 将 递 归 算 法 转 化 为 非 递 归 算 法 的 方 法 。四 、 串考 试 内 容串 类 型 的 定 义 串 的 表 示 和 实 现 串 的 模 式 匹 配 算 法 串 操 作 应 用考 试 要 求1 了 解 串 的 定 义 和 相 关 概 念 ；2 掌 握 串 的 基 本 运 算 及 其 组 合 应 用 方 法 ；3 理 解 串 的 静 态 存 储 结 构 和 动 态 存 储 结 构 ， 及 其 对 应 的 各 种 运 算 ；4. 理 解 串 的 模 式 匹 配 算 法 。五 、 数 组 和 广 义 表考 试 内 容数 组 的 定 义 数 组 的 顺 序 表 示 和 实 现 矩 阵 的 压 缩 存 储 广 义 表 的 定 义 广 义 表的 存 储 结 构考 试 要 求1 理 解 数 组 存 储 方 式 ， 熟 练 掌 握 数 组 在 以 行 序 为 主 的 存 储 结 构 中 的 地 址 计 算 方法 ；2 理 解 稀 疏 矩 阵 的 压 缩 存 储 方 法 ， 掌 握 稀 疏 矩 阵 运 算 采 用 的 处 理 方 法 ；3. 了 解 广 义 表 的 定 义 及 存 储 结 构 。六 、 树 和 二 叉 树考 试 内 容树 的 定 义 和 基 本 术 语 二 叉 树 遍 历 二 叉 树 和 线 索 二 叉 树 树 和 森 林考 试 要 求1 掌 握 树 的 定 义 和 相 关 术 语 ， 熟 练 掌 握 二 叉 树 的 定 义 、 性 质 和 存 储 结 构 ；2 熟 练 掌 握 二 叉 树 按 各 种 顺 序 遍 历 的 递 归 和 非 递 归 算 法 ；3. 了 解 线 索 二 叉 树 的 定 义 和 线 索 的 建 立 方 法 ；4. 了 解 树 的 各 种 存 储 结 构 ， 森 林 与 二 叉 树 的 转 换 ， 树 和 森 林 的 遍 历 。七 、 图考 试 内 容图 的 定 义 和 术 语 图 的 存 储 结 构 图 的 遍 历 图 的 连 通 性 问 题 有 向 无 环 图 及 其应 用 最 短 路 径考 试 要 求1 了 解 图 的 定 义 和 有 关 术 语 ， 理 解 并 掌 握 图 的 各 种 存 储 结 构 ；2 熟 练 掌 握 按 深 度 优 先 和 广 度 优 先 遍 历 图 的 算 法 ；3. 理 解 图 的 连 通 性 问 题 ；4. 理 解 拓 扑 排 序 和 关 键 路 径 ；5. 熟 练 掌 握 求 最 短 路 径 的 算 法 。八 、 查 找考 试 内 容静 态 查 找 表 动 态 查 找 表 哈 希 表考 试 要 求1 熟 练 掌 握 顺 序 查 找 、 折 半 查 找 和 索 引 查 找 算 法 ；2 掌 握 二 叉 排 序 树 的 查 找 方 法 和 构 造 方 法 ；3. 熟 练 掌 握 哈 希 函 数 的 构 造 方 法 以 及 哈 希 表 的 查 找 方 法 。九 、 内 部 排 序考 试 内 容内 部 排 序 的 概 念 插 入 排 序 快 速 排 序 选 择 排 序 归 并 排 序 基 数 排 序 各种 内 部 排 序 方 法 的 比 较 讨 论考 试 要 求1.熟 练 掌 握 插 入 排 序 、 快 速 排 序 、 选 择 排 序 、 归 并 排 序 和 基 数 排 序 的 排 序 方 法 、过 程 和 特 点 ;2. 掌 握 各 种 排 序 方 法 的 应 用 ， 并 能 够 灵 活 选 择 ；3. 掌 握 各 种 排 序 方 法 的 时 间 复 杂 度 分 析 方 法 。 参 阅 ： 数 据 结 构 （ C 语 言 版 ） 严 蔚 敏 吴 伟 民 清 华 大 学 出 版 社 2011 年
展开阅读全文