第一部分 数据结构绪论 2
考试范围 2
知识点归纳 2
（一）基本概念和术语 2
（二）数据结构的定义 2
（三）抽象数据类型ADT 3
（四）算法定义及其特征 5
经典例题解析 6
题型练习 8
参考答案 11
一、线性表 12
考试范围 12
知识点归纳 12
（一）线性表的定义和基本操作 12
（二）线性表的实现 14
经典例题解析 22
题型练习 25
参考答案 28
二、栈、队列和数组 34
考试范围 34
知识点归纳 34
（一）栈和队列的基本概念 34
（二）栈和队列的顺序存储结构 35
（三）栈和队列的链式存储结构 38
（四）栈和队列的应用 41
（五）特殊矩阵的压缩存储 44
经典例题解析 53
题型练习 57
参考答案 60
三、树和二叉树 65
考试范围 65
知识点归纳 65
（一）树的基本概念 65
（二）二叉树 66
（三）树和森林 77
（四）树的应用 81
经典例题解析 89
题型练习 95
参考答案 103
四、图 109
考试范围 109
知识点归纳 109
（一）图的基本概念 109
（二）图的存储及基本操作 113
（三）图的遍历 115
（四）图的基本应用 116
经典例题解析 123
题型练习 130
参考答案 135
五、查找 141
考试范围 141
知识点归纳 141
（一）查找的基本概念 141
（二）顺序查找法 142
（三）折半查找法 143
（四）B—树及其基本操作、B＋树的基本概念 145
（五）散列（Hash）表 146
（六）查找算法的分析与应用 149
经典例题解析 150
题型练习 152
参考答案 157
六、内部排序 162
考试范围 162
知识点归纳 162
（一）排序的基本概念 162
（二）插入排序 163
（三）起泡排序 165
（四）简单选择排序 167
（五）希尔排序 168
（六）快速排序 169
（七）堆排序 171
（八）二路归并排序 173
（九）基数排序 174
（十）各种内部排序算法的比较 175
（十一）内部排序算法的应用 176
经典例题解析 177
题型练习 178
参考答案 181
第二部分 计算机组成原理一、计算机系统概论 186
考试范围 186
知识点归纳 186
（一）计算机的发展历程 186
（二）计算机系统层次结构 187
（三）计算机的主要性能指标 192
经典例题解析 194
题型练习 195
参考答案 196
二、数据的表示和运算 198
考试范围 198
知识点归纳 198
（一）数制与编码 198
（二）定点数的表示和运算 200
（三）浮点数的表示和运算 204
（四）算数逻辑单元ALU 205
经典例题解析 207
题型练习 209
参考答案 212
三、存储器层次结构 215
考试范围 215
知识点归纳 215
（一）存储器的分类 215
（二）存储系统的层次结构 216
（三）半导体主存储器 217
（四）只读存储器 218
（五）主存储器和CPU的连接 218
（六）双口RAM和多模块存储器 219
（七）高速缓冲存储器（Cache） 219
（八）虚拟存储器 221
经典例题解析 223
题型练习 226
参考答案 229
四、指令系统 230
考试范围 230
知识点归纳 230
（一）指令格式 230
（二）指令的寻址方式 231
（三）指令的功能和类型 233
（四）CISC和RISC的基本概念 234
经典例题解析 235
题型练习 240
参考答案 241
五、中央处理器（CPU） 242
考试范围 242
知识点归纳 242
（一）CPU的功能和基本结构 242
（二）指令执行的过程 244
（三）时序控制与指令序列间的衔接 245
（四）数据通路的基本功能和结构 245
（五）控制器的功能和工作原理 246
（六）指令流水线 247
经典例题解析 249
题型练习 258
参考答案 261
六、总线 264
考试范围 264
知识点归纳 264
（一）总线概述 264
（二）总线仲裁 266
（三）总线操作和定时 267
（四）总线标准 268
经典例题解析 268
题型练习 269
参考答案 271
七、输入输出系统 273
考试范围 273
知识点归纳 273
（一）I/O系统基本概念 273
（二）外部设备 274
（三）输入输出接口 275
（四）输入输出方式 276
经典例题解析 279
题型练习 281
参考答案 283
第三部分 计算机操作系统一、操作系统概述 286
考试范围 286
知识点归纳 286
（一）操作系统的概念、特征、功能和提供的服务 286
（二）操作系统的发展与分类 289
（三）操作系统的运行环境 291
经典例题解析 292
题型练习 294
参考答案 297
二、进程管理 300
考试范围 300
知识点归纳 301
（一）进程与线程 301
（二）处理机调度 307
（三）进程同步 310
（四）死锁 322
经典例题解析 326
题型练习 334
参考答案 339
三、内存管理 347
考试范围 347
知识点归纳 347
（一）内存管理基础 347
（二）虚拟内存管理 353
经典例题解析 356
题型练习 360
参考答案 365
四、文件管理 370
考试范围 370
知识点归纳 370
（一）文件系统基础 370
（二）文件系统实现 381
（三）磁盘组织与管理 384
经典例题解析 388
题型练习 389
参考答案 392
五、输入输出（I/O）管理 397
考试范围 397
知识点归纳 397
（一）I/O管理概述 397
（二）I/O核心子系统 401
经典例题解析 408
题型练习 410
参考答案 413
第四部分 计算机网络一、计算机网络体系结构 418
考试范围 418
知识点归纳 418
（一）计算机网络概述 418
（二）计算机网络体系结构与参考模型 419
经典例题解析 420
题型练习 423
参考答案 424
二、物理层 427
考试范围 427
知识点归纳 427
（一）通信基础 427
（二）传输介质 430
（三）物理层设备 430
经典例题解析 431
题型练习 435
参考答案 437
三、数据链路层 441
考试范围 441
知识点归纳 442
（一）数据链路层的功能 442
（二）组帧 442
（三）差错控制 442
（四）流量控制与可靠传输机制 443
（五）介质访问控制 444
（六）局域网 447
（七）广域网 448
（八）数据链路层设备 450
经典例题解析 451
题型练习 456
参考答案 458
四、网络层 464
考试范围 464
知识点归纳 465
（一）网络层的功能 465
（二）路由算法 467
（三）IP4 468
（四）IP6 471
（五）路由协议 472
（六）IP组播 474
（七）移动IP 475
（八）网络层设备 476
经典例题解析 476
题型练习 485
参考答案 488
五、传输层 492
考试范围 492
知识点归纳 492
（一）传输层提供的服务 492
（二）UDP协议 493
（三）TCP协议 495
经典例题解析 498
题型练习 504
参考答案 506
六、应用层 509
考试范围 509
知识点归纳 509
（一）网络应用模型 509
（二）DNS系统 511
（三）文件传送协议FTP 514
（四）电子邮件 515
（五）万维网WWW 517
经典例题解析 520
题型练习 523
参考答案 525
附录2009年全国硕士研究生入学统一考试试题 528
2009年全国硕士研究生入学统一考试试题参考答案 535