2024年北京航空航天大学非全日制研究生招生考试《软件工程基础综合》考试大纲

来源：在职研究生招生信息网发布时间：2023-12-14 13:19:59

　　一、绪论

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

　　二、线性表与数组

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

　　三、堆栈与队列

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

　　四、树与二叉树

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

　　五、图

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

　　六、内排序

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

　　七、递归分析技术

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

　　八、动态规划法

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

　　九、贪心法

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

　　十、字符串匹配

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