2017年西北师范大学955数据结构考研大纲

硕士研究生入学统一考试
《数据结构》科目大纲
(科目代码：955)
学院名称(盖章)：物理与电子工程学院
学院负责人(签字)：
编制时间： 2014 年 7 月 12 日
《数据结构》科目大纲
(科目代码：955)
一、考核要求
本科目是电子通信、控制科学与工程等许多学科专业的基础理论课程，为招收智能信息处理专业硕
士生而设置的具有选拔功能的水平考试。它的主要目的是测试考生对数据结构基础理论和应用的掌握程
度。要求考生具有分析和解决问题的能力，并能加以灵活应用。
二、考核评价目标
数据结构考试的目标在于考查考生对数据结构的基础知识、基本理论和基本技能的掌握情况，考察
考生综合运用所学知识分析和解决问题的能力。考生应能：
1．系统地理解数据结构的基本概念；
2．掌握各种基本数据结构(线性结构、树形结构、图形结构)的定义、应用和实现；
3．掌握常用的两种数据处理技术：查找和排序；
4．掌握在不同的存储结构上实现算法的设计思想，从中体会和掌握选择数据结构的方法和算法设计
的思考方式及技能，提高分析问题和解决问题的能力。
三、考核内容
1．绪论
数据结构的基本概念，包括逻辑结构、物理结构的基本概念、两者之间的区别与联系。
算法的基本概念和性质。算法的复杂度的基本概念，并掌握对非递归代码的复杂度计算的基本方法。
2．线性表
线性表的逻辑结构定义。线性表的顺序结构实现，以及顺序结构下的基本操作的实现，
并能写出操作代码。线性表的链式结构实现，以及链式结构下的基本操作的实现，并能写出操作代
码。能够设计针对顺序结构和链式结构线性表的一般应用问题的算法，并编写算法代码。
栈的基本概念、栈的性质。栈的顺序结构和链式结构实现，以及相应的操作的实现，能够写出操作
代码。栈与递归的关系，能够编写递归算法，能够将递归算法转换为非递归形式。栈的应用方法，能够
运用栈解决相关问题，并编写出算法代码。队列的基本概念和性质。队列的顺序结构和链式结构实现，
以及相应操作的实现，能够写出操作代码。
3．串
串的概念，串与一般线性表的差别。串的基本操作的实现。串的朴素模式匹配算法。改进KMP算法
的思想和步骤，能够手工计算出模式串的nextval向量。
4．数组、稀疏矩阵和广义表
了解多维数组的概念，以及多维数组的一维数组实现。掌握多维下标向一维下标的换算算法，并能
进行手工计算。掌握稀疏矩阵的三元组结构。了解广义表的概念。
5．树和二叉树
树的定义和性质。
二叉树的概念。二叉树的基本性质，并能够进行描述和证明。掌握二叉树的二叉链结构的实现。掌
握二叉树的前序遍历、中序遍历、后序遍历和层次遍历规则，能够手工写出二叉树的遍历序。掌握二叉
树的遍历性质，能够根据前序+中序或中序+后序还原出二叉树。掌握二叉树的前序、中序和后序递归遍
历算法、前序、中序非递归遍历算法，并能够写出算法代码。
了解线索化二叉树的概念、遍历算法和线索化算法。
了解哈夫曼树的概念。掌握哈夫曼算法的思想和步骤，能够手工计算哈夫曼树。了解哈夫曼编码的
概念，能够手工计算哈夫曼编码。
了解树、森林和二叉树的关系。
6．图
了解图的定义。掌握图的邻接矩阵、邻接表的实现方法。掌握图的深度优先和广度优先遍历算法，
能够手工计算图的深度优先遍历序和广度优先遍历序。掌握图的连通性问题的求解算法，包括生成树/
森林计算、最小生成树计算（Prim算法和Kruskal算法）。掌握关键路径问题的求解算法，并能够进行手
工计算。掌握单源起点最短路径算法（Dijkstra算法）和任两点间最短路径算法（Floyd算法），并能够进
行手工计算。
7．查找
掌握静态表的概念和折半查找算法，并能够进行手工计算。掌握散列表的基本概念，散列函数的基
本设计技巧。掌握二叉排序树的概念，以及二叉排序树上的查找、插入、删除算法，并能够进行手工计
算。掌握平衡二叉树的概念，以及平衡二叉树的插入和调整算法，并能够进行手工计算。了解B-、B+树
的概念，以及B-树的插入和删除算法。
8．内排序
掌握简单排序法（选择排序、插入排序、交换排序）的算法思想和步骤，能够写出排序过程。掌握
快速排序的算法思想和步骤，能够写出排序过程。掌握堆排序的算法思想和步骤，能够写出排序过程（建
堆过程、排序过程）。掌握归并排序的算法思想和步骤，能够写出排序过程。掌握基数排序的算法思想
和步骤，能够写出排序过程。
了解各种排序方法的特点，能够针对特定问题背景选择适当的排序方法。