计算机软件技术基础

第1 章 数据结构.............................................................................................................1
1.1 数据结构的基本概念.................................................................................................... 1
1.1.1 数据结构的研究内容及其重要性...................................................................... 1
1.1.2 数据结构的基本概念和术语............................................................................. 2
1.1.3 数据结构、数据类型和抽象数据类型.............................................................. 5
1.2 线性结构....................................................................................................................... 7
1.2.1 线性表............................................................................................................... 7
1.2.2 栈和队列......................................................................................................... 22
1.2.3 数组和广义表.................................................................................................. 29
1.2.4 串..................................................................................................................... 37
1.3 树和二叉树................................................................................................................. 39
1.3.1 树形结构基本概念.......................................................................................... 39
1.3.2 二叉树............................................................................................................. 42
1.3.3 二叉树的遍历.................................................................................................. 46
1.3.4 树、森林与二叉树的转换............................................................................... 49
1.3.5 哈夫曼树和哈夫曼编码................................................................................... 50
1.3.6 二叉排序树...................................................................................................... 53
1.4 图................................................................................................................................ 54
1.4.1 图的基本概念.................................................................................................. 54
1.4.2 有向图和无向图.............................................................................................. 54
1.4.3 子图与路径...................................................................................................... 56
1.4.4 连通图和连通分量.......................................................................................... 56
1.4.5 图的存储结构.................................................................................................. 57
1.4.6 图的遍历......................................................................................................... 59
1.5 查找和排序................................................................................................................. 61
1.5.1 查找................................................................................................................. 61
1.5.2 排序................................................................................................................. 69
本章小结.............................................................................................................................. 79
习题..................................................................................................................................... 79
第2 章 计算机操作系统................................................................................................ 91
2.1 计算机操作系统简介.................................................................................................. 91
2.1.1 操作系统概述.................................................................................................. 91
2.1.2 操作系统的发展及分类................................................................................... 92
2.1.3 操作系统的主要特征和功能........................................................................... 96
2 计算机软件技术基础
2.2 处理器管理................................................................................................................. 98
2.2.1 程序执行的基本特征...................................................................................... 98
2.2.2 进程的定义及特征.......................................................................................... 99
2.2.3 进程的状态和转换.........................................................................................100
2.2.4 进程的描述.....................................................................................................103
2.2.5 处理器调度.....................................................................................................107
2.2.6 进程调度........................................................................................................110
2.2.7 并发进程........................................................................................................113
2.2.8 临界区管理.....................................................................................................116
2.2.9 进程消息传递.................................................................................................124
2.2.10 死锁..............................................................................................................127
2.2.11 作业调度.......................................................................................................128
2.2.12 线程..............................................................................................................130
2.3 存储管理....................................................................................................................134
2.3.1 存储管理概述.................................................................................................134
2.3.2 连续存储管理.................................................................................................137
2.3.3 可变分区存储管理.........................................................................................138
2.3.4 主存扩充技术.................................................................................................140
2.3.5 分页式存储管理.............................................................................................141
2.3.6 分段式存储管理.............................................................................................144
2.3.7 段页式存储管理.............................................................................................145
2.3.8 虚拟存储管理.................................................................................................146
2.4 设备管理....................................................................................................................149
2.4.1 设备管理概述.................................................................................................149
2.4.2 I/O 控制方式..................................................................................................152
2.4.3 设备的分配.....................................................................................................155
2.4.4 设备无关性和缓冲技术..................................................................................157
2.4.5 设备驱动程序.................................................................................................159
2.5 文件管理....................................................................................................................160
2.5.1 文件系统的基本概念.....................................................................................160