第一部分 计算机和数据 1
第1章 绪论 1
1.1 计算机作为黑盒 1
1.1.1 数据处理器 1
1.1.2 可编程数据处理器 1
1.2 冯·诺伊曼模型 3
1.2.1 4个子系统 3
1.2.2 存储的程序概念 3
1.2.3 指令的顺序执行 4
1.3 计算机硬件 4
1.4 数据 4
1.4.1 存储数据 4
1.4.2 组织数据 4
1.5 计算机软件 5
1.5.1 必须存储程序 5
1.5.2 指令的序列 5
1.5.3 算法 5
1.5.4 语言 5
1.5.5 软件工程 6
1.5.6 操作系统 6
1.6 历史 6
1.6.1 机械计算机器（1930年以前） 6
1.6.2 电子计算机的诞生（1930—1950） 7
1.6.3 计算机的诞生（1950—现在） 7
1.7 关键术语 8
1.8 小结 8
1.9 练习 9
第2章 数据的表示 11
2.1 数据的类型 11
2.2 计算机内部的数据 11
2.2.1 位 12
2.2.2 位模式 12
2.2.3 字节 12
2.3 表示数据 12
2.3.1 文本 12
2.3.2 数 14
2.3.3 图像 14
2.3.4 音频 16
2.3.5 视频 16
2.4 十六进制表示法 16
2.5 八进制表示法 18
2.6 关键术语 19
2.7 小结 19
2.8 练习 20
第3章 数的表示 22
3.1 十进制和二进制 22
3.1.1 十进制系统 22
3.1.2 二进制系统 22
3.2 转换 23
3.2.1 二进制数向十进制数转换 23
3.2.2 十进制数向二进制数转换 23
3.3 整数的表示法 24
3.3.1 无符号整数格式 25
3.3.2 符号加绝对值格式 26
3.3.3 二进制反码格式 28
3.3.4 二进制补码格式 30
3.3.5 整数表示法小结 32
3.4 EXCESS系统 32
3.5 浮点表示法 33
3.5.1 转换成二进制 33
3.5.2 规范化 34
3.5.3 符号、幂和尾数 34
3.5.4 IEEE标准 35
3.6 十六进制表示法 36
3.7 关键术语 36
3.8 小结 37
3.9 练习 37
第4章 位运算 42
4.1 算术运算 42
4.1.1 整数的算术运算 42
4.1.2 浮点数的算术运算 45
4.2 逻辑运算 45
4.2.1 真值表 46
4.2.2 一元运算符 46
4.2.3 二元运算符 47
4.2.4 应用 48
4.3 移位运算 51
4.4 关键术语 52
4.5 小结 52
4.6 练习 53
第二部分 计算机硬件 57
第5章 计算机组成 57
5.1 中央处理单元 57
5.1.1 算术逻辑单元 57
5.1.2 寄存器 57
5.1.3 控制单元 58
5.2 主存储器 58
5.2.1 地址空间 58
5.2.2 存储器的种类 59
5.2.3 存储器的层次结构 60
5.2.4 高速缓冲存储器 60
5.3 输入／输出 61
5.3.1 非存储设备 61
5.3.2 存储设备 61
5.4 子系统的内部连接 67
5.4.1 CPU和主存的连接 67
5.4.2 I/O设备的连接 68
5.4.3 输入／输出设备的寻址 70
5.5 程序执行 71
5.5.1 机器周期 71
5.5.2 机器周期的例子 71
5.5.3 输入／输出操作 73
5.6 两种不同的体系结构 74
5.6.1 CISC 75
5.6.2 RISC 75
5.7 关键术语 75
5.8 小结 77
5.9 练习 77
第6章 计算机网络 82
6.1 网络，大和小 82
6.2 OSI模型 82
6.2.1 7层结构 82
6.2.2 层的功能 83
6.3 网络分类 85
6.3.1 局域网（LAN） 85
6.3.2 城域网（MAN） 86
6.3.3 广域网（WAN） 87
6.4 连接设备 87
6.4.1 中继器 87
6.4.2 网桥 88
6.4.3 路由器 89
6.4.4 网关 89
6.4.5 OSI模型和连接设备 90
6.5 互联网和TCP/IP 90
6.5.1 物理层和数据链路层 90
6.5.2 网络层 91
6.5.3 传输层 91
6.5.4 应用层 91
6.6 关键术语 95
6.7 小结 96
6.8 练习 97
第三部分 计算机软件 101
第7章 操作系统 101
7.1 定义 101
7.2 演化 101
7.2.1 批处理系统 101
7.2.2 分时系统 102
7.2.3 个人系统 102
7.2.4 并行系统 102
7.2.5 分布式系统 102
7.3 组成部分 102
7.3.1 内存管理器 103
7.3.2 进程管理器 105
7.3.3 设备管理器 110
7.3.4 文件管理器 110
7.3.5 用户界面 111
7.4 主流操作系统 111
7.4.1 Windows 2000 111
7.4.2 UNIX 111
7.4.3 Linux 111
7.5 关键术语 112
7.6 小结 112
7.7 练习 113
第8章 算法 117
8.1 概念 117
8.1.1 非正式定义 117
8.1.2 示例 117
8.1.3 定义动作 118
8.1.4 精化 118
8.1.5 泛化 120
8.2 三种结构 120
8.2.1 顺序 121
8.2.2 判断 121
8.2.3 循环 121
8.3 算法的表示 121
8.3.1 流程图 121
8.3.2 伪代码 121
8.4 更正式的定义 124
8.4.1 有序集合 124
8.4.2 明确步骤 124
8.4.3 产生结果 124
8.4.4 在有限的时间内终止 125
8.5 子算法 125
8.6 基本算法 126
8.6.1 求和 126
8.6.2 乘积 126
8.6.3 最大和最小 127
8.6.4 排序 127
8.6.5 查找 130
8.7 递归 132
8.7.1 迭代的定义 132
8.7.2 递归的定义 132
8.8 关键术语 134
8.9 小结 134
8.10 练习 135
第9章 程序设计语言 138
9.1 演化 138
9.1.1 机器语言 138
9.1.2 符号语言 139
9.1.3 高级语言 139
9.1.4 自然语言 140
9.2 构建程序 140
9.2.1 编写和编辑程序 140
9.2.2 编译程序 141
9.2.3 链接程序 141
9.3 程序的执行 141
9.4 语言的分类 142
9.4.1 过程化（强制性）语言 142
9.4.2 面向对象的语言 143
9.4.3 函数型语言 145
9.4.4 说明性（逻辑）语言 146
9.4.5 专用语言 147
9.5 过程化语言：C 148
9.5.1 标识符 148
9.5.2 数据类型 149
9.5.3 变量 149
9.5.4 常量 150
9.5.5 输入和输出 151
9.5.6 表达式 151
9.5.7 语句 152
9.5.8 函数 153
9.5.9 选择 155
9.5.10 循环 155
9.5.11 派生数据类型 157
9.5.12 递归 157
9.6 关键术语 157
9.7 小结 158
9.8 练习 159
第10章 软件工程 163
10.1 软件生命周期 163
10.1.1 分析阶段 163
10.1.2 设计阶段 164
10.1.3 实现阶段 164
10.1.4 测试阶段 165
10.2 开发过程模型 165
10.2.1 瀑布模型 165
10.2.2 增量模型 166
10.3 模块化 166
10.3.1 工具 166
10.3.2 耦合 167
10.3.3 内聚 168
10.4 质量 169
10.4.1 质量定义 169
10.4.2 质量因素 169
10.4.3 质量周期 171
10.5 文档 172
10.5.1 用户文档 172
10.5.2 系统文档 172
10.5.3 进行过程中的文档化 173
10.6 关键术语 173
10.7 小结 174
10.8 练习 174
第四部分 数据组织 177
第11章 数据结构 177
11.1 数组 177
11.1.1 数组的应用 179
11.1.2 二维数组 180
11.2 记录 181
11.3 链表 182
11.3.1 节点 182
11.3.2 链表的指针 182
11.3.3 链表的操作 183
11.4 关键术语 184
11.5 小结 184
11.6 练习 185
第12章 抽象数据类型 188
12.1 背景 188
12.1.1 定义 188
12.1.2 抽象数据类型模型 189
12.1.3 抽象数据类型的操作 189
12.2 线性列表 189
12.2.1 线性列表的操作 190
12.2.2 广义线性列表的实现 192
12.2.3 线性列表的应用 192
12.3 栈 192
12.3.1 栈的操作 192
12.3.2 栈的实现 193
12.3.3 栈的应用 194
12.4 队列 194
12.4.1 队列的操作 195
12.4.2 队列的实现 195
12.4.3 队列的应用 195
12.5 树 196
12.5.1 树的基本概念 196
12.5.2 树的操作 197
12.6 二叉树 198
12.6.1 二叉树的操作 199
12.6.2 二叉树的实现 200
12.6.3 二叉树的应用 201
12.7 图 201
12.7.1 术语 201
12.7.2 图的操作 202
12.7.3 图的实现 204
12.7.4 图的应用 204
12.8 关键术语 205
12.9 小结 206
12.10 练习 208
第13章 文件结构 213
13.1 存取方法 213
13.1.1 顺序存取 213
13.1.2 随机存取 213
13.2 顺序文件 214
13.3 索引文件 216
13.4 哈希文件 217
13.4.1 哈希方法 217
13.4.2 冲突 218
13.5 文本与二进制 220
13.5.1 文本文件 220
13.5.2 二进制文件 220
13.6 关键术语 220
13.7 小结 221
13.8 练习 221
第14章 数据库 225
14.1 数据库管理系统 225
14.2 体系结构 226
14.2.1 内层 226
14.2.2 概念层 226
14.2.3 外层 226
14.3 数据库模型 226
14.3.1 层次模型 226
14.3.2 网络模型 227
14.3.3 关系模型 227
14.4 关系模型 227
14.5 关系的操作 228
14.5.1 插入 228
14.5.2 删除 229
14.5.3 更新 229
14.5.4 选择 229
14.5.5 投影 230
14.5.6 连接 230
14.5.7 并 231
14.5.8 交 231
14.5.9 差 231
14.6 结构化查询语言 232
14.7 其他数据库模型 234
14.7.1 分布式数据库 235
14.7.2 面向对象数据库 235
14.8 关键术语 235
14.9 小结 236
14.10 练习 236
第五部分 高级主题 241
第15章 数据压缩 241
15.1 无损压缩 241
15.1.1 游程长度编码 241
15.1.2 霍夫曼编码 242
15.1.3 Lempel Ziv编码 244
15.2 有损压缩方法 247
15.2.1 图像压缩：JPEG 247
15.2.2 视频压缩：MPEG 250
15.3 关键术语 251
15.4 小结 251
15.5 练习 252
第16章 安全 254
16.1 保密 254
16.1.1 加密／解密 254
16.1.2 使用组合的保密 257
16.2 数字签名 258
16.2.1 签署整个文档 258
16.2.2 签署摘要 258
16.3 关键术语 260
16.4 小结 260
16.5 练习 260
第17章 计算理论 263
17.1 简单语言 263
17.1.1 递增语句 263
17.1.2 递减语句 263
17.1.3 循环语句 263
17.1.4 简单语言的威力 264
17.1.5 结论 266
17.2 图灵机 266
17.2.1 图灵机组成部件 266
17.2.2 对简单语言的模拟 268
17.2.3 结论 270
17.3 歌德尔数 270
17.3.1 描述程序 271
17.3.2 翻译数 271
17.4 停机问题 272
17.5 可解的和不可解的问题 273
17.5.1 不可解问题 273
17.5.2 可解问题 274
17.6 关键术语 275
17.7 小结 275
17.8 练习 275
附录 279
附录A ASCII码 279
附录B Unicode 283
附录C 流程图 286
附录D 伪代码 290
附录E 结构图 293
附录F 离散余弦变换 297
附录G 缩略语和术语表 298
索引 323