徐小贱-数据结构 | 天软9月第一轮复习计划&考纲重点!@芝芝老师

重刷数据结构视频课程(先复习C语言）

在回看视频之前先做课后习题，带着问题去看课程

看完课程后重刷练习册

整理讲义例题、本章习题、练习册上的错题，定期重刷

国庆节后开始数据结构的复习

本章以概念为主，通过背诵对数据结构进行基础掌握，为后边的学习做铺垫。

1. 基本概念和术语：数据、数据元素（基本）、数据项（最小）、数据对象

2. 数据结构四种基本类型：集合、线性结构、树型结构、网状结构

3. 数据结构三要素：逻辑结构、存储结构、数据的运算

4. 抽象数据类型：ADT<D,R,P>(数据对象、关系、操作）

5. 算法：特点、评价、效率和存储（重点掌握时间复杂度计算）

建议重点复习第二章，它是所有章节中难度最高、分值最重的知识点，吃透核心算法，多刷同类大题!

1.数据结构讲义上的蓝框代码需要重点复习

2.重点掌握顺序表、单链表、顺序表、单链表的对比以及各种基本操作的时间复杂度，必须掌握对单链表中各操作的指针变化。

本章重点掌握基础定义、操作逻辑及简单应用，确保基础题型不丢分。

1.掌握栈的特点和基本操作（栈的数学性质：n个不同元素进栈，出栈元素不同排列的个数）

2.掌握队列的特点和基本操作：链式存储、顺序存储和循环队列（判定空、满的条件）

①栈→顺序：

空：S.top==S.base.

满：S.top-S.base>=S.stacksize

②队列→链式：

空：Q.front==Q.rear

→顺序：

空：front==rear

→循环队列：

满：（rear+1)%M==front

1. 掌握串的定义和基本操作

2. 串的存储表示方式：定长顺序存储表示和堆分配存储表示

1. 熟悉数组的存储结构，重点掌握元素地址的计算

2. 特殊矩阵的压缩存储：对称矩阵、三角矩阵、稀疏矩阵（三元组表）

3. 广义表的操作

顶级大重点，选择、填空、大题全覆盖，核心攻克二叉树遍历、算法及代码实现，熟记相关性质与应用。

1. 掌握树的定义和性质

2. 二叉树的定义和性质（二叉树、满二叉树、完全二叉树）

3. 二叉树的存储结构：顺序存储和链式存储

4.重点：二叉树的遍历(非常重要）→掌握先序遍历、中序遍历、后序遍历、层序遍历，重点复习由二叉树的遍历序列构造二叉树的列论和P72页例题

5.次重点：树和森林及其遍历（明白树的三种存储结构的表示方法和优缺点）

6.重点：树（森林）和二叉树的相互转换

7.难点：哈夫曼树（带权路径长度、构造算法、哈夫曼编码）

全章节都是重点，画图能力是关键，树与图的难点在于理解，务必反复强化。

1. 掌握图的定义和11种基本术语

2. 掌握度的相关计算

3. 图的四种存储结构(重点：邻接矩阵表示法和邻接表表示法）

4. 图的两种遍历（BFS和DFS要会画图)

5.最小生成树的两个算法（重点）：Prim算法（稠密图）、Kruskal算法（疏密图）

6.最短路径（重点）：单源最短路径Dijkstra算法

7. 拓扑排序的步骤

核心攻克散列查找（哈希表），熟记构造方法与冲突解决策略，新增的二叉排序树、二叉平衡树重中之重。

1. 重点掌握顺序查找、折半查找和分块查找这三个查找的平均查找长度以及时间复杂度。

2. 散列查找重点复习直接地址法和除留余数法（重点），很重要!

3. 这四种查找均须掌握他们的查找步骤

熟悉各算法的操作步骤，能写出每一趟的排序的结果，P127中的各个排序算法对比表需要背诵

1. 直接插入排序：5个相关结论

2. 希尔排序：直接插入排序的改进方案

3. 交换排序：冒泡排序和快速排序

4. 选择排序：简单选择排序和堆排序

5. 归并排序：4个相关结论