武汉工程大学2023年复试《算法与数据结构》考试大纲.pdf
武 汉 工 程 大 学 2024 年 硕 士 研 究 生 复 试 算 法 与 数 据 结 构 考 试 大 纲一 、 课 程 总 体 要 求考 生 应 认 真 把 握 该 课 程 的 考 试 、 学 习 要 求 、 考 核 知 识 点 和 有 关 考 核 的 具 体 问题 。 要 求 数 据 结 构 算 法 设 计 题 编 程 全 部 采 用 C语 言 。1、 基 本 理 论 知 识(l)什 么 是 数 据 结 构 、 基 本 概 念 和 基 本 术 语 、 数 据 结 构 的 发 展 简 史 及 它 在 计 算 机科 学 中 所 处 的 地 位 ,算 法 的 描 述 和 算 法 分 析 。(2)什 么 是 线 性 表 、 在 线 性 表 上 常 进 行 的 基 本 操 作 以 及 这 些 操 作 分 别 在 顺 序 存 储和 链 式 存 储 结 构 下 的 实 现 及 复 杂 度 分 析 。 (3)栈 和 队 列 的 定 义 、 表 示 方 法 和 实 现 。(4)串 的 定 义 及 其 基 本 操 作 。(5)数 组 的 定 义 、 运 算 和 存 储 、 稀 疏 矩 阵 的 压 缩 存 储 、 广 义 表 的 定 义 和 操 作 。(6)树 的 定 义 、 基 本 术 语 和 存 储 结 构 、 二 叉 树 的 定 义 和 性 质 ,二 叉 树 的 存 储 结 构 及其 各 种 操 作 ,哈 夫 曼 树 。(7)图 的 定 义 和 术 语 、 图 的 存 储 结 构 及 其 各 种 操 作 。(8)各 种 查 找 方 法 的 算 法 、 适 用 范 围 及 时 间 复 杂 度 的 分 析 。(9)内 部 排 序 、 基 数 排 序 和 比 较 排 序 ,各 种 基 本 排 序 方 法 的 算 法 和 时 间 复 杂 度 。2、 基 本 技 能(1)能 阅 读 用 类 C语 言 编 写 的 算 法 。(2)能 分 析 算 法 所 完 成 的 功 能 、 运 行 结 果 和 时 间 复 杂 度 。(3)能 根 据 要 求 用 类 C语 言 编 写 算 法 。 二 、 考 核 知 识 点第 一 章 绪 论1.数 据 、 数 据 元 素 、 数 据 项 、 数 据 对 象 、 数 据 结 构 、 逻 辑 结 构 、 物 理 结 构 、 元 素 、结 点 等 基 本 概 念 。2.实 现 关 系 的 两 种 方 法 (顺 序 和 链 式 )及 相 应 的 存 储 结 构 。3.算 法 、 算 法 的 特 性 、 如 何 用 类 C语 言 来 描 述 算 法 。4.评 价 算 法 好 坏 的 主 要 标 准 、 “ 0(f(n)的 形 式 定 义 、 了 解 算 法 的 渐 近 时 间 复 杂度 、 语 句 的 频 度 、 最 坏 情 况 时 间 复 杂 度 和 平 均 时 间 复 杂 度 的 概 念 。第 二 章 线 性 表1.线 性 表 的 定 义 和 操 作 。2.顺 序 存 储 线 性 表 的 实 现 和 运 算 。 3.链 式 存 储 线 性 表 (静 态 链 表 和 动 态 链 表 ),带 有 附 加 表 头 结 点 和 不 带 附 加 表 头 结点 的 单 链 表 、 循 环 链 表 和 双 向 链 表 的 实 现 和 查 找 对 插 入 、 删 除 等 基 本 操 作 。4.链 表 应 用 举 例 一 一 一 元 多 项 式 的 表 示 及 相 加 的 算 法 。第 三 章 栈 和 队 列1.栈 和 队 列 的 定 义 及 其 存 储 结 构 、 循 环 队 列 。2.栈 和 队 列 的 主 要 运 算 。3.栈 的 应 用 举 例 一 一 表 达 式 求 值 的 过 程 。第 四 章 串1.串 的 定 义 、 空 串 、 空 格 串 。2.串 的 基 本 操 作 。3.串 的 顺 序 存 储 结 构 及 在 顺 序 存 储 结 构 下 基 本 操 作 的 实 现 。第 五 章 数 组 和 广 义 表 1.数 组 的 顺 序 存 储 结 构 。2.二 维 数 组 的 按 行 存 储 及 按 列 存 储 和 计 算 数 组 元 素 的 地 址 计 算 公 式 。3.矩 阵 的 压 缩 存 储 、 特 殊 矩 阵 的 表 示 。4.广 义 表 的 定 义 和 操 作 (HEAD和 TAIL)。第 六 章 树 和 二 叉 树1.树 的 定 义 和 术 语 。2.树 的 存 储 表 示 法 孩 子 表 示 法 、 双 亲 表 示 法 、 孩 子 兄 弟 表 示 法 。3.树 和 森 林 转 换 为 二 叉 树 的 方 法 。4.二 叉 树 (完 全 ;二 叉 树 、 满 二 叉 树 )的 定 义 和 性 质 (结 论 )、 二 叉 树 的 存 储 结 构 顺 序 表 示 法 和 二 叉 链 表 表 示 法 。5.二 叉 树 遍 历 的 递 归 算 法 。6.树 的 路 径 长 度 、 树 的 带 权 路 径 长 度 、 Huffman树 的 构 造 方 法 。 第 七 章 图1.图 的 定 义 。2.图 的 基 本 术 语 。(1)图 及 无 向 图 、 有 向 图 、 网 、 子 图 、 连 通 图 、 强 连 通 图 。(2)顶 点 的 度 、 入 度 、 出 度 。(3)顶 点 间 路 径 、 路 径 长 度 、 环 。3.图 的 存 储 结 构(l)邻 接 矩 阵 。(2)邻 接 表 (含 逆 邻 接 表 )。4.遍 历 图(l)深 度 优 先 插 索 遍 历 图 的 算 法 及 其 时 间 复 杂 度 。 (2)广 度 优 先 插 索 遍 历 图 的 算 法 及 其 时 间 复 杂 度 。5.生 成 树(1)生 成 树 、 最 小 生 成 树 的 概 念 。(2)最 小 生 成 树 的 算 法 (Prim算 法 和 Kruskai算 法 )及 其 时 间 复 杂 度 。6.最 短 路 径(l)求 源 点 到 其 余 各 顶 点 间 的 最 短 路 径 。 DijKstra算 法 的 思 想 及 其 时 间 复 杂 度 。(2)求 各 顶 点 对 间 的 最 短 路 径 。 Floyed算 法 的 思 想 及 其 时 间 复 杂 度 。第 九 章 查 找1.查 找 的 定 义 关 键 字 、 查 找 、 平 均 查 找 长 度 。2.静 态 查 找 表 的 查 找 算 法 及 其 效 率 (最 坏 和 平 均 长 度 )。(l)顺 序 查 找 。(2)折 半 查 找 。 (3)分 块 查 找 (索 引 顺 序 表 的 查 找 )。3.动 态 查 找 表(1)二 叉 排 序 树 的 查 找 算 法 及 其 效 率 。(2)平 衡 二 叉 树 (AVid树 )的 定 义 。4.哈 希 表(l)哈 希 法 的 特 点 。(2)哈 希 函 数 和 散 列 地 址 。(3)构 造 哈 希 函 数 的 几 种 方 法 。 直 接 定 址 法 、 除 留 余 数 法 、 平 方 取 中 法 、 折 叠 法 、数 字 分 析 法 。(4)处 理 冲 突 的 方 法 。冲 突 的 处 理 ,开 放 定 址 法 和 链 地 址 法 ,开 放 定 址 法 又 分 为 线 性 探 测 再 散 列 、 二 次 探测 再 散 列 和 伪 随 机 探 测 再 散 列 。 第 十 章 内 部 排 序1.排 序 的 目 的 、 分 类 和 排 序 方 法 的 稳 定 性 的 定 义 。2.插 入 排 序 。(1)直 接 插 入 排 序 的 算 法 。(2)折 半 插 入 排 序 的 算 法 。3.希 尔 排 序 的 思 想 。4.选 择 排 序 的 思 想 。5.堆 排 序 的 方 法 、 堆 的 定 义 、 初 始 堆 的 求 取 。6.起 泡 排 序 的 思 想 。7.快 速 排 序 的 算 法 、 快 速 排 序 的 最 坏 情 况 时 间 复 杂 度 的 分 析 。8.归 并 排 序 的 思 想 、 影 响 归 并 排 序 稳 定 性 的 因 素 。 9.基 数 排 序 的 思 想 及 特 点 。三 、 考 试 要 求 ( 包 括 考 试 时 间 、 总 分 、 考 试 方 式 、 题 型 、 分 数 比 例 等 )考 试 时 间 2小 时 , 总 分 100分 , 考 试 方 式 为 闭 卷 考 试 , 试 卷 题 型 及 分 数 比 例 为 :选 择 题 和 判 断 题 共 40分 ; 简 答 题 30分 ; 算 法 设 计 题 : 30分 ;四 、 主 要 参 考 书 目1、 严 蔚 敏 ,李 冬 梅 ,吴 伟 民 . 数 据 结 构 (C 语 言 版 第 2 版 )M.北 京 : 清 华 大学 出 版 社 , 2015 年2、 秦 友 淑 , 曹 化 工 . C 语 言 程 序 设 计 教 程 ( 第 二 版 ) M.武 汉 : 华 中 科 技 大学 出 版 社 , 2002年