2013全国硕士研究生入学统一考试 计算机专业基础综合考试大纲解析PDF电子书下载

第一部分 数据结构 2

第1章 线性表 2

1.1考纲解读 2

1.2知识归纳 2

一、基本概念 2

二、线性表 3

三、顺序表 3

四、链表 5

1.3解题指导 8

一、基本概念 8

二、顺序表的存储、操作 8

三、动态链表的操作及头结点 9

四、双向链表 11

五、静态链表 12

六、插入和删除结点的时间复杂度 13

1.4习题 13

第2章 栈、队列和数组 16

2.1考纲解读 16

2.2知识归纳 16

一、基本概念 16

二、栈和队列的存储结构 18

三、矩阵的存储 20

四、栈和队列的基本操作 23

五、栈和队列的应用 24

2.3解题指导 24

一、出栈和出队顺序问题 24

二、循环队列操作细节问题 25

三、多维数组线性化存储问题 26

四、顺序栈和顺序队列的空间需求问题 26

五、递归程序的非递归化 27

六、栈和队列的应用 27

2.4习题 29

第3章 树和二叉树 31

3.1考纲解读 31

3.2知识归纳 31

一、基本概念 31

二、二叉树的性质 33

三、二叉树的存储结构 33

四、二叉树的遍历 34

五、线索二叉树 35

六、二叉排序树 36

七、平衡二叉树 36

八、哈夫曼树 36

九、树和森林 37

3.3解题指导 41

一、基本概念 41

二、二叉树性质 41

三、二叉树遍历 42

四、线索二叉树 44

五、哈夫曼树的构造及应用 45

六、二叉排序树 45

七、平衡二叉树 46

八、树、森林与二叉树的相互转化 47

3.4习题 48

第4章 图 52

4.1考纲解读 52

4.2知识归纳 52

一、基本概念 52

二、图的存储结构 54

三、图的遍历 55

四、图的应用 56

4.3解题指导 60

一、基本概念 60

二、图的存储结构 61

三、图的遍历 62

四、最小生成树的生成 63

五、拓扑排序 63

六、关键路径 64

七、最短路径 65

4.4习题 66

第5章 查找 69

5.1考纲解读 69

5.2知识归纳 69

一、基本概念 69

二、静态查找表 70

三、B-树和B+树 72

四、哈希表 75

5.3解题指导 78

一、基本概念 78

二、折半查找的查找过程及查找效率 79

三、B-树结点的分裂与合并 79

四、哈希表的构建 81

五、哈希表的查找过程及性能分析 81

5.4习题 82

第6章 内部排序 85

6.1考纲解读 85

6.2知识归纳 85

一、基本概念 85

二、简单排序 86

三、快速排序 89

四、堆排序 92

五、希尔排序 94

六、归并排序 95

七、基数排序 96

八、各种排序方法比较 99

6.3解题指导 99

一、基本概念 99

二、各种排序方法的排序过程 100

三、各种排序方法的效率分析和比较 101

四、各种排序方法的稳定性 101

五、排序方法的应用 102

6.4习题 104

模拟题 107

模拟题一 107

模拟题二 108

参考答案 110

算法总结 124

第二部分 计算机组成原理 126

第1章 概述 126

1.1考纲解读 126

1.2知识归纳 126

一、基本概念 126

二、计算机的发展历程 127

三、计算机系统的硬件组成 127

四、计算机系统的软件 128

五、指令的执行过程 128

六、计算机系统的层次结构 128

七、计算机系统的性能指标 129

1.3解题指导 129

一、基本概念 129

二、计算机系统硬件组成及功能 129

三、冯·诺依曼计算机的特点 129

四、计算机系统的层次结构 130

五、计算机的软件系统 130

六、计算机的性能指标 130

1.4习题 131

第2章 运算器 133

2.1考纲解读 133

2.2知识归纳 133

一、重要概念 134

二、数的表示 134

2.3解题指导 149

一、计算结果分析 149

二、运算原理及实现 149

2.4习题 150

第3章 主存储器 152

3.1考纲解读 152

3.2知识归纳 153

一、基本概念 153

二、存储器的分类 154

三、存储器的层次化结构 155

四、半导体存储器 155

五、主存储器与CPU的连接与控制 155

六、双口RAM和多模块存储器 157

七、高速缓冲存储器（Cache） 158

八、虚拟存储器 160

3.3解题指导 162

一、基本概念 162

二、存储器的编址单位和地址范围的计算 163

三、半导体存储器与CPU的连接 164

四、动态RAM的刷新 166

五、Cache的地址映射规则 168

六、Cache命中率的计算 168

七、虚拟存储器的工作原理和虚实地址的转换 170

八、虚拟存储器的页面替换算法 171

3.4习题 171

第4章 指令系统 175

4.1考纲解读 175

4.2知识归纳 175

一、指令格式 175

二、寻址方式 176

三、操作数的个数 177

四、CISC和RISC的基本概念 178

4.3解题指导 178

一、指令系统设计 178

二、寻址方式 179

4.4习题 180

第5章 中央处理器 182

5.1考纲解读 182

5.2知识归纳 182

一、重要概念 183

二、CPU组成 184

三、CPU功能 184

四、模型机概念 184

五、指令周期 185

六、CPU控制方式 191

七、微程序控制器 193

八、硬布线控制器 193

5.3解题指导 194

一、控制器和模型机概念 194

二、数据通路和指令周期 195

三、设计题 195

5.4习题 197

第6章 总线 202

6.1考纲解读 202

6.2知识归纳 202

一、基本概念 203

二、总线的分类 203

三、总线的组成和性能指标 203

四、总线的连接结构 204

五、总线的特性 204

六、总线的仲裁方式 204

七、总线的一次信息传送过程 206

八、总线的定时方式 206

九、常见系统总线标准 206

十、常见设备总线标准 207

6.3解题指导 207

一、基本概念 207

二、总线仲裁方法 207

三、总线定时 208

四、总线带宽的计算 208

五、常见总线标准及特点 209

6.4习题 209

第7章 输入/输出系统 211

7.1考纲解读 211

7.2知识归纳 211

7.3解题指导 220

一、基本概念 220

二、主要外部设备的工作原理 221

三、外部存储器的工作原理 221

四、外部设备参数计算 221

五、不同I/O方式的工作原理 223

六、中断处理过程的分析和计算 224

7.4习题 227

模拟题 230

模拟题一 230

模拟题二 231

参考答案 233

第三部分 操作系统 248

第1章 操作系统概述 248

1.1考纲解读 248

1.2知识归纳 248

一、操作系统的概念、目标和作用 249

二、操作系统的基本特征 249

三、操作系统的主要功能 249

四、操作系统的发展过程与分类 249

五、操作系统的结构设计 250

六、操作系统提供的服务 250

七、操作系统的运行环境 251

1.3解题指导 251

1.4习题 251

第2章 进程管理 253

2.1考纲解读 253

2.2知识归纳 253

一、进程的基本概念 253

二、进程控制 256

三、进程同步 256

四、进程通信 257

五、线程 258

2.3解题指导 258

一、进程及进程状态转换 258

二、判断进程同步问题算法是否正确 260

三、对信号量概念的理解 263

四、利用信号量实现前趋关系 264

五、利用信号量解决进程同步问题 265

2.4习题 275

第3章 处理机调度与死锁 278

3.1考纲解读 278

3.2知识归纳 278

一、处理机调度的基本概念 278

二、调度算法 280

三、产生死锁的原因和必要条件 283

四、预防死锁的方法 284

五、死锁的检测与解除 284

3.3解题指导 284

一、常见调度算法的比较 284

二、作业调度 285

三、死锁及其相关概念 288

四、采用银行家算法实施死锁避免策略 289

五、利用死锁定理检测死锁 291

3.4习题 292

第4章 存储器管理 294

4.1考纲解读 294

4.2知识归纳 294

一、程序的装入和链接 294

二、连续分配方式 296

三、基本分页存储管理方式 297

四、基本分段存储管理方式 299

五、段页式存储管理方式 301

六、虚拟存储管理 301

七、请求分页存储管理方式 302

八、页面置换算法 304

九、请求分段存储管理方式 305

4.3解题指导 306

一、基本概念 306

二、逻辑地址到物理地址的转换 309

三、动态分区分配算法 311

四、页面置换 311

4.4习题 314

第5章 设备管理 317

5.1考纲解读 317

5.2知识归纳 317

一、设备管理的任务和功能 317

二、I/O系统 317

三、I/O控制方式 319

四、缓冲管理 320

五、I/O应用接口 321

六、设备分配 322

七、磁盘存储器的管理 323

5.3解题指导 325

一、基本概念 325

二、磁盘调度算法及磁盘访问时间 328

5.4习题 331

第6章 文件管理 333

6.1考纲解读 333

6.2知识归纳 333

一、文件和文件系统 333

二、文件的逻辑结构 335

三、外存分配方式 336

四、目录管理 337

五、文件存储空间的管理 338

六、文件共享与文件保护 339

6.3解题指导 340

一、基本概念辨析及基本原理 340

二、混合索引下计算文件实际占用磁盘空间和最大文件 340

三、计算访问磁盘次数 341

6.4习题 343

模拟题 345

模拟题一 345

模拟题二 346

参考答案 348

第四部分 计算机网络 362

第1章 计算机网络体系结构 362

1.1考纲解读 362

1.2知识归纳 362

一、计算机网络概述 362

二、计算机网络体系结构与参考模型 364

1.3解题指导 365

一、计算机网络基本概念 365

二、计算机网络分类 365

三、计算机体系结构与参考模型基本概念 365

四、计算机体系结构与参考模型综合理解 365

1.4习题 367

第2章 物理层 368

2.1考纲解读 368

2.2知识归纳 368

一、通信基础 368

二、传输介质 371

三、物理层设备 372

2.3解题指导 372

一、通信基础概念和定理 372

二、通信中的编码与调制 373

三、通信中的三种交换方式 374

四、通信中的两种服务方式 374

五、传输介质 375

六、物理层设备 375

2.4习题 376

第3章 数据链路层 378

3.1考纲解读 378

3.2知识归纳 378

一、数据链路层的功能 379

二、组帧 379

三、差错控制 379

四、流量控制与可靠传输机制 380

五、介质访问控制 380

六、局域网 381

七、广域网 382

八、数据链路层设备 382

3.3解题指导 383

一、数据链路层的功能 383

二、组帧 383

三、差错控制 383

四、流量控制与可靠传输机制 384

五、介质访问控制 385

六、局域网 386

七、广域网 387

八、数据链路层设备 387

3.4习题 388

第4章 网络层 390

4.1考纲解读 390

4.2知识归纳 391

一、网络层的功能 391

二、路由算法 392

三、IPv4 392

四、IPv6 394

五、路由协议 395

六、IP组播 396

七、移动IP 396

八、网络层设备 396

4.3解题指导 397

一、IP 397

二、路由算法与协议 400

三、IP组播 403

四、移动IP 403

五、网络层设备 403

六、综合题 404

4.4习题 407

第5章 传输层 410

5.1考纲解读 410

5.2知识归纳 410

一、传输层提供的服务 410

二、UDP 411

三、TCP 412

5.3解题指导 414

一、传输层基础 414

二、UDP 415

三、TCP连接管理 415

四、TCP可靠传输 417

五、TCP流量控制与拥塞控制 418

5.4习题 418

第6章 应用层 421

6.1考纲解读 421

6.2知识归纳 421

一、网络应用模型 421

二、DNS系统 422

三、FTP 424

四、电子邮件 424

五、WWW 424

6.3解题指导 426

一、网络应用基础 426

二、DNS系统 427

三、FTP 428

四、电子邮件 428

五、WWW 429

6.4习题 429

模拟题 432

模拟题一 432

模拟题二 432

参考答案 434

参考书目 439