<4D6963726F736F667420576F7264202D2032303133C4EACBB6CABFD1D0BEBFC9FAC8EBD1A7BFBCCAD4525543BCC6CBE3BBFAD7A8D2B5BFCEBCB0B2CEBFBCCAE92E646F63>

2013 年 硕 士 研 究 生 入 学 考 试 ( 初 试 ) 中 国 人 民 大 学 信 息 学 院 计 算 机 专 业 综 合 科 目 设 置 方 案 科 目 代 码 :848 考 试 内 容 : 由 数 据 结 构 系 统 软 件 和 系 统 结 构 三 方 面 的 内 容 构 成 分 数 分 配 : 总 分 150 分, 各 门 课 程 分 配 如 下 : 1 数 据 结 构 ( 用 C 语 言 ):50 分 2 系 统 软 件 ( 操 作 系 统 与 数 据 库 二 选 一 ):50 分 3 系 统 结 构 ( 计 算 机 网 络 与 计 算 机 组 成 原 理 二 选 一 ):50 分 附 注 : 操 作 系 统 需 结 合 Linux 系 统 作 答 考 试 大 纲 : 以 408 的 大 纲 为 参 照, 略 有 调 整, 另 行 发 布 中 国 人 民 大 学 信 息 学 院 2012 年 9 月 参 考 书 推 荐 数 据 结 构 : 清 华 大 学 出 版 社 的 数 据 结 构 (C 语 言 版 ), 严 蔚 敏 吴 伟 民 编 著 操 作 系 统 : William Stallings 的 Operating Systems: Internals and Design Principles(Sixth Edition) 电 子 工 业 出 版 社 引 进 版 : 操 作 系 统 : 精 髓 与 设 计 原 理 ( 第 六 版 - 英 文 版 ) 中 译 本 : 操 作 系 统 : 精 髓 与 设 计 原 理 ( 原 书 第 6 版 ), 陈 向 群 陈 渝 等 译, 机 械 工 业 出 版 社 数 据 库 : 高 等 教 育 出 版 社 的 数 据 库 系 统 概 论 ( 第 4 版 ), 王 珊 萨 师 煊 著 计 算 机 网 络 : 清 华 大 学 出 版 社 的 计 算 机 网 络 ( 第 5 版 ), 特 南 鲍 姆 韦 瑟 罗 尔 著, 严 伟 潘 爱 民 译 计 算 机 组 成 原 理 : 清 华 大 学 出 版 社 的 计 算 机 组 成 与 结 构 ( 第 4 版 ), 王 爱 英 编 著

数 据 结 构 课 程 说 明 考 查 目 的 : 1 掌 握 数 据 结 构 的 基 本 概 念 原 理 和 基 本 方 法 ; 2 掌 握 数 据 结 构 中 的 逻 辑 结 构 存 储 结 构 及 基 本 操 作 的 实 现, 能 够 对 算 法 进 行 基 本 的 时 间 复 杂 度 和 空 间 复 杂 度 的 分 析 ; 3 能 够 运 用 数 据 结 构 的 基 本 原 理 和 方 法 进 行 问 题 的 分 析 与 求 解, 并 能 够 采 用 C C++ 或 Java 语 言 完 成 算 法 的 设 计 与 实 现 推 荐 教 材 : 严 蔚 敏 吴 伟 民 编 著, 数 据 结 构 (C 语 言 版 ), 清 华 大 学 出 版 社 阅 读 建 议 : 一 绪 论 1. 数 据 结 构 基 本 概 念 和 术 语 2. 算 法 和 算 法 分 析 时 间 复 杂 度 和 空 间 复 杂 度 二 线 性 表 1. 线 性 表 的 类 型 定 义 和 基 本 操 作 2. 线 性 表 的 顺 序 表 示 和 实 现 3. 线 性 表 的 链 式 表 示 和 实 现 3.1 线 性 链 表 3.2 循 环 链 表 3.3 双 向 链 表 4. 线 性 表 的 应 用 三 栈 和 队 列 1. 栈 和 队 列 的 基 本 概 念 2. 栈 和 队 列 的 顺 序 存 储 结 构 3. 栈 和 队 列 的 链 式 存 储 结 构 4. 栈 和 队 列 的 应 用 四 串 和 数 组 1. 串 的 模 式 匹 配 算 法 2. 数 组 的 顺 序 表 示 和 实 现 3. 特 殊 矩 阵 的 压 缩 存 储 五 树 与 二 叉 树 1. 树 的 定 义 和 基 本 概 念 2. 二 叉 树

2.1. 二 叉 树 的 定 义 2.2. 二 叉 树 的 性 质 2.3. 二 叉 树 的 存 储 结 构 2.3.1. 顺 序 存 储 结 构 2.3.2. 链 式 存 储 结 构 2.4 二 叉 树 的 遍 历 2.5 线 索 二 叉 树 的 基 本 概 念 和 构 造 3. 树 和 森 林 3.1. 树 的 存 储 结 构 3.2. 森 林 与 二 叉 树 的 转 换 3.3. 树 和 森 林 的 遍 历 4. 赫 夫 曼 树 及 其 应 用 六 图 1. 图 的 基 本 概 念 2. 图 的 存 储 及 基 本 操 作 2.1 邻 接 矩 阵 法 2.2 邻 接 表 法 3. 图 的 遍 历 3.1 深 度 优 先 搜 索 3.2 广 度 优 先 搜 索 4. 图 的 基 本 应 用 4.1 最 小 生 成 树 4.2 拓 扑 排 序 4.3 关 键 路 径 4.4 最 短 路 径 七 查 找 1. 静 态 查 找 表 1.1 顺 序 表 的 查 找 1.2 有 序 表 的 查 找 1.3 索 引 顺 序 表 的 查 找 2. 动 态 查 找 树 表 2.1 二 叉 排 序 树 2.2 B_ 树 和 B+ 树 3. 哈 希 表 3.1 哈 希 表 的 定 义 3.2 哈 希 函 数 的 构 造 方 法 3.3 处 理 冲 突 的 方 法 3.4 哈 希 表 的 查 找 及 其 分 析 4. 查 找 算 法 的 分 析 及 其 应 用 八 内 部 排 序 1. 排 序 的 基 本 概 念

2. 插 入 排 序 2.1 直 接 插 入 排 序 2.2 折 半 插 入 排 序 3. 快 速 排 序 4. 选 择 排 序 5. 归 并 排 序 6. 基 数 排 序 7. 各 种 内 部 排 序 方 法 的 比 较

操 作 系 统 课 程 说 明 推 荐 教 材 :[ 美 ] William Stallings 著, 操 作 系 统 精 髓 与 设 计 原 理 ( 第 六 版 ), 电 子 工 业 出 版 社, 2010 年 8 月 阅 读 建 议 : Chapter 1 Computer System Overview 1.1 Basic Elements 1.2 Processor Registers 1.3 Instruction Execution 1.4 Interrupts 1.5 The Memory Hierarchy 1.6 Cache Memory 1.7 I/O Communication Techniques Chapter 2 Operating System Overview 2.1 Operating System Objectives and Functions 2.2 The Evolution of Operating Systems 2.3 Major Achievements 2.4 Developments Leading to Modern Operating Systems 2.5 Not Required 2.6 Not Required 2.7 Not Required 2.8 Linux Chapter 3 Process Description and Control 3.1 What is a Process? 3.2 Process States 3.3 Process Description 3.4 Process Control 3.5 Execution of the Operating System Chapter 4 Threads, SMP, and Microkernels 4.1 Processes and Threads 4.2 Symmetric Multiprocessing (SMP) 4.3 Microkernels 4.4 Not Required 4.5 Not Required 4.6 Linux Process and Thread Management Chapter 5 Concurrency: Mutual Exclusion and Synchronization

5.1 Principles of Concurrency 5.2 Mutual Exclusion: Hardware Support 5.3 Semaphores 5.4 Monitors 5.5 Message Passing 5.6 Readers/Writers Problem Chapter 6 Concurrency: Deadlock and Starvation 6.1 Principles of Deadlock 6.2 Deadlock Prevention 6.3 Deadlock Avoidance 6.4 Deadlock Detection 6.5 Not Required 6.6 Dining Philosophers Problem 6.7 Not Required 6.8 Linux Kernel Concurrency Mechanisms Chapter 7 Memory Management 7.1 Memory Management Requirements 7.2 Memory Partitioning 7.3 Paging 7.4 Segmentation Chapter 8 Virtual Memory 8.1 Hardware and Control Structures 8.2 Operating System Software 8.3 Not Required 8.4 Linux Memory Management Chapter 9 Uniprocessor Scheduling 9.1 Types of Scheduling 9.2 Scheduling Algorithms Chapter 10 Multiprocessor and Real-Time Scheduling Not Required Chapter 11 I/O Management and Disk Scheduling 11.1 I/O Devices 11.2 Organization of the I/O Function 11.3 Operating System Design Issues 11.4 I/O Buffering 11.5 Disk Scheduling 11.6 Not Required 11.7 Not Required

11.8 Not Required 11.9 Linux I/O Chapter 12 File Management 12.1 Overview 12.2 File Organization and Access 12.3 File Directories 12.4 File Sharing 12.5 Record Blocking 12.6 Secondary Storage Management 12.7 File System Security 12.8 Not Required 12.9 Linux File Management

数 据 库 课 程 说 明 推 荐 教 材 : 王 珊 萨 师 煊 著, 数 据 库 系 统 概 论 ( 第 4 版 ), 高 等 教 育 出 版 社 阅 读 建 议 : 教 材 的 前 十 一 章, 其 中, 带 星 号 的 部 分 不 作 要 求

计 算 机 网 络 课 程 说 明 课 程 名 称 ( 中 文 / 英 文 ): 计 算 机 网 络 (Computer Network) 推 荐 教 材 : 书 名 :Computer Networks 5th edition 作 者 : 特 南 鲍 姆 韦 瑟 罗 尔 译 者 : 严 伟 潘 爱 民 出 版 社 : 清 华 大 学 出 版 社 出 版 日 期 : 2012 年 3 月 阅 读 建 议 : 1. 概 论 1.1 计 算 机 网 络 的 应 用 1.2 计 算 机 网 络 的 硬 件 组 成 1.3 计 算 机 网 络 软 件 概 论 1.4 计 算 机 网 络 的 参 考 模 型 2. 物 理 层 : 数 据 通 信 基 础 2.1 数 据 通 信 理 论 基 础 2.2 传 输 媒 体 2.3 通 信 卫 星 2.4 电 话 系 统 3. 数 据 链 路 层 3.1 数 据 链 路 层 的 设 计 3.2 检 错 与 纠 错 3.3 基 本 数 据 链 路 协 议 3.4 滑 动 窗 口 协 议 4. 介 质 访 问 控 制 子 层 4.1 信 道 分 配 问 题 4.2 多 路 访 问 协 议 4.3 以 太 网 4.4 数 据 链 路 层 的 交 换 5. 网 络 层 5.1 网 络 层 的 设 计 问 题 5.2 路 由 算 法 5.3 拥 塞 控 制 5.4 服 务 质 量 5.5 网 络 互 连 5.6 Internet 中 的 网 络 层

6. 传 输 层 6.1 传 输 服 务 6.2 传 输 协 议 要 素 6.3 Internet 传 输 协 议 :UDP 6.4 Internet 传 输 协 议 :TCP 7. 应 用 层 7.1 DNS 7.2 电 子 邮 件 7.3 WWW 技 术 7.4 多 媒 体 7.5 内 容 分 发

计 算 机 组 成 原 理 课 程 说 明 I 考 查 目 标 要 求 考 生 比 较 系 统 地 掌 握 计 算 机 组 成 基 础 课 程 的 基 本 概 念 基 本 原 理 和 基 本 方 法, 能 够 综 合 运 用 所 学 的 基 本 原 理 和 基 本 方 法 分 析 判 断 和 解 决 有 关 理 论 问 题 和 实 际 问 题 II 考 查 范 围 1. 理 解 单 处 理 器 计 算 机 系 统 中 各 部 件 的 内 部 工 作 原 理 组 成 结 构 以 及 相 互 连 接 方 式, 具 有 完 整 的 计 算 机 系 统 的 整 机 概 念 2. 理 解 计 算 机 系 统 层 次 化 结 构 概 念, 熟 悉 硬 件 与 软 件 之 间 的 界 面, 掌 握 指 令 集 体 系 结 构 的 基 本 知 识 和 基 本 实 现 方 法 3. 能 够 运 用 计 算 机 组 成 的 基 本 原 理 和 基 本 方 法, 对 有 关 计 算 机 硬 件 系 统 中 的 理 论 和 实 际 问 题 进 行 计 算 分 析, 并 能 对 一 些 基 本 部 件 进 行 简 单 设 计 推 荐 教 材 : 王 爱 英 著, 计 算 机 组 成 与 结 构, 清 华 大 学 出 版 社,2009 年 第 四 版 阅 读 建 议 : 一 计 算 机 系 统 概 论 ( 一 ) 计 算 机 的 语 言 一 般 计 算 机 的 解 题 过 程, 引 入 机 器 语 言 汇 编 语 言 高 级 语 言 的 概 念 ( 二 ) 计 算 机 的 硬 件 计 算 机 系 统 的 基 本 概 念, 组 成 总 线 计 算 机 的 工 作 过 程 ( 三 ) 计 算 机 系 统 的 层 次 结 构 虚 拟 机 的 概 念, 解 释 和 编 译 的 概 念, 计 算 机 的 分 层 概 念 ( 四 ) 电 子 计 算 机 的 发 展 历 史 计 算 机 的 发 展 和 4 代 的 概 念, 计 算 机 的 分 类 和 计 算 机 的 应 用 场 合 二 计 算 机 的 逻 辑 部 件 ( 一 ) 布 尔 代 数 ( 二 ) 逻 辑 函 数 化 简 1. 代 数 化 简 法 2. 卡 诺 图 化 简 法 ( 三 ) 计 算 机 中 常 用 的 组 合 电 路 1. 加 法 器 及 快 速 进 位 电 路 2. 算 术 逻 辑 单 元 ALU 的 功 能 和 结 构 3. 译 码 器 4. 数 据 选 择 器

( 四 ) 时 序 逻 辑 电 路 1. 触 发 器 2. 寄 存 器 和 移 位 寄 存 器 3. 计 数 器 三 运 算 方 法 和 运 算 部 件 ( 一 ) 数 据 的 表 示 方 法 和 转 换 1. 进 位 计 数 制 及 其 相 互 转 换 2. 真 值 和 机 器 数 3. BCD 码 4. 字 符 与 字 符 串 ( 二 ) 带 符 号 的 二 进 制 数 在 计 算 机 中 的 表 示 方 法 及 加 减 运 算 1. 原 码 反 码 补 码 的 表 示 方 法, 以 及 加 减 法 运 算 2. 加 减 法 运 算 的 溢 处 ( 三 ) 浮 点 数 的 表 示 阶 码 尾 数 规 格 化 等 概 念 ( 四 ) 二 进 制 乘 法 / 除 法 运 算 1. 定 点 一 位 乘 法 2. 定 点 二 位 乘 法 3. 定 点 除 法 运 算 ( 五 ) 校 验 码 1. 奇 偶 校 验 2. 海 明 校 验 码 四 主 存 储 器 ( 一 ) 主 存 储 器 分 类 ( 二 ) 主 存 储 器 的 主 要 技 术 指 标 ( 三 ) 主 存 储 器 的 基 本 操 作 ( 四 ) 读 / 写 存 储 器 (RAM) 1. SRAM 存 储 器 的 工 作 原 理 2. DRAM 存 储 器 的 工 作 原 理 ( 五 ) 非 易 失 性 半 导 体 存 储 器 ROM PROM EPROM EEPROM flash 的 工 作 原 理 ( 六 ) 半 导 体 存 储 器 的 组 成 与 控 制 位 扩 展 字 扩 展 字 位 扩 展 五 指 令 系 统 ( 一 ) 指 令 格 式 1. 指 令 的 基 本 格 式 2. 定 长 操 作 码 指 令 格 式 3. 扩 展 操 作 码 指 令 格 式

( 二 ) 寻 址 方 式 1. 有 效 地 址 的 概 念 2. 数 据 寻 址 和 指 令 寻 址 3. 常 见 寻 址 方 式 ( 三 ) 指 令 类 型 ( 四 ) 精 简 指 令 系 统 计 算 机 和 复 杂 指 令 系 统 计 算 机 CISC 和 RISC 的 基 本 概 念 六 中 央 处 理 机 (CPU) ( 一 ) 计 算 机 的 硬 件 系 统 一 般 计 算 机 的 加 电 启 动, 程 序 执 行 过 程 的 概 念 ( 二 ) 控 制 器 的 组 成 1. 控 制 器 的 功 能 2. 控 制 器 的 组 成 3. 指 令 的 执 行 过 程 ( 三 ) 微 程 序 控 制 计 算 机 的 基 本 工 作 原 理 1. 微 程 序 的 基 本 概 念 2. 实 现 微 程 序 控 制 的 基 本 原 理 ( 四 ) 微 程 序 设 计 技 术 1. 微 指 令 的 编 译 法 2. 微 程 序 流 的 控 制 3. 微 指 令 格 式 ( 五 ) 硬 布 线 控 制 的 计 算 机 1. 时 序 与 节 拍 2. 操 作 控 制 信 号 的 产 生 3. 控 制 器 的 组 成 4. 硬 布 线 控 制 逻 辑 设 计 中 的 若 干 问 题 5. 硬 布 线 控 制 与 微 程 序 控 制 比 较 七 存 储 系 统 ( 一 ) 存 储 系 统 的 层 次 结 构 ( 二 ) 高 速 缓 冲 存 储 器 (Cache) 1. Cache 存 储 器 工 作 原 理 2. Cache 存 储 器 组 织 ( 三 ) 虚 拟 存 储 器 1. 虚 拟 存 储 器 概 述 2. 页 式 虚 拟 存 储 器 3. 段 页 式 虚 拟 存 储 器 4. 虚 拟 存 储 器 工 作 的 全 过 程 ( 四 ) 相 联 存 储 器 ( 五 ) 存 储 保 护

八 辅 助 存 储 器 ( 一 ) 辅 助 存 储 器 的 总 类 和 技 术 指 标 ( 二 ) 磁 记 录 原 理 和 记 录 方 式 1. 磁 记 录 原 理 2. 磁 记 录 介 质 与 磁 头 3. 磁 记 录 方 式 ( 三 ) 硬 磁 盘 存 储 器 1. 硬 盘 存 储 器 的 种 类 及 其 基 本 结 构 2. 硬 盘 驱 动 器 和 硬 盘 控 制 器 九 输 入 / 输 出 (I/O) 设 备 ( 一 ) 外 部 设 备 概 述 ( 二 ) 输 入 设 备 键 盘 鼠 标 光 笔 操 纵 杆 触 摸 屏 等 输 入 设 备 的 一 般 性 原 理 ( 三 ) 输 出 设 备 显 示 器 字 符 显 示 器 图 形 显 示 器 图 像 显 示 器 阴 极 射 线 管 (CRT) 显 示 器 图 形 和 图 像 分 辨 率 和 灰 度 级 刷 新 和 帧 存 储 器 随 机 扫 描 和 光 栅 扫 描 等 概 念 ( 四 ) 输 出 设 备 打 印 机 点 阵 式 打 印 机 激 光 打 印 机 喷 墨 打 印 机 的 一 般 性 原 理 十 输 入 / 输 出 (I/O) 系 统 ( 一 ) 输 入 输 出 系 (I/O) 统 概 述 概 述 1. 输 入 输 出 设 备 的 编 址 和 设 备 控 制 器 的 基 本 功 能 2. I/O 设 备 的 控 制 方 式 ( 二 ) 程 序 中 断 输 入 输 出 方 式 1. 中 断 的 作 用 产 生 和 响 应 2. 中 断 处 理 3. 程 序 中 断 设 备 接 口 和 工 作 原 理 ( 三 )DMA 输 入 输 出 方 式 1.DMA 的 三 种 工 作 方 式 2.DMA 控 制 器 组 成 3.DMA 的 数 据 传 送 过 程 ( 四 ) 通 道 控 制 方 式 和 外 围 处 理 机 方 式 1.I/O 通 道 的 种 类 2. 通 道 型 I/O 处 理 机 和 外 围 处 理 机 ( 五 ) 总 线 结 构 1. 总 线 类 型 2. 总 线 组 成 3. 微 机 总 线