第 1 部分 数据结构
第 1 章 绪论 ............................................................................................................................................................. 1
1.1 大纲要求 .............................................................................................................................................. 2
1.2 知识点归整 .......................................................................................................................................... 3
1.2.1 数据结构的基本概念 ........................................................................................................... 3
1.2.2 算法及其分析 ....................................................................................................................... 5
1.2.3 递归算法设计 ....................................................................................................................... 5
1.3 例题解析 .............................................................................................................................................. 6
第 2 章 线性表 ....................................................................................................................................................... 10
2.1 大纲要求 ............................................................................................................................................ 10
2.2 知识点归整 ........................................................................................................................................ 11
2.2.1 线性表的定义 ..................................................................................................................... 11
2.2.2 顺序表 ................................................................................................................................. 11
2.2.3 单链表 ................................................................................................................................. 12
2.2.4 双链表 ................................................................................................................................. 16
2.2.5 循环链表 ............................................................................................................................. 18
2.2.6 有序表 ................................................................................................................................. 19
2.3 例题解析 ............................................................................................................................................ 20
第 3 章 栈、队列和数组 ........................................................................................................................................ 37
3.1 大纲要求 ............................................................................................................................................ 37
3.2 知识点归整 ........................................................................................................................................ 38
3.2.1 栈 ......................................................................................................................................... 38
3.2.2 队列 ..................................................................................................................................... 41
3.2.3 数组和稀疏矩阵 ................................................................................................................. 44
3.3 例题解析 ............................................................................................................................................ 46
第 4 章 树与二叉树 ............................................................................................................................................... 54
4.1 大纲要求 ............................................................................................................................................ 54
4.2 知识点归整 ........................................................................................................................................ 56
4.2.1 树的概念 ............................................................................................................................. 56
4.2.2 二叉树的概念 ..................................................................................................................... 58
4.2.3 二叉树的遍历 ..................................................................................................................... 60
4.2.4 二叉树的构造 ..................................................................................................................... 67
4.2.5 树和二叉树的相互转换 ..................................................................................................... 67
4.2.6 线索二叉树 ......................................................................................................................... 68目 录
VII
4.2.7 二叉排序树 ......................................................................................................................... 68
4.2.8 平衡二叉树 ......................................................................................................................... 70
4.2.9 哈夫曼树 ............................................................................................................................. 73
4.3 例题解析 ............................................................................................................................................ 74
第 5 章 图 ............................................................................................................................................................... 97
5.1 大纲要求 ............................................................................................................................................ 97
5.2 知识点归整 ........................................................................................................................................ 99
5.2.1 图的基本概念 ..................................................................................................................... 99
5.2.2 图的存储结构 ................................................................................................................... 100
5.2.3 图的遍历 ........................................................................................................................... 102
5.2.4 最小生成树 ....................................................................................................................... 106
5.2.5 最短路径 ........................................................................................................................... 107
5.2.6 拓扑排序 ........................................................................................................................... 108
5.2.7 关键路径 ........................................................................................................................... 109
5.3 例题解析 .......................................................................................................................................... 110
第 6 章 查找 ......................................................................................................................................................... 127
6.1 大纲要求 .......................................................................................................................................... 127
6.2 知识点归整 ...................................................................................................................................... 128
6.2.1 查找的基本概念 ............................................................................................................... 128
6.2.2 线性表 ............................................................................................................................... 128
6.2.3 B - 树 .................................................................................................................................. 130
6.2.4 B+ 树 .................................................................................................................................. 133
6.2.5 哈希表 ............................................................................................................................... 134
6.3 例题解析 .......................................................................................................................................... 136
第 7 章 内部排序 ................................................................................................................................................. 146
7.1 大纲要求 .......................................................................................................................................... 146
7.2 知识点归整 ...................................................................................................................................... 148
7.2.1 排序的基本概念 ............................................................................................................... 148
7.2.2 插入排序 ........................................................................................................................... 149
7.2.3 交换排序 ........................................................................................................................... 151
7.2.4 选择排序 ........................................................................................................................... 154
7.2.5 归并排序 ........................................................................................................................... 157
7.2.6 基数排序 ........................................................................................................................... 159
7.3 例题解析 .......................................................................................................................................... 160
第 2 部分 计算机组成原理
第 8 章 计算机系统概述 ..................................................................................................................................... 170
8.1 大纲要求 .......................................................................................................................................... 170
8.2 知识点归整 ...................................................................................................................................... 171
8.2.1 计算机发展历程 ............................................................................................................... 171
8.2.2 计算机系统层次结构 ....................................................................................................... 171
8.2.3 计算机的性能指标 ........................................................................................................... 174
8.3 例题解析 .......................................................................................................................................... 175
第 9 章 数据的表示和运算 ................................................................................................................................. 178
9.1 大纲要求 .......................................................................................................................................... 178
9.2 知识点归整 ...................................................................................................................................... 180计算机学科专业基础综合联考辅导教程 201 2 版
VIII
9.2.1 数制与编码 ....................................................................................................................... 180
9.2.2 定点数的表示和运算 ....................................................................................................... 185
9.2.3 浮点数的表示和运算 ....................................................................................................... 197
9.2.4 算术逻辑单元 ALU .......................................................................................................... 200
9.3 例题解析 .......................................................................................................................................... 204
第 10 章 存储器层次结构 ................................................................................................................................... 220
10.1 大纲要求 ........................................................................................................................................ 220
10.2 知识点归整 .................................................................................................................................... 222
10.2.1 存储器的分类和层次化结构 .......................................................................................... 222
10.2.2 半导体随机存取存储器 ................................................................................................. 223
10.2.3 只读存储器 ..................................................................................................................... 227
10.2.4 主存储器与 CPU 的连接 ................................................................................................ 228
10.2.5 双口 RAM 和多模块存储器 .......................................................................................... 235
10.2.6 高速缓冲存储器（ Cache ） ............................................................................................ 237
10.2.7 虚拟存储器 ..................................................................................................................... 241
10.3 例题解析 ........................................................................................................................................ 243
第 11 章 指令系统 ............................................................................................................................................... 262
11.1 大纲要求 ........................................................................................................................................ 262
11.2 知识点归整 .................................................................................................................................... 263
11.2.1 指令格式 ......................................................................................................................... 263
11.2.2 指令的寻址方式 ............................................................................................................. 266
11.2.3 CISC 和 RISC 的基本概念 ............................................................................................. 268
11.3 例题解析 ........................................................................................................................................ 269
第 12 章 中央处理器 ........................................................................................................................................... 277
12.1 大纲要求 ........................................................................................................................................ 277
12.2 知识点归整 .................................................................................................................................... 278
12.2.1 CPU 和控制器 ................................................................................................................. 278
12.2.2 指令执行过程 ................................................................................................................. 280
12.2.3 数据通路的功能和基本结构 .......................................................................................... 282
12.2.4 硬布线控制器和微程序控制器 ...................................................................................... 289
12.2.5 指令流水线 ..................................................................................................................... 296
12.3 例题解析 ........................................................................................................................................ 300
第 13 章 总线 ....................................................................................................................................................... 317
13.1 大纲要求 ........................................................................................................................................ 317
13.2 知识点归整 .................................................................................................................................... 318
13.2.1 总线概述 ......................................................................................................................... 318
13.2.2 总线仲裁 ......................................................................................................................... 319
13.2.3 总线操作和定时 ............................................................................................................. 321
13.2.4 总线标准 ......................................................................................................................... 322
13.3 例题解析 ........................................................................................................................................ 323
第 14 章 输入输出（ I/O ）系统 .......................................................................................................................... 327
14.1 大纲要求 ........................................................................................................................................ 327
14.2 知识点归整 .................................................................................................................................... 329
14.2.1 I/O 系统的基本概念 ....................................................................................................... 329
14.2.2 外部设备 ......................................................................................................................... 330目 录
IX
14.2.3 I/O 接口 （ I/O 控制器 ） ................................................................................................. 334
14.2.4 I/O 方式 ........................................................................................................................... 336
14.3 例题解析 ........................................................................................................................................ 346
第 3 部分 计算机操作系统
第 15 章 操作系统概述 ....................................................................................................................................... 356
15.1 大纲要求 ........................................................................................................................................ 356
15.2 知识点归整 .................................................................................................................................... 357
15.2.1 操作系统的基本概念 ..................................................................................................... 357
15.2.2 操作系统的发展与分类 ................................................................................................. 358
15.2.3 操作系统的运行环境 ..................................................................................................... 360
15.3 例题解析 ........................................................................................................................................ 363
第 16 章 进程管理 ............................................................................................................................................... 367
16.1 大纲要求 ........................................................................................................................................ 367
16.2 知识点归整 .................................................................................................................................... 369
16.2.1 进程与线程 ..................................................................................................................... 369
16.2.2 处理机调度 ..................................................................................................................... 375
16.2.3 进程同步 ......................................................................................................................... 381
16.2.4 死锁 ................................................................................................................................. 396
16.3 例题解析 ........................................................................................................................................ 403
第 17 章 内存管理 ............................................................................................................................................... 426
17.1 大纲要求 ........................................................................................................................................ 426
17.2 知识点归整 .................................................................................................................................... 428
17.2.1 内存管理基础 ................................................................................................................. 428
17.2.2 虚拟内存管理 ................................................................................................................. 443
17.3 例题解析 ........................................................................................................................................ 456
第 18 章 文件管理 ............................................................................................................................................... 474
18.1 大纲要求 ........................................................................................................................................ 474
18.2 知识点归整 .................................................................................................................................... 476
18.2.1 文件系统基础 ................................................................................................................. 476
18.2.2 文件系统实现 ................................................................................................................. 486
18.2.3 磁盘组织与管理 ............................................................................................................. 493
18.3 例题解析 ........................................................................................................................................ 496
第 19 章 输入输出管理 ....................................................................................................................................... 505
19.1 大纲要求 ........................................................................................................................................ 505
19.2 知识点归整 .................................................................................................................................... 506
19.2.1 I/O 管理概述 ................................................................................................................... 506
19.2.2 I/O 核心子系统 ............................................................................................................... 511
19.3 例题解析 ........................................................................................................................................ 516
第 4 部分 计算机网络
第 20 章 计算机网络体系结构 ........................................................................................................................... 522
20.1 大纲要求 ........................................................................................................................................ 522
20.2 知识点归整 .................................................................................................................................... 523
20.2.1 计算机网络概述 ............................................................................................................. 523计算机学科专业基础综合联考辅导教程 201 2 版
X
20.2.2 计算机网络体系结构与参考模型 .................................................................................. 524
20.3 例题解析 ........................................................................................................................................ 526
第 21 章 物理层 ................................................................................................................................................... 529
21.1 大纲要求 ........................................................................................................................................ 529
21.2 知识点归整 .................................................................................................................................... 531
21.2.1 通信基础 ......................................................................................................................... 531
21.2.2 传输介质 ......................................................................................................................... 536
21.2.3 物理层设备 ..................................................................................................................... 539
21.3 例题解析 ........................................................................................................................................ 539
第 22 章 数据链路层 ........................................................................................................................................... 544
22.1 大纲要求 ........................................................................................................................................ 544
22.2 知识点归整 .................................................................................................................................... 546
22.2.1 数据链路层的功能 ......................................................................................................... 546
22.2.2 介质访问控制 ................................................................................................................. 549
22.2.3 局域网 ............................................................................................................................. 553
22.2.4 广域网 ............................................................................................................................. 556
22.2.5 数据链路层设备 ............................................................................................................. 557
22.3 例题解析 ........................................................................................................................................ 559
第 23 章 网络层 ................................................................................................................................................... 565
23.1 大纲要求 ........................................................................................................................................ 565
23.2 知识点归整 .................................................................................................................................... 567
23.2.1 网络层的功能 ................................................................................................................. 567
23.2.2 路由算法 ......................................................................................................................... 568
23.2.3 IPv4 ................................................................................................................................. 569
23.2.4 IPv6 ................................................................................................................................. 572
23.2.5 路由协议 ......................................................................................................................... 574
23.2.6 IP 组播 ............................................................................................................................. 576
23.2.7 移动 IP ............................................................................................................................. 577
23.2.8 网络层设备 ..................................................................................................................... 578
23.3 例题解析 ........................................................................................................................................ 579
第 24 章 传输层 ................................................................................................................................................... 588
24.1 大纲要求 ........................................................................................................................................ 588
24.2 知识点归整 .................................................................................................................................... 590
24.2.1 传输层提供的服务 ......................................................................................................... 590
24.2.2 UDP 协议 ........................................................................................................................ 591
24.2.3 TCP 协议 ......................................................................................................................... 592
24.3 例题解析 ........................................................................................................................................ 595
第 25 章 应用层 ................................................................................................................................................... 599
25.1 大纲要求 ........................................................................................................................................ 599
25.2 知识点归整 .................................................................................................................................... 601
25.2.1 网络应用模型 ................................................................................................................. 601
25.2.2 DNS 系统 ........................................................................................................................ 601
25.2.3 FTP .................................................................................................................................. 602
25.2.4 电子邮件 ......................................................................................................................... 603
25.2.5 WWW .............................................................................................................................. 605
25.3 例题解析 ........................................................................................................................................ 605
