第一部分 数据结构 2
第1章 线性表 2
1.1 考纲解读 2
一、考纲提示 2
二、考纲分析 2
1.2 知识归纳 2
一、基本概念 2
二、线性表 3
三、顺序表 4
四、链表 5
1.3 解题指导 8
一、基本概念 8
二、顺序表的存储、操作 8
三、动态链表的操作及头结点 9
四、双向链表 11
五、静态链表 12
六、插入和删除结点的时间复杂度 13
1.4 习题 13
一、选择题 13
二、综合应用题 15
第2章 栈、队列和数组 16
2.1 考纲解读 16
一、考纲提示 16
二、考纲分析 16
2.2 知识归纳 16
一、基本概念 16
二、栈和队列的存储结构 18
三、矩阵的存储 20
四、栈和队列的基本操作 23
五、栈和队列的应用 24
2.3 解题指导 24
一、出栈和出队顺序问题 24
二、循环队列操作细节问题 25
三、多维数组线性化存储问题 26
四、顺序栈和顺序队列的空间需求问题 26
五、递归程序的非递归化 27
六、栈和队列的应用 27
2.4 习题 29
一、选择题 29
二、综合应用题 30
第3章 树和二叉树 31
3.1 考纲解读 31
一、考纲提示 31
二、考纲分析 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
一、选择题 48
二、综合应用题 50
第4章 图 51
4.1 考纲解读 51
一、考纲提示 51
二、考纲分析 51
4.2 知识归纳 51
一、基本概念 51
二、图的存储结构 53
三、图的遍历 55
四、图的应用 56
4.3 解题指导 60
一、基本概念 60
二、图的存储结构 61
三、图的遍历 62
四、最小生成树的生成 63
五、拓扑排序 64
六、关键路径 65
七、最短路径 65
4.4 习题 66
一、选择题 66
二、综合应用题 68
第5章 查找 69
5.1 考纲解读 69
一、考纲提示 69
二、考纲分析 69
5.2 知识归纳 69
一、基本概念 70
二、静态查找表 71
三、B-树和B+树 73
四、哈希表 76
5.3 解题指导 79
一、基本概念 79
二、折半查找的查找过程及查找效率 80
三、B-树结点的分裂与合并 80
四、哈希表的构建 82
五、哈希表的查找过程及性能分析 82
六、字符串模式匹配的细节 83
5.4 习题 84
一、选择题 84
二、综合应用题 85
第6章 内部排序 87
6.1 考纲解读 87
一、考纲提示 87
二、考纲分析 87
6.2 知识归纳 87
一、基本概念 87
二、简单排序 88
三、快速排序 91
四、堆排序 94
五、希尔排序 96
六、归并排序 97
七、基数排序 98
八、各种排序方法比较 101
6.3 解题指导 101
一、基本概念 101
二、各种排序方法的排序过程 102
三、各种排序方法的效率分析和比较 103
四、各种排序方法的稳定性 103
五、排序方法的应用 104
6.4 习题 106
一、选择题 106
二、综合应用题 107
模拟题 108
模拟题一 108
模拟题二 109
参考答案 111
算法总结 125
第二部分 计算机组成原理 128
第1章 概述 128
1.1 考纲解读 128
一、考纲提示 128
二、考纲分析 128
1.2 知识归纳 128
一、基本概念 128
二、计算机的发展历程 129
三、计算机系统的硬件组成 129
四、计算机系统的软件 130
五、计算机软件和硬件的关系 130
六、指令的执行过程 130
七、计算机系统的层次结构 130
八、计算机系统的性能指标 131
1.3 解题指导 131
一、基本概念 131
二、计算机系统硬件组成及功能 131
三、冯·诺依曼计算机的特点 132
四、计算机系统的层次结构 132
五、计算机的软件系统 132
六、计算机的性能指标 133
1.4 习题 133
第2章 运算器 135
2.1 考纲解读 135
一、考纲提示 135
二、考纲分析 135
2.2 知识归纳 135
一、重要概念 136
二、数的表示 136
2.3 解题指导 151
一、计算结果分析 151
二、运算原理及实现 151
2.4 习题 152
一、选择题 152
二、综合应用题 153
第3章 主存储器 154
3.1 考纲解读 154
一、考纲提示 154
二、考纲分析 154
3.2 知识归纳 155
一、基本概念 155
二、存储器的分类 156
三、存储器的层次化结构 157
四、半导体存储器 157
五、主存储器与CPU的连接与控制 157
六、双口RAM和多模块存储器 160
七、高速缓冲存储器（Cache） 160
八、虚拟存储器 162
3.3 解题指导 164
一、基本概念 164
二、存储器的编址单位和地址范围的计算 165
三、半导体存储器与CPU的连接 166
四、动态RAM的刷新 168
五、Cache的地址映射规则 170
六、Cache命中率的计算 171
七、虚拟存储器的工作原理和虚实地址的转换 172
八、虚拟存储器的页面替换算法 173
3.4 习题 173
一、选择题 173
二、综合应用题 175
第4章 指令系统 177
4.1 考纲解读 177
一、考纲提示 177
二、考纲分析 177
4.2 知识归纳 177
一、指令格式 177
二、寻址方式 178
三、操作数的个数 179
四、CISC和RISC的基本概念 180
4.3 解题指导 180
一、指令系统设计 180
二、寻址方式 181
4.4 习题 182
一、选择题 182
二、综合应用题 182
第5章 中央处理器 184
5.1 考纲解读 184
一、考纲提示 184
二、考纲分析 184
5.2 知识归纳 184
一、重要概念 185
二、CPU组成 186
三、CPU功能 186
四、模型机概念 186
五、指令周期 187
六、CPU控制方式 193
七、微程序控制器 195
八、硬布线控制器 195
5.3 解题指导 196
一、控制器和模型机概念 196
二、数据通路和指令周期 197
三、设计题 197
5.4 习题 199
一、选择题 199
二、综合应用题 201
第6章 总线 204
6.1 考纲解读 204
一、考纲提示 204
二、考纲分析 204
6.2 知识归纳 204
一、基本概念 205
二、总线的分类 205
三、总线的组成和性能指标 205
四、总线的连接结构 206
五、总线的特性 206
六、总线的仲裁方式 206
七、总线的一次信息传送过程 208
八、总线的定时方式 208
九、常见系统总线标准 208
十、常见设备总线标准 209
6.3 解题指导 209
一、基本概念 209
二、总线仲裁方法 209
三、总线定时 210
四、总线带宽的计算 210
五、常见总线标准及特点 211
6.4 习题 211
一、选择题 211
二、综合应用题 212
第7章 输入／输出系统 213
7.1 考纲解读 213
一、考纲提示 213
二、考纲分析 213
7.2 知识归纳 213
7.3 解题指导 222
一、基本概念 222
二、主要外部设备的工作原理 223
三、外部存储器的工作原理 223
四、外部设备参数计算 223
五、不同L/O方式的工作原理 225
六、中断处理过程的分析和计算 226
7.4 习题 229
一、选择题 229
二、综合应用题 231
模拟题 232
模拟题一 232
模拟题二 233
参考答案 235
第三部分 操作系统 250
第1章 操作系统概述 250
1.1 考纲解读 250
一、考纲提示 250
二、考纲分析 250
1.2 知识归纳 250
一、操作系统的概念、目标和作用 251
二、操作系统的基本特征 251
三、操作系统的主要功能 251
四、操作系统的发展过程与分类 251
五、操作系统的结构设计 252
六、操作系统提供的服务 252
七、操作系统的运行环境 253
1.3 解题指导 253
1.4 习题 253
第2章 进程管理 255
2.1 考纲解读 255
一、考纲提示 255
二、考纲分析 255
2.2 知识归纳 255
一、进程的基本概念 255
二、进程控制 258
三、进程同步 258
四、进程通信 259
五、线程 260
2.3 解题指导 260
一、进程及进程状态转换 260
二、判断进程同步问题算法是否正确 262
三、对信号量概念的理解 265
四、利用信号量实现前趋关系 266
五、利用信号量解决进程同步问题 267
2.4 习题 277
一、选择题 277
二、综合应用题 278
第3章 处理机调度与死锁 280
3.1 考纲解读 280
一、考纲提示 280
二、考纲分析 280
3.2 知识归纳 280
一、处理机调度的基本概念 280
二、调度算法 282
三、产生死锁的原因和必要条件 285
四、预防死锁的方法 286
五、死锁的检测与解除 286
3.3 解题指导 286
一、常见调度算法的比较 286
二、作业调度 287
三、死锁及其相关概念 290
四、采用银行家算法实施死锁避免策略 291
五、利用死锁定理检测死锁 293
3.4 习题 294
一、选择题 294
二、综合应用题 294
第4章 存储器管理 296
4.1 考纲解读 296
一、考纲提示 296
二、考纲分析 296
4.2 知识归纳 296
一、程序的装入和链接 296
二、连续分配方式 298
三、基本分页存储管理方式 299
四、基本分段存储管理方式 301
五、段页式存储管理方式 303
六、虚拟存储管理 303
七、请求分页存储管理方式 304
八、页面置换算法 306
九、请求分段存储管理方式 307
4.3 解题指导 308
一、基本概念 308
二、逻辑地址到物理地址的转换 311
三、动态分区分配算法 313
四、页面置换 313
4.4 习题 316
一、选择题 316
二、综合应用题 317
第5章 设备管理 319
5.1 考纲解读 319
一、考纲提示 319
二、考纲分析 319
5.2 知识归纳 319
一、设备管理的任务和功能 319
二、I/O系统 319
三、I/O控制方式 321
四、缓冲管理 322
五、L/O应用接口 323
六、设备分配 324
七、磁盘存储器的管理 325
5.3 解题指导 327
一、基本概念 327
二、磁盘调度算法及磁盘访问时间 330
5.4 习题 333
一、选择题 333
二、综合应用题 334
第6章 文件管理 335
6.1 考纲解读 335
一、考纲提示 335
二、考纲分析 335
6.2 知识归纳 335
一、文件和文件系统 335
二、文件的逻辑结构 337
三、外存分配方式 338
四、目录管理 339
五、文件存储空间的管理 340
六、文件共享与文件保护 341
6.3 解题指导 342
一、基本概念辨析及基本原理 342
二、混合索引下计算文件实际占用磁盘空间和最大文件 342
三、计算访问磁盘次数 343
6.4 习题 345
一、选择题 345
二、综合应用题 345
模拟题 347
模拟题一 347
模拟题二 348
参考答案 350
第四部分 计算机网络 364
第1章 计算机网络体系结构 364
1.1 考纲解读 364
一、考纲提示 364
二、考纲分析 364
1.2 知识归纳 364
一、计算机网络概述 364
二、计算机网络体系结构与参考模型 366
1.3 解题指导 367
一、计算机网络基本概念 367
二、计算机网络分类 367
三、计算机体系结构与参考模型基本概念 367
四、计算机体系结构与参考模型综合理解 367
1.4 习题 369
第2章 物理层 371
2.1 考纲解读 371
一、考纲提示 371
二、考纲分析 371
2.2 知识归纳 371
一、通信基础 371
二、传输介质 374
三、物理层设备 375
2.3 解题指导 375
一、通信基础概念和定理 375
二、通信中的编码与调制 376
三、通信中的三种交换方式 377
四、通信中的两种服务方式 378
五、传输介质 378
六、物理层设备 379
2.4 习题 379
一、选择题 379
二、综合应用题 380
第3章 数据链路层 381
3.1 考纲解读 381
一、考纲提示 381
二、考纲分析 381
3.2 知识归纳 381
一、数据链路层的功能 382
二、组帧 382
三、差错控制 382
四、流量控制与可靠传输机制 383
五、介质访问控制 383
六、局域网 384
七、广域网 385
八、数据链路层设备 385
3.3 解题指导 386
一、数据链路层的功能 386
二、组帧 386
三、差错控制 386
四、流量控制与可靠传输机制 387
五、介质访问控制 388
六、局域网 389
七、广域网 390
八、数据链路层设备 390
3.4 习题 391
一、选择题 391
二、综合应用题 392
第4章 网络层 393
4.1 考纲解读 393
一、考纲提示 393
二、考纲分析 393
4.2 知识归纳 394
一、网络层的功能 394
二、路由算法 395
三、IPv4 397
四、IPv6 399
五、路由协议 399
六、IP组播 400
七、移动IP 401
八、网络层设备 401
4.3 解题指导 401
一、IP 401
二、路由算法与协议 404
三、IP组播 407
四、移动IP 408
五、网络层设备 408
六、综合题 408
4.4 习题 413
一、选择题 413
二、综合应用题 414
第5章 传输层 416
5.1 考纲解读 416
一、考纲提示 416
二、考纲分析 416
5.2 知识归纳 416
一、传输层提供的服务 416
二、UDP 417
三、TCP 418
5.3 解题指导 420
一、传输层基础 420
二、UDP 421
三、TCP连接管理 421
四、TCP可靠传输 423
五、TCP流量控制与拥塞控制 424
5.4 习题 425
一、选择题 425
二、综合应用题 426
第6章 应用层 427
6.1 考纲解读 427
一、考纲提示 427
二、考纲分析 427
6.2 知识归纳 427
一、网络应用模型 427
二、DNS系统 428
三、FTP 430
四、电子邮件 430
五、WWW 431
6.3 解题指导 432
一、网络应用基础 432
二、DNS系统 433
三、FTP 434
四、电子邮件 434
五、WWW 435
6.4 习题 435
一、选择题 435
二、综合应用题 437
模拟题 438
模拟题一 438
模拟题二 438
参考答案 440
附录 2014年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题 445
参考书目 452