数据结构重点难点

数据结构重点难点

1.数据结构重点内容：

什么是数据结构？

数据元素和数据项的基本概念。

4大类逻辑结构。

算法的时间复杂度。

线性结构的基本特征；

在线性表（n个元素）的第i个位置前插入一个元素核心语句；

链表插入的核心语句；

栈 ( Stack )的定义和特点；

栈的操作实现(1) 入栈(2)出栈；

会做入栈出栈的题；实现递归；

队列的定义和特性；

顺序循环队列的表示和实现；

链式队列的存储结构；

判断链队列是否空；

串的基本概念；

串长的求法；

空串和空白串的区别；

串相等的条件；

串联接操作；

串的表示和实现；

数组的两种顺序映象的方式：1)以行序为主序，2)以列序为主序；

稀疏矩阵的压缩存储；

广义表的定义；

广义表的长度定义；

广义表的深度定义；

非空广义表的表头、表尾；

二叉树的定义；

二叉树的特点；

二叉树的性质；

二叉树的第i层上至多有多少个结点；

深度为k的二叉树中至多含有2k-1个结点；二叉树的先（根）序遍历；

二叉树的中（根）序遍历；

二叉树的后（根）序遍历；

线索二叉树的生成——线索化；

森林与二叉树的转换；

树与二叉树的转换；

树的先根遍历和后根遍历；

Huffman树定义；

构造Huffman树的步骤并会做题；Huffman树编码；

图的结构定义；

图的数组(邻接矩阵)存储表示并会做题；图的邻接表存储表示并会做题；

有向图的十字链表存储表示并会做题；

深度优先搜索遍历图；

广度优先搜索遍历图；

普里姆算法求最小生成树；

克鲁斯卡尔算法求最小生成树；

求每一对顶点之间的最短路径；

顺序表的查找；

有序表的折半查找；

有序表的折半查找适用条件；

二叉排序树的构建过程；

二叉排序树上的查找；

哈希查找表的定义；

散列法存储的基本思想；

哈希函数的构造方法；

哈希函数的构造方法除留余数法；

哈希冲突解决方法

排序定义；

排序算法的稳定性；

直接插入排序过程；

折半插入排序过程；

希尔排序(缩小增量法)的基本思想和排序过程；

快速排序基本思想和排序过程；

归并排序的2-路归并排序排序过程；

2.数据结构的知识点：

数据结构的基本概念和术语；

数据结构在软件系统中的作用；

课程的研究、学习内容和方法。

线性表的逻辑结构、各种存储结构、基本操作（算法）的实现及性能分析；

不同存储结构的比较；

线性表的应用算法。

线性表的逻辑结构和各种存储表示方法，

定义在逻辑结构上的各种基本操作

在存储结构上如何实现基本操作

栈和队列的逻辑结构定义；

在两种存储结构上实现栈和队列的基本操作；

栈和队列的本质区别；

栈和队列的应用；

串的逻辑结构、存储结构及其上的基本操作；

多维数组的逻辑结构特征及其存储方式；

特殊矩阵和稀疏短阵的压缩存储方法；

广义表的概念和性质。

二元树的定义、性质、存储结构、遍历、线索化；

树的定义、存储结构、遍历；

树和森林与二元树的转换；

树（森林）与二元树的应用（哈夫曼树及其应用、集合表示与等价分类、表达式求值）。

（无向和有向图）的基本概念；

两种常用的存储结构；

两种遍历算法；

图的应用算法(最小生成树算法、关节点和双连通分量算法、强连通性判定和求双连通分量的算法、拓扑分类算法、关键路径算法、最短路经算法等)。

在线性表、树结构和散列表上进行查找的基本思想和方法

查找算法的实现以及各种查找方法的时间性能(平均查找长度)分析；

基于关键字的查找与基于关键字散列地址的查找的本质区别

内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析；

各种排序方法的比较和选择；

外部排序的一般过程；

适合外存特点的归并排序的关键技术。

3.数据结构的难点：

数据结构的逻辑结构、存储结构及数据操作之间的相互关系。

能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。

栈与队列.

循环队列中对边界条件的处理；

在什么样的情况下能够使用栈或队列。

多维数组和广义表（2学时）

稀疏矩阵的压缩存储表示下实现的算法。

设计解决与树或二元树相关的应用问题的有效算法。

图的存储结构和遍历算法。

有关图的应用算法。

散列表。

查找算法的性能分析

快速排序、堆排序、归并排序和基数排序算法的时间和空间复杂性及其分析方法。