第1部分 数据结构 2
第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最短路径 84
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知识点精讲 101
5.2.1查找的基本概念 101
5.2.2顺序查找法 102
5.2.3折半查找法 103
5.2.4动态查找法 103
5.2.5 B-树和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基数排序 128
6.2.7对各种排序算法的比较 129
6.3例题精析 130
6.4习题 133
6.5习题答案 137
第2部分 计算机组成原理 142
第1章 计算机系统概述 142
1.1复习提示 142
1.1.1复习目标和要求 142
1.1.2命题方向提示 143
1.2知识点精讲 143
1.2.1计算机的发展历程 143
1.2.2计算机硬件的基本组成 144
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命题方向提示 151
2.2知识点精讲 151
2.2.1进位计数制及其相互转换 151
2.2.2真值和机器数 152
2.2.3 BCD码 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
3.2.9 Cache的基本工作原理 193
3.2.10 Cache和主存之间的映射方式 193
3.2.11 Cache中主存块的替换算法 195
3.2.12 Cache写策略 195
3.2.13虚拟存储器的基本概念 196
3.2.14页式虚拟存储器 196
3.2.15 段式虚拟存储器 196
3.2.16段页式虚拟存储器 197
3.2.17 TLB（快表） 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.7 CISC和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.1 CPU的功能和基本结构 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.1 I/O系统基本概念 302
7.2.2输入设备：键盘、鼠标 302
7.2.3输出设备：显示器、打印机 303
7.2.4外存储器：硬盘存储器、磁盘阵列、光盘存储器 305
7.2.51/O接口的功能和基本结构 307
7.2.6 I/O端口及其编址 307
7.2.7程序查询方式 308
7.2.8程序中断方式 309
7.2.9 DMA控制器 310
7.3例题精析 311
7.4习题 315
7.5参考答案 320
第3部分 操作系统 326
第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.7 OS结构设计 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章 文件管理系统 397
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
4.4习题 409
4.5习题解答 411
第5章 输入输出管理 413
5.1复习提示 413
5.1.1复习目标和要求 413
5.1.2命题方向提示 414
5.2知识点详解 414
5.2.1 I/O系统概述和I/O设备的分类 414
5.2.2 设备控制器I/O通道 415
5.2.3 I/O控制方式 416
5.2.4缓冲管理和分类 418
5.2.5 I/O设备分配方式 420
5.2.6假脱机技术 421
5.2.7磁盘出错处理 421
5.3例题精析 422
5.4习题 425
5.5习题解答 428
第4部分 计算机网路 432
第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.6 ISO/OSI参考模型 436
1.2.7 TCP/IP模型 437
1.2.8 OSI参考模型与TCP/IP参考模型的比较 438
1.3例题精析 439
1.4习题 442
1.5习题答案 443
第2章 物理层 445
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
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.4 IPv4地址和IP协议 499
4.2.5子网划分与子网掩码 503
4.2.6 ARP协议、DHCP协议、ICMP协议 504
4.2.7 IPv6主要特点与IPv6地址 506
4.2.8自治系统、域内路由与域间路由 506
4.2.9 RIP路由信息协议、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.4 UDP协议 526
5.2.5 TCP段、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.3 FTP协议的工作原理 543
6.2.4电子邮件系统 544
6.2.5 WWW的概念与组成结构和HTTP协议 546
6.3例题精析 548
6.4习题 551
6.4习题答案 552
第5部分 模拟试题 556
模拟试题1 556
模拟试题2 563
模拟试题3 572
模拟试题4 579
附录 588
附录12009全国计算机专业统考试题及答案评析 588
附录2计算机学科专业基础综合考试大纲（2010版） 599