华北电力大学（北京）

华北电力大学2021年硕士生入学考试初试科目考试大纲

考试科目编号：844

考试科目名称：数据结构

一、考试的总体要求

掌握常用数据结构的逻辑结构、存储结构和基本操作，灵活运用所学的数据结构解决实际问题。

二、考试的内容

(一)基本概念和术语

(二)常用数据结构及算法

1、线性表

①线性表的特点;

②顺序表数据类型描述和基本操作的实现;

③单向链表的数据类型描述和基本操作的实现;

④单向循环链表、双向循环链表的数据类型描述和基本操作的实现;

⑤线性表的应用：两个线性表的合并、一元多项式的求和与求积。

2、栈与队列

①栈与队列的特点;

②顺序栈、链栈的数据类型描述和基本操作的实现;

③循环队列、链队列的数据类型描述和基本操作的实现;

④表达式求值的两种方法。

3、二叉树与树

①二叉树的特点和性质;

②二叉树的顺序存储与二叉链表的数据类型描述和基本操作的实现(创建、查找、递归遍历、非递归遍历、层次遍历)和遍历的应用;

③二叉树与树、森林的转换以及遍历的对应关系;

④树的存储结构：双亲表示、孩子链表、双亲孩子链表和孩子兄弟链表的数据类型描述;

⑤树的算法：创建、查找、插入、删除、遍历以及遍历的应用;

⑥表达式二叉树的创建与求值;

⑥哈夫曼树及哈夫曼编码。

4、图

①图的特点;

②邻接矩阵、邻接表的数据类型描述;

③图的创建、图的遍历、最小生成树、最短路径、AOV网及拓扑排序、AOE网及关键路径;

④图的遍历算法的应用。

(三)数据处理技术

1、查找

①静态查找：顺序查找(带岗哨)、折半查找;

②动态查找：二叉排序树和二叉平衡树的查找、插入和删除;

③哈希表：哈希函数、处理冲突的方法;

④查找性能分析(ASL)。

2、内排序

①插入类排序(直接插入排序、折半插入排序、希尔排序)

②交换类排序(冒泡排序、快速排序)

③选择类排序(简单选择排序、堆排序)

④归并类排序(二路归并排序)

⑤排序算法的复杂度分析

三、考试的题型

单选题、填空题(概念及算法)、算法应用题、算法设计题。

四、参考书目

1.林碧英主编，新编数据结构及算法教程，清华大学出版社.