华北电力大学2023硕士研究生考试大纲：软件工程专业基础综合

近日华北电力大学关于调整软件工程硕士研究生入学考试初试科目的通知发布，我校学术型硕士软件工程（083500）和专业型硕士软件工程（085405）专业的入学考试业务课二采用自命题科目“软件工程专业基础综合”，具体以学校发布的招生专业目录相关内容为准。

《软件工程专业基础综合》考试大纲

本门课程由数据结构和操作系统两门课程组成，两门课程各占 75分，具体要求如下：

第一部分：数据结构

一、考试的总体要求

掌握数据结构的基本概念、原理和方法。掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度和空间复杂度分析。

能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C语言设计与实现算法的能力。

二、考试的内容

1.绪论

数据结构的基本概念，数据的逻辑结构、存储结构。

算法的定义、特性和设计要求，算法的时间复杂度分析与空间复杂度分析。

2.线性表

线性表的定义；线性表的逻辑结构；线性表的存储结构（顺序存储、链式存储），两种存储方式的特点和适用场合；不同存储方式下基本操作的实现；线性表的应用。

3.栈与队列

栈：栈的定义和基本概念；栈的逻辑结构；栈的存储结构（顺序存储，链式存储）；不同存储方式下基本操作的实现；栈的应用。

队列：队列的定义和基本概念；队列的逻辑结构；队列的存储结构（顺序，链式）；不同存储方式下基本操作的实现；队列的应用。

4.二叉树与树

二叉树：二叉树的定义和基本概念；二叉树的基本性质；二叉树的逻辑结构；二叉树的存储结构（顺序、链式）；不同存储结构上的基本操作实现；二叉树的遍历及应用；线索二叉树的基本概念和构造。

树与森林：树（森林）的定义和基本概念；树（森林）的逻辑结构；树（森林）的存储结构（双亲表示法，孩子链表表示法，双亲孩子链表表示法，孩子兄弟链表表示法）；树（森林）的基本操作实现；树（森林）的遍历及应用。

树（森林）与二叉树之间的相互转换以及遍历的对应关系。

哈夫曼树（最优二叉树）和哈夫曼编码。

5.图

图的定义与基本概念；图的逻辑结构；图的存储结构（邻接矩阵、邻接表、邻接多重表、十字链表）；不同存储结构上的基本操作实现；图的遍历（深度优先遍历，广度优先遍历）及应用；图的应用（最小生成树、最短路径、AOV网及拓扑排序、AOE网及关键路径）。

6.查找

查找的基本概念与术语；静态查找表（顺序查找、折半查找、分块查找）；动态查找表（二叉排序树、二叉平衡树和 B-树）；哈希表（哈希表的概念、常用的哈希函数、解决冲突的方法）；查找算法的分析（ASL）及应用。

7.排序

排序的基本概念；插入类排序（直接插入排序、折半插入排序、希尔排序）、交换类排序（冒泡排序、快速排序）、选择类排序（简单选择排序、堆排序）、归并类排序（二路归并排序）、基数排序；各种内部排序算法的稳定性和时间复杂度与空间复杂度分析；排序算法的应用。

8．综合应用：根据实际问题，设计有效的数据结构和算法，并进行时间复杂度分析。

1 2