本书着重对考试大纲规定的内容有**地细化和深化,内容涵盖了考试大纲的所有知识点,包括数据结构、计算机组成原理、操作系统和计算机网络基础课的概念、基本原理和方法。
由于编写组成员均为研究生考试**线的辅导专家,负责和参与了历年的考试培训与辅导、教程编写、考试阅卷等方面的工作,因此,本书凝聚了专家们的知识、经验、心得和体会,集成了专家们的精力和心血。 本书由希赛IT教育研发**组织编写,是“快乐考研,轻松过关”系
列丛书的**本的上册,作为全国硕士研究生入学统一考试计算机学科专
业基础综合考试的教材。
本书紧扣考试大纲,着重对考试大纲规定的内容有**地细化和深化
,内容涵盖了考试大纲的所有知识点,包括数据结构、计算机组成原理、
操作系统和计算机网络基础课的概念、基本原理和方法。阅读本书,就相
当于阅读了一本��细的、带有知识注释的教程。考生可通过阅读本书掌握
考试大纲规定的知识,掌握考试**和难点,熟悉内容的分布。
本书是为备考全国硕士研究生入学统一考试计算机学科专业基础综合
考试的考生而量身定做的。

第1篇 数据结构篇
第1章 线性表

本书着重对考试大纲规定的内容有**地细化和深化,内容涵盖了考试大纲的所有知识点,包括数据结构、计算机组成原理、操作系统和计算机网络基础课的概念、基本原理和方法。
由于编写组成员均为研究生考试**线的辅导专家,负责和参与了历年的考试培训与辅导、教程编写、考试阅卷等方面的工作,因此,本书凝聚了专家们的知识、经验、心得和体会,集成了专家们的精力和心血。 本书由希赛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

本书着重对考试大纲规定的内容有**地细化和深化,内容涵盖了考试大纲的所有知识点,包括数据结构、计算机组成原理、操作系统和计算机网络基础课的概念、基本原理和方法。
由于编写组成员均为研究生考试**线的辅导专家,负责和参与了历年的考试培训与辅导、教程编写、考试阅卷等方面的工作,因此,本书凝聚了专家们的知识、经验、心得和体会,集成了专家们的精力和心血。 本书由希赛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

本书着重对考试大纲规定的内容有**地细化和深化,内容涵盖了考试大纲的所有知识点,包括数据结构、计算机组成原理、操作系统和计算机网络基础课的概念、基本原理和方法。
由于编写组成员均为研究生考试**线的辅导专家,负责和参与了历年的考试培训与辅导、教程编写、考试阅卷等方面的工作,因此,本书凝聚了专家们的知识、经验、心得和体会,集成了专家们的精力和心血。 本书由希赛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