资源描述
大 连 海 事 大 学 硕 士 研 究 生 入 学 考 试 大 纲考 试 科 目 ： 数 据 结 构试 卷 满 分 及 考 试 时 间 ： 试 卷 满 分 为 150分 ， 考 试 时 间 为 180分 钟 。考 试 内 容1. 绪 论问 题 、 问 题 实 例 ； 数 据 、 数 据 元 素 、 数 据 对 象 、 数 据 结 构 ； 集 合 、 线 性 结 构 、树 形 结 构 、 图 形 结 构 ； 逻 辑 结 构 、 存 储 结 构 ； 算 法 及 其 特 性 、 算 法 的 正 确 性 、可 读 性 、 健 壮 性 、 算 法 的 时 间 与 空 间 复 杂 度 分 析 及 其 度 量 。2. 线 性 表线 性 表 的 定 义 与 结 构 特 点 ； 线 性 表 的 存 储 结 构 及 其 基 本 操 作 ； 有 序 表 ； 静 态 链表 ； 循 环 链 表 与 双 向 链 表 ； 关 于 线 性 表 的 问 题 实 例 。3. 栈 与 队 列栈 的 定 义 与 结 构 特 点 ； 栈 的 存 储 结 构 及 其 基 本 操 作 ； 递 归 与 递 归 的 执 行 过 程 ；关 于 栈 的 问 题 实 例 。队 列 的 定 义 与 结 构 特 点 ； 队 列 的 存 储 结 构 及 其 基 本 操 作 ； 循 环 队 列 ； 关 于 队 列的 问 题 实 例 。4. 串串 的 定 义 与 结 构 特 点 ； 串 的 存 储 结 构 及 其 基 本 操 作 ； 串 的 模 式 匹 配 算 法 。5. 数 组 与 广 义 表数 组 的 定 义 与 结 构 特 点 ； 数 组 的 存 储 结 构 及 其 基 本 操 作 ； 矩 阵 的 压 缩 存 储 。广 义 表 的 定 义 与 结 构 特 点 ； 广 义 表 的 存 储 结 构 及 其 基 本 操 作 。6. 树 与 二 叉 树树 的 定 义 与 结 构 特 点 ； 树 的 相 关 概 念 ； 有 序 树 与 无 序 树 ； 森 林 ； 二 叉 树 的 定 义与 结 构 特 点 ； 二 叉 树 的 性 质 ； 二 叉 树 的 存 储 结 构 及 其 基 本 操 作 ； 遍 历 二 叉 树 与线 索 二 叉 树 ； 树 与 森 林 的 存 储 结 构 ； 树 与 二 叉 树 的 转 换 关 系 ； 树 与 森 林 的 遍 历 ；Huffman 树 及 其 应 用 ； 关 于 树 与 二 叉 树 的 问 题 实 例 。7 图图 的 定 义 与 结 构 特 点 ； 图 的 相 关 概 念 ； 有 向 图 、 无 向 图 、 有 向 网 、 无 向 网 ； 图的 存 储 结 构 ； 图 的 遍 历 ； 最 小 生 成 树 ； 有 向 无 环 图 及 其 应 用 、 拓 扑 排 序 、 关 键路 径 ； 最 短 路 径 ； 关 于 图 的 问 题 实 例 。8. 查 找 表查 找 表 的 相 关 概 念 ； 静 态 查 找 表 、 有 序 表 的 查 找 、 索 引 顺 序 表 的 查 找 ； 动 态 查找 表 、 二 叉 排 序 树 与 平 衡 二 叉 树 、 B-树 与 B+树 ； 哈 希 (Hash)表 ； 关 于 查 找 表 的问 题 实 例 。9. 排 序排 序 的 概 念 ； 稳 定 排 序 、 不 稳 定 排 序 、 内 部 排 序 、 外 部 排 序 ； 插 入 排 序 、 快 速排 序 、 选 择 排 序 、 归 并 排 序 、 基 数 排 序 、 各 种 排 序 方 法 的 比 较 分 析 ； 外 部 排 序及 其 外 部 排 序 方 法 。10. 文 件文 件 的 相 关 概 念 。考 试 要 求1. 理 解 数 据 结 构 的 基 本 概 念 ， 掌 握 反 映 数 据 元 素 之 间 关 系 的 集 合 、 线 性 结 构 、树 形 结 构 、 图 形 结 构 等 四 类 基 本 结 构 。 掌 握 顺 序 存 储 结 构 与 链 式 存 储 结 构 的 存储 方 式 与 特 点 。 掌 握 算 法 的 概 念 及 其 特 性 ， 理 解 算 法 的 正 确 性 、 可 读 性 、 健 壮性 ， 以 及 算 法 的 时 间 与 空 间 复 杂 度 分 析 方 法 。2. 理 解 和 熟 练 掌 握 线 性 表 的 结 构 特 点 、 基 本 操 作 ， 区 别 理 解 顺 序 存 储 、 链 式 存储 的 特 点 ， 了 解 头 指 针 、 头 结 点 、 首 元 结 点 、 尾 结 点 等 基 本 概 念 ， 了 解 静 态 链表 、 循 环 链 表 、 双 向 链 表 等 结 构 。 掌 握 有 序 表 的 相 关 操 作 。 学 会 编 程 实 现 关 于线 性 表 的 相 关 问 题 实 例 。3. 理 解 栈 的 结 构 特 点 与 操 作 特 性 ， 熟 练 掌 握 栈 的 相 关 操 作 。 理 解 递 归 是 循 环 、递 归 是 分 解 的 问 题 求 解 思 路 ， 掌 握 递 归 执 行 中 栈 的 状 态 变 化 、 递 归 算 法 执 行 的初 始 条 件 、 参 数 传 递 以 及 结 果 返 回 方 式 ， 能 够 运 用 递 归 思 想 解 决 实 际 问 题 。4. 理 解 队 列 的 结 构 特 点 与 操 作 特 性 ， 熟 练 掌 握 队 列 的 相 关 操 作 ， 熟 悉 循 环 队 列的 实 现 方 法 。5. 理 解 串 的 结 构 特 点 ， 熟 练 掌 握 模 式 匹 配 运 算 的 思 想 与 过 程 。6. 理 解 数 组 的 结 构 特 点 ， 掌 握 数 组 的 存 储 方 式 ， 了 解 矩 阵 的 压 缩 存 储 。7. 理 解 广 义 表 的 结 构 特 点 ， 掌 握 广 义 表 的 基 本 操 作 ， 了 解 广 义 表 的 存 储 结 构 。8. 理 解 二 叉 树 的 结 构 特 点 ， 熟 练 掌 握 二 叉 树 的 性 质 、 二 叉 树 的 存 储 结 构 及 其 基本 操 作 、 二 叉 树 的 遍 历 算 法 及 其 典 型 应 用 。 了 解 线 索 二 叉 树 的 概 念 与 构 造 过 程 。学 会 编 程 实 现 关 于 二 叉 树 的 相 关 问 题 实 例 。9. 理 解 树 与 森 林 的 结 构 特 点 ， 熟 练 掌 握 树 与 森 林 的 基 本 概 念 、 树 与 森 林 的 遍 历方 法 。 掌 握 树 与 二 叉 树 的 转 换 方 法 。 了 解 Huffman 树 的 特 性 及 其 应 用 ， 学 会 构造 Huffman 树 。10 理 解 图 的 结 构 特 点 ， 掌 握 有 向 图 、 无 向 图 、 有 向 网 、 无 向 网 等 基 本 概 念 ，理 解 图 的 存 储 结 构 ， 掌 握 图 的 遍 历 方 法 。 理 解 图 的 生 成 树 、 连 通 分 量 、 拓 扑 排序 、 关 键 路 径 和 最 短 路 径 的 意 义 ， 了 解 相 应 求 解 算 法 的 思 想 。 能 够 运 用 图 结 构求 解 相 应 的 实 际 问 题 。11. 理 解 查 找 表 的 基 本 概 念 ， 熟 练 掌 握 顺 序 表 和 有 序 表 的 查 找 方 法 。 理 解 折 半查 找 与 树 表 查 找 间 的 关 系 。 熟 练 掌 握 二 叉 排 序 树 、 平 衡 二 叉 树 、 B-树 与 B+树 的结 构 特 点 与 构 造 方 法 。 熟 练 掌 握 哈 希 (Hash)表 的 结 构 特 点 与 构 造 方 法 。 能 够 按定 义 计 算 等 概 率 情 况 下 各 种 查 找 方 法 的 查 找 成 功 (或 不 成 功 )时 的 平 均 查 找 长度 。12. 理 解 排 序 的 定 义 和 各 种 排 序 方 法 的 特 点 ， 掌 握 各 种 排 序 方 法 的 实 现 过 程 ，并 加 以 灵 活 运 用 。 理 解 排 序 方 法 “ 稳 定 ” 和 “ 不 稳 定 ” 的 含 义 与 实 际 意 义 。 掌握 各 种 排 序 方 法 的 时 间 复 杂 度 。 了 解 简 单 (低 效 )排 序 方 法 与 复 杂 (高 效 )排 序 方法 的 区 别 与 应 用 选 择 。 了 解 外 部 排 序 算 法 优 化 的 目 标 和 主 要 手 段 ， 熟 悉 应 用 败者 树 实 现 多 路 归 并 ， 以 及 通 过 置 换 -选 择 进 行 外 部 排 序 的 方 法 。13. 了 解 文 件 的 相 关 概 念 。 参 阅1. 数 据 结 构 （ C 语 言 版 ） 严 蔚 敏 、 吴 伟 民 编 著 ， 清 华 大 学 出 版 社2. 数 据 结 构 习 题 集 （ C 语 言 版 ） 严 蔚 敏 、 吴 伟 民 编 著 ， 清 华 大 学 出 版 社
展开阅读全文