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