全国硕士研究生入学统一考试计算机学科专业基础综合考前串讲

第1章 考试指南 1
1.1 考试题型分析 1
1.2 考试知识点分析 2
1.2.1 数据结构 2
1.2.2 计算机组成原理 3
1.2.3 操作系统 5
1.2.4 计算机网络 7
1.3 备考指南 8
1.3.1 专业课学习 9
1.3.2 学习效果检测 10
1.3.3 辅导和培训 10

第2章 线性表 12
2.1 考点归纳与考点分析 12
2.2 线性表的定义和基本操作★1◎2 13
2.3 线性表的顺序存储结构★2◎3 13
2.4 线性表的链式存储结构★2◎3 18
2.5 静态链表★2◎4 21
2.6 双向链表★3◎4 23
2.7 循环链表★3◎4 26

第3章 栈、队列和数组 27
3.1 考点归纳与考点分析 27
3.2 栈的基本概念★1◎4 28
3.3 栈的顺序存储结构★2◎3 29
3.4 栈的链式存储结构★3◎3 31
3.5 队列的基本概念★1◎3 31
3.6 队列的顺序存储结构★2◎4 32
3.7 队列的链式存储结构★3◎3 35
3.8 特殊矩阵的压缩存储★3◎2 36

第4章 树与二叉树 39
4.1 考点归纳与考点分析 39
4.2 树的概念★1◎4 40
4.3 二叉树★2◎4 41
4.4 树、森林★3◎3 44
4.5 树的应用★3◎3 47

第5章 图 49
5.1 考点归纳与考点分析 49
5.2 图的概念★1◎2 50
5.3 图的存储及基本操作★3◎2 52
5.4 图的遍历★3◎3 56
5.5 最小（代价）生成树★3◎4 61
5.6 最短路径★3◎4 64
5.7 拓扑排序★3◎3 66
5.8 关键路径★3◎4 67

第6章 查找 70
6.1 考点归纳与考点分析 70
6.2 查找的基本概念★1◎2 71
6.3 顺序查找法★2◎3 72
6.4 折半查找法★2◎3 73
6.5 二叉排序树★3◎4 75
6.6 平衡二叉树（AVL树）★3◎4 77
6.7 B-树★4◎3 79
6.8 哈希表及其查找★3◎4 82

第7章 排序 87
7.1 考点归纳与考点分析 87
7.2 排序的基本概念★1◎2 88
7.3 插入排序★2◎3 88
7.4 冒泡排序★2◎3 90
7.5 简单选择排序★2◎4 90
7.6 希尔排序★3◎4 91
7.7 快速排序★3◎4 91
7.8 堆排序★4◎4 93
7.9 二路归并排序★3◎4 95
7.10 基数排序★4◎3 96
7.11 各种内部排序算法的比较★4◎4 97

第8章 计算机系统概述 100
8.1 考点归纳与考点分析 100
8.2 计算机发展历程★1◎1 101
8.3 计算机系统层次结构★1◎2 102
8.4 计算机硬件的基本组成★2◎2 103
8.5 计算机软件的分类★2◎2 104
8.6 计算机的工作过程★2◎2 104
8.7 计算机性能指标★3◎2 104

第9章 数据的表示和运算 106
9.1 考点归纳与考点分析 106
9.2 进位计数制及其相互转换★4◎5 107
9.3 真值和机器数★3◎4 108
9.4 BCD码★3◎4 109
9.5 字符与字符串★3◎3 110
9.6 校验码★3◎4 110
9.7 定点数的表示★3◎4 111
9.8 定点数的运算★3◎4 111
9.9 浮点数的表示★3◎4 119
9.10 浮点数运算★3◎4 121
9.11 算术逻辑单元ALU★4◎5 123

第10章 存储器层次结构 124
10.1 考点归纳与考点分析 124
10.2 存储器的分类★1◎1 125
10.3 存储器的层次化结构★2◎4 125
10.4 半导体随机存取存储器★3◎4 126
10.5 只读存储器★2◎3 127
10.6 主存储器与CPU的连接★3◎3 127
10.7 双口RAM和多模块存储器★3◎4 127
10.8 高速缓冲存储器（Cache）★4◎5 128
10.9 虚拟存储器★4◎5 130

第11章 指令系统 134
11.1 考点归纳与考点分析 134
11.2 指令格式★4◎5 134
11.3 指令的寻址方式★4◎5 136
11.4 CISC和RISC的基本概念★3◎5 138

第12章 中央处理器 140
12.1 考点归纳与考点分析 140
12.2 CPU的功能和基本结构★2◎4 141
12.3 指令执行过程★3◎5 142
12.4 数据通路的功能和基本结构★3◎4 142
12.5 控制器的功能和工作原理★3◎4 142
12.6 指令流水线★4◎5 148

第13章 总线 149
13.1 考点归纳与考点分析 149
13.2 总线概述★3◎5 150
13.3 总线仲裁★4◎5 152
13.4 总线操作和定时★4◎5 153
13.5 总线标准★3◎3 154

第14章 输入/输出（I/O）系统 156
14.1 考点归纳与考点分析 156
14.2 I/O系统基本概念★2◎2 157
14.3 外部设备★2◎2 158
14.3.1 输入设备 158
14.3.2 输出设备 158
14.4 I/O接口（I/O控制器）★3◎3 164
14.4.1 I/O接口的功能 164
14.3.2 I/O接口的基本结构 164
14.3.3 I/O端口及其编址 165
14.5 I/O方式★4◎5 165
14.5.1 程序查询方式 165
14.5.2 中断方式 166
14.5.3 DMA方式 169
14.5.4 通道方式 172

第15章 操作系统概述 173
15.1 考点归纳与考点分析 173
15.2 操作系统的基本概念★1◎2 174
15.3 操作系统的发展与分类★1◎1 174
15.3.1 操作系统的发展 174
15.3.2 操作系统的分类 174
15.4 操作系统的类型和特点★2◎2 175
15.4.1 操作系统的类型 175
15.4.2 各类操作系统的主要特征 175
15.5 操作系统的特征和服务★2◎2 178
15.5.1 操作系统的特征 178
15.5.2 操作系统的服务 179
15.6 操作系统的功能★2◎2 179
15.7 操作系统的运行环境★1◎2 180
15.7.1 传统计算 180
15.7.2 基于Web的计算 180
15.7.3 嵌入式计算 180

第16章 进程管理 181
16.1 考点归纳与考点分析 181
16.2 进程与线程★2◎3 184
16.2.1 关于进程 184
16.2.2 进程的状态与转换 185
16.2.3 进程控制 186
16.2.4 进程组织 187
16.2.5 进程通信 188
16.2.6 线程概念与多线程模型 189
16.3 处理机调度★3◎3 191
16.3.1 调度的基本概念 191
16.3.2 调度时机、切换与过程 191
16.3.3 调度的基本准则 192
16.3.4 调度方式 193
16.4 进程同步★4◎4 194
16.4.1 基本概念和准则 194
16.4.2 实现临界区互斥的基本方法 195
16.4.3 信号量 198
16.4.4 管程 199
16.4.5 经典同步问题 202
16.5 死锁★3◎4 205
16.5.1 死锁的概念 205
16.5.2 死锁处理策略 205
16.5.3 死锁预防 206
16.5.4 死锁避免 206
16.5.5 死锁检测和解除 208

第17章 内存管理 209
17.1 考点归纳与考点分析 209
17.2 内存管理基础★2◎3 212
17.2.1 内存管理概念 212
17.2.2 交换与覆盖 214
17.2.3 连续分配管理方式 214
17.2.4 非连续分配管理方式 217
17.3 虚拟内存管理★4◎4 219
17.3.1 虚拟内存基本概念 219
17.3.2 请求分页管理方式 220
17.3.3 页面置换算法 221
17.3.4 页面分配策略 222
17.3.5 抖动 223
17.3.6 请求分段管理方式 225
17.3.7 请求段页式管理方式 226

第18章 文件管理 227
18.1 考点归纳与考点分析 227
18.2 文件系统基础★1◎1 229
18.2.1 文件概念 229
18.2.2 文件结构 230
18.2.3 目录结构 231
18.2.4 文件共享 233
18.2.5 文件保护 234
18.3 文件系统实现★2◎2 235
18.3.1 文件系统层次结构 235
18.3.2 目录实现 236
18.3.3 文件实现 237
18.4 磁盘组织与管理★3◎3 237
18.4.1 磁盘的结构 237
18.4.2 磁盘调度算法 238
18.4.3 磁盘的管理 239

第19章 输入/输出管理 241
19.1 考点归纳与考点分析 241
19.2 I/O管理概述★2◎3 243
19.2.1 I/O设备 243
19.2.2 I/O管理目标 245
19.2.3 I/O管理功能 245
19.2.4 I/O应用接口 245
19.2.5 I/O控制方式 247
19.3 I/O核心子系统★4◎4 250
19.3.1 I/O调度概念 250
19.3.2 高速缓存与缓冲区 251
19.3.3 设备分配与回收 252
19.3.4 假脱机技术（SPOOLing） 253
19.3.5 出错处理 254

第20章 计算机网络体系结构 255
20.1 考点归纳与考点分析 255
20.2 计算机网络的概念、组成与功能★1◎2 255
20.3 计算机网络的分类★1◎2 256
20.4 计算机网络与互联网的发展历史★1◎2 256
20.5 计算机网络的标准化工作及相关组织★1◎2 257
20.6 计算机网络分层结构★3◎4 258
20.7 计算机网络协议、接口、服务等概念★2◎3 259
20.8 ISO/OSI参考模型和TCP/IP模型★4◎5 260
20.8.1 ISO/OSI参考模型 260
20.8.2 TCP/IP参考模型 260
20.8.3 TCP/IP与OSI参考模型的对应关系 261
20.8.4 TCP/IP各层的功能与主要常见协议 261

第21章 物理层 262
21.1 考点归纳与考点分析 262
21.2 信道、信号、宽带、码元、波特、速率等基本概念★1◎3 262
21.3 奈奎斯特定理与香农定理★2◎2 263
21.4 信源与信宿★2◎2 264
21.5 编码与调制★3◎4 264
21.6 电路交换、报文交换与分组交换★4◎4 265
21.6.1 电路交换 265
21.6.2 报文交换 266
21.6.3 分组交换 266
21.7 数据报与虚电路★3◎3 267
21.8 双绞线、同轴电缆、光纤与无线传输介质★2◎3 267
21.8.1 双绞线 267
21.8.2 同轴电缆 268
21.8.3 光纤 268
21.8.4 无线传输介质 268
21.9 物理层接口的特性★2◎3 268
21.9.1 机械特性 269
21.9.2 电气特性 269
21.9.3 功能特性 269
21.9.4 规程特性 269
21.10 中继器与集线器★2◎3 269
21.10.1 中继器 269
21.10.2 集线器 270

第22章 数据链路层 271
22.1 考试大纲及考点分析 271
22.2 数据链路层的功能★2◎2 272
22.3 组帧★2◎2 272
22.4 差错控制★3◎4 273
22.5 流量控制与可靠传输机制★2◎3 274
22.6 介质访问控制★3◎4 275
22.7 局域网★2◎3 277
22.8 广域网★3◎1 279
22.9 数据链路层设备★2◎3 281

第23章 网络层 283
23.1 考点归纳与考点分析 283
23.2 网络层的功能★1◎3 283
23.3 路由算法★2◎2 284
23.4 IPv4★3◎4 285
23.4.1 A类地址 285
23.4.2 B类地址 285
23.4.3 C类地址 286
23.4.4 特殊地址形式 286
23.4.5 子网及掩码 286
23.5 IPv6★3◎3 288
23.5.1 IPv6地址分类 288
23.5.2 IPv6地址表示方法 289
23.5.3 IPv6地址表示时需要注意的问题 289
23.6 路由协议★2◎2 290
23.6.1 路由信息协议 291
23.6.2 开放最短路径优先协议 291
23.6.3 外部网关协议BGP 292

第24章 传输层 295
24.1 考点归纳及考点分析 295
24.2 传输层提供的服务★1◎2 295
24.2.1 传输层在协议层次中的位置 295
24.2.2 运输层的主要功能及协议数据单元 296
24.2.3 传输层两个协议 296
24.2.4 端口的概念和Socket地址 297
24.3 UDP协议★2◎3 297
24.3.1 UDP概述 297
24.3.2 UDP数据报格式 298
24.3.3 UDP的特点 298
24.4 TCP协议★3◎4 299
24.4.1 TCP概述 299
24.4.2 TCP的服务 299
24.4.3 TCP的可靠性 299
24.4.4 TCP的数据传输 300
24.4.5 TCP的拥塞控制 302
24.4.6 TCP差错控制 304
24.4.7 TCP的连接管理 304

第25章 应用层 306
25.1 考点归纳与考点分析 306
25.2 应用层协议原理★2◎2 307
25.3 DNS系统★2◎3 307
25.3.1 DNS概述 307
25.3.2 DNS提供的服务 308
25.3.3 Internet的域名结构 309
25.3.4 DNS服务器工作原理 310
25.3.5 DNS报文 312
25.4 FTP★2◎2 312
25.4.1 FTP概述 312
25.4.2 FTP工作原理 313
25.4.3 FTP的工作方式 314
25.4.4 FTP协议的优缺点 314
25.4.5 通过FTP传输文件 314
25.4.6 简单文件传输协议 315
25.5 远程终端协议（Telnet）★2◎2 316
25.5.1 Telnet概述 316
25.5.2 Telnet的工作过程 316
25.5.3 Telnet协议 316
25.6 电子邮件 317
25.6.1 电子邮件概述 317
25.6.2 电子邮件的传递过程 317
25.6.3 简单邮件传送协议 318
25.6.4 电子邮件的收信协议 319
25.6.5 电子邮件的格式 320
25.6.6 多用途因特网邮件扩展（MIME） 321
25.7 WWW 322
25.7.1 WWW概述 322
25.7.2 超文本链接、超媒体和超文本标记语言 323
25.7.3 统一资源定位符URL 325
25.7.4 超文本传送协议HTTP 325