研究生入学考试《数据结构》考试大纲

一、考查目标

1、掌握数据结构的基本概念、基本原理和基本方法。

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

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

二、知识点解析

1、绪论

掌握数据结构的基本概念，常见的4种基本数据结构（集合、线性、树形、图状）的特点，顺序存储结构与链式存储结构各自的优缺点；掌握时间和空间复杂度的概念及度量方法。

2、线性表

掌握线性表的定义和基本操作与实现；在线性表实现方面，掌握线性表的两种存储结构：顺序存储结构和链式存储结构；掌握在顺序表上实现插入、删除、定位等运算的算法；在链式存储结构方面，理解头指针、头结点、首元结点和元素结点的差别，掌握单链表、循环链表、双向链表等几种常用链表的特点及其插入、删除、遍历等操作，并能够设计出实现线性表其他运算的算法；从时间复杂度和空间复杂度的角度综合比较线性表在顺序和链式存储结构下的特点及其各自使用的场合。

3、栈和队列

掌握栈和队列的定义及其相关概念，包括：顺序栈、链栈、循环队列、链队列等，栈与队列存取数据的特点；掌握顺序栈和链栈上的进栈和出栈的算法，理解栈空和栈满的特点，能够利用栈这种数据结构解决实际问题；掌握在链队列上实现入队列和出队列的算法；理解构造循环队列的原理以及队列空及队列满的条件，掌握循环队列中入队列与出队列算法。

4、数组和广义表

掌握数组采用顺序存储表示时两种存储方式：按行优先和按列优先，能够对多维数组中的某个数组元素的地址进行求解；掌握特殊矩阵（对称矩阵、三角矩阵、对角矩阵）的压缩存储方法；掌握稀疏矩阵的三种不同存储方式：三元组、行逻辑链接的顺序表、十字链表存储等；掌握广义表的概念，特别是表头与表尾的定义，掌握广义表链式存储结构的两种表示形式：头尾链表存储表示和扩展线性链表存储表示。

5、树和二叉树

掌握树的定义和基本术语；掌握二叉树的定义以及特殊二叉树的定义，如完全二叉树及满二叉树，能够灵活应用二叉树的5个性质，掌握二叉树的两种存储结构：顺序存储结构和链式存储结构（二叉链表）；掌握二叉树三种遍历方式（先序遍历、中序遍历、后序遍历）的递归算法，能够运用遍历的递归算法编写程序解决实际问题，能够利用二叉树的先序中序序列或后序中序序列构造二叉树；掌握树的三种存储结构：双亲表示法，孩子表示法以及孩子兄弟表示法，掌握树、二叉树、森林之间的相互转换的方法，掌握森林的两种遍历方法：先序遍历和中序遍历；理解赫夫曼树的特点，掌握赫夫曼树的构造过程及赫夫曼编码的原理。

6、图

掌握图的定义和相关的术语；掌握图的三种存储结构：数组表示法，邻接表和十字链表；掌握图的两种遍历方式：深度优先搜索和广度优先搜索；掌握图的相关应用，如最小生成树，拓扑排序，关键路径，最短路径等，理解各种算法的原理及其解决的实际问题。

7、查找

掌握查找表的定义以及两种查找表（静态查找表和动态查找表）的特点及相关操作；在静态查找表方面，掌握顺序表、有序表的查找（折半查找）、索引顺序表的查找的原理，能够运用平均查找长度概念对查找性能进行分析；在动态查找表方面，掌握二叉排序树的定义、构造过程、插入和删除操作以及性能分析，掌握平衡二叉树的定义及特点，掌握平衡调整的4种方式（LL型、LR型、RR型，RL型），掌握B-树的定义、插入和删除操作及性能分析；掌握哈希表的定义，构造方法、处理冲突方法、查找及性能分析。

8、排序

掌握排序的定义以及稳定和不稳定排序方法的定义；掌握直接插入排序、希尔排序、起泡排序、快速排序、简单的选择排序、堆排序、归并排序等排序算法的原理并能灵活运用。

三、教材选择

作为高校普遍使用的数据结构课程的教材，数据结构(C语言版)(第2版)(严蔚敏等编著,人民邮电出版社)是我院考研教材。该书比较全面系统地介绍了线性表、树、图等基本类型的数据结构及其应用，同时介绍了查找和排序的各种实现方法及其综合分析比较，并有配套的习题集供考生练习。

考试分值为150分，考试时间为180分钟。