数据结构重点知识
2021-12-31 15:35:51 0 举报AI智能生成
一定要动手写代码，大题的代码书写十分重要，不要做个理论家，加油，就算考研也要做programmer
作者其他创作
大纲/内容
绪论
基础知识
基本概念和术语 王道 P1
数据的定义是什么？
数据元素和数据项关系，自身的地位是什么？
数据对象的定义是什么？
数据类型分为哪三类？
数据结构包括哪三方面？
数据结构三要素 王道 P2
数据的逻辑结构是哪两种，及这两种包括什么数据结构？
数据的存储结构有哪四种存储方式？
数据的运算（知道就行）
算法的基本概念 王道 P5
算法的5个重要特性（背）
算法设计的4个要求（背）
算法时间复杂度的排序（背）
严书补充知识点
考点难点
ADT组成（三元组） 王道 P2
设计取决于？结构代表有？，实现取决于？结构代表有？ P2
有序表，哈希表，顺序表，单链表，树，图，循环队列，栈 属于逻辑结构还是存储结构？
线性表
基础知识
线性表的定义
线性表定义是什么？ P11
表头，表尾元素是什么意思？ P11
直接前驱和直接后继的特性是什么？ P11
线性表是什么结构？顺序表和链表是什么结构？ P12
线性表的顺序表示
顺序表的特征（连续+相邻） P13
位序的含义是什么？ P13
线性表定义式书写（静态，动态分配） P13
线性表三大特点 P14
基本操作
插入 复杂度 P14
删除 复杂度 P14
查找 复杂度 P15
顺序表链式表示
单链表
单链表的逻辑结构是什么？ P27
节点的书写是什么？ P27
头结点带来的优点？ P27
头插法和尾插法建表的书写和复杂度是什么？ P28
按序号和按值查找的书写和复杂度是什么？P29
插入（前插，后插）和删除节点操作的过程和复杂度是什么（顺序）？P30
求表长操作复杂度？ P31
双链表
节点书写是什么？ P31
访问前驱和后继的复杂度？ P32
插入和删除节点操作的过程和复杂度是什么（顺序）？P30
循环链表
结构怎么样？画图（单链，双链） P33
静态链表
书写方式是什么？ P33
画图存储结构是什么？ P33
结束标志是什么？P34
顺序表和链表比较 P34
4个方面
选取的根据
考点难点
顺序表
线性表定义三个关键点重复一下 P11
顺序存储结构优点 P13
复杂度分别多少？ P18
题目集合 P18
链表
顺序存储方式只能用于存储线性结构吗？Ｐ27
简单几题 P40
链表操作 P41
双链表和单链表比较的优点是什么？ P41-17题
链表结构选择 P41
（游标）静态链表指针表示什么？P33
静态链表地址 P42
栈和队列
基础知识
栈
栈的定义是什么？（操作+存储） P60
栈顶，栈底，空栈的概念是什么？ P61
n个不同元素进栈，出栈元素不同的排列个数是多少？ P61
顺序栈
定义（存储） P61
存储定义式是什么？ P61
栈顶指针初始值是什么？ 栈顶元素怎么取？进栈/出栈过程怎么写？栈空/栈满/栈长怎么算？ P61
操作实现（初始化，判空，进栈，出栈，读栈顶元素） P63
栈顶指针指向栈顶元素和指向栈顶元素的下一个位置的操作怎么写？ P63
共享栈
怎么判0/1号栈空？怎么判栈满？ P63
存取元素时间复杂度是什么？ P63
链栈
定义式怎么写？ P63
队列
队列的定义是什么？ P72
入队（离队）/出队（进队），队头，队尾知道名词
栈中某个数据可以直接读取吗？ P73
队列的顺序存储
实现时定义式怎么写？ P73
初始化，进队，出队操作怎么实现？ P73
循环队列
下面处理方法的队空，队满，队列长度分别是多少？ P74
牺牲一个存储单元
size变量存
增设tag变量
初始化，判空，入队，出队操作的实现方法？ P75
链式队列
逻辑结构怎么样？ P75
实现链式存储的方法？ P75
适用场景是什么？ P76
初始化，判空，入队，出队操作的实现方法？ P76
双端队列
输入受限，输出受限的概念是什么？ P77
栈和队列的应用
栈的应用有什么方面？ 队列的应用有什么方面？ P89
考点难点
栈
栈和队列有什么相同的什么东西？ P61
判断链栈 P67
栈可能取值 P69
栈序列个数 P69
栈可能上溢，没有下溢
队列
队列长度 P78
队空队满 P81
合适链表 P81
判断输出序列 P82
应用
概念和表达式 P91
表达式 P92
串
基础知识
基本概念和术语 王道 P103
串的定义，子串，串长，位置 概念的定义分别是什么？
空格串与空串区别，空串的表示符号分别怎么表示？
串的存储结构 王道 P104
顺序存储（数组存储）
截断是什么意思？
结束方法有哪两种？
定义式怎么写？
堆分配存储（指针）
定义式怎么写？
块链存储
不满时 # 补充
串的五个基本操作 （背，展开答案）
StrAssign
StrCompare
StrLength
Concat
SubString
串的模式匹配 王道 P107
暴力算法（理解）
KMP算法
求next数组（必须会）
KMP算法原理（了解）
KMP算法优化（知道就行）
严书补充知识点 P73
顺序存储函数实现（尽量了解实现）
Index函数
Index函数
Concat函数
Concat函数
SubString函数
SubString函数
堆分配存储函数实现（尽量了解实现）
StrInsert
StrAssign
Concat
SubString
考点难点
模式匹配是什么意思？ P105
简单模式匹配算法和KMP算法的时间复杂度分别是？ P113
KMP复习5题 P113 （7难题）
KMP知识点 P114
树和二叉树
基础知识
树的定义 P118
树的定义是什么？
空树，子树的定义是什么？
树前驱和后继的性质是什么？
基本术语 P119
K的祖先，子孙，双亲，孩子，兄弟
B的度
分支结点和叶子结点是什么？非终端和终端结点是什么？
结点的深度，高度，层次，树的高度
有序/无序树是什么？
路径和路径长度是什么？
森林是什么？
树的性质 P120
结点和结点度数有什么性质？
度为m的树中第i层上至多有多少结点？
高度为h的m叉数至多有多少结点？
具有n个结点的m叉数最小高度是多少？
ki为度为i的结点数量，n为结点总数，那么k0（叶子）与其他结点有什么关系？
二叉树定义及特性 P122
二叉树的定义是什么？二叉树是有序树吗？
二叉树和度为2有序树的区别？
满二叉树（h表示）
定义是什么？
有多少结点？（h表示）
对于编号为i的结点，若有双亲，双亲为什么？左孩子，右孩子的序号为什么？
完全二叉树（h表示，n个结点）
定义是什么？
对于编号为i的结点，i为分支结点和叶子结点条件是什么？
度为1结点的性质是什么？
n为奇数和偶数有什么性质？
二叉排序树和平衡二叉树含义是什么？
二叉树的性质 P123
非空二叉树叶子结点与度为2结点有什么关系？怎么推出？那么任意一棵树，若结点数量为n,则边的数量为？
非空二叉树上第K层至多有多少结点？
高度为H的二叉树至多有多少结点？
完全二叉树性质（某结点编号为i）
i>1,i的双亲编号为？i为偶数/奇数，双亲编号为什么？是左/右孩子？
2i<n,i的左孩子编号为什么？否则如何？
2i+1<=n，i的右孩子编号为什么？否则如何？
结点i所在深度为多少？
具有n个结点的完全二叉树高度为多少？如何推出？
二叉树存储结构 P124
顺序存储
如何存储？
适合什么类型二叉树？
最后情况，高度为h有h个结点单支树占据多少存储空间？
链式存储
存储结构如何？
n个结点的二叉链表，空链域数量是多少？
二叉树遍历 P131
定义是什么？
前中后序分别顺序是什么？空间复杂度是多少？
前中后序的非递归算法是什么？如何实现？
层次遍历如何实现？
线索二叉树 P135
每个结点的结构是什么？
存储结构如何？
前中后序的二叉树找前驱和后继方便吗？大概过程如何？
树，森林 P160
树存储结构
双亲表示法如何实现？（存储结构，画图）如何找双亲和孩子？
孩子表示法如何实现？（画图）如何找双亲和孩子？
孩子表示法如何实现？（存储结构，画图）如何找双亲和孩子？
树，森林，二叉树转换
三种互相转换过程怎么样？
图
树和森林遍历
树的遍历怎么样的？森林的呢？
遍历对应的顺序如何？
图
重点难点
树概念 P121
二叉树 Q6 P128
叶节点个数 P128
图1
图2
二叉链表存储树，非空指针数=？，空指针数=？ P126
结点个数 P129
二叉树遍历 P143
图1
图2
n在m前类型 P143
条件反推树数量
题1 P144
题2 P147 =>前序和中序的关系是什么？
二叉树关系 P144
遍历序列 P144
反推序列 P145
线索二叉树
题1 P146
题2 P146
题3 P147
题4 P147
图
基础知识
图的基础概念
图的定义是什么？表示方法是什么？ P198
概念与术语 P199
有向图的定义和表示方法是什么？
无向图的定义和表示方法是什么？
简单图，多重图的定义和表示方法是什么？
完全图的定义和表示方法是什么？
子图的定义和表示方法是什么？
连通，连通图，连通分量的定义和表示方法是什么？
强连通图，强连通分量的定义和表示方法是什么？
生成树，生成森林的定义和表示方法是什么？
顶点的度，入度，出度的定义和表示方法是什么？有向图和无向图呢？
边的权和网的定义是什么？
稠密图，稀疏图的定义和表示方法是什么？
路径，路径长度，回路的定义是什么？
简单路径，简单回路的定义是什么？
距离的的定义是什么？
有向树的定义是什么？
图的存储和基础操作
邻接矩阵 P205
定义是什么？
如何书写？
写出结构定义是什么？
注意点
特点
无向图的邻接矩阵是什么？
无向图第i行非零元素的个数是什么？
有向图第i行非零元素的个数是什么？第i列非零元素的个数是什么？
邻接矩阵如何找任意两顶点是否有边相连？
什么图适合邻接矩阵表示？
概念
邻接表 P206
定义是什么？
逻辑结构？
写出结构定义是什么？
特点
无向图和有向图的存储空间是多少？
什么图适合邻接表表示？
邻接表查找顶点临边效率和邻接矩阵的是多少？
邻接表如何找入度？如何找出度？
邻接表唯一吗？
十字链表 P208
定义是什么？
逻辑结构？
画出该图的十字链表表示
优点是什么？
邻接多重表 P208
定义是什么？
逻辑结构？
优点是什么？
画出该图的邻接多重表表示
图的基础操作
图的遍历
定义是什么？ P215
BFS P215
基本思想是什么？
伪代码书写出来？
该图的遍历结构是什么？
性能分析
邻接表的时间和空间复杂度是什么？
邻接矩阵的时间和空间复杂度是什么？
求单源最短路径伪代码如何书写？
邻接表和邻接矩阵生成树唯一吗？
DFS P217
基本思想是什么？
伪代码书写出来？
邻接表和邻接矩阵遍历序列唯一吗？
性能分析
邻接表的时间和空间复杂度是什么？
邻接矩阵的时间和空间复杂度是什么？
邻接表和邻接矩阵生成树唯一吗？
图的遍历和连通 P218
图的应用
最小生成树 P226
最小生成树定义是什么？
性质
树形唯一的条件是什么？图G的最小生成树是本身的条件是什么？
边权值和是怎样的？
边数是多少？
Prim算法 P227
画出该图流程？
写出简单实现代码？
时间复杂度是什么？适用于什么类型图？
Kruskal算法 P227
该图流程是什么？
写出简单实现代码？
选择最小边的时间复杂度多少？总复杂度多少？适用于什么类型图？
最短路径 P228
Dijkstra算法
适用于什么问题？
运行步骤如何？构造的辅助数组dist[],path[]如何初始化和使用？
该图执行过程如何？
邻接矩阵复杂度多少？邻接表复杂度多少？
适用于什么类型的图？
Floyd算法 P230
A(k)[i][j]的含义是什么？
该图的执行过程是什么？
时间复杂度是什么？
适用于什么类型的图？
有环无向图 P231
定义是什么？
改成有环无向图表示？((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)
拓扑序列 P232
AOV网的定义是什么？
什么是拓扑排序？
该图的拓扑排序？
拓扑排序算法是什么？
时间复杂度是什么？
处理AOV的问题
入度为0的顶点如何？
排序结果是否唯一的影响因素是什么？
顶点地位如何？一般图来说，邻接矩阵为三角矩阵如何？
关键路径 P233
AOE网与AOV网的区别是什么？
AOE网的特点是什么？源点，汇点？
事件发生的最早和最迟时间是什么？活动发生的最早和最迟时间是什么？
画出关键路径
加快关键活动有什么影响？
只提高一条关键路径上的关键活动影响如何？
重点难点
图的基础概念 P203
Q4-8
Q10-13
Q16-18
图的存储和基础操作 P213
Q11-13
图的遍历 P221
Q10-11
Q13-15
图的应用 P243
Q4-6
Q7-9
Q16-17
Q19-21
Q24-29
查找
基础知识
查找基本概念 P257
查找的定义是什么？
静态查找表方法有什么？动态的呢？
平均查找长度公式怎么样？
顺序查找和折半查找
顺序查找 P258
一般线性表
写出数据结构及搜索代码
进行多少次关键字的比较？平均查找长度是多少？顺序查找失败长度为？
优缺点是什么？
有序表
圆形矩形节点是什么意思？
查找失败概率是多少？
可以是链式存储吗？
折半查找 P260
基本思想如何？
查找代码如何书写？
查找11和32过程如何？
查找成功与失败的路径是什么？
平均查找长度是多少？时间复杂度是多少？
适合什么存储结构？
分块查找（索引顺序查找） P261
基本思想是什么？
此查找长度为？最大时s为多少？采用折半查找呢？
B树和B+树
B树 （多路平衡查找树） P270
B树的阶是什么意思？
m阶的B树性质
对着例子说明以下特点？
每个节点至多多少子树/关键字？
根节点不是终端结点？
除根节点外所有非叶节点有多少子树/关键字？
结构如何？
叶节点特征是什么？
B树的高度
磁盘存储次数与B树高度成正比，高度不包括最后叶节点层
此B树高度为？高度最大为？
B树的查找
基本操作是什么？
查找过程如何？
B树的插入
插入过程如何？
B树的删除
删除情况1
删除情况2
删除情况3
B+ 树 P273
m阶B树条件
每个分支最多多少子树？
非根节点或者分支结点至少多少子树？
结点子树和关键字个数如何？
叶节点有什么性质？
分支结点性质如何？
主要差异
关键字结点子树个数？
关键字个数？
索引作用？
叶节点关键字？
散列表 P281
散列函数定义是什么？
冲突和关键词的意思是什么？
散列表构造方法
定义域和值域如何？
如何减小冲突发生？
如何短时间算出值？
常见定址方法
直接定址法
计算方法函数
适合情况
除留余数法
计算方法函数
适合情况
数字分析法
适合情况
平方取中法
计算方法
适合情况
开放定址法
含义是什么？
递推公式是什么？
线性探测法
方法是什么？
平方探测法
方法是什么？
缺点是什么？
再散列法
具体函数是什么？
伪随机序列法
方法是什么？
开放定址法如何删除元素？
拉链法
说明拉链法作用方法？
性能分析
模拟查找过程，写成关键词比较次数，和算出平均查找长度
三个查找效率的决定因素是什么？
写出装填因子的表达式是什么？
重点难点
顺序、折半查找 P265
Q2
Q4
Q10-15
Q19-21
B树，B+树 P277
Q7-11
Q12-17
散列表 P287
Q4-Q8
Q11-13
Q17,18
排序
基础知识
基本概念 P294
稳定性的概念是什么？
分为哪两类？
插入排序 P295
直接插入排序
模拟排序
排序代码书写
空间复杂度是什么？最好最坏时间复杂度是什么？平均时间复杂度是什么？稳定性如何？
适用什么类型？
折半插入排序
排序代码书写
时间空间复杂度是什么？稳定性如何？
适用什么类型？
希尔排序
模拟排序
排序代码书写
空间复杂度是什么？最好最坏时间复杂度是什么？平均时间复杂度是什么？稳定性如何？
适用什么类型？
交换排序 P302
冒泡排序
模拟排序
排序代码书写
空间复杂度是什么？最好最坏移动次数是什么？平均时间复杂度是什么？稳定性如何？
快速排序
模拟排序
排序代码书写
空间复杂度是什么？最好最坏时间复杂度是什么？平均时间复杂度是什么？稳定性如何？
选择排序 P313
简单选择排序
书写排序代码
空间复杂度是什么？最好最坏时间复杂度是什么？平均时间复杂度是什么？稳定性如何？
堆排序
大根堆和小根堆的概念是什么？
调整为大根堆
建堆，排序代码书写
空间复杂度是什么？最好最坏时间复杂度是什么？平均时间复杂度是什么？稳定性如何？
适合情况是什么？
归并排序和基数排序 P322
归并排序
模拟排序
排序代码书写
空间复杂度是什么？时间复杂度是什么？稳定性如何？
基数排序
MSD和LSD是什么？
模拟排序过程
空间复杂度是什么？时间复杂度是什么？稳定性如何？
排序比较 P328
填充表格
N较小？初始状态有序？N较大？N较大并关键字位数较少？
外部排序 P334
主要时间代价是什么？
说出排序基本步骤
外部排序总时间哪3部分组成？
如何减少总IO次数？
填空
多路平衡归并和败者树
S趟归并的比较次数是什么？
填空
置换-选择排序
模拟排序
最佳归并树
优化成最佳模式
重点难点
基本概念 P295
插入排序 P300
Q1-3
Q7-10
交换排序 P307
Q4-Q7
Q12-17
选择排序 P318
Q1-4
Q8-15
Q16
归并排序和基数排序 P326
Q3-7
Q10-13
排序比较 P331
Q1-2
Q6-10
Q11-14
外部排序 P340
全做了
0 条评论
下一页
