计算机学科专业基础综合教程PDF电子书下载

第1篇 数据结构 1

第1章 线性表 1

1.1线性表的定义和基本操作 1

1.2线性表的实现 1

1.2.1顺序存储结构 1

1.2.2链式存储结构 2

1.2.3线性表的应用 4

1.3典型例题分析 5

1.4精选试题练习 8

第2章 栈、队列和数组 10

2.1栈和队列的基本概念 10

2.2栈和队列的顺序存储结构 11

2.3栈和队列的链式存储结构 12

2.4栈和队列的应用 13

2.4.1栈的应用 13

2.4.2队列的应用 14

2.5特殊矩阵的压缩存储 15

2.5.1对称矩阵 15

2.5.2对角矩阵 16

2.6典型例题分析 17

2.7精选试题练习 21

第3章 树与二叉树 23

3.1树的概念 23

3.2二叉树 24

3.2.1二叉树的定义及其主要特征 24

3.2.2二叉树的存储结构 26

3.2.3二叉树的遍历 28

3.2.4线索二叉树的基本概念和构造 29

3.2.5二叉排序树 29

3.2.6平衡二叉树 32

3.3树、森林 33

3.3.1树的存储结构 33

3.3.2森林与二叉树的转换 35

3.3.3树和森林的遍历 35

3.4树的应用 36

3.4.1等价类问题 36

3.4.2哈夫曼树和哈夫曼编码 36

3.5典型例题分析 38

3.6精选试题练习 43

第4章 图 47

4.1图的概念 47

4.2图的存储及基本操作 48

4.2.1邻接矩阵法 48

4.2.2邻接表法 49

4.3图的遍历 50

4.3.1深度优先搜索 50

4.3.2广度优先搜索 51

4.4图的基本应用及其复杂度分析 52

4.4.1最小生成树 52

4.4.2最短路径 54

4.4.3拓扑排序 55

4.4.4关键路径 56

4.5典型例题分析 56

4.6精选试题练习 62

第5章 查找 65

5.1查找的基本概念 65

5.2顺序查找法 65

5.3折半查找法 66

5.4 B—树 67

5.4.1 B—树的查找分析 68

5.4.2 B—树的插入和删除 68

5.5散列表及其查找 69

5.5.1哈希函数构造方法 70

5.5.2哈希表查找 71

5.6查找算法的分析及应用 72

5.7典型例题分析 73

5.8精选试题练习 76

第6章 内部排序 78

6.1排序的基本概念 78

6.2插入排序 78

6.2.1直接插入排序 78

6.2.2折半插入排序 79

6.3气泡排序 80

6.4简单选择排序 81

6.5希尔排序 81

6.6快速排序 82

6.7堆排序 84

6.8二路归并排序 85

6.9基数排序 86

6.10各种内部排序算法的比较 87

6.11内部排序算法的应用 88

6.12典型例题分析 89

6.13精选试题练习 91

第2篇 计算机组成原理 93

第7章 计算机系统概述 93

7.1计算机发展历程 93

7.2计算机系统层次结构 94

7.2.1计算机硬件的基本组成 95

7.2.2计算机软件的分类 95

7.2.3计算机的工作过程 96

7.3计算机性能指标 96

7.4典型例题分析 96

7.5精选试题练习 97

第8章 数据的表示和运算 99

8.1数制与编码 99

8.1.1进位计数制及其相互转换 99

8.1.2真值和机器数 100

8.1.3 BCD码 100

8.1.4字符与字符串 101

8.1.5校验码 102

8.2定点数的表示和运算 103

8.2.1定点数的表示 103

8.2.2定点数的运算 104

8.3浮点数的表示和运算 108

8.3.1浮点数的表示 108

8.3.2浮点数的加／减运算 110

8.4算术逻辑单元ALU 111

8.4.1串行加法器和并行加法器 111

8.4.2算术逻辑单元ALU的功能和机构 113

8.5典型例题分析 114

8.6精选试题练习 116

第9章 存储器层次结构 119

9.1存储器的分类 119

9.2存储器的层次化结构 120

9.3半导体随机存取存储器 121

9.3.1 SRAM存储器的工作原理 121

9.3.2 DRAM存储器的工作原理 122

9.4只读存储器 122

9.5主存储器与CPU的连接 123

9.6双口RAM和多模块存储器 124

9.7高速缓冲存储器（Cache） 125

9.7.1程序访问的局部性 125

9.7.2 Cache的基本工作原理 126

9.7.3 Cache和主存之间的映射方式 126

9.7.4 Cache中主存块的替换算法 129

9.7.5 Cache写策略 129

9.8虚拟存储器 130

9.8.1虚拟存储器的基本概念 130

9.8.2页式虚拟存储器 130

9.8.3段式虚拟存储器 131

9.8.4段页式虚拟存储器 132

9.8.5 TLB（快表） 132

9.9典型例题分析 132

9.10精选试题练习 134

第10章 指令系统 136

10.1指令格式 136

10.1.1指令的基本格式 136

10.1.2定长操作码指令格式 137

10.1.3扩展操作码指令格式 137

10.2指令的寻址方式 137

10.2.1有效地址的概念 137

10.2.2数据寻址和指令寻址 138

10.2.3常见寻址方式 138

10.3 CISC和RISC的基本概念 140

10.4典型例题分析 140

10.5精选试题练习 141

第11章 中央处理器 143

11.1 CPU的功能和基本架构 143

11.2指令执行过程 145

11.3数据通路的功能和基本结构 147

11.4控制器的功能和工作原理 148

11.4.1硬布线控制器 148

11.4.2微程序控制器 149

11.5指令流水线 151

11.5.1指令流水线的基本概念 151

11.5.2超标量和动态流水线的基本概念 152

11.6典型例题分析 152

11.7精选试题练习 154

第12章 总线 158

12.1总线概述 158

12.1.1总线的基本概念 158

12.1.2总线的分类 159

12.1.3总线的组成及性能指标 159

12.2总线仲裁 161

12.2.1集中仲裁方式 161

12.2.2分布仲裁方式 163

12.3总线操作和定时 163

12.3.1同步定时方式 163

12.3.2异步定时方式 164

12.4总线标准 164

12.5典型例题分析 167

12.6精选试题练习 169

第13章 输入输出（I/O）系统 172

13.1 I/O系统基本概念 172

13.2外部设备 172

13.2.1输入设备：键盘、鼠标 172

13.2.2输出设备：显示器、打印机 172

13.2.3外存储器：硬盘存储器、磁盘阵列、光盘存储器 173

13.3 I/O接口（I/O控制器） 174

13.3.1 I/O接口的功能和基本结构 175

13.3.2 I/O端口及其编址 176

13.4 I/O方式 177

13.4.1程序查询方式 177

13.4.2程序中断方式 177

13.4.3 DMA方式 179

13.4.4通道方式 180

13.5典型例题分析 181

13.6精选试题练习 182

第3篇 操作系统 185

第14章 操作系统概述 185

14.1操作系统的概念、特征、功能和提供的服务 185

14.1.1操作系统的概念 185

14.1.2操作系统的特征 186

14.1.3操作系统的功能 186

14.1.4操作系统提供的服务 187

14.2操作系统的发展与分类 187

14.2.1操作系统的发展 187

14.2.2操作系统的分类 189

14.3操作系统的运行环境 191

14.4典型例题分析 192

14.5精选试题练习 193

第15章 进程管理 195

15.1进程和线程 195

15.1.1进程概念 195

15.1.2进程的状态与转换 196

15.1.3进程控制 198

15.1.4进程组织 200

15.1.5进程通信 200

15.1.6线程概念与多线程模型 201

15.2处理机调度 203

15.2.1调度的基本概念 203

15.2.2调度时机、切换与过程 204

15.2.3调度的基本准则 204

15.2.4调度方式 205

15.2.5典型调度算法 205

15.3进程同步 208

15.3.1进程同步的基本概念 208

15.3.2实现临界区互斥的基本方法 209

15.3.3信号量 210

15.3.4管程 212

15.3.5经典同步问题 212

15.4死锁 218

15.4.1死锁的概念 218

15.4.2死锁处理策略 219

15.4.3死锁预防 219

15.4.4死锁避免 220

15.4.5死锁检测和解除 223

15.5典型例题分析 223

15.6精选试题练习 225

第16章 内存管理 228

16.1内存管理基础 228

16.1.1内存管理概念 228

16.1.2交换与覆盖 230

16.1.3连续分配管理方式 231

16.1.4非连续分配管理方式 232

16.2虚拟内存管理 235

16.2.1虚拟内存基本概念 235

16.2.2请求分页管理方式 235

16.2.3页面置换算法 236

16.2.4页面分配策略 237

16.2.5抖动 238

16.2.6请求分段管理方式 239

16.2.7请求段页式管理方式 239

16.3典型例题分析 240

16.4精选试题练习 241

第17章 文件管理 243

17.1文件系统基础 243

17.1.1文件概念 243

17.1.2文件结构 243

17.1.3目录结构 244

17.1.4文件共享 245

17.1.5文件保护 247

17.2文件系统实现 248

17.2.1文件系统层次结构 248

17.2.2目录实现 249

17.2.3文件实现 249

17.3磁盘组织与管理 251

17.3.1磁盘的结构 251

17.3.2磁盘调度算法 251

17.3.3磁盘的管理 253

17.4典型例题分析 254

17.5精选试题练习 255

第18章 输入输出（I/O）管理 257

18.1 I/O管理概述 257

18.1.1 I/O设备 257

18.1.2 I/O管理目标 257

18.1.3 I/O管理功能 258

18.1.4 I/O应用接口 258

18.1.5 I/O控制方式 258

18.2 I/O核心子系统 260

18.2.1 I/O调度概念 260

18.2.2高速缓存与缓冲区 260

18.2.3设备分配与回收 261

18.2.4假脱机技术 263

18.2.5出错处理 264

18.3典型例题分析 265

18.4精选试题练习 266

第4篇 计算机网络 268

第19章 计算机网络体系结构 268

19.1计算机网络概述 268

19.1.1计算机网络的概念、组成与功能 268

19.1.2计算机网络的分类 269

19.1.3计算机网络与互联网的发展历史 269

19.1.4计算机网络的标准化工作及相关组织 270

19.2计算机网络体系结构与参考模型 270

19.2.1计算机网络分层结构 270

19.2.2计算机网络协议、接口和服务的概念 271

19.2.3 ISO/OSI参考模型和TCP/IP模型 271

19.3典型例题分析 274

19.4精选试题练习 275

第20章 物理层 277

20.1通信基础 277

20.1.1信道、信号、宽带、码元、波特、速率等基本概念 277

20.1.2奈奎斯特定理与香农定理 277

20.1.3信源与信宿 278

20.1.4编码与调制 278

20.1.5电路交换、报文交换与分组交换 279

20.1.6虚电路和数据报 280

20.2传输介质 281

20.2.1双绞线、同轴电缆、光纤与无线传输介质 281

20.2.2物理层接口的特性 283

20.3物理层设备 283

20.4典型例题分析 284

20.5精选试题练习 285

第21章 数据链路层 287

21.1数据链路层的功能 287

21.2组帧 287

21.3差错控制 288

21.4流量控制与可靠传输机制 288

21.4.1流量控制、可靠传输与滑动窗口机制 288

21.4.2单帧滑动窗口与停止—等待协议 289

21.4.3多帧滑动窗口与后退N帧协议（GBN） 289

21.4.4多帧滑动窗口与选择重传协议（SR） 290

21.5介质访问控制 290

21.5.1信道划分介质访问控制 290

21.5.2随机访问介质访问控制 291

21.5.3轮询访问介质访问控制：令牌传递协议 293

21.6局域网 293

21.6.1局域网的基本概念与体系结构 293

21.6.2以太网与IEEE 802.3 294

21.6.3 IEEE 802.11 294

21.6.4令牌环网的基本原理 295

21.7广域网 295

21.8数据链路层设备 297

21.8.1网桥 297

21.8.2局域网交换机及其工作原理 298

21.9典型例题分析 299

21.10精选试题练习 301

第22章 网络层 307

22.1网络层的功能 307

22.2路由算法 307

22.3 IPv4 308

22.3.1 IP分组 308

22.3.2 IPv4地址与NAT 309

22.3.3子网划分与子网掩码 311

22.3.4 ARP协议、DHCP协议与ICMP协议 312

22.4 IPv6 313

22.4.1 IPv6的主要特点 313

24.4.2 IPv6地址 313

22.5路由协议 314

22.6 IP组播 317

22.7移动IP 317

22.7.1移动IP的概念 317

22.7.2移动IP的通信过程 318

22.8网络层设备 318

22.8.1路由器的组成和功能 318

22.8.2路由表和路由转发 319

22.9典型例题分析 319

22.10精选试题练习 322

第23章 传输层 327

23.1传输层提供的服务 327

23.1.1传输层的功能 327

23.1.2传输层寻址与端口 327

23.1.3连接服务与面向连接服务 328

23.2 UDP协议 328

23.2.1 UDP数据报 328

23.2.2 UDP校验 329

23.3 TCP协议 330

23.3.1 TCP段 330

23.3.2 TCP连接管理 331

23.3.3 TCP可靠传输 332

23.3.4流量控制和拥塞控制 333

23.4典型例题分析 334

23.5精选试题练习 336

第24章 应用层 338

24.1网络应用模型 338

24.1.1客户机／服务器模型 338

24.1.2 P2P模型 339

24.2 DNS系统 340

24.2.1层次域名空间 340

24.2.2域名服务器 341

24.2.3域名解析过程 341

24.3 FTP 342

24.3.1 FTP协议的工作原理 342

24.3.2控制连接与数据连接 342

24.4电子邮件 343

24.4.1电子邮件系统的组成结构 343

24.4.2电子邮件格式与MIME 344

24.4.3 SMTP协议与POP3协议 344

24.5 WWW 345

24.5.1 WWW的概念与组成结构 345

24.5.2 HTTP协议 345

24.6典型例题分析 346

24.7精选试题练习 346

参考文献 350