951“数据结构”复习参考提纲

一、 考察目标

通信、计算机学科专业基础综合考试涵盖数据结构学科专业基础课程。要求考生比较系统地掌握数据结构专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

二、 考试形式和试卷结构

1、 试卷满分及考试时间：本试卷满分为150，考试时间为180分钟

2、 答题方式：闭卷，笔试

3、 试卷内容结构：数据结构150分

三、 总体要求

“数据结构”要求学生掌握数据结构的基本理论和基本方法，熟悉解决程序设计问题所需的基本数据结构和基础算法，掌握各种程序设计中常用的数据结构的基本概念、对应的逻辑结构和存储结构及其基本运算，各种数据结构的基本特点和典型应用场景。熟练使用基础数据结构进行算法程序设计。

四、 各章复习要点

（一）数据结构基本概念       

1.复习内容

数据结构的概念，数据结构的逻辑结构和物理结构，程序设计的关键技术。

2.具体要求

数据结构的概念、名词和术语

数据结构的逻辑结构

数据结构的物理结构

（二）线性表       

1.复习内容

线性表的基本概念和运算，顺序表的基本运算，单链表、循环链表、双向链表的基本运算，顺序表和链表的应用实例分析。

2.具体要求

线性表的概念和基本运算

线性表的顺序存储表示及算法

线性表的链式存储表示及算法

顺序表及链表的应用

 （三）栈和队列      

1.复习内容

栈和队列的基本概念、基本操作、存储结构和应用。

2.具体要求

 栈和队列的基本概念和基本操作

栈和队列的顺序存储结构

栈和队列的链式存储结构

栈和队列的应用

（四）串和数组

1.复习内容

串的基本概念、运算和存储结构，模式匹配算法，数组的概念、存储结构，矩阵压缩存储。

2.具体要求

 串的基本概念和基本操作

串的存储结构

模式匹配算法

数组的概念

数组的存储结构

矩阵压缩存储

（五）树

1.复习内容

数、二叉树、森林的基本概念，二叉树的遍历方法，树和森林之间的转换方法，二叉树的应用。

2.具体要求

树结构的基本概念、术语

二叉树的性质和存储表示。

二叉树的遍历及递归算法的运用

树和森林（存储表示、转化方法、树的遍历）

二叉树的应用（哈夫曼树及应用、二叉排序树）

（六）图 

1.复习内容

图的基本概念和存储结构，图的遍历，生成树和最小生成树，最短路径，拓扑排序，关键路径。

2.具体要求

图的基本概念、术语

图的存储方法（邻接矩阵、邻接表）

图的DFS和BFS搜索算法及相关应用

生成树和最小生成树（Prime算法、Kruskal算法）

最短路径

拓扑排序

关键路径

（七）索引结构与散列技术

1.复习内容

索引和散列技术的应用背景，索引结构，散列表的概念，散列函数的构造方法，解决冲突的方法。

2.具体要求

索引结构的表示

索引结构的应用

散列表的概念

散列表的构造

散列表的查找

（八）缩小规模算法

1.复习内容

分治与递归算法设计，动态规划的基本要素，贪心算法。

2.具体要求

递归与分治算法

动态规划算法

掌握贪心算法