沈阳建筑大学

2021年硕士研究生考试复试 数据结构 科目考试大纲

一、考查目标

《数据结构》是计算机科学中的一门重要的基础理论课，该课程考核的内容主要包括复杂度分析、链表、栈和队列、递归、二叉树、B-树、图、堆与优先级队列、排序、哈希方法等。通过本课程学习，理解计算机加工的数据结构的特性，掌握各类数据结构的灵活应用，为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并掌握算法的时间复杂度和空间复杂度的简要分析技术。

二、考核形式与试卷结构

(一)试卷满分及考试时间

满分为100分，考试时间为2小时。

(二)答题方式

答题方式为闭卷、笔试。

(三)试卷内容结构

客观题，包括选择题、填空题、判断题。主观题，包括程序设计和代码编写题。

(四)试卷题型结构

客观题20%—30%分，程序设计和代码编写题占70%—80%分。

三、考查内容及要求

(一)数据结构和算法简介

1. 数据结构、逻辑结构、存储结构和抽象数据类型的基本概念。

2. 各种算法描述方法和算法设计。

3. 算法的复杂度分析。

(二)线性结构

1. 线性表的概念、定义、逻辑结构和存储结构。

2. 掌握线性表的顺序结构及其各种基本运算。

3. 单链表、循环链表、双向链表的存储结构及其各种基本运算，链表的应用。

4. 栈的定义、表示、实现和应用。

5. 递归的概念和递归的实现过程。

6. 队列的定义以及顺序和链式存储结构的实现。

7. 串的基本概念及顺序和链式存储结构，串的各种基本运算，串的模式匹配算法。

8. 数组的顺序存储结构。

9. 稀疏矩阵的三元组存储结构和基本运算，十字链表存储结构。

10. 广义表的基本概念，广义表的存储结构。

(三)树结构

1. 树的基本概念及其存储结构。

2. 掌握二叉树的定义、性质以及各种存储结构和遍历算法。

3. 线索二叉树的概念、存储结构及线索化算法。

4. 哈夫曼树的概念、存储结构和应用。

(四)图结构

1. 图的基本概念，掌握图的邻接矩阵和邻接表的存储结构。

2. 十字链表，邻接多重表等存储结构。

3. 掌握图的深度优先和广度优先遍历算法。

4. 图的连通性、最小生成树的概念。

5. 求最小生成树算法。

(五)查找

1. 查找的概念及其效率的评价方法。

2. 静态查找表的概念，熟练掌握顺序、折半和分块查找算法。

3. 动态查找表和二叉排序树的概念。

4. 平衡二叉树的概念。

5. 哈希表的含义，掌握哈希函数的构造和处理冲突的基本方法。

(六)排序

1. 插入类排序的算法：直接插入排序、希尔排序。

2. 交换类排序的算法：冒泡排序、快速排序。

3. 选择类排序的算法：简单选择排序、堆排序。

4. 归并排序、基数排序的思想，外排序的概念。

四、考试用具说明

考试时仅需要携带笔。

五、参考书目或参考资料

1. 《数据结构》(C语言版)，严蔚敏、吴伟民，清华大学出版社，2011。