计算机科学导论PDF电子书下载

第一部分 计算机和数据 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