印次：1-1

印刷日期：2009-9-30

《全国硕士研究生入学统一考试计算机学科专业基础综合（2010年版）》是专门针对计算机专业研究生入学考试的特点和需求量身打造的，书中融合了编者多年的教学辅导经验，完全针对考研大纲的要求，知识点覆盖全面，文字通俗易懂，简洁精炼，是複习备考不可缺少的??白柿稀?br>从去年全国计算机专业课统考以来，市面上出现了一些有关专业课统考的複习用书，但并非特别适合考生使用，大部分辅导用书由于编写时间极短，覆盖知识点不全，难易程度控制不到位，不仅没能起到总结归纳的作用，反而浪费考生的複习时间，影响複习效果。

本书在编写过程中，注重吸取目前市面上专业複习用书出现的一些问题，特别针对当前国内大学生学习水平和複习时间，给出考生複习计算机专业课的目标、考点精解、例题精析和习题、参考答案等。使得本书无论是在知识面的覆盖上，还是在题目的难易程度上都儘量与考试一致。使考生高效率的複习知识点，提高对知识的认识水平，总结和归纳套用技巧。因此，学生完全可以放心选择本书作为计算机专业的複习全书。

目录

第1部分数据结构

第1章线性表············································2

1.1複习提示··················································2

1.1.1複习目标和要求·································2

1.1.2命题方向提示·····································3

1.2知识点精讲···············································3

1.2.1数据结构的基本概念和线性结构······3

1.2.2顺序表的类型和定义·························3

1.2.3线性表的顺序表示和实现··················4

1.2.4线性表的链式表示和实现··················6

1.2.5递归概念及算法实现·························8

1.3例题精析··················································8

1.4习题························································15

1.5习题解答················································18

第2章栈、伫列和数组·····························21

2.1複习提示················································21

2.1.1複习目标和要求·······························21

2.1.2命题方向提示···································22

2.2知识点精讲·············································22

2.2.1栈和伫列的基本概念·······················22

2.2.2顺序栈和链栈及其套用···················23

2.2.3链队、顺序队和循环伫列················27

2.2.4对称矩阵···········································29

2.2.5特殊矩阵的压缩存储·······················29

2.3例题精析················································31

2.4习题························································37

2.5习题答案················································40

第3章树与二叉树····································45

3.1複习提示················································45

3.1.1複习目标和要求·······························45

3.1.2命题方向提示···································46

3.2知识点精讲·············································46

3.2.1树和二叉树的定义和主要特徵········46

3.2.2二叉树的顺序存储结构

和链式存储结构································48

3.2.3二叉树的遍历····································49

3.2.4线索二叉树的基本概念和构造········50

3.2.5排序二叉树和平衡二叉树················53

3.2.6树的存储结构和森林························53

3.2.7树和森林的遍历································55

3.2.8树的套用：哈夫曼树

和哈夫曼编码···································56

3.3例题精析················································58

3.4习题························································65

3.5习题答案·??69

第4章图···················································78

4.1複习提示················································78

4.1.1複习目标和要求································78

4.1.2命题方向提示····································79

4.2知识点精讲············································79

4.2.1图的概念和基本术语························79

4.2.2图的存储结构和操作························80

4.2.3图的遍历············································82

4.2.4最小生成树和生成森林····················83

4.2.5最短路径·································??4

4.2.6拓扑排序············································85

4.2.7关键路径············································86

4.3例题精析················································87

4.4习题························································93

4.5习题答案················································96

第5章查找·············································100

5.1複习提示···············································100

5.1.1複习目标和要求······························100

5.1.2命题方向提示··································101

5.2知识点精讲··············01

目录

VI

5.2.1查找的基本概念·····························101

5.2.2顺序查找法·····································102

5.2.3折半查找法·····································103

5.2.4动态查找法·····································103

5.2.5B-树和B+树···································106

5.2.6哈希表·············································107

5.3例题精析··············································110

5.4习题······················································114

5.5习题答案··············································116

第6章内部排序······································120

6.1複习提示··············································120

6.1.1複习目标和要求·····························120

6.1.2命题方向提示·································121

6.2知识点精讲···········································121

6.2.1排序的基本概念······························121

6.2.2插入排序··········································122

6.2.3交换排序··········································123

6.2.4选择排序··········································124

6.2.5归併排序··········································127

6.2.6基数排序································?ぁぁぁぁぁぁぁぁぁ?28

6.2.7对各种排序算法的比较··················129

6.3例题精析···············································130

6.4习题·······················································133

6.5习题答案···············································137

第2部分计算机组成原理

第1章计算机系统概述···························142

1.1複习提示··············································142

1.1.1複习目标和要求·····························142

1.1.2命题方向提示·································143

1.2知识点精讲···········································143

1.2.1计算机的发展历程·························143

1.2.2计算机硬1.2.3计算机软体及程式语言·················144

1.2.4计算机系统的层次结构·················145

1.2.5计算机的工作过程·························146

1.2.6计算机性能指标·····························146

1.3例题精析··············································147

1.4习题······················································147

1.5习题答案··············································149

第2章数据的表示与运算·······················150

2.1複习提示··············································150

2.1.1複习目标和要求·····························150

2.1.2命题方向提示2.2知识点精讲···········································151

2.2.1进位计数制及其相互转换··············151

2.2.2真值和机器数·································152

2.2.3BCD码············································152

2.2.4字元与字元串表示·························152

2.2.5校验码·············································153

2.2.6数的表示·········································153

2.2.7定点数的表示·································154

2.2.8定点数的运算·································156

2.2.9浮点数的表示·································160

2.2.10浮点数的加/减运算····················161

2.2.11串?屑臃ㄆ骱筒⑿屑臃ㄆ鳌ぁぁぁぁぁ?162

2.3例题精析··············································163

2.4习题······················································169

2.5习题答案··············································177

第3章存储器层次结构···························189

3.1複习提示··············································189

3.1.1複习目标和要求·····························189

3.1.2命题方向提示·································190

3.2知识点精讲··········································190

3.2.1存储器的分类·································190

3.2.2存储器的层次化结构······················190

3.2.3半导体?婊?嫒〈娲Ⅰ?191

3.2.4只读存储器·····································191

3.2.5主存储器与CPU的连线················191

3.2.6双口RAM·······································192

3.2.7多模组交叉存储器·························192

3.2.8程式访问的局部性·························193

目录

VII

3.2.9Cache的基本工作原理··················193

3.2.10Cache和主存之间的映射方式·····193

3.2.11Cache中主存块的替换算法·········195

3.2.12Cache写策略································195

3.2.13虚拟存储器的基本概念···············196

3.2.14页式虚拟存储器···························196

3.2.15段式虚拟存储器···························196

3.2.16段页式虚拟存储器3.2.17TLB（快表）································198

3.3例题精析··············································198

3.4习题······················································207

3.5习题答案··············································213

第4章指令系统······································222

4.1複习提示··············································222

4.1.1複习目标和要求·····························222

4.1.2命题方向提示·································223

4.2知识点精讲···········································223

4.2.1指令的基本格式·····························223

4.2.2定长操作码指令格式·····················224

4.2.3扩展操作码指令格式·····················224

4.2.4有效地址的概念·····························224

4.2.5数据定址和指令定址·····················224

4.2.6常见定址方式·································224

4.2.7CISC和RISC的基本概念·············228

4.3例题精析··············································229

4.4习题······················································236

4.5习题答案··············································243

第5章中央处理器··································250

5.1複习提示··············································250

5.1.1複习目标和要求?250

5.1.2命题方向提示·································251

5.2知识点精讲···········································251

5.2.1CPU的功能和基本结构·················251

5.2.2指令执行过程·································252

5.2.3数据通路的功能和基本结构··········253

5.2.4控制器的功能和工作原理··············253

5.2.5微操作命令的分析·························254

5.2.6多级时序系统·································255

5.2.7控制方式·········································255

5.2.8硬布线控制器·································256

5.2.9微程式控制器·································257

5.2.10指令流水线的基本概念················259

5.2.11指令流水线中的相关问题

及其解方案····································261

5.2.12超标量和动态流水线的基本概念··263

5.3例题精析··············································264

5.4习题······················································270

5.5参考答案··············································280

第6章汇流排·············································289

6.1複习提示··············································289

6.1.1複习目标和要求·····························289

6.1.2複习方向提示·································290

6.2知识点精讲··········································290

6.2.1汇流排的基本概念·····························290

6.2.2汇流排的分类·····································290

6.2.3汇流排的组成及性能指标··················290

6.2.4集中式仲裁方式·····························291

6.2.5分布仲裁方式·································292

6.2.6汇流排操作和定时·····························292

6.2.7汇流排标準·········································293

6.3例题精析··············································293

6.4习题······················································296

6.5参考答案··············································298

第7章输入输出系统·······························301

7.1複习提示··············································301

7.1.1複习目标和要求·····························301

7.1.2命题方向提示·································302

7.2知识点精讲··········································302

7.2.1I/O系统基本概念···························302

7.2.2输入设备：键盘、滑鼠··················302

7.2.3输出设备：显示器、印表机··········303

7.2.4外存储器：硬碟存储器、

磁碟阵列、光碟存储器·················305

7.2.5I/O接口的功能和基本结构···········307

7.2.6I/O连线埠及其编址···························307

7.2.7程式查询方式·································308

7.2.8程式中断方式·································309

7.2.9DMA控制器···································310

目录

VIII

7.3例题精析··············································311

7.4习题······················································315

7.5参考答案··············································320

第3部分作业系统

第1章作业系统概述······························326

1.1複习提示··············································326

1.1.1複习目标和要求·····························326

1.1.2命题方向提示·································327

1.2知识点精讲···········································327

1.2.1作业系统的基本概念和特徵··········327

1.2.2作业系统的目标·····························327

1.2.3作业系统的作用·····························328

1.2.4作业系统的发展过程·····················328

1.2.5作业系统的基本特徵·····················330

1.2.6作业系统的主要功能·····················330

1.2.7OS结构设计···································332

1.3例题精析··············································333

1.4习题······················································334

1.5习题答案··············································336

第2章进程管理与处理器调度················337

2.1複习提示··············································338

2.1.1複习目标和要求·····························338

2.1.2命题方向提示·································338

2.2知识点详解···········································338

2.2.1进程的基本概念和特点·················338

2.2.2进程的状态与转换·························339

2.2.3进程的组成·····································340

2.2.4进程通信·········································341

2.2.5执行绪基本概念·································342

2.2.6处理器调度的基本概念和分类······342

2.2.7进程调度的调度方式

和调度的基本準则························342

2.2.8几种典型的调度算法·····················343

2.2.9进程同步和互斥的基本概念··········345

2.2.10实现临界区互斥的基本方法········345

2.2.11信号量机制及管程的引入············348

2.2.12经典同步问题分析·······················349

2.2.13死锁的基本概念

和四个必要条件······················352

2.2.14死锁的处理策略和死锁预防········352

2.2.15死锁避免、系统安全

状态以及银行家算法··············353

2.2.16死锁检测与解除···························354

2.3例题解析··············································354

2.4习题······················································364

2.5习题解答··············································369

第3章记忆体管理······································377

3.1複习提示··············································377

3.1.1複习目标和要求·····························377

3.1.2命题方向提示·································378

3.2知识点详解··········································378

3.2.1记忆体管理的基本概念······················378

3.2.2交换与覆盖思想·····························379

3.2.3连续分配管理方式·························380

3.2.4非连续分配方式·····························381

3.2.5虚拟记忆体的基本概念

和局部性原理································384

3.2.6几种经典的页面置换算法··············385

3.3例题精析··············································386

3.4习题······················································390

3.5习题答案··············································394

第4章档案管理系统??97

4.1複习提示··············································397

4.1.1複习目标和要求·····························397

4.1.2命题方向提示·································398

4.2知识点详解··········································398

4.2.1档案概念和分类·····························398

4.2.2档案逻辑结构和物理结构··············400

4.2.3目录档案和目录结构······················402

4.2.4档案共享动机及其方式··················403

4.2.5档案存取控制（档案保护）··········403

4.2.6磁碟结构和磁碟调度算法··············404

4.3例题精选··············································405

目录

IX

4.4习题·················??409

4.5习题解答··············································411

第5章输入输出管理······························413

5.1複习提示··············································413

5.1.1複习目标和要求·····························413

5.1.2命题方向提示·································414

5.2知识点详解···········································414

5.2.1I/O系统概述和I/O设备的分类····414

5.2.2设备控制器I/O通道······················415

5.2.3I/O控制方式···································416

5.2.4缓冲管理和分类·····························418

5.2.5I/O设备分配方式···················?ぁぁぁぁぁぁぁ?420

5.2.6假脱机技术·····································421

5.2.7磁碟出错处理·································421

5.3例题精析··············································422

5.4习题······················································425

5.5习题解答··············································428

第4部分计算机网路

第1章计算机网路体系结构···················432

1.1複习提示··············································432

1.1.1複习目标和要求·····························432

1.1.2命题方向提示·································433

1.2知识点精讲···········································433

1.2.1计算机网路的概念组成和功能······433

1.2.2计算机网路的分类和拓扑结构······434

1.2.3计算机网路与网际网路的发展历史··435

1.2.4计算机网路的标準化

工作及其相关组织··························435

1.2.5计算机网路分层结构和

协定、接口等概念··························435

1.2.6ISO/OSI参考模型··························436

1.2.7TCP/IP模型····································437

1.2.8OSI参考模型与

TCP/IP参考模型的比较·················438

1.3例题精析··············································439

1.4习题······················································442

1.5习题答案··············································443

第2章物理层······························??45

2.1複习提示··············································445

2.1.1複习目标和要求·····························445

2.1.2命题方向提示·································446

2.2知识点精讲···········································446

2.2.1信道、信号、宽频、码元、

波特、速率等基本概念·················446

2.2.2奈奎斯特定理与香农定理··············448

2.2.3编码与调製·····································449

2.2.4电路交换、报文交换与分组交换··450

2.2.5数据报与虚电路·····························452

2.2.6双绞线、同轴电缆、

光纤与无线传输介质······················452

2.2.7物理层接口的特性·························454

2.2.8中继器、集线器·····························454

2.3例题精析··············································455

2.4习题······················································458

2.5习题答案··············································460

第3章数据链路层··································463

3.1複习提示··············································464

3.1.1複习目标和要求·····························464

3.1.2命题方向提示·································464

3.2知识点精讲··········································464

3.2.1数据链路层的基本概念··················464

3.2.2差错控制机制、检错编码

和纠错编码······································466

3.2.3流量控制与可靠性传输机制··········469

3.2.4信道划分介质访问控制

（多路复用技术）··························471

3.2.5介质访问控制方法·························472

3.2.6区域网路·············································474

3.2.7数链层设备·····································478

3.2.8数据链路层协定·····························480

3.3例题精析··············································483

3.4习题······················································488

目录

X

3.5习题答案··············································492

第4章网路层·········································496

4.1複习提示··············································497

4.1.1複习目标和要求·····························497

4.1.2命题方向提示·································497

4.2知识点精讲···········································497

4.2.1网路层的功能·································497

4.2.2路由算法的基本要求

和静态路由、动态路由··················498

4.2.3距离-向量路由算法、链路

状态路由算法和层次路由··············498

4.2.4IPv4地址和IP协定·······················499

4.2.5子网划分与子网掩码·····················503

4.2.6ARP协定、DHCP协定、

ICMP协定·······································504

4.2.7IPv6主要特点与IPv6地址···········506

4.2.8自治系统、域内路由与域间路由··506

4.2.9RIP路由信息协定、OSPF路由

协定、BGP路由协定·····················506

4.2.10组播的基本概念···························508

4.2.11网路层设备···································509

4.2.12移动IP的概念和通信过程··········509

4.3例题精析··············································509

4.3习题······················································514

4.5习题答案··············································518

第5章传输层·········································524

5.1複习提示··············································524

5.1.1複习目标和要求·····························524

5.1.2命题方向提示·································525

5.2知识点精讲··········································525

5.2.1传输层的功能·································525

5.2.2定址与连线埠·····································526

5.2.3无连线服务与面向连线服务··········526

5.2.4UDP协定········································526

5.2.5TCP段、TCP连线管理·················528

5.3例题精析··············································534

5.4习题······················································536

5.5习题答案··············································537

第6章套用层·········································540

6.1複习提示··············································540

6.1.1複习目标和要求·····························540

6.1.2命题方向提示·································541

6.2知识点精讲··········································541

6.2.1客户/伺服器模型与P2P模型········541

6.2.2层次域名空间和域名解析··············541

6.2.3FTP协定的工作原理······················543

6.2.4电子邮件系统·································544

6.2.5WWW的概念与组成结构

和HTTP协定································546

6.3例题精析··············································548

6.4习题······················································551

6.4习题答案··············································552

第5部分模拟试题

模拟试题1·················································556

模拟试题2·················································563

模拟试题3··················································572

模拟试题4··················································579

附录

附录12009全国计算机专业统考试题及答案评析·····························································588

附录2计算机学科专业基础综合考试大纲（2010版）······················································599