资源描述
沈 阳 理 工 大 学 硕 士 研 究 生 入 学 考 试 自 命 题 考 试 大 纲科 目 代 码 ： 812 科 目 名 称 ： 数 据 结 构适 用 专 业 ： 081200 计 算 机 科 学 与 技 术 、 083500 软 件 工 程一、考试基本内容（ 一 ） 绪 论（ 1） 数 据 结 构 的 基 本 概 念 和 相 关 术 语 。（ 2） 数 据 的 逻 辑 结 构 、 存 储 结 构 。（ 3） 算 法 、 算 法 的 基 本 特 性 以 及 算 法 分 析 。（ 二 ） 线 性 表（ 1） 线 性 结 构 、 线 性 表 的 定 义 ， 线 性 表 的 基 本 操 作 。（ 2） 线 性 表 的 顺 序 存 储 结 构 与 链 式 存 储 结 构 (单 链 表 、 循 环 链 表 和 双 向 链表 )。 在 两 种 存 储 结 构 上 主 要 的 操 作 算 法 (包 括 建 立 、 插 入 和 删 除 等 )的 实 现 。（ 3） 线 性 表 的 应 用 。（ 三 ） 栈 与 队 列（ 1） 栈 与 队 列 的 基 本 概 念 、 基 本 操 作 。（ 2） 栈 和 队 列 的 两 种 存 储 结 构 及 基 本 操 作 算 法 的 实 现 。（ 3） 栈 和 队 列 的 应 用 。（ 四 ） 串（ 1） 串 的 基 本 概 念 、 串 的 基 本 操 作 和 存 储 结 构 。（ 2） 串 的 模 式 匹 配 算 法 的 实 现 。（ 五 ） 数 组 和 广 义 表（ 1） 数 组 的 概 念 、 多 维 数 组 的 实 现 。（ 2） 特 殊 矩 阵 和 稀 疏 矩 阵 的 压 缩 存 储（ 3） 广 义 表 的 基 本 概 念（ 六 ） 树 与 二 叉 树（ 1） 树 的 概 念 、 术 语 ， 树 的 存 储 结 构 。（ 2） 二 叉 树 的 概 念 、 性 质 ， 二 叉 树 的 存 储 结 构 。（ 3） 遍 历 二 叉 树 和 线 索 二 叉 树 。（ 4） 树 和 森 林 。（ 5） 赫 夫 曼 树 及 其 应 用 。（ 七 ） 图（ 1） 图 的 定 义 ， 图 的 分 类 ， 常 用 概 念 术 语 。（ 2） 图 的 存 储 结 构 。（ 3） 图 的 遍 历 操 作 。（ 4） 最 小 生 成 树 ， 最 短 路 径 ， 关 键 路 径 ， 拓 扑 排 序 。（ 八 ） 查 找（ 1） 查 找 的 概 念 和 术 语 。（ 2） 静 态 查 找 表 。（ 3） 动 态 查 找 表 。（ 4） 哈 希 表 。（ 九 ） 内 排 序（ 1） 排 序 的 基 本 概 念 ， 排 序 方 法 的 分 类 。（ 2） 插 入 排 序 法 、 选 择 排 序 法 、 交 换 排 序 法 、 归 并 排 序 、 基 数 排 序 。 各 种排 序 方 法 排 序 的 原 理 、 规 律 和 特 点 ， 各 种 排 序 算 法 的 时 空 复 杂 度 简 单 分 析 。二、考试要求（ 一 ） 掌 握 数 据 结 构 的 相 关 术 语 ， 建 立 有 关 数 据 结 构 的 基 本 概 念 ， 掌 握 数 据的 逻 辑 结 构 、 存 储 结 构 和 算 法 ， 掌 握 算 法 分 析 的 基 本 概 念 与 基 本 方 法 。（ 二 ） 掌 握 线 性 表 的 基 本 概 念 ， 了 解 线 性 表 在 两 种 存 储 结 构 上 实 现 的 不 同 特点 ， 掌 握 线 性 表 的 两 种 存 储 结 构 及 其 操 作 算 法 实 现 ， 掌 握 利 用 线 性 表 实 现 不 同 问题 的 设 计 方 法 。（ 三 ） 掌 握 栈 和 队 列 的 基 本 概 念 与 特 征 ， 掌 握 在 两 种 存 储 结 构 下 栈 和 队 列 进行 插 入 和 删 除 等 操 作 的 实 现 ， 掌 握 栈 和 队 列 的 应 用 问 题 。（ 四 ） 了 解 串 的 基 本 概 念 、 掌 握 串 的 存 储 结 构 和 相 关 的 操 作 算 法 。（ 五 ） 掌 握 数 组 、 广 义 表 和 稀 疏 矩 阵 的 基 本 概 念 ， 掌 握 数 组 的 物 理 结 构 和 基本 操 作 的 实 现 ， 掌 握 特 殊 矩 阵 的 压 缩 存 储 及 操 作 实 现 。（ 六 ） 了 解 树 与 二 叉 树 的 逻 辑 特 征 ， 掌 握 二 叉 树 的 性 质 ， 掌 握 树 与 二 叉 树 的存 储 结 构 ， 掌 握 树 与 二 叉 树 的 相 互 转 换 ， 能 够 熟 练 地 利 用 常 用 的 三 种 遍 历 方 法 及线 索 树 的 一 般 操 作 方 法 ， 掌 握 哈 夫 曼 编 码 的 设 计 与 实 现 。（ 七 ） 了 解 图 的 逻 辑 结 构 的 特 点 ， 掌 握 常 用 的 两 种 存 储 方 法 ， 掌 握 最 小 生 成树 、 最 短 路 径 、 拓 扑 排 序 、 关 键 路 径 的 求 解 过 程 及 算 法 实 现 ， 能 运 用 上 述 算 法 解决 一 般 问 题 。（ 八 ） 掌 握 顺 序 查 找 、 折 半 查 找 方 法 ， 掌 握 二 叉 排 序 树 的 基 本 算 法 实 现 ， 掌握 平 衡 二 叉 排 序 树 及 插 入 、 删 除 时 的 方 法 ， 掌 握 哈 希 表 的 构 造 方 法 及 处 理 冲 突 的方 法 ， 了 解 B 树 和 B+树 的 操 作 过 程 ， 了 解 查 找 成 功 及 失 败 的 平 均 查 找 长 度 ， 了解 各 种 查 找 算 法 之 间 时 空 效 率 的 差 异 。（ 九 ） 掌 握 各 种 排 序 方 法 的 排 序 特 点 和 排 序 过 程 ， 对 于 任 意 给 出 的 数 据 元 素序 列 ， 能 够 熟 练 地 采 用 指 定 排 序 方 法 进 行 排 序 ， 并 且 能 够 对 每 一 种 排 序 方 法 排 序过 程 中 所 进 行 的 元 素 之 间 的 比 较 次 数 、 相 应 排 序 算 法 的 时 间 、 空 间 、 排 序 的 稳 定性 等 性 能 进 行 分 析 。三、题型（ 一 ） 选 择 或 判 断 或 填 空 ， 20分（ 二 ） 简 答 题 ， 40分（ 三 ） 综 合 应 用 ， 60分（ 四 ） 算 法 设 计 题 ， 30分
展开阅读全文