(科目代码：955)

一、考核要求

本科目是电子通信、控制科学与工程等许多学科专业的基础理论课程，为招收智能信息处理专业硕士生而设置的具有选拔功能的水平考试。它的主要目的是测试考生对数据结构基础理论和应用的掌握程度。要求考生具有分析和解决问题的能力，并能加以灵活应用。

二、考核评价目标

数据结构考试的目标在于考查考生对数据结构的基础知识、基本理论和基本技能的掌握情况，考察考生综合运用所学知识分析和解决问题的能力。考生应能：

1．系统地理解数据结构的基本概念；

2．掌握各种基本数据结构(线性结构、树形结构、图形结构)的定义、应用和实现；

3．掌握常用的两种数据处理技术：查找和排序；

4．掌握在不同的存储结构上实现算法的设计思想，从中体会和掌握选择数据结构的方法和算法设计的思考方式及技能，提高分析问题和解决问题的能力。

三、考核内容

1．绪论

数据结构的基本概念，包括逻辑结构、物理结构的基本概念、两者之间的区别与联系。

算法的基本概念和性质。算法的复杂度的基本概念，并掌握对非递归代码的复杂度计算的基本方法。

2．线性表

线性表的逻辑结构定义。线性表的顺序结构实现，以及顺序结构下的基本操作的实现，

并能写出操作代码。线性表的链式结构实现，以及链式结构下的基本操作的实现，并能写出操作代码。能够设计针对顺序结构和链式结构线性表的一般应用问题的算法，并编写算法代码。

栈的基本概念、栈的性质。栈的顺序结构和链式结构实现，以及相应的操作的实现，能够写出操作代码。栈与递归的关系，能够编写递归算法，能够将递归算法转换为非递归形式。栈的应用方法，能够运用栈解决相关问题，并编写出算法代码。队列的基本概念和性质。队列的顺序结构和链式结构实现，以及相应操作的实现，能够写出操作代码。

3．串

串的概念，串与一般线性表的差别。串的基本操作的实现。串的朴素模式匹配算法。改进KMP算法的思想和步骤，能够手工计算出模式串的nextval向量。

4．数组、稀疏矩阵和广义表

了解多维数组的概念，以及多维数组的一维数组实现。掌握多维下标向一维下标的换算算法，并能进行手工计算。掌握稀疏矩阵的三元组结构。了解广义表的概念。

5．树和二叉树

树的定义和性质。

二叉树的概念。二叉树的基本性质，并能够进行描述和证明。掌握二叉树的二叉链结构的实现。掌握二叉树的前序遍历、中序遍历、后序遍历和层次遍历规则，能够手工写出二叉树的遍历序。掌握二叉树的遍历性质，能够根据前序+中序或中序+后序还原出二叉树。掌握二叉树的前序、中序和后序递归遍历算法、前序、中序非递归遍历算法，并能够写出算法代码。

了解线索化二叉树的概念、遍历算法和线索化算法。

了解哈夫曼树的概念。掌握哈夫曼算法的思想和步骤，能够手工计算哈夫曼树。了解哈夫曼编码的概念，能够手工计算哈夫曼编码。

了解树、森林和二叉树的关系。

6．图

了解图的定义。掌握图的邻接矩阵、邻接表的实现方法。掌握图的深度优先和广度优先遍历算法，能够手工计算图的深度优先遍历序和广度优先遍历序。掌握图的连通性问题的求解算法，包括生成树/森林计算、最小生成树计算（Prim算法和Kruskal算法）。掌握关键路径问题的求解算法，并能够进行手工计算。掌握单源起点最短路径算法（Dijkstra算法）和任两点间最短路径算法（Floyd算法），并能够进行手工计算。

7．查找

掌握静态表的概念和折半查找算法，并能够进行手工计算。掌握散列表的基本概念，散列函数的基本设计技巧。掌握二叉排序树的概念，以及二叉排序树上的查找、插入、删除算法，并能够进行手工计算。掌握平衡二叉树的概念，以及平衡二叉树的插入和调整算法，并能够进行手工计算。了解B-、B+树的概念，以及B-树的插入和删除算法。

8．内排序

掌握简单排序法（选择排序、插入排序、交换排序）的算法思想和步骤，能够写出排序过程。掌握快速排序的算法思想和步骤，能够写出排序过程。掌握堆排序的算法思想和步骤，能够写出排序过程（建堆过程、排序过程）。掌握归并排序的算法思想和步骤，能够写出排序过程。掌握基数排序的算法思想和步骤，能够写出排序过程。

了解各种排序方法的特点，能够针对特定问题背景选择适当的排序方法。

更多学历考试信息请查看学历考试网