计算机考研指导全书

本书是计算机专业研究生入学考试四门主干课程的综合复习用书，内容分为数据结构篇、计算机组成原理篇、操作系统篇、计算机网络篇。全书严格按照近期新计算机考研大纲，对大纲所涉及的知识点进行集中梳理，精选名校历年考研真题，给出详细的解题思路，力求达到讲练结合、灵活掌握、举一反三的功效，并力求内容精炼、重点突出、深入浅出。同时，创新的“书本＋在线”的学习方式与网上答疑，可大大提高考生的复习效果，达到事半功倍的复习效率。

王道，本科毕业于中南大学，研究生毕业于哈尔滨工业大学，现为王道论坛主要负责人，曾出版图书多种。1、与机工社合作推出王道计算机考研系列教材。2、与中南大学出版社合作推出王道计算机考研系列教材。

第1篇数据结构
第1章绪论2
1.1基本概念和术语2
1.2算法和算法评价3
1.2.1算法3
1.2.2算法评价4
例题精析4
习题精选5
参考答案5
第2章线性表7
2.1线性表的定义和基本操作7
2.1.1线性表的定义7
2.1.2线性表的基本操作7
2.2线性表的顺序存储结构及实现8
2.2.1线性表的顺序存储8
2.2.2顺序表上基本操作的实现9
2.3线性表的链式存储结构及实现11
2.3.1单链表11
2.3.2双链表15
2.3.3循环链表16
2.3.4静态链表17
2.4顺序存储和链式存储的对比18
例题精析19
习题精选20
参考答案22
第3章栈、队列和数组30
3.1栈和队列的基本概念30
3.1.1栈的基本定义和运算30
3.1.2队列的基本定义和运算31
3.2栈的存储结构及其基本运算的实现31
3.2.1栈的顺序存储结构31
3.2.2栈的链式存储结构32
3.3队列的存储结构及其基本运算的实现33
3.3.1队列的顺序存储结构33
3.3.2队列的链式存储结构35
3.3.3双端队列35
3.4栈和队列的应用36
3.4.1栈在括号匹配中的应用36
3.4.2栈在表达式计算中的应用36
3.4.3栈在递归中的应用37
3.4.4队列在层次遍历中的应用37
3.4.5队列在计算机系统中的应用38
3.5特殊矩阵的压缩存储38
3.5.1对称矩阵的压缩存储38
3.5.2三角矩阵的压缩存储39
3.5.3三对角矩阵的压缩存储40
例题精析40
习题精选41
参考答案43
第4章树与二叉树48
4.1树的基本概念和性质48
4.2二叉树49
4.2.1二叉树的定义及其主要特征49
4.2.2二叉树的顺序存储结构和链式存储结构50
4.2.3二叉树的遍历51
4.2.4线索二叉树的基本概念和构造53
4.3树、森林55
4.3.1树的存储结构55
4.3.2树、森林和二叉树的转换56
4.3.3树和森林的遍历57
4.4树与二叉树的应用57
4.4.1二叉排序树57
4.4.2平衡二叉树60
4.4.3赫夫曼（Huffman）树和赫夫曼编码62
例题精析63
习题精选67
参考答案70
第5章图78
5.1图的基本概念78
5.2图的存储结构79
5.2.1邻接矩阵79
5.2.2邻接表80
5.2.3十字链表82
5.2.4邻接多重表83
5.3图的遍历84
5.3.1深度优先搜索84
5.3.2广度优先搜索85
5.4图的基本应用87
5.4.1最小生成树87
5.4.2最短路径89
5.4.3拓扑排序91
5.4.4关键路径93
例题精析94
习题精选96
参考答案99
第6章查找103
6.1基本概念103
6.2顺序查找104
6.2.1一般线性表的顺序查找104
6.2.2有序表的顺序查找105
6.3折半查找105
6.4B-树和B+树106
6.4.1B-树的概念106
6.4.2B-树的查找107
6.4.3B-树的插入108
6.4.4B-树的删除108
6.4.5B+树的基本概念109
6.5散列（Hash）表110
6.5.1散列表的基本概念110
6.5.2散列函数110
6.5.3处理冲突的方法111
6.5.4散列法性能分析112
例题精析112
习题精选114
参考答案115
第7章排序119
7.1排序的基本概念119
7.2插入排序120
7.2.1直接插入排序120
7.2.2折半插入排序120
7.2.3希尔排序121
7.3交换排序122
7.3.1冒泡排序122
7.3.2快速排序122
7.4选择排序124
7.4.1简单选择排序124
7.4.2堆排序124
7.5二路归并排序126
7.6基数排序127
7.7不同排序算法的比较128
7.8外部排序129
7.8.1外部排序的方法130
7.8.2多路平衡归并与败者树131
7.8.3置换-选择排序（生成初始归并段）132
7.8.4最佳归并树133
例题精析134
习题精选135
参考答案138
第2篇计算机组成原理
第1章计算机系统概论144
1.1计算机发展历程144
1.1.1计算机的发展144
1.1.2计算机的分类145
1.2计算机系统层次结构145
1.2.1计算机硬件的基本组成145
1.2.2计算机系统的层次结构146
1.2.3计算机软件的分类147
1.2.4计算机的工作过程148
1.3计算机性能指标149
1.3.1计算机的主要性能指标149
1.3.2几个专业术语的概念150
例题精析150
习题精选150
参考答案152
第2章数据的表示和运算154
2.1数制与编码154
2.1.1进位计数制及其相互转换154
2.1.2真值和机器数155
2.1.3BCD码155
2.1.4字符与字符串156
2.1.5校验码157
2.2定点数的表示和运算159
2.2.1数的机器码表示159
2.2.2定点数的表示161
2.2.3定点数的运算162
2.2.3强制类型转换165
2.3浮点数的表示和运算166
2.3.1浮点数的表示法166
2.3.2浮点数的加/减运算168
2.4算术逻辑单元（ALU）169
2.4.1串行加法器和并行加法器170
2.4.2算术逻辑单元的功能和结构172
例题精析174
习题精选175
参考答案178
第3章存储器系统的层次结构182
3.1存储器的分类182
3.1.1存储器的分类182
3.1.2存储器的性能指标183
3.2存储器的层次结构183
3.3半导体随机存取存储器184
3.3.1存储芯片的基本结构184
3.3.2SRAM存储器184
3.3.3DRAM存储器184
3.3.4存储器的读、写周期185
3.3.5SRAM和DRAM的比较186
3.4只读存储器186
3.5存储器与CPU的连接187
3.5.1连接原理187
3.5.2存储容量的扩展187
3.5.3存储芯片的地址分配和片选189
3.5.4存储器与CPU的连接189
3.6双口RAM和多模块存储器190
3.6.1双端口RAM190
3.6.2多模块存储器190
3.7高速缓冲存储器192
3.7.1程序访问的局部性原理192
3.7.2Cache的基本工作原理192
3.7.3Cache和主存的映射方式193
3.7.4Cache中主存块的替换算法194
3.7.5Cache写策略194
3.8虚拟存储器195
3.8.1基本概念195
3.8.2页式虚拟存储器195
3.8.3段式虚拟存储器196
3.8.4段页式虚拟存储器196
3.8.5TLB（快表）197
3.8.6虚拟存储器与Cache的比较197
例题精析197
习题精选200
参考答案204
第4章指令系统209
4.1指令格式209
4.1.1指令的基本格式209
4.1.2定长操作码指令格式210
4.1.3扩展操作码指令格式211
4.2指令的寻址方式211
4.2.1有效地址的概念211
4.2.2数据寻址和指令寻址211
4.3CISC和RISC的基本概念215
例题精析216
习题精选218
参考答案221
第5章中央处理器（CPU）224
5.1CPU的功能和基本结构224
5.1.1CPU的功能224
5.1.2CPU的基本结构224
5.2指令执行过程225
5.2.1指令的执行225
5.2.2指令周期226
5.2.3指令执行方案227
5.3数据通路的功能和基本结构227
5.3.1数据通路的功能227
5.3.2数据通路的基本结构228
5.4控制器的功能和工作原理229
5.4.1控制器的地位与结构229
5.4.2硬布线控制器230
5.4.3微程序控制器232
5.5指令流水线237
5.5.1指令流水线的基本概念237
5.5.2影响流水线的因素238
5.5.3流水线的分类239
5.5.4流水线的性能指标240
例题精析241
习题精选243
参考答案247
第6章总线252
6.1总线概述252
6.1.1总线的基本概念252
6.1.2总线的分类253
6.1.3总线的结构与性能指标253
6.2总线仲裁254
6.2.1集中仲裁方式254
6.2.2分布仲裁方式256
6.3总线操作和定时256
6.3.1数据的传输256
6.3.2同步定时方式256
6.3.3异步定时方式256
6.4总线标准257
例题精析258
习题精选258
参考答案260
第7章输入/输出（I/O）系统263
7.1I/O系统基本概念263
7.2外部设备264
7.2.1输入设备264
7.2.2输出设备264
7.2.3外存储器265
7.3I/O接口（I/O控制器）267
7.3.1I/O接口的功能267
7.3.2I/O接口的基本结构267
7.3.3I/O接口的类型268
7.3.4I/O端口及其编址268
7.4I/O方式268
7.4.1程序查询方式269
7.4.2程序中断方式269
7.4.3DMA方式272
例题精析274
习题精选276
参考答案278
第3篇操作系统
第1章操作系统概述283
1.1操作系统的概念、特征、功能和提供的服务283
1.1.1操作系统的基本概念283
1.1.2操作系统的特征283
1.1.3操作系统的功能284
1.2操作系统的发展与分类285
1.3操作系统的运行环境286
1.4操作系统的体系结构288
例题精析289
习题精选289
参考答案291
第2章进程管理293
2.1进程与线程293
2.1.1进程概念293
2.1.2进程的状态与转换294
2.1.3进程控制295
2.1.4进程组织296
2.1.5进程与程序的区别297
2.1.6进程通信297
2.1.7线程概念与多线程模型298
2.2处理器调度300
2.2.1调度的基本概念300
2.2.2调度时机、切换与过程301
2.2.3进程的调度方式302
2.2.4调度的基本准则302
2.2.5典型调度算法303
2.3进程同步305
2.3.1进程同步的基本概念305
2.3.2实现临界区互斥的基本方法306
2.3.3信号量309
2.3.4管程311
2.3.5经典同步问题311
2.4死锁316
2.4.1死锁的概念316
2.4.2死锁处理策略317
2.4.3死锁预防318
2.4.4死锁避免318
2.4.5死锁检测和解除320
例题精析321
习题精选325
参考答案329
第3章内存管理336
3.1内存管理基础336
3.1.1内存管理的概念336
3.1.2覆盖与交换339
3.1.3连续分配管理方式339
3.1.4非连续分配管理方式341
3.2虚拟内存管理348
3.2.1虚拟内存的基本概念348
3.2.2请求分页管理方式350
3.2.3页面置换算法351
3.2.4页面分配策略353
3.2.5抖动和工作集354
例题精析355
习题精选358
参考答案361
第4章文件管理367
4.1文件系统基础367
4.1.1文件概念367
4.1.2文件的逻辑结构368
4.1.3目录结构368
4.1.4文件共享371
4.1.5文件保护372
4.2文件系统实现373
4.2.1文件系统层次结构373
4.2.2目录实现373
4.2.3文件实现374
4.3磁盘组织与管理377
4.3.1磁盘的结构377
4.3.2磁盘调度算法378
4.3.3磁盘的管理381
例题精析382
习题精选383
参考答案387
第5章输入/输出（I/O）管理391
5.1I/O管理概述391
5.1.1I/O设备391
5.1.2I/O控制方式392
5.2I/O核心子系统395
5.2.1I/O层次结构395
5.2.2高速缓存与缓冲区395
5.2.3设备分配与回收397
5.2.4SPOOLing技术（假脱机技术）399
5.2.5出错处理399
例题精析400
习题精选401
参考答案402
第4篇计算机网络
第1章计算机网络体系结构406
1.1计算机网络概述406
1.1.1计算机网络的概念、组成与功能406
1.1.2计算机网络的分类407
1.1.3计算机网络的标准化及相关组织407
1.1.4计算机网络的性能指标407
1.2计算机网络体系结构与参考模型408
1.2.1计算机网络的分层结构408
1.2.2计算机网络协议、接口、服务等概念408
1.2.3ISO/OSI参考模型和TCP/IP模型409
例题精析411
习题精选411
参考答案412
第2章物理层415
2.1通信基础415
2.1.1物理层相关的基本概念415
2.1.2奈奎斯特定理与香农定理416
2.1.4编码与调制417
2.1.5电路交换、报文交换与分组交换418
2.1.6数据报与虚电路420
2.2传输介质421
2.2.1传输介质简介421
2.2.2物理层接口的特性422
2.3物理层设备422
2.3.1中继器422
2.3.2集线器（Hub）422
例题精析423
习题精选424
参考答案426
第3章数据链路层429
3.1数据链路层的功能429
3.2组帧430
3.3差错控制430
3.3.1检错编码430
3.3.2纠错编码431
3.4流量控制与可靠传输机制431
3.4.1流量控制、可靠传输与滑动窗口机制431
3.4.2单帧滑动窗口与停止―等待协议432
3.4.3多帧滑动窗口与后退N帧协议433
3.4.4多帧滑动窗口与选择重传协议433
3.5介质访问控制433
3.5.1信道划分介质访问控制433
3.5.2随机访问介质访问控制435
3.5.3轮询访问介质访问控制436
3.6局域网436
3.6.1局域网的基本概念与体系结构436
3.6.2以太网与IEEE802.3437
3.6.4令牌环网的基本原理441
3.7广域网441
3.7.1广域网的基本概念441
3.7.2PPP协议442
3.7.3HDLC协议443
3.8数据链路层设备444
3.8.1网桥的概念和基本原理444
3.8.2局域网交换机及其工作原理445
例题精析446
习题精选448
参考答案452
第4章网络层458
4.1网络层的功能458
4.1.1异构网络互连458
4.1.2路由选择与转发459
4.1.3拥塞控制459
4.2路由算法459
4.2.1静态路由与动态路由459
4.2.2距离向量路由算法460
4.2.3链路状态路由算法460
4.2.4层次路由460
4.3IPv4461
4.3.1IPv4分组461
4.3.2IPv4地址与网络地址转换NAT462
4.3.3子网划分与子网掩码、CIDR464
4.3.4ARP协议、DHCP协议与ICMP协议466
4.4IPv6468
4.4.1IPv6的主要特点468
4.4.2IPv6地址469
4.5路由协议470
4.5.1自治系统470
4.5.2域内路由与域间路由470
4.5.3内部网关协议：RIP协议470
4.5.4内部网关协议：OSPF协议471
4.5.5外部网关协议：BGP协议473
4.6IP组播474
4.6.1IP组播的概念474
4.6.2IP组播地址475
4.7网络层设备476
4.7.1路由器的组成和功能476
4.7.2路由表与路由转发477
例题精析478
习题精选481
参考答案485
第5章传输层490
5.1传输层提供的服务490
5.1.1传输层的功能490
5.1.2传输层的寻址与端口491
5.1.3无连接服务与面向连接服务492
5.2用户数据报协议UDP492
5.2.1UDP数据报493
5.2.2UDP校验493
5.3传输控制协议TCP494
5.3.1TCP报文段494
5.3.2TCP连接管理496
5.3.3TCP可靠传输498
5.3.4TCP流量控制与拥塞控制499
例题精析502
习题精选503
参考答案505
第6章应用层508
6.1网络应用模型508
6.1.1客户/服务器模型508
6.1.2P2P模型508
6.2DNS系统509
6.2.1层次域名空间509
6.2.2域名服务器509
6.2.3域名解析过程510
6.3文件传输协议FTP511
6.3.1FTP协议的工作原理511
6.3.2控制连接与数据连接511
6.4电子邮件512
6.4.1电子邮件系统的组成结构512
6.4.2电子邮件的格式与MIME513
6.4.3SMTP协议与POP3协议514
6.5万维网WWW514
6.5.1WWW的概念与组成结构514
6.5.2超文本传输协议HTTP515
例题精析517
习题精选518
参考答案520
参考文献522