第一章 数据结构

【要点】

第一节 数据结构的基本概念

一、 什么是数据结构

数据结构主要研究计算机系统中数据的组织形式及其相互关系。

二、数据结构中的基本概念

数据、数据元素、数据项、数据结构、线性结构、非线性结构。

数据的存储方法可分为：顺序存储、链式存储、索引存储、散列存储。

三、抽象数据类型

抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。抽象数据类型的定义与使用实现了数据的封装和隐藏，为对象程序设计方法提供了基础，也使过程语言的可维护性大大提高。

第二节 线性表

一、线性表的概念

线性结构的基本特点是数据元素有序并有限。线性表是n（n≥0）个相同类型的元素a1，a2，an所构成的有限线性序列。

二、顺序表

在顺序表的存储结构中，数据元素按其逻辑次序依次存放在一组地址连续的存储单元里。

三、线性链表

采用链式存储结构的链表是用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零散分布在内存中的任何位置上。

四、循环链表

循环链表是一种首尾相接的链表。

第三节 栈、队列及数组

一、栈

栈是限制仅在表的一端进行插入和删除运算的线性表，它的特点是后进先出。

二、队列

队列是允许在线性表的一端进行数据元素插入操作而在另一端才能进行数据元素删除操作的线性表。

三、栈和队列的应用

栈和队列是应用非常广泛的数据结构之一。

第四节 非线性结构

一、树结构及其基本概念

树结构是结点之间有分支、层次关系的结构。

二、二叉树结构

二叉树是n个结点的有限集合（n≥0），它或者是空集（n=0）或者由一个根结点及两棵互不相交的、分别称做这个根的左子树和右子树的二叉树组成。

三、图

图G由两个集合V和E组成，记为G=(V,E)，其中V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集。

四、图的遍历

第五节 查找与排序

一、查找

查找分为简单查找方法（顺序查找、二分查找、分块查找）、树表查找和哈希查找。

二、排序

排序分为简单排序、快速排序以及归并排序。

【要求】

本章要求学生掌握数据结构、线性表、栈、队列、二叉树等概念，了解和掌握顺序表的插入算法、单链表的插入运算算法、二叉树的有关操作、图的有关操作、查找与排序算法等。

第二章 操作系统

【要点】

第一节 操作系统概论

一、操作系统的功能

操作系统主要有五大功能：处理机、存储器管理、设备管理、文件管理和作业管理。

二、操作系统的特征

操作系统具有以下特征：并发行、共享性、虚拟性和不确定性。

三、操作系统的分类

操作系统的基本类型有:批处理操作系统、分时操作系统、实时操作系统、网络操作系统、分布式操作系统。

第二节 处理机管理

一、进程的概念

进程是可并发执行的程序在给定数据集合上的一次执行过程；是系统进行资源分配合调度的一个独立的基本单位和实体；是指执行一个映象程序的总环境。

二、进程控制与进程调度

进程控制是对进程在其生命期的各种活动及状态转变实施有效的控制；进程调度的任务是协调和控制各进程对CPU的使用，按照某种策略动态地将处理机分配给处于就绪状态的某个进程。

三、进程互斥与同步

进程的互斥是由多个进程竞争同一共享资源而产生的相互制约的关系；进程之间通过执行时序上的某种限制而达到相互合作，这种因相互合作而产生的制约关系称为进程的同步。

四、进程的通信

目前常用的进程通信的高级方式有消息缓冲通信，管道通信和信箱通信。

五、死锁

对资源的管理使用不当，在一定条件下会导致系统发生随机故障，出现进程被阻塞的现象，即若干进程彼此互相等待对方所拥有且又不放的资源，其结果是谁也无法得到继续运行所需的全部资源，因而永远等待下去。这种现象称为死锁。

第三节 作业管理

一、作业的概念

一个作业，就是用户请求计算机系统执行的一次独立的上机任务，是能共享公共资源区域的一族有关进程（进程家族）。

二、作业控制

作业控制包括两方面含义：从用户角度看，作业控制是用户通过作业控制级接口，组织和控制其作业在计算机上的运行的全过程。从系统管理的角度看，作业控制是系统接受、分析并执行用户发出的控制命令，为作业的每个发展阶段提供必要的系统服务。

三、作业调度

作业从用户提交开始到真正占有处理机而被执行，要经过多级调度才能实现。

第四节 存储管理

一、存储管理的功能

存储管理主要有五个方面的功能：内存分配和回收、内存空间的共享、存储保护、地址映射、内存空间的扩充。

二、分区存储管理

分区存储管理的基本思想是把内存划分成若干个大小不等的连续区域，称为分区。每个作业可占用一个或多个分区。

三、覆盖与交换技术

覆盖就是一个作业的若干程序段，或几个作业的某些部分共享某一内存区域，即一个内存区域可以先后被不同的程序段重复使用，当某程序段不再需要该内存区域时另一程序段可占用。

交换技术是指在内外存之间交换程序和数据。

第五节 设备管理

一、数据传送控制方式

外设与内存间常用的数据传送方式有：中断控制方式、DMA方式和通道方式。

二、缓冲技术

缓冲技术的基本思想是：在内存中开辟一个或多个专用的区域，即缓冲区，作为CPU与I/O设备之间信息传送的集散地。

四、设备分配

设备分配的原则由设备特性及用户请求、系统中设备使用情况而定。

第六节 文件管理

一、文件系统的概念

由于软件资源是以文件形式存储的，因此，对软件资源的管理也就导致了文件系统的出现。

二、文件的组织

文件组织是指文件中信息的配置和构造方式。

三、文件目录

文件一般有一级目录结构、二级目录结构和多级目录结构。

【要求】

本章要求学生掌握操作系统的概念和功能、进程、作业概念，掌握进程调度的过程、作业调度过程以及存储管理和设备管理中的常用技术。

第三章 软件工程

【要点】

第一节 软件与软件生存周期

一、 软件工程及软件工程学的概念

软件工程学主要包括软件开发技术和软件工程管理两方面的内容。

二、软件生存周期的概念

一个软件从用户提出开发要求，到废弃不用为止的全过程，称为软件的生存周期。

第二节 软件的需求分析与软件设计

一、需求分析概述

需求分析的主要内容有：技术可行性、经济可行性和操作可行性。

二、结构分析方法

结构化分析方法简称SA方法，它适用于分析大型数据处理系统，它与设计阶段的结构化设计方法一起联合使用，能够较好地实现一个软件系统的研制。

三、数据流图

对数据流图中包含的所有元素的定义的集合构成了数据词典。

四、数据词典

对数据流图中包含的所有元素的定义的集合构成了数据词典。

五、软件设计准则

软件设计准则涉及软件结构的准则、模块化的准则以及模块独立性的准则几个方面的问题。

第三节 软件编程、软件测试及软件维护

一、程序设计语言

程序设计语言可以分为机器语言、汇编语言和高级语言三类。

二、编程风格

编程风格是指一个程序员在编程时，对程序的结构形式，行文方式及编写特点的要求。

三、面向对象的程序设计概念

面向对象软件开发方法又称OOSD(Object-Oriented Software Development)；OOSD包括面向对象分析（OOA）、面向对象设计（OOD）和面向对象程序设计（OOP）三个方面。

四、软件测试策略

软件的测试过程是按单元测试、组装测试、确认测试和系统测试四个步骤进行的。

五、常用的测试方法

常用的测试方法有黑盒测试和白盒测试两种。

六、软件维护的步骤与方法

具体的维护工作需要经过理解分析、修改和重新验证现有软件系统三个过程。

七、软件维护的副作用

软件维护的副作用可以分为三类：修改程序的副作用、修改数据的副作用和文档的副作用。

【要求】

要求学生掌握软件、软件生存周期概念，掌握软件工程方法的各个阶段的任务和工作流程。

第四章 数据库技术

【要点】

第一节 数据库技术概论

一、 数据、信息与数据处理

数据是一种物理符号序列，它的内容是事物特性的反映；信息是经过加工处理的数据，是人们消化理解了的数据，是数据的具体含义；数据处理是指将数据转换成信息的过程。

二、数据管理技术的发展

数据库管理技术的发展大致经历四个阶段：手工管理阶段、文件系统阶段、数据库系统阶段以及分布式数据库系统阶段。

三、数据库系统的组成

数据库系统由五个部分组成：硬件系统、数据库集合、数据库管理系统及相关软件、数据库管理员（DBA）和用户。

四、数据和数据联系的描述

第二节 数据模型及结构化查询语言――SQL

一、非关系模型

非关系模型有层次模型、网状模型和面向对象模型。

二、关系模型

关系模型是以二维表格结构作为基础的由若干个关系模式组成的集合。

三、关系运算

从集合论的观点来定义关系，关系是一个元数为K的元组集合，即这个关系有若干个元组，每个元组有K个属性值。

四、数据库的基本查询

查询是从数据库中提取出满足用户需要的数据，查询是由SELECT命令实现的。

【要求】

本章要求学生掌握数据库系统概念和数据模型的种类，掌握主要的SQL语句。

五、教材及主要参考资料

1、《软件技术基础》 张选芳 李廷元 付茂洺，中国铁道出版社，2016年1月

2、《C程序设计（第三版）》，谭浩强，清华大学出版社。