本书着重对考试大纲规定的内容有重点地细化和深化，内容涵盖了考试大纲的所有知识点，包括数据结构、计算机组成原理、操作系统和计算机网络基础课的概念、基本原理和方法。

由于编写组成员均为研究生考试第一线的辅导专家，负责和参与了历年的考试培训与辅导、教程编写、考试阅卷等方面的工作，因此，本书凝聚了专家们的知识、经验、心得和体会，集成了专家们的精力和心血。

本书由希赛IT教育研发中心组织编写，是“快乐考研，轻松过关”系列丛书的第一本的上册，作为全国硕士研究生入学统一考试计算机学科专业基础综合考试的教材。

本书紧扣考试大纲，着重对考试大纲规定的内容有重点地细化和深化，内容涵盖了考试大纲的所有知识点，包括数据结构、计算机组成原理、操作系统和计算机网络基础课的概念、基本原理和方法。阅读本书，就相当于阅读了一本详细的、带有知识注释的教程。考生可通过阅读本书掌握考试大纲规定的知识，掌握考试重点和难点，熟悉内容的分布。

本书是为备考全国硕士研究生入学统一考试计算机学科专业基础综合考试的考生而量身定做的。

第1篇 数据结构篇

第1章 线性表 

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

1.1.1 线性表的逻辑定义与特征 2

1.1.2 线性表的基本操作 3

1.2 顺序存储结构的存储结构和实现 5

1.3 链式存储结构的存储结构和实现 14

1.3.1 线性链表 15

1.3.2 双向链表 27

1.3.3 循环链表 35

1.3.4 静态链表 36

1.4 线性表的应用 40

1.4.1 有序表的运算应用 40

1.4.2 线性表的遍历应用 42

第2章 栈、队列和数组

2.1 栈的概念和实现 44

2.1.1 栈的基本操作 46

2.1.2 顺序栈的定义和实现 47

2.1.3 链栈的定义和实现 51

2.2 栈的应用 54

2.3 队列的概念和实现 59

2.3.1 队列的基本操作 60

2.3.2 循环队列的定义和实现 62

2.3.3 链队列的定义和实现 68

2.4 队列的应用 70

2.5 数组的概念和实现 72

2.5.1 特殊矩阵 72

2.5.2 稀疏矩阵 74

第3章 树和二叉树

3.1 树的基本概念 80

3.2 二叉树 82

3.2.1 二叉树的定义 82

3.2.2 二叉树的性质 84

3.2.3 二叉树的存储结构 87

3.2.4 二叉树的遍历 89

3.2.5 线索二叉树 92

3.3 树与森林 95

3.3.1 树的性质 95

3.3.2 树的存储结构 96

3.3.3 树、森林与二叉树的转换 100

3.3.4 树与森林的遍历 101

3.4 树的应用 103

3.4.1 等价类的问题 103

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

第4章 图

4.1 图的概念和相关术语 112

4.2 图的存储 115

4.2.1 邻接矩阵及其实现 117

4.2.2 邻接表及其实现 120

4.3 图的遍历 124

4.3.1 深度优先搜索 125

4.3.2 广度优先搜索 129

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

4.4.1 最小生成树定义 133

4.4.2 最短路径 138

4.4.3 拓扑排序 140

4.4.4 关键路径 143

第5章 查找

5.1 查找概念 147

5.2 静态查找法 148

5.2.1 顺序表查找 148

5.2.2 有序表查找 150

5.2.3 静态树表查找 154

5.2.4 索引顺序表查找 157

5.3 动态查找法 159

5.3.1 二叉排序树 159

5.3.2 平衡二叉树 169

5.3.3 B-树 174

5.4 哈希表及其查找 183

5.4.1 哈希函数构造方法 184

5.4.2 冲突解决办法 186

5.4.3 哈希表的查找及其性能分析 190

第6章 内部排序 192

6.1 排序的基本概念 192

6.2 插入排序 193

6.2.1 直接插入排序 193

6.2.2 折半插入排序 196

6.2.3 希尔排序 197

6.3 交换排序 200

6.3.1 冒泡排序 200

6.3.2 快速排序 203

6.4 选择排序 207

6.4.1 简单选择排序 207

6.4.2 堆排序 209

6.5 二路归并排序 213

6.6 基数排序 216

6.6.1 多关键字排序 216

6.6.2 链式基数排序 217

6.7 各种内部排序算法比较与选择 220

6.7.1 内部排序算法的比较 220

6.7.2 内部排序算法的选择 221

第2篇 操作系统篇

第7章 操作系统概述 224

7.1 操作系统的概念 224

7.2 操作系统的特征 226

7.3 操作系统的功能 227

7.4 操作系统提供的服务 228

7.4.1 程序启动与结束 228

7.4.2 系统调用与中断 232

7.5 操作系统的发展与分类 240

7.5.1 操作系统的发展 240

7.5.2 操作系统的分类 242

第8章 进程管理 244

8.1 进程管理概述 244

8.2 进程与线程 245

8.1.1 进程的概念 245

8.1.2 进程的状态与转换 248

8.1.3 进程控制 250

8.1.4 进程组织 252

8.1.5 进程通信 252

8.1.6 线程概念与多线程模型 254

8.2 处理机调度 256

8.2.1 调度时机与过程 256

8.2.2 典型调度算法 258

8.3 进程同步 259

8.3.1 实现临界区互斥的基本方法 260

8.3.2 信号量 264

8.3.3 管程 265

8.3.4 经典同步问题 265

8.3.5 死锁 266

第9章 内存管理 270

9.1 内存管理的概念 270

9.1.1 内存的概念与作用 270

9.1.2 内存管理的功能与任务 272

9.1.3 程序装入与连接 278

9.1.4 内存保护 279

9.2 交换与覆盖 279

9.2.1 覆盖技术 279

9.2.2 交换技术 280

9.3 连续分配管理方式 281

9.3.1 单一连续分配 281

9.3.2 分区分配 283

9.4 非连续分配管理方式 288

9.4.1 分页管理方式 288

9.4.2 分段管理方式 291

9.4.3 段页式管理方式 295

9.5 虚拟内存管理 296

9.5.1 请求分页管理方式 296

9.5.2 页面置换算法 303

9.5.3 页面分配策略 304

9.5.4 抖动 306

第10章 文件管理

10.1 外存储器 307

10.2 文件系统基础 309

10.2.1 文件概述 309

10.2.2 文件结构 312

10.2.3 目录结构 315

10.2.4 文件共享 320

10.2.5 文件保护 321

10.3 文件系统的实现 322

10.3.1 文件系统层次结构 322

10.3.2 目录的实现 328

10.3.3 文件的实现 334

10.4 磁盘组织与管理 344

10.4.1 磁盘结构 345

10.4.2 磁臂调度算法 347

10.4.3 磁盘的管理 350

第11章 输入输出管理

11.1 I/O管理概述 352

11.1.1 I/O设备 352

11.1.2 I/O管理目标与功能 361

11.1.3 I/O应用接口 364

11.1.4 I/O控制方式 366

11.1.5 设备管理功能的结构与过程 372

11.2 I/O核心子系统 377

11.2.1 高速缓存与缓冲区 377

11.2.2 设备分配与回收 379

11.2.3 假脱机技术 380

11.2.4 出错处理 381

参考文献 382