2017年中科院计算机学科综合(非专业)考研参考书

《2017年中科院计算机学科综合(非专业)考研参考书》由会员分享，可在线阅读，更多相关《2017年中科院计算机学科综合(非专业)考研参考书（6页珍藏版）》请在金锄头文库上搜索。

1、中 国 科 学 院 大 学 硕 士 研 究 生 入 学 考 试 计 算 机 学 科 综 合 (非 专 业 ) 考 试 大 纲本 计 算 机 学 科 综 合 (非 专 业 ) 考 试 大 纲 适 用 于 中 国 科 学 院 大 学 非 计 算 机 科 学 与 技 术 一级 学 科 下 各 专 业 的 硕 士 研 究 生 入 学 考 试 。 计 算 机 学 科 综 合 (非 专 业 ) 主 要 内 容 包 括 数 据 结构 、 操 作 系 统 和 计 算 机 网 络 三 大 部 分 。 要 求 考 生 对 计 算 机 科 学 与 技 术 及 相 关 学 科 的 基 本 概 念有 较 深 入 、 系

2、 统 的 理 解 ； 掌 握 各 种 数 据 结 构 的 定 义 和 实 现 算 法 ； 掌 握 操 作 系 统 和 计 算 机 网 络所 涉 及 的 关 键 内 容 ， 并 具 有 综 合 运 用 所 学 知 识 分 析 问 题 和 解 决 问 题 的 能 力 。一 、 考 试 内 容数 据 结 构1 、 绪 论（ 1 ） 数 据 结 构 的 基 本 概 念 ， 数 据 的 逻 辑 结 构 、 存 储 结 构 。（ 2 ） 算 法 的 定 义 、 算 法 的 基 本 特 性 以 及 算 法 分 析 的 基 本 概 念 。2 、 线 性 表（ 1 ） 线 性 关 系 、 线 性 表 的 定 义

3、 ， 线 性 表 的 基 本 操 作 。（ 2 ） 线 性 表 的 顺 序 存 储 结 构 与 链 式 存 储 结 构 (包 括 单 链 表 、 循 环 链 表 和 双 向 链 表 )的 构 造 原理 。 在 以 上 两 种 存 储 结 构 上 对 线 性 表 实 施 的 最 主 要 的 操 作 (包 括 三 种 链 表 的 建 立 、 插 入 和 删除 、 检 索 等 )的 算 法 设 计 。3 、 堆 栈 与 队 列（ 1 ） 堆 栈 与 队 列 的 基 本 概 念 、 基 本 操 作 。（ 2 ） 堆 栈 与 队 列 的 顺 序 存 储 结 构 与 链 式 存 储 结 构 的 构 造 原

4、 理 。（ 3 ） 在 不 同 存 储 结 构 的 基 础 上 对 堆 栈 与 队 列 实 施 插 入 与 删 除 等 基 本 操 作 对 应 的 算 法 设 计 。4 、 串（ 1 ） 串 的 基 本 概 念 、 串 的 基 本 操 作 和 存 储 结 构 。（ 2 ） 串 的 模 式 匹 配 算 法 和 改 进 的 KMP 算 法5 、 数 组 和 广 义 表（ 1 ） 数 组 的 概 念 ， 以 及 表 示 和 实 现（ 2 ） 矩 阵 （ 对 称 矩 阵 和 稀 疏 矩 阵 ） 的 压 缩 存 储（ 3 ） 广 义 表 的 基 本 概 念6 、 树 与 二 叉 树（ 1 ） 树 的 定

5、 义 和 性 质（ 2 ） 二 叉 树 的 概 念 、 性 质 和 实 现（ 3 ） 遍 历 二 叉 树 和 线 索 二 叉 树（ 4 ） 树 和 森 林（ 5 ） 赫 夫 曼 树 及 其 应 用（ 6 ） 回 溯 法 与 树 的 遍 历（ 7 ） 树 的 计 数7 、 图（ 1 ） 图 的 定 义 ， 基 本 概 念 ， 图 的 分 类 ， 常 用 名 词 术 语 。（ 2 ） 图 的 邻 接 矩 阵 存 储 方 法 、 邻 接 表 存 储 方 法 的 构 造 原 理 。（ 3 ） 图 的 遍 历 操 作 。（ 4 ） 图 的 连 通 性 、 最 小 生 成 树（ 5 ） 最 短 路 径 的

6、 计 算（ 6 ） AOV 网 与 拓 扑 排 序 。8 、 查 找（ 1 ） 静 态 查 找 表 ： 顺 序 表 、 有 序 表 、 静 态 树 表 以 及 索 引 表 的 查 找 。（ 2 ） 动 态 查 找 表 ： 二 叉 排 序 树 和 平 衡 二 叉 树 ， 以 及 B 树 和 B+树 的 基 本 概 念 和 操 作 。（ 3 ） 哈 希 表 ： 基 本 概 念 和 构 造 方 法 ， 冲 突 处 理 方 法 和 查 询 及 性 能 分 析 。9 、 内 排 序（ 1 ） 排 序 的 基 本 概 念 ， 排 序 方 法 的 分 类 。（ 2 ） 插 入 排 序 法 (含 折 半 插

7、入 排 序 法 )、 选 择 排 序 法 、 快 速 排 序 法 、 堆 排 序 法 、 归 并 排 序 、基 数 排 序 。 各 种 排 序 方 法 排 序 的 原 理 、 规 律 和 特 点 ， 各 种 排 序 算 法 的 时 空 复 杂 度 简 单 分 析 。操 作 系 统1、 操 作 系 统 概 述（ 1） 计 算 机 基 本 构 成 、 处 理 器 的 内 部 结 构 、 高 速 缓 冲 存 储 器 CACHE；（ 2） 操 作 系 统 的 概 念 、 演 变 历 程 、 特 性 、 分 类 、 运 行 环 境 、 功 能（ 3） 存 储 器 的 层 次 结 构2 、 、 进 程进

8、程 、 进 程 描 述 及 进 程 状 态 转 换3 、 线 程 、 对 称 多 处 理 SMP和 微 内 核（ 1） 线 程 的 概 念 ， 定 义 线 程 的 必 要 性 和 可 能 性 ；（ 2） 线 程 的 功 能 特 性 与 实 现 方 式 ；（ 3） 对 称 多 处 理 SMP体 系 结 构 ；（ 4） 操 作 系 统 的 体 系 结 构 （ 微 内 核 与 巨 内 核 ） 及 其 性 能 分 析 。4、 并 发 性（ 1） 并 发 性 问 题 及 相 关 概 念 ， 如 临 界 区 、 互 斥 、 信 号 量 和 管 程 等 ；（ 2） 进 程 互 斥 、 同 步 和 通 信 的

9、 各 种 算 法 ；（ 3） 死 锁 的 概 念 、 死 锁 的 原 因 和 条 件（ 4） 死 锁 的 预 防 、 避 免 和 检 测 算 法 。5、 存 储 器 管 理（ 1） 分 区 存 储 管 理 、 覆 盖 与 交 换 ；（ 2） 页 式 管 理 及 段 式 管 理 ；（ 3） 段 、 页 式 存 储 管 理 方 法 及 实 现 技 术 ；（ 4） 虚 存 的 原 理 及 相 关 的 各 种 算 法 和 数 据 结 构 。6、 单 处 理 器 调 度（ 1） 处 理 器 的 三 种 调 度 类 型 ；（ 2） 进 程 调 度 的 各 种 算 法 及 其 特 点 。7、 多 处 理 器

10、 调 度 和 实 时 调 度（ 1） 多 处 理 器 对 进 程 调 度 的 影 响（ 2） 多 处 理 器 环 境 下 的 进 程 和 线 程 调 度 算 法 ；（ 3） 实 时 进 程 的 特 点 ；（ 4） 限 期 调 度 和 速 率 单 调 调 度 方 法 。8、 设 备 管 理 和 磁 盘 调 度（ 1） 操 作 系 统 中 输 入 /输 出 功 能 的 组 织 ；（ 2） 中 断 处 理 ；（ 3） 设 备 驱 动 程 序 、 设 备 无 关 的 软 件 接 口 和 spooling技 术 ；（ 4） 缓 冲 策 略 ；（ 5） 磁 盘 调 度 算 法 ；（ 6） 磁 盘 阵 列

11、。9、 文 件 系 统（ 1） 文 件 系 统 特 点 与 文 件 组 织 方 式 ；（ 2） 文 件 系 统 的 数 据 结 构 ；（ 3） 目 录 的 基 本 性 质 及 其 实 现 方 法 ；（ 4） 磁 盘 空 间 的 管 理 。10、 分 布 式 系 统（ 1） 分 布 式 处 理 的 特 点 、 类 型 ；（ 2） 多 层 体 系 结 构 、 中 间 件 技 术 ；（ 3） 机 群 系 统 ；（ 4） 分 布 式 进 程 管 理 相 关 的 操 作 系 统 设 计 问 题 。计 算 机 网 络1、 绪 论（ 1） 计 算 机 网 络 的 概 念 、 分 类 、 标 准 、 组 成

12、与 功 能（ 2） 计 算 机 网 络 分 层 结 构 ， 协 议 、 接 口 、 服 务 等 概 念 ， ISO/OSI模 型 和 TCP/IP模 型2、 物 理 层（ 1） 通 信 信 道 、 信 号 、 宽 带 、 码 元 、 波 特 、 速 率 、 信 源 与 信 宿 等 基 本 概 念 ， 电 路 交 换 、报 文 交 换 与 分 组 交 换 ， 数 据 报 与 虚 电 路（ 2） 双 绞 线 ， 物 理 层 接 口 的 特 性 ， 中 继 器 ， 集 线 器3、 数 据 链 路 层（ 1） 数 据 链 路 层 的 功 能 ， 组 帧 ， 差 错 控 制 （ 检 错 与 纠 错 编

13、码 ）（ 2） 流 量 控 制 、 可 靠 传 输 与 滑 轮 窗 口 机 制 ， 停 止 -等 待 协 议 ， 后 退 N 帧 协 议 (GBN)， 选择 重 传 协 议 (SR)（ 3） CSMA/CA协 议 、 令 牌 传 递 协 议（ 4） 局 域 网 的 概 念 及 其 体 系 结 构 ， 以 太 网 与 IEEE 802.3， IEEE802.114、 网 络 层（ 1） 网 络 层 的 功 能 ， 异 构 网 络 互 联 ， 路 由 与 转 发 ， 拥 塞 控 制（ 2） 路 由 算 法 ， 静 态 路 由 与 动 态 路 由 ， 距 离 -向 量 路 由 算 法 ， 链 路 状

14、 态 路 由 算 法（ 3） IPv4 分 组 ， IPv4地 址 与 NAT， 子 网 划 分 与 子 网 掩 码 、 CIDR， ARP 协 议 、 DHCP协 议与 ICMP协 议（ 4） IPv6 的 主 要 特 点 ， IPv6 地 址（ 5） 路 由 协 议 ， 自 治 系 统 ， 域 内 路 由 与 域 间 路 由 ， RIP路 由 协 议 、 OSPF 路 由 协 议 、 BGP路 由 协 议（ 6） 组 播 的 概 念 ， IP组 播 地 址（ 7） 路 由 器 的 组 成 和 功 能 ， 路 由 表 与 路 由 转 发5、 传 输 层（ 1） 传 输 层 的 功 能 ， 传

15、 输 层 寻 址 与 端 口 ， 无 连 接 服 务 与 面 向 连 接 服 务（ 2） UDP协 议 ， UDP数 据 报 ， UDP 校 验（ 3） TCP 协 议 ， TCP 段 ， TCP 连 接 管 理 ， TCP可 靠 传 输 ， TCP 流 量 控 制 与 拥 塞 控 制6、 应 用 层（ 1） 客 户 /服 务 器 模 型 ， P2P模 型（ 2） DNS 概 念 ， 层 次 域 名 空 间 ， 域 名 服 务 器 ， 域 名 解 析 过 程（ 3） FTP 协 议 的 工 作 原 理 ， 控 制 连 接 与 数 据 连 接（ 4） 电 子 邮 件 系 统 的 组 成 结 构

16、， SMTP 协 议 与 POP3协 议（ 5） WWW 的 概 念 与 组 成 结 构 ， HTTP协 议二 、 考 试 要 求数 据 结 构1 、 建 立 有 关 数 据 结 构 最 基 本 的 概 念 ， 包 括 数 据 的 逻 辑 结 构 、 存 储 结 构 和 算 法 ， 算 法 分 析 的基 本 概 念 与 基 本 方 法2 、 掌 握 线 性 表 的 基 本 概 念 以 及 两 种 存 储 结 构 的 构 造 原 理 ， 掌 握 在 各 种 存 储 结 构 下 对 线 性 表进 行 的 基 本 操 作 的 算 法 设 计 。3 、 掌 握 堆 栈 和 队 列 的 基 本 概 念 与 特 征 ， 掌 握 在 两 种 存 储 结 构 下 如 何 对 堆 栈 和 队 列 进 行 插 入和 删 除 等 操 作 ， 以 及 利 用 堆 栈 与 队 列 解 决 实 际 问 题 的 基 本 方 法 。4 、 充 分 了 解 串 的 基 本 概 念 、 掌 握 串 的 存 储 结 构 和 相 关 的 操 作 算 法 。5 、 掌 握 数 组