资源描述
2022年全国硕士研究生招生考试自命题科目考试大纲科 目 代 码 ： 823 考 试 科 目 ： 数 据 结 构一、考试性质本 课 程 是 计 算 机 类 专 业 、 网 络 空 间 安 全 专 业 的 专 业 基 础 必 修 课 ，其 涵 盖 知 识 是 相 关 专 业 研 究 生 开 展 创 新 研 究 必 须 具 备 的 基 础 。二、考查目标本 课 程 主 要 考 核 常 见 数 据 结 构 （ 线 性 表 、 树 、 图 等 ） 表 示 方 法 、 操 作 及 应 用 ； 常 用 查 找 技 术 与 排 序 算 法 等 。 主 要 考 查 目 标 有 ：1 数 据 结 构 和 算 法 设 计 基 础 知 识 ， 计 算 机 内 部 数 据 对 象 的 表 示 和特 性 分 析 ， 主 要 包 括 线 性 表 、 栈 、 队 列 、 树 、 图 、 字 典 等 的 逻辑 结 构 、 存 储 结 构 表 示 及 其 差 异 ， 针 对 具 体 问 题 的 选 型 、 建 模与 求 解 。2 常 见 数 据 结 构 上 的 典 型 操 作 和 算 法 实 现 ； 排 序 、 查 找 等 算 法 原理 及 实 现 ； 算 法 的 时 间 复 杂 度 和 空 间 复 杂 度 分 析 方 法 。3 综 合 运 用 课 程 知 识 开 展 数 据 结 构 、 算 法 的 设 计 与 分 析 。三、适用范围 本 考 试 大 纲 适 用 于 我 校 计 算 机 与 信 息 安 全 学 院 的 081200 计 算 机科 学 与 技 术 、 083900网 络 空 间 安 全 、 085400电 子 信 息 （ 01计 算 机 技术 、 02软 件 工 程 ） 专 业 的 硕 士 研 究 生 招 生 考 试 。 四、考试形式和试卷结构1 试 卷 满 分 及 考 试 时 间试 卷 满 分 ： 150分 ； 考 试 时 间 ： 180分 钟 。2 试 卷 内 容 结 构1) 数 据 结 构 和 算 法 基 础 知 识 ： 约 20分 ；2) 数 据 结 构 及 其 操 作 的 设 计 、 使 用 和 分 析 ： 约 80 分 ；3) 数 据 结 构 和 算 法 的 代 码 实 现 和 分 析 ： 约 50分 。3 试 卷 题 型 结 构 及 分 值 比 例 （ 注 ： 题 型 和 分 值 是 参 考 值 ） 题 型 单 项 选 择 题 简 答 或 计 算 题 程 序 阅 读 填 空和 分 析 题 算 法 设 计 与 实现 题分 值 30 60 45 154 命 题 可 根 据 考 核 需 要 ， 对 试 卷 内 容 结 构 、 题 型 结 构 及 分 值 比 例做 适 当 调 整 。五、考查内容1 数 据 结 构 与 算 法 绪 论1) 数 据 结 构 的 基 本 概 念 ， 包 括 数 据 的 逻 辑 特 点 、 存 储 表 示 ；2) 数 据 抽 象 方 法 ， 数 据 结 构 的 抽 象 数 据 类 型 ADT表 示 ； 3) 算 法 描 述 方 法 、 算 法 精 化 过 程 和 算 法 时 间 、 空 间 复 杂 度 分 析 方 法 。2 线 性 表1) 线 性 表 的 逻 辑 结 构 和 抽 象 数 据 类 型 定 义 ；2) 线 性 表 的 顺 序 存 储 和 链 式 存 储 ， 线 性 表 创 建 、 插 入 、 删 除 和 查 找等 基 本 操 作 的 实 现 以 及 算 法 时 间 复 杂 度 分 析 ；3) 能 分 析 不 同 存 储 结 构 的 优 缺 点 和 适 用 场 合 ， 能 分 析 不 同 的 存 储 方 式 对 算 法 性 能 的 影 响 ；4) 单 循 环 链 表 、 双 链 表 和 循 环 双 链 表 的 实 现 以 及 应 用 ；5) 线 性 表 的 应 用 实 例 分 析 ： 一 元 多 项 式 运 算 ； Josephus问 题 ；6) 字 符 串 的 逻 辑 结 构 、 存 储 结 构 和 模 式 匹 配 。3 栈 和 队 列1) 栈 和 队 列 的 逻 辑 特 点 、 抽 象 数 据 类 型 ；2) 栈 和 队 列 的 顺 序 表 示 和 链 接 表 示 ， 以 及 基 于 不 同 存 储 结 构 的 基 本操 作 的 实 现3) 递 归 函 数 的 执 行 过 程 以 及 使 用 栈 进 行 递 归 函 数 与 非 递 归 函 数 的 转换 ； 4) 栈 的 应 用 ： 数 制 转 换 ； 迷 宫 问 题 ；5) 队 列 的 应 用 ： 农 夫 过 河 问 题 ； 银 行 业 务 模 拟 ；6) 深 度 优 先 和 广 度 优 先 搜 索 策 略 的 原 理 、 不 同 之 处 以 及 应 用 场 合 。4 树 与 二 叉 树1) 树 与 二 叉 树 抽 象 数 据 类 型 、 不 同 存 储 实 现 与 约 束 分 析 ；2) 树 与 二 叉 树 周 游 算 法 及 复 杂 度 分 析 ；3) 最 优 前 缀 编 码 问 题 及 算 法 分 析 ；4) 线 索 二 叉 树 ；5) 二 叉 排 序 树 表 示 、 操 作 实 现 以 及 时 间 、 空 间 复 杂 度 分 析 ；6) 平 衡 二 叉 排 序 树 表 示 、 操 作 实 现 以 及 时 间 、 空 间 复 杂 度 分 析 ； 7) B+、 B-树 特 征 及 其 在 索 引 中 应 用 ；5 图1) 图 的 抽 象 数 据 类 型 、 不 同 存 储 结 构 与 适 用 性 分 析 ；2) 图 的 深 度 优 先 周 游 和 广 度 优 先 周 游 两 类 策 略 和 实 现 方 法 ， 能 基 于 图 的 具 体 存 储 结 构 分 析 周 游 的 处 理 过 程 ， 并 分 析 两 类 周 游 算 法 的复 杂 度 ；3) 面 向 应 用 的 核 心 算 法 实 现 与 分 析 ， 包 括 Prim 和 Kruskal最 小 生 成树 算 法 、 Dijkstra和 Floyd最 短 路 径 算 法 ；4) 面 向 特 定 应 用 的 图 形 态 ， 包 括 AOV网 和 AOE 网 。6 集 合 与 字 典1) 集 合 与 字 典 的 顺 序 表 示 、 操 作 实 现 以 及 时 间 、 空 间 复 杂 度 分 析 ；2) 字 典 的 散 列 表 示 、 操 作 实 现 以 及 时 间 、 空 间 复 杂 度 分 析 ；3) 散 列 冲 突 的 解 决 方 法 ；7 排 序 1) 插 入 类 排 序 ： 直 接 插 入 、 二 分 插 入 和 希 尔 插 入 排 序 ；2) 选 择 类 排 序 ： 直 接 选 择 和 堆 排 序 ；3) 交 换 类 排 序 ： 冒 泡 排 序 和 快 速 排 序 ；4) 分 配 类 排 序 ： 基 数 排 序 ；5) 归 并 类 排 序 ： 两 路 归 并 排 序 ；6) 各 种 排 序 算 法 时 间 复 杂 度 、 空 间 复 杂 度 、 算 法 稳 定 性 等 方 面 的 综合 比 较 ， 根 据 应 用 场 合 选 择 合 适 的 排 序 算 法 。六、参考书目张 乃 孝 ， 陈 光 ， 孙 猛 . 算 法 与 数 据 结 构 （ C语 言 描 述 ） （ 第 3版 ） ， 高 等 教 育 出 版 社 ， 2012 年 .
展开阅读全文