资源描述
807软 件 工 程 专 业 综 合第 一 部 分 数 据 结 构 （ 90/150）一 、 考 试 要 求要 求 考 生 比 较 系 统 地 理 解 数 据 结 构 的 基 本 概 念 和 基 本 理 论 ， 掌 握 各 种 数 据 结 构 的 特 点 和 基 本 方 法 ， 着 重 考察 考 生 综 合 运 用 所 学 知 识 分 析 问 题 和 解 决 问 题 的 能 力 。 要 求 考 生 能 够 用 C/C+语 言 描 述 数 据 结 构 中 的 算 法 。二 、 考 试 内 容（ 一 ） 绪 论数 据 结 构 的 基 本 概 念 ， 数 据 的 逻 辑 结 构 、 存 储 结 构 ；算 法 的 定 义 和 应 具 有 的 特 性 ， 算 法 设 计 的 要 求 ， 算 法 的 时 间 复 杂 度 分 析 和 算 法 的 空 间 复 杂 度 分 析 。（ 二 ） 线 性 表线 性 结 构 的 特 点 、 线 性 表 的 定 义 ， 线 性 表 的 基 本 操 作 ；线 性 表 的 顺 序 存 储 结 构 ， 对 其 进 行 检 索 、 插 入 和 删 除 等 操 作 ；线 性 表 的 链 式 存 储 结 构 ， 单 链 表 、 双 向 链 表 和 循 环 链 表 这 三 种 链 表 形 式 的 存 储 结 构 和 特 点 以 及 基 本 操 作 。（ 三 ） 栈 和 队 列 ， 递 归 算 法栈 的 定 义 、 结 构 特 点 及 其 存 储 方 式 (顺 序 存 储 与 链 接 存 储 )和 基 本 操 作 的 实 现 算 法 ；队 列 的 结 构 、 特 点 及 其 存 储 方 式 (顺 序 存 储 与 链 接 存 储 )和 基 本 操 作 的 实 现 算 法 。递 归 的 基 本 概 念 和 实 现 原 理 以 及 用 递 归 的 思 想 描 述 问 题 和 书 写 算 法 的 方 法 ；用 栈 实 现 递 归 问 题 的 非 递 归 解 法 。（ 四 ） 数 组 和 串串 的 基 本 概 念 、 串 的 存 储 结 构 和 相 关 的 操 作 算 法 ；数 组 的 存 储 结 构 ， 在 顺 序 存 储 的 情 况 下 ， 数 组 元 素 与 存 储 单 元 的 对 应 关 系 ；稀 疏 矩 阵 的 存 储 结 构 和 特 点 以 及 基 本 操 作 。字 符 串 匹 配 算 法 (例 如 KMP算 法 )。（ 五 ） 树 和 森 林树 的 结 构 和 主 要 概 念 ， 各 种 二 叉 树 的 结 构 及 其 特 点 ；二 叉 树 的 三 种 遍 历 方 法 的 实 现 原 理 和 性 质 ， 能 将 二 叉 树 的 遍 历 方 法 应 用 于 求 解 二 叉 树 的 叶 子 结 点 个 数 、 二叉 树 计 数 等 问 题 ， 遍 历 的 非 递 归 实 现 方 法 ；线 索 化 二 叉 树 的 结 构 和 基 本 操 作 ；森 林 的 定 义 和 存 储 结 构 ， 森 林 的 遍 历 等 方 法 的 实 现 ；基 于 霍 夫 曼 树 生 成 霍 夫 曼 编 码 的 方 法 ；AVL树 的 定 义 和 特 点 以 及 AVL树 调 整 操 作 的 实 现 原 理 ；最 优 二 叉 树 的 构 造 原 理 和 相 关 算 法 。（ 六 ） 图图 的 各 种 基 本 概 念 和 各 种 存 储 方 式 ；图 的 两 种 搜 索 方 法 和 图 连 的 连 通 性 ；两 种 最 小 生 成 树 的 生 成 方 法 ；各 种 求 最 短 路 径 的 方 法 ；用 顶 点 表 示 活 动 和 用 边 表 示 活 动 的 两 种 网 络 结 构 特 点 和 相 关 操 作 的 实 现 算 法 。（ 七 ） 排 序插 入 排 序 法 (含 折 半 插 入 排 序 法 )、 选 择 排 序 法 、 泡 排 序 法 、 快 速 排 序 法 、 堆 积 排 序 法 、 归 并 排 序 、 基 数 排序 等 排 序 方 法 排 序 的 原 理 、 规 律 和 特 点 ；各 种 排 序 算 法 的 时 空 复 杂 度 的 简 单 分 析 。（ 八 ） 索 引 结 构 与 散 列线 性 索 引 结 构 、 倒 排 表 、 静 态 搜 索 树 的 结 构 和 特 点 ；B树 的 结 构 ；散 列 的 实 现 原 理 和 各 种 操 作 的 实 现 算 法 。三 、 试 卷 结 构考 试 题 型 ： 填 空 题 、 选 择 题 、 简 答 题 、 编 程 题第 二 部 分 操 作 系 统 （ 60/150） (与 第 三 部 分 二 选 一 )一 、 考 试 要 求要 求 考 生 比 较 系 统 地 理 解 和 掌 握 操 作 系 统 的 基 本 概 念 、 主 要 功 能 、 主 要 组 成 部 分 、 各 个 主 要 组 成 部 分 的 不同 实 现 方 法 ； 从 资 源 管 理 和 应 用 程 序 与 硬 件 系 统 接 口 的 观 点 掌 握 操 作 系 统 设 计 的 基 本 思 想 ， 掌 握 现 代 计 算机 系 统 对 其 各 种 软 硬 资 源 的 管 理 技 术 。 要 求 考 生 具 备 综 合 运 用 所 学 知 识 分 析 问 题 和 解 决 问 题 的 能 力 。二 、 考 试 内 容（ 一 ） 基 本 概 念计 算 机 基 本 构 成 、 处 理 器 的 内 部 结 构 、 高 速 缓 冲 存 储 器 CACHE；操 作 系 统 的 概 念 、 演 变 历 程 、 特 性 、 分 类 、 运 行 环 境 、 功 能 ；存 储 器 的 层 次 结 构 。（ 二 ） 进 程进 程 的 概 念 和 特 点 ；进 程 状 态 转 换 。（ 三 ） 线 程 、 对 称 多 处 理 SMP和 微 内 核线 程 的 概 念 ， 定 义 线 程 的 必 要 性 和 可 能 性 ；线 程 的 功 能 特 性 与 实 现 方 式 ；对 称 多 处 理 SMP体 系 结 构 ；操 作 系 统 的 体 系 结 构 （ 微 内 核 与 单 内 核 ） 及 其 性 能 分 析 。（ 四 ） 并 发并 发 性 问 题 及 相 关 概 念 ， 如 临 界 区 、 互 斥 、 信 号 量 和 管 程 等 ；进 程 互 斥 、 同 步 和 通 信 的 各 种 算 法 ；死 锁 的 概 念 、 死 锁 的 原 因 和 条 件 ；死 锁 的 预 防 、 避 免 和 检 测 算 法 。（ 五 ） 存 储 器 管 理分 区 存 储 管 理 、 覆 盖 与 交 换 ；页 式 管 理 及 段 式 管 理 ；段 、 页 式 存 储 管 理 方 法 及 实 现 技 术 ；虚 存 的 原 理 及 相 关 的 各 种 算 法 和 数 据 结 构 。（ 六 ） 单 处 理 器 调 度处 理 器 的 三 种 调 度 类 型 ；进 程 调 度 的 各 种 算 法 及 其 特 点 。（ 七 ） 多 处 理 器 调 度 和 实 时 调 度多 处 理 器 对 进 程 调 度 的 影 响 ；多 处 理 器 环 境 下 的 进 程 和 线 程 调 度 算 法 ；实 时 进 程 的 特 点 ；限 期 调 度 和 速 率 单 调 调 度 方 法 。（ 八 ） 设 备 管 理 和 磁 盘 调 度操 作 系 统 中 输 入 /输 出 功 能 的 组 织 ；中 断 处 理 ；设 备 驱 动 程 序 、 设 备 无 关 的 软 件 接 口 和 spooling技 术 ；缓 冲 策 略 ；磁 盘 调 度 算 法 ；磁 盘 阵 列 。（ 九 ） 文 件 系 统文 件 系 统 特 点 与 文 件 组 织 方 式 ；文 件 系 统 的 数 据 结 构 ；目 录 的 基 本 性 质 及 其 实 现 方 法 ；磁 盘 空 间 的 管 理 。（ 十 ） 分 布 式 系 统分 布 式 处 理 的 特 点 、 类 型 ；多 层 体 系 结 构 、 中 间 件 技 术 ；机 群 系 统 ；分 布 式 进 程 管 理 相 关 的 操 作 系 统 设 计 问 题 。三 、 试 卷 结 构考 试 题 型 ： 填 空 题 、 选 择 题 、 简 答 题 、 计 算 题第 三 部 分 数 据 库 系 统 原 理 （ 60/150） (与 第 二 部 分 二 选 一 )一 、 考 试 要 求要 求 考 生 熟 悉 数 据 库 系 统 的 基 本 概 念 、 原 理 和 基 础 理 论 ， 熟 悉 关 系 数 据 模 型 、 关 系 代 数 、 关 系 系 统 、 关 系数 据 库 设 计 方 法 ， 以 及 数 据 库 恢 复 、 并 发 控 制 、 安 全 性 、 完 整 性 等 数 据 库 系 统 技 术 ； 能 够 熟 练 使 用 SQL，具 备 使 用 数 据 库 管 理 系 统 和 设 计 数 据 库 的 能 力 。二 、 考 试 内 容（ 一 ） 概 论数 据 、 数 据 库 、 数 据 库 管 理 系 统 、 数 据 库 系 统 、 数 据 库 系 统 的 特 点 等 基 本 概 念 的 定 义 、 数 据 管 理 的 三个 阶 段 ；数 据 模 型 ： 概 念 模 型 、 关 系 模 型 、 面 向 对 象 等 的 构 造 形 式 及 特 点 ；数 据 库 系 统 结 构 ： 三 级 结 构 、 两 级 映 像 。（ 二 ） 关 系 数 据 库关 系 模 型 、 关 系 模 式 、 关 系 数 据 库 等 基 本 概 念 以 及 关 系 代 数 理 论 ；能 够 运 用 关 系 代 数 （ 并 、 交 、 差 、 除 、 笛 卡 尔 积 、 选 择 、 投 影 、 连 接 ） 完 成 关 系 运 算 。（ 三 ） SQL语 言SQL特 点 、 SQL标 准 ；各 类 SQL 语 句 的 语 法 构 成 、 语 义 与 功 能 ， 能 够 运 用 标 准 SQL 完 成 数 据 存 取 ；视 图 的 概 念 、 视 图 的 定 义 、 视 图 操 纵 、 视 图 的 更 新 ；存 储 过 程 、 触 发 器 。（ 四 ） 关 系 存 储 和 查 询 优 化表 的 存 储 、 索 引 结 构 、 聚 簇 结 构 ；关 系 系 统 分 类 ；查 询 优 化 概 念 、 查 询 优 化 方 法 。（ 五 ） 数 据 库 设 计数 据 库 设 计 的 步 骤 ， 以 及 每 个 步 骤 重 点 关 心 的 问 题 ；实 体 联 系 分 析 ， ER模 型 ， ER模 型 向 关 系 模 型 转 换 规 则 ；（ 六 ） 关 系 规 范 化数 据 库 设 计 的 冗 余 和 异 常 问 题 ；函 数 依 赖 、 多 汁 依 赖 、 逻 辑 蕴 涵 、 阿 姆 斯 特 朗 公 理 ；基 本 依 赖 闭 包 、 候 选 码 ；无 损 分 解 ， 1NF、 2NF、 3NF、 BCNF、 4NF定 义 与 算 法 。（ 七 ） 安 全 性 和 完 整 性数 据 库 安 全 性 控 制 的 基 本 技 术 ： 用 户 、 角 色 、 权 限 、 授 权 ；完 整 性 分 类 和 完 整 性 控 制 方 法 。触 发 器 的 使 用 方 法 。（ 八 ） 事 务 管 理事 务 的 概 念 、 性 质 ， 事 务 的 实 现 ；数 据 库 故 障 、 日 志 ， 数 据 库 恢 复 原 理 和 方 法 ；并 发 问 题 ： 数 据 不 一 致 性 ；数 据 锁 、 封 锁 粒 度 、 封 锁 协 议 ，死 锁 检 测 和 死 锁 处 理 ；三 、 试 卷 结 构考 试 题 型 ： 填 空 题 、 选 择 题 、 简 答 题 、 计 算 题 、 设 计 题
展开阅读全文