《软件工程专业基础综合》考试大纲
本门课程由数据结构和操作系统两门课程组成，两门课程各占 75分，具体要求如下：
第一部分：数据结构
一、考试的总体要求
掌握数据结构的基本概念、原理和方法。掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度和空间复杂度分析。
能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C语言设计与实现算法的能力。
二、考试的内容
1.绪论
数据结构的基本概念，数据的逻辑结构、存储结构。
算法的定义、特性和设计要求，算法的时间复杂度分析与空间复杂度分析。
2.线性表
线性表的定义；线性表的逻辑结构；线性表的存储结构（顺序存储、链式存储），两种存储方式的特点和适用场合；不同存储方式下基本操作的实现；线性表的应用。
3.栈与队列
栈：栈的定义和基本概念；栈的逻辑结构；栈的存储结构（顺序存储，链式存储）；不同存储方式下基本操作的实现；栈的应用。
队列：队列的定义和基本概念；队列的逻辑结构；队列的存储结构（顺序，链式）；不同存储方式下基本操作的实现；队列的应用。
4.二叉树与树
二叉树：二叉树的定义和基本概念；二叉树的基本性质；二叉树的逻辑结构；二叉树的存储结构（顺序、链式）；不同存储结构上的基本操作实现；二叉树的遍历及应用；线索二叉树的基本概念和构造。
树与森林：树（森林）的定义和基本概念；树（森林）的逻辑结构；树（森林）的存储结构（双亲表示法，孩子链表表示法，双亲孩子链表表示法，孩子兄弟链表表示法）；树（森林）的基本操作实现；树（森林）的遍历及应用。
树（森林）与二叉树之间的相互转换以及遍历的对应关系。
哈夫曼树（最优二叉树）和哈夫曼编码。
5.图
图的定义与基本概念；图的逻辑结构；图的存储结构（邻接矩阵、邻接表、邻接多重表、十字链表）；不同存储结构上的基本操作实现；图的遍历（深度优先遍历，广度优先遍历）及应用；图的应用（最小生成树、最短路径、AOV网及拓扑排序、AOE网及关键路径）。
6.查找
查找的基本概念与术语；静态查找表（顺序查找、折半查找、分块查找）；动态查找表（二叉排序树、二叉平衡树和 B-树）；哈希表（哈希表的概念、常用的哈希函数、解决冲突的方法）；查找算法的分析（ASL）及应用。
7.排序
排序的基本概念；插入类排序（直接插入排序、折半插入排序、希尔排序）、交换类排序（冒泡排序、快速排序）、选择类排序（简单选择排序、堆排序）、归并类排序（二路归并排序）、基数排序；各种内部排序算法的稳定性和时间复杂度与空间复杂度分析；排序算法的应用。
8．综合应用：根据实际问题，设计有效的数据结构和算法，并进行时间复杂度分析。