上篇 题目与思考 3
第一部分 数据结构 3
第1章 线性表 5
1.1线性表的定义和基本操作 5
1.2线性表的实现 5
第2章栈、队列和数组 9
2.1栈和队列的基本概念 9
2.2栈和队列的顺序存储结构 10
2.3栈和队列的链式存储结构 10
2.4栈和队列的应用 11
2.5特殊矩阵的压缩存储 12
第3章 树和二叉树 13
3.1树的基本概念 13
3.2二叉树 13
3.3树、森林 19
3.4树与二叉树的应用 21
第4章图 23
4.1图的基本概念 23
4.2图的存储及基本操作 24
4.3图的遍历 24
4.4图的基本应用 26
第5章 查找 29
5.1查找的基本概念 29
5.2顺序查找法 29
5.3折半查找法 29
5.4 B树及其基本操作、B+树的基本概念 30
5.5散列（Hash）表 31
5.6查找算法的分析及应用 32
第6章 排序 33
6.1排序的基本概念 33
6.2插入排序 33
6.3起泡排序（Bubble Sort） 34
6.4简单选择排序 34
6.5希尔排序（Shell Sort） 35
6.6快速排序 35
6.7堆排序 35
6.8二路归并排序（Merge Sort） 36
6.9基数排序 36
6.10外部排序 37
6.11各种内部排序算法的比较 37
6.12排序算法的应用 38
第二部分 计算机组成原理 39
第1章 计算机系统概述 41
1.1计算机发展历程 41
1.2计算机系统层次结构 41
1.3计算机性能指标 42
第2章 数据的表示和运算 44
2.1数制与编码 44
2.2定点数的表示和运算 46
2.3浮点数的表示和运算 48
2.4算术逻辑单元ALU 50
第3章 存储器层次结构 52
3.1存储器分类 52
3.2存储器的层次化结构 52
3.3半导体随机存储存储器 53
3.4主存储器与CPU的连接 55
3.5双口RAM和多模块存储器 57
3.6高速缓冲存储器（Cache） 58
3.7虚拟存储器 60
第4章 指令系统 62
4.1指令格式 62
4.2指令的寻址方式 63
4.3 CISC和RISC的基本概念 66
第5章 中央处理器 68
5.1 CPU的功能和基本结构 68
5.2指令执行过程 69
5.3数据通路的功能和基本结构 70
5.4控制器的功能和工作原理 72
5.5指令流水线 74
第6章 总线 76
6.1总线概述 76
6.2总线仲裁 77
6.3总线操作和定时 78
6.4总线标准 78
第7章 输入输出系统 79
7.1 I/O系统基本概念 79
7.2外部设备 79
7.3 I/O接口（I/O控制器） 81
7.4 I/O方式 81
第三部分 操作系统 85
第1章 操作系统概述 87
1.1操作系统的概念、特征、功能和提供的服务 87
1.2操作系统的发展和分类 88
1.3操作系统的运行环境 89
1.4操作系统的体系结构 90
第2章 进程管理 92
2.1进程与线程 92
2.2处理机调度 93
2.3同步与互斥 97
2.4死锁 100
第3章 内存管理 105
3.1内存管理基础 105
3.2虚拟内存管理 107
第4章 文件管理 113
4.1文件系统基础 113
4.2文件系统实现 114
4.3磁盘组织与管理 115
第5章 输入输出（I/O）管理 117
5.1 I/O管理概述 117
5.2 I/O核心子系统 118
第四部分 计算机网络 120
第1章 计算机网络体系结构 121
1.1计算机网络概述 121
1.2计算机网络系统结构与参考模型 121
第2章 物理层 123
2.1通信基础 123
2.2传输介质 124
2.3物理层设备 125
第3章 数据链路层 126
3.1数据链路层的功能 126
3.2组帧 126
3.3差错控制 126
3.4流量控制与可靠传输机制 127
3.5介质访问控制 129
3.6局域网 129
3.7广域网 130
3.8数据链路层设备 130
第4章 网络层 132
4.1网络层的功能 132
4.2路由算法 132
4.3 IPv4 133
4.4 IPv6 135
4.5路由协议 136
4.6 IP组播 137
4.7移动IP 137
4.8网络层设备 138
第5章 传输层 140
5.1传输层提供的服务 140
5.2 UDP协议 141
5.3 TCP协议 141
第6章 应用层 144
6.1网络应用模型 144
6.2 DNS系统 144
6.3 FTP 145
6.4电子邮件 145
6.5 WWW 145
下篇 答案与解析 149
第一部分 数据结构 149
第1章 线性表 149
1.1线性表的定义和基本操作 149
1.2线性表的实现 149
第2章栈、队列和数组 163
2.1栈和队列的基本概念 163
2.2栈和队列的顺序存储结构 166
2.3栈和队列的链式存储结构 166
2.4栈和队列的应用 168
2.5特殊矩阵的压缩存储 170
第3章 树和二叉树 173
3.1树的基本概念 173
3.2二叉树 173
3.3树、森林 187
3.4树与二叉树的应用 189
第4章图 194
4.1图的基本概念 194
4.2图的存储及基本操作 195
4.3图的遍历 196
4.4图的基本应用 199
第5章 查找 205
5.1查找的基本概念 205
5.2顺序查找法 205
5.3折半查找法 206
5.4 B树及其基本操作、B+树的基本概念 207
5.5散列（Hash）表 209
5.6查找算法的分析及应用 211
第6章 排序 213
6.1排序的基本概念 213
6.2插入排序 213
6.3起泡排序（Bubble Sort） 214
6.4简单选择排序 216
6.5希尔排序（Shell Sort） 216
6.6快速排序 217
6.7堆排序 218
6.8二路归并排序（Merge Sort） 219
6.9基数排序 220
6.10外部排序 221
6.11各种内部排序算法的比较 221
6.12排序算法的应用 223
第二部分 计算机组成原理 224
第1章 计算机系统概述 224
1.1计算机发展历程 224
1.2计算机系统层次结构 224
1.3计算机性能指标 226
第2章 数据的表示与运算 228
2.1数制与编码 228
2.2定点数的表示和运算 231
2.3浮点数的表示和运算 233
2.4算术逻辑单元ALU 237
第3章 存储器层次结构 240
3.1存储器分类 240
3.2存储器的层次化结构 240
3.3半导体随机存储存储器 242
3.4主存储器与CPU的连接 244
3.5双口RAM和多模块存储器 247
3.6高速缓冲存储器（Cache） 248
3.7虚拟存储器 252
第4章 指令系统 254
4.1指令格式 254
4.2指令的寻址方式 255
4.3 CISC和RISC的基本概念 258
第5章 中央处理器 260
5.1 CPU的功能和基本结构 260
5.2指令执行过程 260
5.3数据通路的功能和基本结构 262
5.4控制器的功能和工作原理 265
5.5指令流水线 267
第6章 总线 269
6.1总线概述 269
6.2总线仲裁 270
6.3总线操作和定时 271
6.4总线标准 271
第7章 输入输出系统 273
7.1 I/O系统基本概念 273
7.2外部设备 273
7.3 I/O接口（I/O控制器） 277
7.4 I/O方式 278
第三部分 操作系统 285
第1章 操作系统概述 285
1.1操作系统的概念、特征、功能和提供的服务 285
1.2操作系统的发展和分类 288
1.3操作系统的运行环境 290
1.4操作系统的体系结构 291
第2章 进程管理 294
2.1进程与线程 294
2.2处理机调度 297
2.3同步与互斥 309
2.4死锁 318
第3章 内存管理 324
3.1内存管理基础 324
3.2虚拟内存管理 327
第4章 文件管理 335
4.1文件系统基础 335
4.2文件系统实现 336
4.3磁盘组织与管理 339
第5章 输入输出（I/O）管理 342
5.1 I/O管理概述 342
5.2 I/O核心子系统 343
第四部分 计算机网络 345
第1章 计算机网络体系结构 345
1.1计算机网络概述 345
1.2计算机网络系统结构与参考模型 346
第2章 物理层 350
2.1通信基础 350
2.2传输介质 352
2.3物理层设备 353
第3章 数据链路层 354
3.1数据链路层的功能 354
3.2组帧 354
3.3差错控制 354
3.4流量控制与可靠传输机制 355
3.5介质访问控制 358
3.6局域网 359
3.7广域网 360
3.8数据链路层设备 361
第4章 网络层 363
4.1网络层的功能 363
4.2路由算法 363
4.3 IPv4 364
4.4 IPv6 368
4.5路由协议 369
4.6 IP组播 371
4.7移动IP 371
4.8网络层设备 371
第5章 传输层 373
5.1传输层提供的服务 373
5.2 UDP协议 375
5.3 TCP协议 375
第6章 应用层 381
6.1网络应用模型 381
6.2 DNS系统 381
6.3 FTP 382
6.4电子邮件 382
6.5 WWW 383
参考文献 385