第一章 基本数据结构 1
1.1 绪论 1
1.1.1 计算机应用与非数值运算 1
1.1.2 数据、数据项、数据元素与数据结构 2
1.1.3 算法的五大特性 4
1.1.4 算法描述语言和算法分析 5
1.2 线性表 8
1.2.1 线性表概念与运算 8
1.2.2 线性表的顺序存储结构 10
1.2.3 线性表的链式存储结构 16
1.2.4 循环链表与双向链表 22
1.3 栈 26
1.3.1 栈的定义 26
1.3.2 栈的运算 26
1.3.3 栈的存储结构及算法 27
1.3.4 栈的应用-表达式求值 31
1.4 队列的存储结构及算法 33
1.4.1 顺序队列 33
1.4.2 链队列 36
1.4.3 队列的应用 38
1.5 数组 38
1.5.1 数组的定义及运算 39
1.5.2 数组的顺序存储结构 39
1.5.3 稀疏矩阵的存储表示 42
1.5.4 稀疏矩阵转置算法 44
1.5.5 规则矩阵的压缩存储 50
1.6 串 51
1.6.1 串的基本概念 51
1.6.2 串的顺序表示法 52
1.6.3 串的链接表示法 54
1.6.4 串的基本运算 55
1.7 树 58
1.7.1 树的定义、基本术语和存储结构 59
1.7.2 二叉树 60
1.7.3 二叉树的遍历 65
1.7.4 树、森林与二叉树的关系 69
1.7.5 哈夫曼树与哈夫曼算法 71
1.8 查找 74
1.8.1 概念和术语 74
1.8.2 顺序表查找 75
1.8.3 散列查找 80
1.8.4 各种查找算法的比较 88
1.9 排序 89
1.9.1 基本概念 89
1.9.2 归并排序 90
1.9.3 插入排序 91
1.9.4 选择排序 95
1.9.5 交换排序 99
1.10 试题分析 104
1.10.1 单选题 104
1.10.2 填空题 111
1.10.3 判断题 117
1.10.4 编程题 118
习题一 120
第二章 操作系统基础 121
2.1 操作系统概念 121
2.1.1 单道程序设计与多道程序设计 121
2.1.2 什么是操作系统 122
2.1.3 操作系统的功能 123
2.1.4 操作系统类型 124
2.2 处理机管理 127
2.2.1 进程的概念与特征 127
2.2.2 进程的状态及进程控制块 128
2.2.3 进程控制 130
2.2.4 进程的互斥与同步 131
2.2.5 进程通信 133
2.2.6 进程调度与调度算法 135
2.2.7 死锁 138
2.3 作业管理 141
2.3.1 作业概念 141
2.3.2 作业控制 142
2.3.3 作业调度 142
2.4 存储管理 144
2.4.1 存储管理概述 144
2.4.2 虚拟存储器 145
2.4.3 分区存储管理 146
2.4.4 交换与覆盖技术 148
2.4.5 分页存储管理 149
2.4.6 分段存储管理 150
2.4.7 段页式存储管理 152
2.5 设备管理 152
2.5.1 设备管理简介 153
2.5.2 数据传送方式、缓冲技术与设备分配 153
2.5.3 虚拟设备与SPOOLing技术 155
2.5.4 输入输出管理 156
2.6 文件管理 156
2.6.1 文件系统基础知识 157
2.6.2 文件的物理结构和逻辑结构 157
2.6.3 文件目录 158
2.6.4 文件共享与保护 159
2.6.5 文件存储空间管理 160
2.6.6 文件操作 160
2.7 网络操作系统 161
2.7.1 概述 161
2.7.2 网络通信模块 163
2.7.3 网络中的进程管理 164
2.8 Windows NT操作系统分析 164
2.8.1 Windows NT概述 164
2.8.2 Windows NT操作系统 165
2.8.3 用户账号、工作组、组与域 167
2.8.4 网络协议 169
2.8.5 Windows NT设计目标 170
2.8.6 Windows NT功能介绍 171
2.9 Unix操作系统分析 175
2.9.1 Unix操作系统的发展过程与主要特点 175
2.9.2 设计思想 176
2.9.3 操作界面 177
2.9.4 系统结构 182
2.10 试题分析 190
2.10.1 单选题 190
2.10.2 填空题 196
2.10.3 判断题 197
2.10.4 问答题 198
习题二 199
第三章 软件工程思想和方法 201
3.1 概述 201
3.2 软件 202
3.2.1 软件的概念和特点 202
3.2.2 软件的发展过程和软件危机 205
3.3 软件工程及软件工程学 209
3.3.1 概述 209
3.3.2 软件工程 210
3.3.3 软件工程的基本原理和目标 211
3.3.4 软件工程模式 212
3.4 软件生存周期 213
3.4.1 软件生存周期 213
3.4.2 软件生存周期模型 216
3.5 软件需求分析 219
3.5.1 需求分析概述 219
3.5.2 软件需求说明书 222
3.5.3 需求分析的原则及步骤 222
3.5.4 结构化分析方法 225
3.6 软件设计 231
3.6.1 软件设计的任务、步骤和方法 231
3.6.2 软件设计准则 233
3.6.3 总体设计方法——结构化设计 236
3.6.4 详细设计方法——结构化程序设计 238
习题三 240
第四章 数据库系统原理 241
4.1 数据库系统的概念 241
4.1.1 基本概念 241
4.1.2 数据库技术的产生与发展 243
4.1.3 数据库管理系统的功能与组成 243
4.2 数据模型 244
4.2.1 数据模型的概念 244
4.2.2 数据模型的组成要素 245
4.2.3 三个世界 245
4.2.4 概念数据模型 246
4.2.5 逻辑数据模型 247
4.3 数据库系统的体系结构与数据独立性 248
4.3.1 数据库系统的三级模式结构 248
4.3.2 数据的独立性 250
4.4 实体—联系模型 251
4.5 关系模型 256
4.5.1 关系数据结构 256
4.5.2 关系数据操作 258
4.5.3 关系完整性约束 261
4.6 关系数据库管理系统 263
4.7 关系数据库标准语言SQL 264
4.7.1 SQL的特点和组成部分 264
4.7.2 SQL语言的基本概念 265
4.7.3 SQL数据定义 266
4.7.4 SQL数据查询 267
4.8 数据库设计 272
4.8.1 数据库设计的内容、特点及设计方法 273
4.8.2 数据库设计步骤 274
习题四 277
参考文献 280