二叉排序树成功查找的时间复杂度_二叉排序树的查找的时间复杂度

计算机/软工408考研–数据结构总览
　　如果觉得对你有帮助，欢迎点赞！

　　408相关内容欢迎专栏：计算机/软工408考研知飞翀：408算法大题–这样刷~

　　0. 前言

　　本篇文章旨在分析408中数据结构的考察内容、形式和重难点，帮助你打好有准备的仗。

　　1. 数据结构在408中的考察形式

　　计算机基础综合408，主要通过选择题(40题，每题2分，共80分)和大题(7题，每题分数不等，共70分)进行考察，一共包含4门学科–数据结构、组成原理、操作系统、计算机网络，其中数据结构和组成原理考察的总分值较高，操作系统其次，计算机网络总分值最低。

　　408真题中，数据结构考察包含如下形式和特点：选择题部分：共11题22分，主要考察对数据结构的细节理解，很多题目并不是简单考察某个结构/算法的最终结果，大都考察结构/算法的中间过程。同时选择题会挖很多坑，一般感觉一眼就能看出答案的反而需要重视，一不小心就入坑。2017年408真题数据结构选择题节选大题目部分：共2题22-25分左右，2个大题分为算法大题和应用大题。其中算法大题主要考察算法思想、伪代码编写、分析时间空间复杂度，集中考察线性表和二叉树的算法；应用大题需要结合结构/算法针对题目来解答，主要以文字+分析+图表的形式作答。2017年408真题算法大题节选2017年408真题应用大题节选

　　2. 数据结构知识点重难点

　　2.0阅读须知

　　在每个知识点/考点后用（选）–选择题，（算）–算法大题，（应）–应用大题 来标注次考点主要出题形式；在每个知识点/考点后用*标注，表明尤其需要注意；用粗体标注的知识点相比较更加重要

　　2.1 时间复杂度和空间复杂度

　　时间复杂度（选+算第3问）非递归函数 1. 利用累加/累乘法分析非递归函数的时间复杂度；递归函数 1. 利用Master公式分析满足T(n)=aT(n/b)+n^d的递归函数的时间复杂度，例如：快速排序；— Master公式适用于递归分治算法 2. 利用依次递归的方式分析普通递归函数的时间复杂度； 3. 利用特例法分析非常规递归函数的时间复杂度，如：分析斐波那契数列的递归函数的时间复杂度，举特例F(5)来分析；空间复杂度（选择题+算法大题第3问）1. 空间复杂度与时间复杂度分析大致相同，只是空间复杂度的侧重点在额外的空间上；2. 需要注意的是递归函数有递归栈这个特殊的额外空间

　　2.2 线性表

　　顺序表(数组)（算）插入：先确定插入点是否合法，然后再将插入点之后的元素都后移一位，最后插入删除：先确定删除点是否合法，然后再将删除点元素删除，最后将删除点之后的元素前移一位查找：按索引下标查找O(1)；按值查找O(n)链表（选+算）单链表1. 头插法、尾插法 2. 删除结点 3. 两种特殊处理*：(1)对p结点进行前插操作；(2)删除p结点;双链表1. 类似单链表的头插法、尾插法 2. 类似单链表的删除结点循环单链表：类似单链表循环双链表：类似双链表静态链表*：利用数组结构来存储链表，起点为0，终点为-1

　　注意：对链表结构的插入和删除操作常考选择题，链表要注意头结点这个概念。

　　2.3 栈和队列

　　栈（选）1.顺序栈的top指针特点（区分队列的rear指针）2.一串数列通过栈来处理能获得新序列的数量（Catlan公式）和可能得到的新序列2.栈在括号匹配上的应用3.栈在中缀表达式与后缀表达式的相互转换的应用*(熟练掌握转换的中间过程)队列（选）1.顺序队列的rear指针的特点2.顺序循环队列判空判满的条件*：(1)牺牲空间法；(2)size法；(3)tag标记法3.栈在二叉树层次遍历中的应用*（变形：利用标记法来辅助确定出当前结点位于那一层）矩阵压缩存储（选）1. 矩阵的压缩存储是套路题，做法如下：(1)看题，分析是按行存储还是按列存储(2)找出等差/等比规律(3)求等差数列/等比数列和，确定出压缩公式2. 稀疏矩阵的存取方式：三元组、十字链表、行逻辑链接顺序表

　　2.4 树和二叉树

　　树和二叉树的基本概念（选）1.树的性质：区分树的度和图的度2.二叉树的性质：（1）n0 = n2 +1;（2）完全二叉树i结点的左孩子为2i，右孩子为2i+1 (从1开始编号)二叉树的存储方式（选）1. 顺序存储，其实就是按照完全二叉树来存储2. 链表存储：链表的空指针数 = 结点数n + 1二叉树的遍历方式（选+算）四种遍历方式（先序，中序，后序，层次）其中先序中序后序不仅要掌握递归方式还要掌握非递归方式，层次遍历需要借助队列来实现；线索二叉树是在先序中序后序递归实现方式上的变形（重点）二叉树的应用（选+应）1. 并查集：图里面最小生成树的基础2. 二叉排序树(算)：代码模板记住3.平衡二叉树AVL(选)：掌握LL型、RR型、LR型、RL型的调整过程3.哈夫曼树和哈夫曼编码(选+应)：不仅会画图还要会用文字来叙述

　　2.5 图

　　图的概念（选）1. 图的度与树的度的区分2. 有向图与无向图的区分（连通性，强连通性）3. 简单路径与简单回路4. 距离：最短路径图的存储方式（选+应一个小问）1. 邻接矩阵*2. 邻接表*3. 十字链表(有向图)4. 邻接多重表(无向图)图的遍历方式（选+算）1. BFS：类似二叉树的层次遍历；注意BFS的变形–求单源最短路径2. DFS：类似二叉树的先序遍历；3. BFS与DFS都需要借助辅助数组visited[]来标记当前结点是否被访问过4. 图的遍历与图的连通性的关系*图的应用（选+应）1. 最小生成树（1）prim算法（2）Kruskal算法2. 最短路径（1）dijkstra算法（2）Floyd算法3. 拓扑排序：可以用来判断图是否有环4.关键路径

　　2.6 查找

　　顺序查找（选）1. 普通顺序表：进行普通的从小到大的遍历查找插入点，然后插入2. 有序顺序表*：进行二分的思想进行查找插入点，然后插入 — 记住二分思想的核心代码以上两种方式由于都需要进行插入，故时间复杂度为O(n^2)分块查找（选）使用了索引表+查找表的结构：（1）索引表：有序表 — 二分查找（2）查找表 — 根据索引分块后采用顺序查找方式查找二叉排序树、AVL树(平衡二叉树)、B树、B+树（选）1. 二叉排序树上的查找2. AVL树上的查找：其实就等效为二叉排序树上的查找，因为AVL树就是一颗二叉排序树3. B树：（1）概念：包含m/2向上取整-1 <= n(非根结点) <= m-1；叶子结点不含数据，数据存在索引上等（2）B树高度求法：logm^(n+1) <= h <= logm/2向下取整^(n+1)/2 + 1（3）B树插入：可能使B树高度h+1（4）B树删除：可能使B树高度h-14. B+树（1）B+树的概念（2）B+树与B树的区别（3）B+树的特点：数据都存在叶子结点上，非终端结点只起索引作用；B+树可以有两种查询方式注意：B/B+一般是以选择题的形式考察，并且考察的深度不高，我们只需要学习基本知识就可以散列表（选+应）1. 散列函数：直接定址法、除留取余法是重点，其他了解即可2. 处理冲突：（1）开放定址法：线性探测法、平方探测法、再散列法是重点（2）拉链法3. 装填因子4. 求散列表上查找成功/不成功的平均查找数*KMP（选+算+应）KMP算法的核心是next[]数组，掌握计算机的next[]数组，这里说的计算机的next[]数组是相当于手动模拟的next[]数组而言的，408考察的是计算机的next[]数组计算机next[] = 手动模拟的next[] 右移一位 + 1KMP算法记下来，注意KMP的特点是主串不回溯

　　2.7 排序

　　插入排序（选）1. 直接插入排序2. 折半插入排序：引入二分思想3. 希尔排序交换排序（选+算）1. 冒泡排序2. 快速排序：把Partition函数当模板记下来选择排序（选）1. 简单选择排序2. 堆排序：向下调整 、向上调整（1）堆的构建：向下调整，这里的时间复杂度为O(n)要知道为什么（2）堆排序：向下调整归并排序（选+算）掌握Merge函数，当模板记下来基数排序（选+算）基数排序是给予非比较的排序拓展：桶排序、计数排序外部排序–多路归并排序（选）1. 败者树：要会自己构建败者树，败者树可以减少比较次数2. 置换-选择排序：划分初试归并段3. 最佳归并树：减少归并过程中的I/O次数注意：虽然外部排序的内容少，但是外部排序的难度比内部排序的难度要高，幸运的是外部排序基本以选择题形式考察；学习外部排序重点是学习思想，要去真正的理解它。

　　3. 经验总结

　　在408真题中的数据结构部分的题目可以看出：选择题大多考察相应结构/算法的中间过程，这就要求我们必须深刻的理解和熟练的掌握此结构/算法，能从计算机的角度出发去思考计算机处理这个问题处理的整个过程是什么样的，而不要从个人主观上出发去看此结构/算法，因为这样只是表面上搞懂了此结构/算法，但是一做题该错的还是错，不会的还是不会；大题部分重点在于积累和做题，因为408真题中算法大题和应用大题基本上每一年考察的知识点和思想都不是很相同，所有我们需要多去做大题，虽然大题比较难做，但是一点要坚持去把王道的课后大题都做完，一边做一边去思考，慢慢的就会变好。选择题经常有很多坑，做题不要想当然，写答案前多问问自己这题真的是这样？真的这麽简单？比别人想的更多才能比别人走的更远；大题主要强调的是思想，多去想想算法大题有什么其他的解法，应用大题考的知识点是哪些，一定要做到看完题目心中有数，方能不乱阵脚。

　　最后，坚持+思考+努力，2021年一战成硕！数据结构？就这？一起搞定它~~~~

　　此篇408数据结构重难点知识总结并不能做到完全正确，如果发现错误或有疑问请及时告知本人，保证传播知识的正确性！

　　408其他科目重难点请本专栏计算机/软工408考研，将陆续更新到位。计算机/软工408考研

　　文章整理不易，欢迎点赞转发，谢谢您的阅读！

　　———-完结————