《软件工程基础综合》考研大纲

《软件工程基础综合》考研内容包括数据结构与算法、软件工程和操作系统三部分内容，各占三分之一，各部分考试范围如下。

第一部分：数据结构与算法

一、绪论

包括但不限于数据结构和算法的基本概念，主要内容有：数据的逻辑结构与存储结构；算法的定义、基本性质和算法分析的基本概念，包括采用大O形式表示时间复杂度和空间复杂度。

二、线性表与数组

包括但不限于线性表与数组的概念、各种存储结构和操作，主要内容有：线性关系、线性表的定义，线性表的基本操作；线性表的顺序存储结构和操作的实现；线性链表及其操作；循环链表及其操作；双向链表及其操作；链表的应用；一维数组和二维数组的存储；矩阵的压缩存储的基本概念；对称矩阵、对角矩阵以及三角矩阵的压缩存储。

三、堆栈与队列

包括但不限于堆栈与队列的基本概念、操作和应用，主要内容有：堆栈与队列的基本概念与基本操作；堆栈与队列的顺序存储结构与链式存储结构的构造原理；在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计；堆栈和队列在解决实际问题中应用。

四、树与二叉树

包括但不限于树与二叉树的基本概念和操作，主要内容有：树、二叉树、完全二叉树与满二叉树的基本概念；二叉树的顺序存储结构与二叉链表存储结构的基本原理；二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，重点是二叉树在以二叉链表为存储结构的遍历算法（包括递归和非递归算法）的设计与应用；线索二叉树的基本概念；二叉排序树的基本概念、建立(插入)、删除结点、查找以及平均查找长度（ASL）的计算；哈夫曼树的基本概念和简单应用。

五、图

包括但不限于图的基本概念和操作，主要内容有：图的基本概念、名词术语；图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点；图的深度优先搜索与广度优先搜索，连通分量；最小（代价）生成树、最短路径、AOV网与拓扑排序、AOE网与关键路径的基本概念和算法原理。

六、内排序

包括但不限于内排序的基本概念、各类算法实现原理和应用，主要内容有：排序的基本概念，各种内排序方法的基本原理和特点；插入排序法（含折半插入排序法）；选择排序法；泡排序法；谢尔排序法；快速排序法；堆排序法；二路归并排序法。

七、递归分析技术

包括但不限于递归分析技术的基本概念和操作，主要内容有：掌握递归算法的分析步骤和计算复杂度分析方法；了解递归方程的求解方法；置换法；迭代法；递归树法；主方法。

八、动态规划法

包括但不限于动态规划法的基本概念和主要思想，主要内容有：动态规划法的特征，包括最优子结构和重叠子问题；掌握装配线调度问题、钢条切割问题、矩阵链相乘问题、最长相同子序列问题、最优二叉搜索树问题、Floyd-Warshall算法求最短路径等问题的动态规划设计方法。

九、贪心法

包括但不限于贪心法的基本概念和主要思想，主要内容有：贪心法的基本特征，包括贪婪选择属性；掌握活动安排问题、背包问题、霍夫曼编码问题、Dijkstra算法求最短路径等问题的贪心策略设计。

十、字符串匹配

包括但不限于字符串匹配的基本概念、各类算法实现原理和应用，主要内容有：各类字符串匹配算法的基本原理、特点和计算复杂度分析；有限自动机字符串匹配算法；KMP算法。

第二部分：软件工程

一、软件工程概述

包括但不限于软件、软件工程等基本概念，主要内容有：软件的概念、特征和分类；软件危机产生的原因和表现；软件工程的概念和原则；软件工程知识体以及相关标准。

二、软件工程过程

包括但不限于软件生命周期和基本过程模型等基本概念，主要内容有：软件生命周期概念和各个阶段，典型软件过程模型：瀑布模型、快速原型模型、螺旋模型、统一过程模型、敏捷模型等。

三、软件需求分析

包括但不限于需求和需求分析相关的概念和应用，主要内容包括：软件需求的基本概念、功能需求、非功能需求和需求的评价准则；常见的需求调方法：竞品分析、观察、访谈、开会、原型和问卷调查等；结构化需求分析基本概念，数据流图、状态转换图和ER图的基本用法；基于用例的需求建模方法和过程，参与者、用例、用例图、用例文档的基本概念，基于用例方法开展需求建模实践；面向对象技术的基本概念，对象和类，面向对象的基本原则：抽象、封装、分解、泛化、多态、分层和复用等；可视化建模语言UML的基本概念、UML特点，UML基本构造块和通用机制，常见的UML图：用例图、活动图、类图、对象图、包图、顺序图、通信图、状态机图、构件图和部署图等；利用UML开展面向对象的分析基本过程，抽取分析类：边界类、控制类和实体类，基于顺序图、通信图等开展交互分析，定义分析类的职责和属性，分析类的关系：泛化关系、关联关系、聚合关系和组合关系。

四、软件设计

包括但不限于软件设计的概念和应用，主要内容有：软件设计的基本原则，概要设计（架构设计）和详细设计（构件设计）的基本过程；软件体系结构（架构）的基本概念和过程、典型架构模式（风格）、性能、安全、可靠性等关键质量属性设计；面向数据流设计的基本概念，流程图、判定表、判定树和过程设计语言等基本设计方法；数据库设计的基本概念，界面设计的基本概念；面向对象设计基本概念，设计类的操作、方法和状态设计，关联关系设计，依赖关系、泛化关系等设计，面向对象设计模式的基本概念。

五、软件构造与测试

包括但不限于软件构造和测试的概念和应用，主要内容有：软件构造的基本概念、一般原则和要点，设计模型与实现模型的映射；软件测试的基本概念、原则和方法；测试用例的基本概念和设计方法，黑盒测试概念和方法：等价类、边界值、因果图等，白盒测试概念和方法：程序流图、逻辑覆盖、圈复杂度等；单元测试、集成测试、系统测试、验收测试、回归测试等基本概念和方法。

六、软件项目管理基础

包括但不限于软件项目管理的基本概念，主要内容有：软件项目管理基础及项目规划；软件成本管理、风险管理、质量管理、配置管理等各类管理概念。

第三部分：操作系统

一、操作系统概述

包括但不限于操作系统的基本概念，主要包括：操作系统基本概念；内核态与用户态、中断、异常和系统调用等。

二、进程管理

包括但不限于进程管理的相关概念和应用，主要内容有：进程、线程的基本概念以及两者的区别；进程控制块、进程的状态与转换；进程同步的基本概念，实现临界区互斥的基本方法，信号量机制及P、V操作，了解经典同步问题，并通过信号量机制解决进程同步问题；进程间通信，包括共享存储系统、消息传递系统、管道；进程调度的基本准则，典型调度算法：先来先服务调度算法、短作业(短进程、短线程)优先调度算法、时间片轮转调度算法、优先级调度算法；死锁的形成原因与必要条件，死锁预防、死锁避免、死锁检测和解除。

三、内存管理

包括但不限于内存管理的相关概念和应用，主要内容有：程序装入与链接，逻辑地址与物理地址空间，重定位，内存保护；分区管理，交换与覆盖技术；分页管理方式，分段管理方式，段页式管理方式；虚拟内存基本概念和局部性原理，缺页中断，地址变换过程；页面置换算法：最佳置换算法(OPT)、先进先出置换算法(FIFO)、最近最少使用置换算法(LRU)、时钟置换算法(CLOCK)，工作集模型；

四、设备管理

包括但不限于设备管理的基本概念和应用，主要内容有：I/O控制方式：程序控制、中断、DMA、通道，缓冲技术；假脱机技术(SPOOLing)。

五、文件系统

包括但不限于文件、文件系统的基本概念和应用，主要内容有：文件与文件系统的基本概念，组织方式，文件控制块，目录结构，文件存取控制，文件系统层次结构；磁盘的结构，磁盘调度算法，廉价冗余磁盘阵列。