数据结构面经
数据结构
第一章绪论
1. 数据结构三要素是什么？逻辑结构包括什么？存储结构包括什么？
数据结构的三要素包括逻辑结构、存储结构（物理结构）、数据的运算。
逻辑结构包括线性结构与非线性结构。
线性结构包括栈、队列、串、数组。非线性结构包括集合、树形结构、图状结构。
存储结构包括顺序存储、链式存储、索引存储、散列存储。
1) 顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系有存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间，缺点时只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
2)链式存储。不要求逻辑上相邻的元素在物理位置上也相邻，借助只是元素存储地址的指针来表示元素之间的逻辑关系。其优点是不会出现碎片现象，能充分利用所有的存储单元；缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。
3)索引存储。在存储元素信息的同时，还建立附加的索引表。索引表的每项称为索引项，索引项的形式一般形式是（关键字，地址）。其优点是检索速度快；缺点是附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表，因而会花费较多的时间。
4)散列存储。根据元素的关键字直接计算出该元素的存储地址，又称哈希存储。其优点是检索、增加和删除结点的操作都很快；缺点是若散列函数不好，则可能出现元素存储单元冲突，而解决冲突会增加时间和空间开销。
2. 顺序存储结构和链式存储结构的概念以及优点与缺点 ★★★
顺序存储:把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。其优点是①可以实现随机存取，通过首地址和元素序号可在时间O(1)内找到指定的元素。②存储密度高，每个结点只存储数据元素。缺点是①只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。②插入和删除操作不方便，以线性表为例，插入和删除均需要移动元素，两者的平均时间复杂度为O(n)。
链式存储:不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。其优点是①不会出现碎片现象，能充分利用所有的存储单元；②以单链表为例，进行插入、删除操作时很方便，不需要移动数据元素。若在指定结点后进行前插、后插操作时间复杂度均为O(1)，都可以转换为后插操作。若在指定结点后进行删除操作，如果不是删除最后一个结点，时间复杂度为O(1)。③不用预先估计存储空间的规模，在需要时向内存申请空间即可，操作灵活。缺点是①每个元素因存储指针而占用额外的存储空间。②只能实现顺序存取。
3. O(n)的大O是什么意思？什么是时间复杂度? 什么是空间复杂度？ ★★★
大O表示法是一种用于描述算法复杂度的数学符号，用于表示算法在最坏情况下的运行时间或空间需求。这里的O(n)中的"O"表示的是"order of"，即“数量级”。
时间复杂度是指算法在运行过程中所需要的计算工作量，通常用“大O符号”来表示。它描述了算法执行所需时间与输入规模之间的关系。空间复杂度是指算法在运行过程中所需的存储空间量，也通常用“大O符号”来表示。它描述了算法运行所需空间与输入规模之间的关系。算法原地工作指算法所需的辅助空间为常量，空间复杂度为O(1)。
空间复杂度包括程序代码所占用的空间、输入数据所占用的空间、辅助变量所占用的空间这三个方面，如果算法是递归的，还应该包括递归调用的栈深度以及每层调用所需的空间。
4. 循环比递归的效率高吗？★
循环和递归两者是可以互换的，不能决定性的说循环的效率比递归高。
递归 优点：代码简洁清晰，容易检查正确性； 缺点：当递归调用的次数较多时，要增加额外的堆栈处理，有可能产生堆栈溢出的情况， 对执行效率有一定的影响。
循环 优点：结构简单，速度快； 缺点：它并不能解决全部问题，有的问题适合于用递归来解决不适合用循环。
第二章线性表
1. 什么是线性表？什么是顺序表？什么是链表？
线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，是一种逻辑结构。
顺序表是线性表的顺序存储，它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同。
typedef struct { // 顺序表的静态分配实现
ElemType data[Maxsize];
int length;
}SqList;
初始化：分为静态分配和动态分配。对数组进行静态分配时，因为数组的大小和空间事先已经固定，所以一旦空间占满，再加入新数据就会产生溢出，进而导致程序崩溃。动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，将原表中的元素全部拷贝到新空间，从而达到扩充数组存储空间的目的，而不需要为线性表一次性地划分所有的空间。
插入操作:在顺序表的第i（1≤i≤L.length+1）个位置插入新元素e，时间复杂为O(n)。其实现方式是先判断插入i的位置是否合法，合法则将第i个元素以及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素e,顺序表的长度增加1，插入成功。
删除操作:删除顺序表L中的第i（1≤i≤L.length）个位置的元素，用引用变量e返回，时间复杂为O(n)。其实现方式是先判断删除i的位置是否合法，合法则将被删除的元素赋给引用变量e，并将第i+1个元素及其后的所有的元素依次往前移动一个位置。
按位查找:在顺序表L中查找第i个位置的元素的值，时间复杂度为O(1)。
按值查找:在顺序表L中查找第一个元素值等于e的元素，返回其位序，时间复杂度为O(n)。其实现方式是遍历整个顺序表，找到第一个元素值等于e的元素停止遍历就返回位序。
链表是线性表的链式存储，它是指通过一组任意的存储单元来存储线性表的数据元素。为了建立数据元素之间的线性关系，对于每个链表结点，除存放元素自身的信息之外，还需存放一个指向其后继的指针。
typedef struct LNode { // 定义单链表结点类型
ElemType data;
struct LNode *next;
}LNode, *LinkList;
初始化：带头结点的单链表初始化时，需要创建一个头结点，并让头指针指向头结点，头结点的next域为初始化为NULL。不带头结点的单链表初始化时，只需要将头指针L初始化为NULL。
求表长:需要从第一个结点开始依次访问表中的每个结点，为此需设置一个计数变量，每访问一个结点，其值加1，直到访问到空结点位置。时间复杂度为O(n)。
按序号查找结点:从单链表的第一个结点开始，沿着next域从前往后一次搜索，直到找到第i个结点为止，则返回该结点的指针；若i大于单链表的表长，则返回NULL。时间复杂度为O(n)。
插入结点:首先判断插入位置是否合法，若合法查找到第i-1个结点，将新插入结点指向第i个结点，将第i-1个结点指向新插入的结点。时间复杂度为O(n)。如果在指定结点后插入新结点，则时间复杂度为O(1)。
删除结点:首先判断删除位置是否合法，若合法查找到第i-1个结点，让第i-1个结点指向第i个结点的后继结点。时间复杂度为O(n)。如果在指定结点后删除新结点，则时间复杂度为O(1)。
2. 线性表包括顺序表和链表，请比较它们的区别。
1)存取方式
顺序表可以顺序存取，也可以随机存取，链表只能从表头开始依次顺序存取。
2)逻辑结构与物理结构
线性表采用顺序存储，逻辑上相邻的元素，对应的物理存储位置也相邻。链表采用链式存储，逻辑上相邻的元素，物理位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。
3)基本操作
在初始化时，顺序表分为静态分配与动态分配。静态分配需要预分配大片连续空间，若分配空间过小，则之后不方便扩展容量；若分配空间过大，则浪费内存资源。动态分配的容量可改变，但需要移动大量元素，时间代价高。链表只需分配一个头结点或不要头结点，只声明一个头指针，之后方便扩展。在销毁时，顺序表使用静态分配则由系统自动回收，使用动态分配则手动回收，链表需要手动回收。
在插入/删除元素时，顺序表需要将后续元素进行前移/后移，时间复杂度为O(n)。链表需要只需要修改指针，但是需要查找到目标元素，时间复杂度为O(n)。查找元素的代价比元素移动要低。
在查找元素时，顺序表按位查找时间复杂度为O(1)，按值查找时间复杂度为O(n)，若有序，则可以用二分查找为O(nlogn)。链表按位查找、按值查找时间复杂度为O(n)。
一般来说，若经常做的操作是按序号访问数据元素，则选顺序表。若经常做的操作是插入、删除数据元素，则选链表。若线性表的长度或存储规模难以估计，选择链表。若线性表的长度或存储规模可以事先预知，则选顺序表，因为链表的存储密度较低。
3. 链表的种类
单链表：每个链表结点，除了存放元素自身的信息之外，还需要存放一个指向其后继的指针next。
双链表：在单链表的基础上，增加了一个指向其前驱的指针prior。双链表可以很方便地找到当前结点的前驱，但存储密度更低。
循环链表：在单链表的基础上，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。
循环双链表：在双链表的基础上，表中最后一个结点的next指针指向头结点，头结点的prior指针指向最后一个结点。
4. 头指针和头结点的区别
以单链表为例，头指针就是指向链表第一个结点的指针，链表的第一个结点的地址可以通过链表的头指针找到，对单链表中任一元素的访问必须根据头指针找到第一个结点。通常用头指针来标识一个链表，指出链表的起始地址，头指针为NULL表示一个空表。
头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。引入头结点后，可以带来两个优点:①在链表的第一个位置上的操作和在表的其他位置上操作一致，无需进行特殊处理。②无论链表是否为空，其头指针都是指向头结点的非空指针，因此空表和非空表的处理得到了统一。
5. 判断链表是否有环（非常重要）
“快慢指针”：创建两个指针fast和slow，开始时两个指针都指向链表头head，在每一步操作中slow向前走一步，fast向前走两步。如果存在环，fast 会在环内不断追赶 slow，最终相遇；如果不存在环，fast 会先到达链表末端 (null)，循环结束。时间复杂为O(n)，空间复杂度为O(1)。
bool hasCycle(ListNode *head) {
if (!head || !head->next) return false;
ListNode *slow = head;
ListNode *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
6. 如何逆置一个链表
定义一个仅包含头结点的新链表，依次从待逆置链表中取下各个节点，并将其采用头插法插入到新链表的头节点之后，直至所有节点都被插入。最后，将原链表的头指针指向新链表的头节点，并将头指针返回。
7. 约瑟夫问题
假设有 n 个人围成一个圈，从第一个人开始按顺序报数，数到某个数（例如3）时，报数的人出局，然后继续从下一个人开始按同样的规则报数。这个过程一直重复，直到所有人都出局，最后剩下的一个人。
可以用模拟的方法来解决这个问题，即用循环链表来模拟围成的圈，并按规则依次删除节点。
8. 两个有序的链表A，B。如何把B的结点插入A链表，使之仍是有序的表?
从链表 B 中依次取出每个节点，将其与链表 A 中的节点关键字进行比较，找到适合的位置后将其插入。可以设置一个指针，指向链表 A 中刚刚插入的元素位置。在后续插入过程中，从该位置向后查找合适的插入点，直至 B 链表的所有节点均已插入到链表 A 中。
9. 两个有序数组拼接为有序数组最少和最多比较几次?
最少比较—次:当某个数组的最大元素比另一个数组的最小元素还要小的时候，只需要比较一次。
最多比较min(len A, len B):最多比较两个数组长度中较小值。
第三章 栈、队列、数组
1. 栈和队列的区别和内存结构
栈是只允许在一端进行插入或删除操作的线性表，其中允许进行插入和删除的那一端叫做栈顶，不允许插入和删除的另一端叫做栈底。操作特性是:后进先出（Last In First Out）
栈的存储结构分为顺序存储和链式存储。采用顺序存储的栈称为顺序栈，采用链式存储的栈称为链栈。顺序栈利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针指示当前栈顶元素位置。链栈是利用一个单链表存储数据元素，并将表头作为栈顶进行插入和删除操作。
队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。其操作的特性是先进先出（First In First Out）。队头，又称队首，允许删除的一端。队尾，允许插入的一端。
队列的存储结构可分为顺序存储和链式存储。采用顺序存储的队列称为循环队列，采用链式存储的队列称为链队列。循环队列
2. 简要说说共享栈。★
让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。这样能够更有效的利用存储空间，只有在整个存储空间被占满时才发生溢出。判断栈满的条件为：仅当两个栈顶指针相邻（top1-top0=1）。
3. 如何区分循环队列是队空还是队满？★★
为了区分是队空还是队满的情况，有三种处理方式。
1）牺牲一个单元来区分队空和队满，入队时少用一个队列单元。约定以“队头指针在队尾指针的下一位置作为队满的标志”。
队满条件：(Q.rear+1)%MaxSize==Q.front
队空条件：(Q.front == Q.rear)
队列中元素的个数：(Q.rear-Q.front+MaxSize)%MaxSize
2) 类型中增设size数据成员，表示元素个数。删除成功size-1，插入成功size+1。
队满条件：Q.size==MaxSize
队空条件：Q.size==0
3) 类型中增设tag数据成员，区分是队满还是队空。删除成功则tag=0，若导致Q.front==Q.rear，则为队空；插入成功则tag=1，若导致Q.front==Q.rear，则为队满。
4. 介绍双端队列
双端队列是指允许两端都可以进行插入和删除操作的线性表。
输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列。
输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列。
5. 说说栈在括号匹配中的算法思想。★★
1）依次扫描所有字符
1）遇到左括号，则入栈；
2）遇到右括号，判断栈是否空，若为空，匹配失败，右括号“有余”；若栈不为空，则弹出栈顶元素，栈顶元素是左括号，那么相匹配，否则不匹配。
3）所有字符扫描结束时，如果栈空则表明表达式中匹配正确，否则表明“左括号”有余。
6. 说说栈在后缀表达式求值的算法思想。★★
从左往右依次扫描表达式的每一项，若该项是操作数，则压入栈中；若该项是操作符<op>，则从栈中退出两个操作数Y和X，形成运算指令X<op>Y，并将计算结果压入栈中。当所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。
7. 说说栈在计算机系统中的应用。★★
1）函数调用/函数递归：栈在函数调用中扮演着重要角色。每当一个函数被调用时，函数的参数、 局部变量和返回地址等信息都会被保存在栈中的帧中。函数执行完毕后，相应的帧会被从栈中弹出，恢复上一个函数的执行。
2）表达式求值：编译器和解释器通常使用栈来求解表达式。例如，中缀表达式转换为后缀表达式时，使用栈来调整操作符的顺序。 后缀表达式的计算。
3）括号匹配：栈也常用于括号匹配的问题。通过遍历输入字符串并将左括号入栈，当 遇到右括号时，检查栈顶元素是否与之匹配。可以利用栈的后进先出（LIFO）特性来快速 判断括号是否匹配。
深度优先搜索图、先序遍历二叉树、迷宫求解---- 涉及到递归工作栈
8. 说说队列在计算机系统中的应用。★★
1）任务调度：操作系统中的任务调度器通常使用队列数据结构来管理和调度进程或线程。操作系统通常按照每个请求在时间上的先后顺序，排成一个队列，每次把CPU分给队首请求的进程/线程使用。
2）缓冲区管理：网络通信、磁盘 I/O 等场景中常需要使用队列来处理数据的缓冲区。例如，打印数据缓冲区中所存储的数据就是一个队列。主机把要打印输出的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求。
3）层次遍历：在层次遍历中，先遍历的结点，其孩子结点也会按顺序被遍历到。可以将遍历操作视为入队操作，而遍历孩子结点视为出队操作。由于这种遍历方式遵循"先进先出"的规则，因此队列是最适合存储遍历过程中结点的结构。
4）图的广度优先遍历：在广度优先遍历中，先被遍历的结点，其相邻的顶点也会按顺序被遍历到。同样地，遍历操作可以视为入队操作，而遍历相邻顶点则相当于出队操作。由于遍历顺序同样遵循"先进先出"的规则，因此队列是广度优先遍历中存储结点的理想选择。
9. 特殊矩阵的压缩存储
压缩矩阵：指为多个值相同的元素只分配一个存储空间，对零元素不分配空间。
特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵灯。
特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩到一个存储空间中。
压缩矩阵可以将二维的矩阵存到一维数组中，对二维数组有行优先、列优先两种存储方式。
10.稀疏矩阵
如果在矩阵中，多数的元素为0，通常认为:非零元素/矩阵所有元素<= 0.5，则称此矩阵为稀疏矩阵。
第四章 串
1. 介绍一下 KMP 算法。
KMP 算法是一种高效的字符串匹配算法，用于在一个文本串中查找一个模式串的出现 位置。KMP 算法通过利用模式串自身的信息，在匹配过程中避免不必要的回溯，从而提高 匹配效率。KMP 算法的核心思想是使用一个部分匹配表，也称为 next 数组，来记录模式串中每个位置的最长公共前后缀的长度。这样，在匹配失败时，可以根据部分匹配表的信息，将模式串向右移动尽可能少的步数。
KMP 算法的时间复杂度 O(n+m)，朴素算法的时间复杂度 O(n*m)，n 和 m 是两个串的 长度。
KMP 算法的具体步骤如下： 1）预处理 next 数组：对于模式串，遍历每个位置，计算该位置之前子串的最长公共前后缀的长度，并保存到 next 数组中。 2）匹配过程：从文本串的起始位置开始，用两个指针分别指向文本串和模式串的当前位置，逐个字符进行比较。 如果当前字符匹配成功，则两个指针同时向后移动一位。 如果当前字符匹配失败： 根据 next 数组中的信息，将模式串向右移动尽可能少的步数。根据当前失败位置的部分匹配值，向右移动模式串的指针。 同时，保持文本串的指针不动，继续与模式串的新位置进行比较。 3）如果模式串的指针移到末尾，则表示匹配成功，返回在文本串中的起始位置。如果文本串的指针移到末尾，则表示未找到匹配，返回-1。
KMP算法还可以进一步优化，将next数组改为nextval数组。
问题描述：在使用KMP算法进行字符串匹配时，当出现失配时，算法会利用next数组跳转到某个位置继续匹配。然而，如果在跳转后的位置的字符与当前失配位置的字符相同，这次匹配必定会再次失败。这种情况下，实际上可以进一步跳转，从而避免不必要的匹配尝试。
优化思路：为了避免上述问题，可以将next数组优化为nextval数组。首先求出next数组，然后构造nextval数组。在构造nextval数组时，若next[k]所指向的位置的字符与pattern[k]相同，那么就令nextval[k] = nextval[next[k]]（到nextval元素与失配元素不同就停止），否则令nextval[k] = next[k]。
2. 介绍下朴素匹配字符串算法
朴素匹配字符串算法（也称为暴力匹配算法）是字符串模式匹配的基本方法。该算法逐个检查主串的每个字符，以确定是否存在与模式串匹配的子串。
原理是从源字符串的起始位置开始搜索，如果遇到不匹配的字符，则将匹配窗口向右移动一位，从新的位置继续搜索。具体操作是将主串中与模式串长度相同的所有子串依次与模式串进行逐字符比较，直到找到一个完全匹配的子串，或者遍历完所有可能的子串但没有发现匹配为止。
第五章 树与二叉树
1. 满二叉树和完全二叉树有什么区别？★★
满二叉树： 对于一颗高为 h 的二叉树，结点个数为 2^h-1，表现为除了最后一层叶子结点之外，根节点以及分支结点都有两个孩子，即每一层都是满的。
完全二叉树：则是在满二叉树的基础上，在最后一层从右往左依次删除一定数量的叶子结点所形成的二叉树。完全二叉树的特点是叶子结点只出现在倒数第一和第二层，且如果有分支结点仅有一个孩子，那只能是左孩子。
满二叉树是一种特殊的完全二叉树，满足完全二叉树的所有条件，并且在所有层次上都是满的。完全二叉树的最后一层不一定是满的，但它要求最后一层的节点从左到右排列，不能有间隙。满二叉树和完全二叉树可以用顺序存储结构来存储。
二叉树排序树：左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于右子树的关键字，左子树、右子树又各是一棵二叉排序树。
二叉平衡树：是一种特殊的二叉排序树，它满足对于树上的任意一个结点，其左子树的深 度与右子树的深度之差的绝对值不超过 1。
2. 如何由遍历序列构造一棵二叉树？
对于一棵给定的二叉树，其先序序列、中序序列、后序序列和层序序列都是确定的。然而，只能给出四种遍历序列的任意一种，却无法唯一地确定一棵二叉树。若已知中序序列，再给出其他三种遍历序列中的任意一种，就可以唯一地确定一棵二叉树。
1) 由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。
在先序遍历序列中，第一个结点一定是二叉树的根结点； 而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。如此递归地进行下去，便能唯一地确定这棵二叉树。
2) 由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。
因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，然后采用类似的方法递归地进行划分，进而得到一棵二叉树。
3) 由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树。
简单来说，先序序列、后序序列、层序序列可以确定根结点，中序序列根据根节点可以划分出左右子树的中序序列。然后递归处理左、右子树。
3. 简要二叉树的存储结构★
①顺序存储： 按照二叉树层序遍历的顺序将结点存储于顺序表中，特别注意空节点也需要占有位置。 若某结点下标为 i，则其左孩子下标为 2i，右孩子下标为 2i+1，父节点下下标为 i/2 向下取整。该存储结构适合存储完全二叉树；
②链式存储： 每个结点通常一个数据域与两个指针域，分别指向自己的左孩子和右孩子。而为了充分利用左右孩子指针，可以将左孩子指向自己的前序、中序或后序遍历的直接前序，右孩子指向直接后继，从而形成二叉线索树，方便查找。
4. 二叉树的遍历
先序遍历：访问根节点----先序遍历左子树----先序遍历右子树
中序遍历：中序遍历左子树----访问根节点----中序遍历右子树
后序遍历：后序遍历左子树----后序遍历右子树----访问根节点
层次遍历：借助队列，先将二叉树的根节点入队，然后出队，访问出队结点，若他有左子树则将左子树的根节点入队，若他有右子树则将右子树的根节点入队。然后再出队，访问出队结点。直至队列为空
5. 简要说说树的存储结构。★
1) 双亲表示法
这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个指针，指示其双亲结点在数组中的位置。根节点下标为0，其伪指针域为-1。
双亲表示法利用了每个结点(根节点除外)只有唯一双亲的性质，可以很快地得到每个结点的双亲结点，但求结点的孩子时则需要遍历整个结构。
2) 孩子表示法
孩子表示法是将每个结点的孩子结点视为一个线性表，且以单链表作为存储结构，则n个结点有n个孩子链表（叶结点的孩子链表为空表），而n个头指针又组成一个线性表，为便于查找，可采用顺序存储结构。
与双亲表示法相反，孩子表示法寻找孩子的操作非常方便，而寻找双亲的操作则需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。
3) 孩子兄弟表示法
孩子兄弟表示法又称二叉树表示法，即二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针、以及指向结点下一个兄弟结点的指针(沿此域可以找到结点的所有兄弟结点)。
这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作。这 种存储方式寻找孩子容易，而寻找双亲的操作麻烦。若为每个结点增设一个 parent 域指向其 父结点，则查找结点的父结点也很方便。
6. 完全二叉树的性质
1、叶子结点只能出现在层数最大的两层上
2、如果有度为1的结点，则该结点只有左孩子，而无右孩子
3、一旦出现某个结点为叶子结点，或只有左孩子，则编号大于该结点的均为叶子结点
7. 简要说说线索二叉树
对于 n 个结点的二叉树，在二叉链存储结构中有 n+1 个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。
根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。 线索二叉树解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题。
8. 线索二叉树的构造/中序线索二叉树的线索化
二叉树的线索化是将二叉链表中的空指针改向指向前驱或后继的线索。而前驱或后继的信息只有在遍历是才能得到，因此线索化的实质就是遍历一次二叉树。
中序线索二叉树的构造：附设指针pre指向刚刚访问过的结点，指针p指向正在访问的结点，即pre指向p的前驱。在中序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre;检查pre的右指针是否为空，若为空就将它指向p。
后序线索二叉树的构造：与上面的过程相同，只是遍历方式为后序遍历。
先序线索二叉树的构造：附设指针pre指向刚刚访问过的结点，指针p指向正在访问的结点，即pre指向p的前驱。在先序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre;检查pre的右指针是否为空，若为空就将它指向p。在先序遍历的过程中，在遍历左孩子时需要判断是否为前驱线索，如果是则不遍历。
在中序、前序、后序线索二叉树的构造中，只有先序线索化存在死循环的情况：这是因为根结点的访问早于左子树的访问，根节点的左孩子可能为前驱线索，进而称为死循环。
9. 在给定结点的情况下，怎么寻找线索二叉树的前驱/后继结点
中序遍历线索二叉树找中序前驱：①若指定结点P的左孩子为前驱线索，则左孩子为中序前驱。②若指定结点P的左孩子为左子树，则找到左子树最右下节点。
中序遍历线索二叉树找中序后继：①若P结点右孩子为后继线索，则右孩子为中序后继。②若P结点右孩子为右子树，则找到右子树最左下结点。
先序遍历线索二叉树找先序前驱：如果指定结点的左孩子为前驱线索，则左孩子为先去前驱。如果不是，就需要找到其父结点。因为按照先序遍历的情况来看，求指定结点P的前驱一定需要找到其父结点，故二叉链表无法找到其前驱。存在两种解决方法，1.土方法，从根结点的出发先序遍历。2.使用三叉链表存储，找到父结点。①如果指定结点P能找到父结点，且P是左孩子或P是右孩子，左兄弟为空，则P的父结点为前驱。②如果指定结点P能找到父结点，且P是右孩子，其左兄弟不为空，P的前驱为左兄弟子树中最后一个被先序遍历的结点。③如果指定结点P没有根节点，则结点P为根节点，则无前驱。
先序遍历线索二叉树找先序后继：①指定结点P的右孩子为后继线索，则结点P的右孩子为先序后继。②指定结点P的右孩子为右子树，若指定结点P有左孩子，则先序后继为左孩子，若指定结点P无左孩子，则指定结点P的右孩子为先序后继。
后序遍历线索二叉树找后序前驱:①在后序线索二叉树中，若指定结点P的左孩子为前驱线索，则找到后序前驱元素。②若指定结点P的左孩子不是后序前驱，若P有右孩子，则后序前序为右孩子。若没有右孩子，则后序前驱为左孩子。
后序遍历线索二叉树找后序后继：①若指定结点P的右孩子为后继线索，则找到后序后继元素。②若指定结点P的右孩子不是后继线索，则比较麻烦。若指定结点P是二叉树的根结点，则后继为空；若指定结点P是父结点的右孩子，或是父结点的左孩子并且父结点没有右孩子，则父结点为双亲。若指定结点P是父结点的左孩子，且父结点有右孩子，则后继为父结点右子树上按后序遍历列出的第一个结点。
这里详细的给出土方法：在不建立线索二叉树的情况下，找到指定结点p在遍历序列的前驱或后继。
思路：从根节点出发，重新进行一次中/前/后序遍历，指针q记录当前访问的结点，指针pre记录上一个被访问的结点。若q=p，pre为前驱。若p=pre，p为后继。
10. 如何在计算机上实现中序线索二叉树的遍历?
首先找到最左下的结点，然后依次找到该节点的后继，直至后继为空。先判断其右子树是否为后继线索，若满足，则进行遍历。若不满足，则遍历右子树中第一个访问的结点（右子树中最左下的结点）为后继。
11. 树、森林、二叉树的转换
（1）树转换为二叉树的规则：每个结点的左指针指向它的第一个孩子，右指针指向它在树中相邻的右兄弟。
（2）森林转换为二叉树的规则：先将森林中的每棵树都转换为二叉树，将第二棵二叉树作为第一棵的右子树，将第三棵二叉树作为第二棵二叉树的右兄弟，以此类推，直至只剩下唯一一棵二叉树。
（3）二叉树转换为森林的规则：将根节点右链断开形成两棵二叉树，以此类推直至所有二叉树根节点都不存在右子树，最后将每棵二叉树都转换为树，得到森林。
12. 什么是哈夫曼树？如何构造？哈夫曼树的应用★★★
哈夫曼树又称为最优二叉树，其特点是，给定一组带权的叶子结点，若构造所得到的 二叉树拥有最小的带权路径长度 WPL，则称该二叉树为一棵哈夫曼树。
构造： 将带权叶子结点并入一个集合，首先在集合中挑选出两个权值最小的叶子结点进行合并得到新的结点加入集合，再将两个被选中的结点剔除出集合。在树的构造上，将这两个结点作为叶子结点衔接到合并而成的新结点上。重复以上过程直到集合中只有一个元素，哈夫曼树则完成构造。
应用： 哈夫曼树的应用是哈夫曼编码，其特点是消除了编码前缀相同的二义性（哈夫曼编码是一种前缀编码，前缀编码就是任何一个编码都不是另外一个编码的前缀）。在哈夫曼编码中， 只有哈夫曼树的叶子结点可以进行编码。
性质：哈夫曼编码不是唯一的，不同的构建顺序可能产生不同的编码方案。哈夫曼编码是最优编码。
采用最小堆来实现。
13. 简单介绍一下并查集，说说如何改进？★★★
查集是一种用于解决集合合并和查询问题的数据结构。它能够高效地进行集合的合并 和判断两个元素是否属于同一集合，并在实际应用中常用于解决图的连通性、最小生成树 等问题。
在并查集中，每个元素被看作是一个结点，并以树的形式存储，通常为树的双亲表示法。每个树的根节点代表一个集合，而每个结点则指向其父结点，形成一棵树。所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根节点的双亲域为负数。
并查集的基本操作：
初始化：将每个结点自成单元素集合。循环遍历数组，数组元素赋值为负数，代表根节点。
Find操作：查找根节点，用于确定元素所属的集合。通过迭代地或递归向上查找父节点，直到找到根节点，即可确定所属的集合。当判断两个元素是否属于同一集合，只需分别找到它们的根，再比较根是否相同即可。
Union操作：用于将两个集合合并为一个集合。通过找到两个元素所属集合的根节点，将其中一个根节点的父节点指向另一个根节点，实现合并操作。
改进措施：
路径压缩：是指在进行 Find 操作时，将指向根结点路径上的所有结点直接连接到根节点，可以减小树的高度，加快查找。可以使用递归或迭代的方式进行路径压缩。每次Find的操作先找到x所属的根结点，再将查找路径上所有结点都直接挂在根结点下面。
按秩合并：是指在进行 Union 操作时，将高度较低的树合并到高度较高的树上，从而保持树的平衡性。可以通过记录每个集合的秩（即树的高度或结点数量）来实现按秩合并。
可以用根结点的负值表示一棵树的结点总数。
第六章 图
1. 什么是稀疏图/稠密图
边数很少的图称为稀疏图，反之称为稠密图。一般当图G满足|E| < |V|log|V|时，可以将G视为稀疏图。
2. 连通、连通图、连通分量、
1.从顶点i到j有路径存在，则称i和j是连通的
2.若图中任意两个顶点都是连通的，则称该图为连通图，否则为非连通图
3.无向图的极大连通子图称为连通分量
3. 强连通、强连通图、强连通分量
1.有向图中，从顶点i到j，顶点j到i都有路径存在，则称i和j是强连通的
2.图中任意一对顶点都是强连通的，则称该图是强连通图
3.有向图的极大连通子图成为强连通分量
4. 什么是完全图
无向完全图:任意两个顶点间都有边的存在，n个顶点，有n(n-1)/2条边
有向完全图:任意两个顶点间都有方向相反的两条弧存在n个顶点，有n(n-1)条边。
5. 什么是生成树
连通图的生成树是包含图中全部结点的一个极小连通子图。极小连通为边尽可能的少，但是保持连通。若有n个顶点则有n-1条边，如果在生成树上减去一条边会变成非连通图，添加一条边，会形成一个环。
6. 非连通图的生成森林
在非连通图中，各个连通分量的生成树，构成了非连通图的生成森林。
7. 什么是极小连通子图
极小连通子图是一个子图，它保持连通性，并且如果再去掉其中的任意一条边，子图就不再连通。
8. 什么是极大连通子图
极大连通子图是指在保持连通性的前提下，不能再增加任何顶点或边的连通子图。如果在该子图中添加任何未包含的顶点或边，子图仍然是连通的，那么它就不再是极大连通子图。
9. 图的存储形式有哪些？各有什么优点？
所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系)，存储顶点之间邻接关系的二维数组称为邻接矩阵。邻接矩阵表示法的空间复杂度为O(n2)，其中n为图中的顶点树|V|。邻接矩阵求顶点的度/出度/入度的时间复杂度为O(|V|)，适合存储稠密图。
所谓邻接表，是指图中顶点用一个一维数组存储，存储顶点数据和边表头指针。为每个顶点建立一个单链表，存储依附于此顶点的边，这个单链表就成为边表（对于有向图来说叫出边表）。邻接表的空间复杂度：无向图（每条边存储了两次）：O（V+2E） 有向图O（V+E）。邻接表求解有向图顶点出度只需要计算器邻接表中的边表结点个数，但是求解入度需要遍历整个邻接表，适合存储稀疏图。
十字链表是有向图的一种链式存储结构。在十字链表中，有向图的每条弧用一个结点（弧结点）来表示，每个顶点也用一个结点（顶点结点）来表示。两种结点的结构如下所示。
弧结点中有5个域:tailvex和 headvex两个域分别指示孤尾和弧头这两个顶点的编号;头链域hlink 指向弧头相同的下一个弧结点;尾链域tlink 指向弧尾相同的下一个弧结点; info域存放该弧的相关信息。这样，弧头相同的弧在同一个链表上，弧尾相同的弧也在同一个链表上。
顶点结点中有3个域: data域存放该顶点的数据信息，如顶点名称;firstin域指向以该顶点为弧头的第一个弧结点;firstout域指向以该顶点为弧尾的第一个弧结点。
注意，顶点结点之间是顺序存储的，弧结点省略了info域。
在十字链表中，既容易找到V为尾的弧，也容易找到V为头的弧，因而容易求得顶点的出度和入度。图的十字链表表示是不唯一的，但一个十字链表表示唯一确定一个图。
空间复杂度为：O(|V| + |E|)，求解入度、出度很方便，只能存储有向图。
邻接多重表是无向图的一种链式存储结构。在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低。与十字链表类似，在邻接多重表中，每条边用一个结点表示，其结构如下所示。
其中，ivex和jvex这两个域指示该边依附的两个顶点的编号; ilink域指向下一条依附于顶点ivex的边; jlink域指向下一条依附于顶点jvex的边，info域存放该边的相关信息。
每个顶点也用一个结点表示，它由如下所示的两个域组成。
其中，data域存放该顶点的相关信息，firstedge域指向第一条依附于该顶点的边。
在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，因为每条边依附于两个顶点，所以每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接表的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。
10. 简单介绍一下 dfs 和 bfs，并说说它们的区别？★★★★
广度优先搜索类似于二叉树的层序遍历算法。其基本思想是，先访问起始顶点v，然后从v出发，依次访问v的各个未访问过的邻接顶点。再从这些访问过的顶点出发，重复上述过程，直至图中所有的顶点都被访问过为止。
使用队列数据结构来辅助实现广度优先搜索。
bfs 适用于找到最短路径，因为它按照距离起始节点的层级进行搜索。适合在广度方向上搜索，例如寻找最短路径、连通性判断、社交网络中查找关系等问题。
无论是邻接表还是邻接矩阵的存储方式，BFS算法都要借助一个辅助队列Q，n个顶点均入队一次，在最坏的情况下，空间复杂度为O(|V|)。时间复杂度：邻接表O(|V|+|E|)，邻接矩阵O(|V|2)。
深度优先搜索类似于二叉树的先序遍历算法。其基本思想是，先访问起始顶点v，然后从v出发，访问与v邻接且未被访问的任意一个顶点，重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有的顶点都被访问过为止。
使用栈数据结构来辅助实现深度优先搜索。
dfs 适用于找到一个可行解，不需要找最短路径的情况。适合在深度方向上搜索，例如拓扑排序、连通性判断、回溯等问题。
DFS是一个递归算法，需要借助于递归工作栈，则空间复杂度为O(|V|)。时间复杂度：邻接表O(|V|+|E|)，邻接矩阵O(|V|2)。
11. 简单介绍一下求最小生成树的算法？★★★★
权值之和最小的那颗生成树称为G的最小生成树(MST)。
Prim(普里姆)：
Prim 算法是一种贪心算法，从一个起始结点开始逐步扩展最小生成树的边。首先选择一个起始节点，然后将该结点标记为已访问。通过不断选择与已访问节点相连且权重最小的边，并将相连结点标记为已访问，将这条边加入到最小生成树中。重复上述步骤，直到所有节点都被访问过，即构建出最小生成树。时间复杂度为O(|V|2)，适合求解边稠密的图的最小生成树。
Kruskal(克鲁斯卡尔)：
Kruskal算法也是一种贪心算法，通过按照边的权重从小到大的顺序逐步构建最小生成 树。将图中的所有边按照权重从小到大进行排序。依次遍历排序后的边，如果当前边的两个端点不在同一棵树中（即不会形成环，常常借助并查集实现），则将该边加入最小生成树中，并将两个端点所在的树合并为一棵树。重复上述步骤，直到最小生成树包含图中的所有结点。时间复杂度为O(|E|log2|E|)，适合边稀疏而顶点较多的图。
12. 简单介绍一下最短路径算法？★★★★
最短路径算法通常有 BFS算法、Dijkstra(迪杰斯特拉) 算法和 Floyd (弗洛伊德)算法。BFS 只能处理无权图-单源最短路径，Dijkstra 算法可以处理带权图-单源最短路径(权值不能为负)，Floyd 可以处理各个顶点之间的最短路径(允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路)。
BFS算法:
通过队列来实现，首先将单源点加入队列 。每次循环将队列中队头元素出队，并且将
与该结点相邻的结点加入队列，直到队列为空。每次循环代表距离加一，BFS可以找出单源点到其他结点的路径长度。
耗费的时间取决于所采用的存储结构，采用邻接表存储时，每个顶点均需要搜索(或入队)一次，时间复杂度为O(|V|)，在搜索每个顶点的邻接点时，每条边至少访问一次，时间复杂度为O(|E|)，总的时间复杂度为O(|V|+|E|)。采用邻接矩阵存储时，查找每个顶点的邻接点所需时间为O(|V|)，总时间复杂度为O(|V|2)。
Dijkstra(迪杰斯特拉) 算法:
应用了贪心的思想，通常解决单源点问题。时间复杂度为 O(|V|²)，堆优化后是 O(nlogn)，n为顶点个数。
算法步骤：
初始化:
- 设定源点为 s，将源点 s 放入集合 S，初始时 S 只包含源点 s。
- 初始化源点到各顶点的最短路径长度。对于源点 s，其自身的路径长度设为 0，对其他顶点 v，若存在从 s 到 v 的边，则设为边的权重，否则为正无穷大（表示不可达）。
迭代过程:
- 在每一步中，从未被选择的顶点集合中选取一个距离源点最近的顶点 u，将其加入集合 S。
- 对于这个新加入的顶点 u，更新源点 s 到其他未在集合 S 中的顶点 v 的最短路径长度。如果通过顶点 u 到达顶点 v 的路径长度比当前记录的 s 到 v 的路径长度更短，则更新 v 的最短路径长度。
终止条件:
- 当所有顶点都被包含在集合 S 中时，算法结束，此时已得出源点到所有其他顶点的最短路径。
Floyd (弗洛伊德)算法
应用了动态规划的思想，通常解决多源点问题，时间复杂度为 O(n³)。
先初始化，声明 dp 数组，dp[i][j]表示从 i 到 j 的权值，一开始数组中值均为 inf，而 后更新 dp[i][i]所有点到自己的权值是 0。 输入每条边的结点和权值 u,v,w，更新 dp[u][v]=w，表示从 u 到 v 的权值是 w。 利用三层循环，然后逐步试探当前加入的点。 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])；如果 i 到 k 的权值+k 到 i 的权值比 i 到 j 的权值小， 那么进行松弛，否则就继承原来的 dp[i][j]。 直到循环结束。
13. 图与树的区别
1.树是一对多的关系，图是多对多的关系
2.树是图的子集
3.树有一个根结点，图没有根节点的概念
4.树可以递归遍历，图要看情况
5.树是一种层次关系，图是网状关系
14. 有向图和无向图的联系，试各举─例说明?
无向图可以看作每条边都有两个方向的有向图
无向图的邻接矩阵一定是对称阵，而有向图的邻接矩阵不一定对称。
无向图能解决的问题都能用有向图表示，但无向图在对称的问题上往往更容易，因为有向图去表示无向图时需要两倍的边数
15. 拓扑排序
AOV网:若用有向无环图表示一个工程，其顶点表示活动，用有向边<Vi, Vj>表示活动Vi必须先于活动Vj进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，简称AOV网。在AOV网中，活动Vi是活动Vj的直接前驱，Vj是Vi的直接后继，这种前驱和后继关系具有传递性，且任何活动Vi不能以它自己作为自己的前驱或后继。
拓扑排序:在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序:
1）每个顶点出现且只出现一次。
2）若顶点A在序列中排在顶点B的前面，则在图中不存在从B到A的路径。
或定义为:拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中B出现在A的后面。每个 AOV网都有一个或多个拓扑排序序列。
对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤:
①从AOV网中选择一个没有前驱（入度为0)的顶点并输出。
②从网中删除该顶点和所有以它为起点的有向边。
③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
16. 关键路径
在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网。AOE网和AOV 网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，AOE网中的边有权值;而AOV网中的边无权值，仅表示顶点之间的前后关系。
AOE网具有以下两个性质:
①只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始;②只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。在AOE网中仅有一个入度为0的顶点，称为开始顶点(源点)，它表示整个工程的开始;也仅有一个出度为0的顶点，称为结束顶点（汇点)，它表示整个工程的结束。
在AOE 网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。
第七章 查找
1. 查找算法的评价指标
平均查找长度。在查找过程中，一次查找的长度是根据需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。
2. 顺序查找（线性查找）
基本思路：作为一种最直观的查找方法，其基本思想:①从线性表的一端开始，逐个检查关键字是否满足给定的条件;②若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置;③若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。
基本实现：对于顺序表，可通过数组下标递增来顺序扫描每个元素；对于每个链表，可以通过指针next来依次扫描每个元素。
适用范围：顺序表和链表
时间复杂度：O(n)
查找成功的平均次数为：1/n + 2/n +3/n + …+ n/n = (n + 1)/2
查找失败的平均次数为：从末尾查找，直到查找到哨兵为止，才知道查找失败，故为n+1次。
优化思路1：若表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回失败信息，降低查找失败的平均查找长度。
优化思路2：若每个元素被查的概率不等，则将被查概率大的放在靠前的位置。
3. 折半查找（二分查找）
基本思想：①首先将给定值key 与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置;②若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分(例如，在查找表升序排列时，若key大于中间元素，则所查找的元素只可能在后半部分)，然后在缩小的范围内继续进行同样的查找。重复上述步骤，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。
基本实现：初始化一个数组A存放有序表中元素，初始化三个伪指针low，high，mid，分别表示查找区域的最左元素下标，查找区域的最右元素下标，以及当前比较元素下标。如果A[mid]>查找值key，则让high=mid-1，查找左半区；如果A[mid]<key，则让low=mid+1，查找右半区。直至A[mid]=key或者low>high为止。
适用范围：有序的顺序表，因为涉及到了随机访问
查找失败/查找成功的次数是一个范围，但是都不会超过树的高度，h = ⌈log2(n+1)⌉或⌊log2n⌋ + 1
时间复杂度：O(log2n)
4. 分块查找（索引顺序查找）
分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的仇点，既有动态结构，又适用于快速查找。
分块查找的基本思想:将查找表分为若干子块。块内的元素可以无序，但块间的元素是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。
分块查找的过程分为两步:第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表;第二步是在块内顺序查找。
适用范围：顺序表和链表，索引表如果是顺序表则可以折半查找索引表。
时间复杂度：分块查找的平均查找长度为索引查找和块内查找的平均长度之和。
若都为顺序查找，则平均查找长度为n1/2 + 1。若折半查找索引表，则为⌈log2(b+1)⌉ + (s + 1)/2，b为块数，s为块内记录数。
5. 简要说说二叉排序树。★★
二叉排序树（也称二叉查找树、二叉搜索树）或者是一棵空树，或者是具有下列特性的二叉树：
1) 若左子树非空，则左子树上所有结点的值均小于根结点的值。
2) 若右子树非空，则右子树上所有结点的值均大于根结点的值。
3) 左、右子树也分别是一颗二叉排序树。
根据二叉排序树的定义，左子树结点值 < 根结点值 < 右子树结点值，因此二叉排序树进行中序遍历，可以得到一个递增的有序序列。
它利用了二分的思想，可以快速查找到关键码，查找效率为 O(nlogn)。
缺点：如果按照从小到大插入构建 BST，会导致查找效率退回 O(n)级别。
改进：插入时要旋转保证平衡因子绝对值不大于 1，于是产生了 AVL 树(平衡二叉树)。
2. 简要说说二叉搜索树的查找、插入和删除过程。★★★
查找：从根节点开始，沿某个分支逐层向下比较的过程。若二叉排序树非空，先将给定值与根结点的关键字比较，若相等，则查找成功；若不等，若小于根节点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找。
插入：若原二叉排序树为空，则直接插入；否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树。插入的结点一定是一个新添加的叶结点，且是查找失败时查找路径上访问的最后一个结点的左孩子或右孩子。
删除：同样是基于查找操作，首先查找到欲删除的结点。此时，删除结点通常包括三种情况 ①若删除的结点是叶子结点，则可以直接删除； ②若删除的结点只有一棵左子树或右子树，则用它的子树代替它； ③若删除的结点有左、右两棵子树，则可以寻找其中序遍历的直接前驱或者直接后继代替它， 再删去该直接前驱或直接后继。
二叉排序树的删除、插入都是基于查找操作，若二叉排序树的左、右子树的高度之差的绝对值不超过1，它的平均查找长度为O(nlog2n)。若二叉排序树是一个只有右(左)孩子的单支树(类似于有序的单链表)，则其平均查找长度为O(n)。
3. 简要说说平衡二叉树。★★★
原因：为了避免树的高度增长过快，降低二叉排序树的性能，引入二叉平衡树。
二叉平衡树是一种特殊的二叉排序树，它满足对于树上的任意一个结点，其左子树的深 度与右子树的深度之差的绝对值不超过 1。平衡因子可以用于描述二叉平衡树，平衡因子是 某个结点的左子树深度与右子树深度之差，对于一棵二叉平衡树，其任意结点的平衡因子只 能是-1，0 或 1。
插入：每当在二叉排序树中插入（删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。如果导致了不平衡，则先找到插入路径上离插入节点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树（最小平衡子树），在保持二叉排序树特性的前提下，调整各节点的位置关系，使之重新达到平衡。
设最小平衡子树的根节点为A
LL:如果由于在结点A的左孩子的左子树上插入新节点而导致失去平衡，则通过一次右单旋转调整。
RR:如果由于在结点A的右孩子的右子树上插入新节点而导致失去平衡，则通过一次左单旋转调整。
LR:如果由于在结点A的左孩子的右子树上插入新结点而导致失去平衡，则先通过一次左旋再通过一次右旋调整。
RL:如果由于在结点A的右孩子的左子树上插入新结点而导致失去平衡，则先通过一次右旋再通过一次左旋调整。
删除：与平衡二叉树的插入操作类似，以删除结点w为例来说明平衡二叉树删除操作的步骤:
1）用二叉排序树的方法对结点w执行删除操作。
2）若导致了不平衡，则从结点w开始向上回溯，找到第一个不平衡的结点z(即最小不平衡子树);y为结点z的高度最高的孩子结点;x是结点y的高度最高的孩子结点。
3）然后对以z为根的子树进行平衡调整，其中x、y和z可能的位置有4种情况:
·y是z的左孩子，x是y的左孩子(LL，右单旋转);
·y是z的左孩子，x是y的右孩子（LR，先左后右双旋转);
·y是z的右孩子，x是y的右孩子（RR，左单旋转);
·y是z的右孩子，x是y的左孩子(RL，先右后左双旋转)。
这四种情况与插入操作的调整方式一样。不同之处在于，插入操作仅需要对以z为根的子树进行平衡调整;而删除操作就不一样，先对以z为根的子树进行平衡调整，若调整后子树的高度减1，则可能需要对z的祖先结点进行平衡调整，甚至回溯到根结点(导致树高减1)。
缺点：如果插入操作比查询操作多，AVL 就要花费大量开销做旋转来调整结点以保证 树的平衡。
改进：为了减少旋转开销，引入了红黑树。
4. 简要说说红黑树★★
原因：为了保持平衡二叉树的平衡性，在插入和删除操作后，会非常频繁地调整全树整体的拓扑结构，代价较大。为此在平衡二叉树的平衡标准上进一步放宽条件，引入了红黑树的结构。
一棵红黑树是满足如下红黑性质的二叉排序树：
①每个结点或是红色，或是黑色的。
②根节点是黑色的。
③叶结点(虚构的外部结点、NULL结点)都是黑色的。
④不存在两个相邻的红结点(即红结点的父结点和孩子结点均是黑色的)。
⑤对每个结点，从该结点到任意一个叶结点的简单路径上，所含黑结点的数量相同。
C++中的map和set(Java中的TreeMap和TreeSet)就是用红黑树实现的。
插入和删除的时间复杂度为O(nlog2n)
5. 简要说说 B 树 ★★★★★
引入 B 树的原因： 若普通二叉树作为文件系统的索引，随着数据的插入，发现树的深度会变深。而文件系统的索引在磁盘上，磁盘的数据要加载到内存中才能处理，需要反复 IO 影响查询的效率， 于是引入了 B 树可以作为文件系统的索引。
B 树是多叉树，一棵 m 阶 B 树的性质：
还可以看看删除与查找。
| 操作 | BST (平均情况) | BST (最坏情况) | AVL Tree | Red-Black Tree |
| 查找 | O(log n) | O(n) | O(log n) | O(log n) |
| 插入 | O(log n) | O(n) | O(log n) | O(log n) |
| 删除 | O(log n) | O(n) | O(log n) | O(log n) |
6. 简要说说 B+树。★★★★
B+树是应数据库所需而出现的一种B树的变形树。
一棵m阶B+树应满足下列条件:
1）每个分支结点最多有m棵子树(孩子结点)。
2）非叶根结点至少有两棵子树，其他每个分支结点至少有⌈m/2⌉棵子树。
3）结点的子树个数与关键字个数相等。
4）所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来（支持顺序查找)。
5）所有分支结点（可视为索引的索引）中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针。
7. 简要说说 B 树和 B+树的区别。★★★★★
1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树;而在B树中，具有n个关键字的结点含有n+1棵子树。
2）在 B+树中，每个结点（非根内部结点）的关键字个数n的范围是⌈m/2⌉≤n≤m（非根结点:2≤n≤m);而在B树中，每个结点(非根内部结点)的关键字个数n的范围是⌈m/2⌉-1≤n≤m-1(根结点:1≤n≤m-1)。
3）在 B+树中，叶结点包含了全部关键字，非叶结点中出现的关键字也会出现在叶结点中;而在B树中，最外层的终端结点包含的关键字和其他结点包含的关键字是不重复的。
4）在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有对应记录的存储地址。这样能使一个磁盘块存储更多的关键字，使得磁盘读/写次数更少，查找速度更快。
5）在B+树中，用一个指针指向关键字最小的叶结点，将所有叶结点串成一个线性链表。
8. 介绍一下哈希表，如何构造哈希函数，如何解决哈希冲突？★★★★
哈希表又称为散列表，是根据关键字的值直接进行访问的数据结构，即它通过把关键码的值映射到表中的一个位置以加快查找速度，其中映射函数叫做哈希函数，存放记录的数组叫做哈希表。
哈希函数的构造方法：
（1）直接定址法：直接取关键字的某个线性函数值作为散列地址，散列函数为H(key)=a*key+b。适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。
（2）除留余数法：取关键字对 p 取余的值作为散列地址，散列函数为H(key)=key%p，p 尽量选择质数，且接近并且不大于表长，为了使散列分布更均匀。这种方法较为通用，只要关键字是整数即可。
（3）数字分析法：设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知关键字集合，若更换了关键字，则需要重新构造新的散列函数。
（4）平方取中法：取关键字的平方值的中间几位作为散列地址。具体取多少位要是视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
哈希冲突的解决方法：
（1）开放地址法：当发生冲突时，使用一定的探测序列方法，在哈希表中寻找下一个可用的空槽位，将冲突的元素插入到这个空槽位中。常见的探测序列方法有线性探测法、平方探测法（二次探测法）、双散列法、伪随机序列法等。
（2）拉链法：将哈希表的每个索引位置看作一个链表的头节点，当发生冲突时，将冲突的元素插入到链表中即可。这样，每个索引位置都可以存储多个元素。也就是把所有的同义词存储在一个线性链表中，这个线性链表有其散列地址唯一标识。
第八章 排序
1. 排序的定义
排序，是重新排列表中的元素，使表中的元素满足关键字有序的过程。
算法的稳定性：两个关键字相同的元素排序前后相对顺序不变
排序算法分类：
内部排序：排序期间元素全部存放在内存中（关注如何降低时间、空间复杂度）
外部排序：在排序期间元素无法全部同时存放在内存中，必须在排序过程中不断在内外存之间移动元素。（关注如何使读/写磁盘次数减少）
2. 直接插入排序
思路：每次将一个待排序的记录按其关键字大小插入前面已经排好序的子序列，直到全部记录插入完成。
空间复杂度：使用常数个辅助单元，空间复杂度为O(1)
时间复杂度：最好：表中元素有序，每插入一个元素只需要比较一次而不需要移动 O(n)；最坏：表中元素逆序，O(n2)，平均时间复杂度为O(n2)。因此，直接插入排序算法的时间复杂度为O(n2)
稳定性：稳定。因为每次插入元素时总是从后往前先比较再移动，所以不会出现相同位置相对位置发生变化的情况。
适用性：顺序存储和链式存储的线性表。
3. 折半插入排序
思路：每次将一个待排序的记录通过折半查找，找出其在前面已经排好序的子序列中的待插入位置，然后统一的移动待插入位置之后的所有元素，将其插入。
实现：初始化一个数组A存放已经排好序的子序列，初始化三个伪指针low，high，mid，分别表示查找区域的最左元素下标，查找区域的最右元素下标，以及当前比较元素下标。如果A[mid]>查找值key，则让high=mid-1，查找左半区；如果A[mid]<key，则让low=mid+1，查找右半区。直至low>high时停止查找，将low指针及之后的元素全部右移一位，并将元素插入到low指针所指位置。
空间复杂度：使用常数个辅助单元，空间复杂度为O(1)
时间复杂度：仅减少了比较元素的次数，约为O(nlog2n)，元素移动次数未改变O(n2)，因此时间复杂度还是O(n2)。最好、最坏、平均情况同直接插入排序。
稳定性：稳定。折半插入排序的插入过程同直接插入排序，只是改变了查找过程。
适用性：顺序存储的线性表（折半查找用到了下标）
4. 希尔排序（缩小增量排序）
思路：即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，缩小增量重复上述过程，直至增量为1为止。
空间复杂度：仅使用了常数个辅助单元，空间复杂度为O(1)
时间复杂度：约为O(n1.3)，最坏情况下为O(n)
稳定性：不稳定，相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序。
适用性：顺序存储的线性表（分割子表用到了下标）
插入排序算法中希尔排序不稳定。
5. 冒泡排序
思路：从后往前两两比较相邻元素的值，若为逆序则交换他们，直至将最小的元素交换到待排序序列的第一个位置，即为一趟冒泡。下一趟冒泡时，前一趟确定的最小元素不再参与比较。重复进行冒泡直至元素不再发生交换为止。每一次冒泡的结果都是可以确定一个最小元素的位置。
空间复杂度：仅使用了常数个辅助单元，空间复杂度为O(1)
时间复杂度：最好情况：初始序列有序，进行一趟冒泡即可跳出循环，O(n);最坏情况：初始序列逆序，要进行n-1趟冒泡，第i趟冒泡要进行n-i次关键词比较，O(n2);平均时间复杂度为O(n2)。时间复杂度还是O(n2)
稳定性：稳定。由于i>j且A[i]=A[j]时，不会发生交换。
适用性：顺序存储和链式存储的线性表
6. 快速排序
思路：快速排序采用了分治的思想。快速排序的核心思想是选择一个基准元素，通过将数组中的元素按照基准元素进行划分，使得左侧的元素都小于基准元素，右侧的元素都大于基准元素。然后对左右两个子数组分别进行递归排序，直到整个数组有序。
实现：从数组中选择一个元素作为基准元素（pivot）。这个基准元素可以是数组的第一个元素、最后一个元素、中间元素，或者随机选择一个元素。将数组中的其他元素按照与基准元素的大小关系分成两部分：一部分元素比基准元素小，另一部分元素比基准元素大。具体的划分方法通常是从数组的两端开始，左指针从左往右移动，直到找到比基准元素大的元素；右指针从右往左移动，直到找到比基准元素小的元素。然后交换这两个元素。重复这个过程，直到左右指针相遇，此时基准元素被放置在正确的位置上。基准元素被放置在正确的位置后，数组被分成了两个子数组：左子数组包含所有小于基准元素的元素，右子数组包含所有大于基准元素的元素。然后对这两个子数组分别进行递归排序。由于每次递归都会把基准元素放在正确的位置，最终整个数组都会变得有序。每一次划分可以确定基准元素的位置。
空间复杂度：快速排序是递归的，需要一个递归工作栈实现，其容量与递归调用的最大深度一致。最好情况下O(log2 n)，最坏情况下O(n)，平均情况下O(log2 n)
时间复杂度：最好：每次选择的枢轴元素都能将序列化分成均匀的两部分，O(nlog2n)；最坏：初始排序表基本有序或者逆序时，O(n2)。平均时间复杂为O(nlog2n)。一般情况下，选择最坏时间复杂度作为快速排序的时间复杂度，但是最坏时间复杂度一般可以避免，选择一个合适的划分即可，所以时间复杂度为O(nlog2n)
稳定性：不稳定
适用性：顺序存储的线性表
交换排序中快速排序不稳定。
7. 简单选择排序
思路：每一趟（比如第i趟）在后面n-i+1个待排序元素中选取关键字最小的元素，与第i个元素进行交换，每一趟排序可以确定一个元素的最终位置，经过i-1趟排序就可以让整个排序表有序。
空间复杂度：O(1)
时间复杂度：所有情况均为O(n2)
稳定性：不稳定
适用性：顺序存储和链式存储的线性表
8. 堆、大顶堆、小顶堆实现及应用 ★★
堆是一种特殊的完全二叉树，可以分为大根堆、小根堆。
大顶堆：每个父结点的值都大于孩子结点
小顶堆：每个父结点的值都小于孩子结点
堆排序思路（以大根堆为例）：首先将元素构成初始大根堆，输出堆顶元素，并把堆底元素送入堆顶。此时根节点已经不满足大根堆的性质，堆被破坏，将堆顶元素向下调整使其继续满足大根堆的性质，再输出栈顶元素。重复上述步骤，直至堆中仅剩一个元素为止。
大根堆先输出的是最大元素的值，可以认为是从大到小输出。同时，也可以从小到大，让栈顶元素与栈底元素交换，这样最大元素被放置在后面。
初始建堆：把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整。将当前结点与更大的一个孩子结点互换，若元素互换破坏了下一级的堆，则采用相同的方法继续向下调整。
插入：将新元素放到表尾，根据大根堆的要求，新元素不断“上升”，直到无法继续上升为止。
删除：被删除元素用表尾元素替代，根据大根堆的要求，替代元素不断下坠，直到无法下坠为止。
空间复杂度：O(1)
时间复杂度：建堆时间为O(n)，之后进行n-1次向下调整，每次调整时间复杂度为O（h），所以在最好、最坏和平均情况下，堆排序的时间复杂度为O（nlog2n）
稳定性：不稳定
适用性：顺序存储的线性表
9. 归并排序
归并的含义是将两个或两个以上的有序表组合成了一个新的有序表。
二路归并排序：将待排序表中的n个记录视为n个有序子表，每个子表长度为1。然后两两归并，得到 ⌈ n/2 ⌉个长度为2或1的有序表，继续两两归并，直至归并成一个长度为n的有序表为止。基于分治法。
MergeSort实现：传入数组A(待排序数组)，low,high。①若low<high，则将序列从中间mid=(low+high)/2分开。②对左半部分[low, mid]递归地进行归并排序。③对右半部分[mid+1,high]递归地进行归并排序。④将左右两个有序子序列Merge。
Merge实现：初始化两个数组A和B，将两个要进行归并操作的有序表复制到数组B的相邻位置，每次从B中的两个有序表分别取出一个关键字进行比较，将小的存入A，当B中有一段的下标超出其对应的表长(即该段的所有元素都已复制到A中)时，将另一段的剩余部分直接复制到A中。
空间复杂度：Merge操作中需要赋值空间为n个单元，O(n)
时间复杂度：每趟归并的时间复杂度为O(n),共进行⌈ log2n⌉趟归并，因此时间复杂度为O(nlog2n)
稳定性：稳定
适用性：顺序存储和链式存储的线性表
10. 基数排序
不基于比较和移动进行排序，而是基于关键字各位的大小进行排序。
思路：设置r个空队列(r为基数)，按照各个关键字位权重递增的次序，对d个关键字位分别进行分配和收集操作。分配：顺序扫描各个元素，根据当前处理的关键字位将元素插入相应队列。收集：把各个队列中的结点依次出队并连接。
空间复杂度：O(r)，r是队列数
时间复杂度：基数排序需要进行d趟分配和收集(d是关键字位数)，一趟分配要O(n)，一趟收集要(O)，时间复杂度为O(d(n+r))
稳定性：稳定
适用性：顺序存储和链式存储的线性表
11. 插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序（必考）、堆排序、基数排序等排序算法的基本思想是什么？时间复杂度？是否稳定？给一个例子，问冒泡和快速排序在最坏的情况下比较几次？（排序必考）★★★★★★
快速排序： 最坏情况下比较n(n-1)/2次
冒泡排序： 最坏情况下比较n(n-1)/2次
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 | |
| 插入排序 | 直接插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 折半插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 | |
| 希尔排序 | O(nlog2 n)~O(n2) | O(n1.3) | O(n2) | O(1) | 不稳定 | |
| 交换排序 | 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 快速排序 | O(nlog2 n) | O(nlog2 n) | O(n2) | O(log2 n)~O(n) | 不稳定 | |
| 选择排序 | 简单选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 堆排序 | O(nlog2 n) | O(nlog2 n) | O(nlog2 n) | O(1) | 不稳定 | |
| 归并排序 | O(nlog2 n) | O(nlog2 n) | O(nlog2 n) | O(n) | 稳定 | |
| 基数排序 | O(d(n+r)) | O(r) | 稳定 |
不稳定的算法：希尔排序、快速排序、简单选择排序、堆排序。
基于分治法的算法：快速排序、堆排序、归并排序
12. 简述一下快速排序和归并排序的优缺点（从平均最坏时间复杂度、空间复杂度、稳定性 的角度）。★★★★★★
（1）快速排序
优点： ①平均时间复杂度较低：快速排序的平均时间复杂度为 O(nlogn)，在大多数情况下都能够达到较好的排序效果。 ②平均空间复杂度较低：快速排序的平均空间复杂度为 O(logn)，快速排序通常只需要使用很少的额外空间。 缺点： ①最坏情况下的性能：在最坏情况下，即待排序序列已经有序或近乎有序时，快速排序的时间复杂度会退化到 O(n²)，空间复杂度为O(n)，导致性能下降。 ②不稳定性：快速排序是一种不稳定的排序算法，在交换元素的过程中可能改变相同关键字元素的相对顺序。
（2）归并排序
优点： ①稳定性：归并排序是一种稳定的排序算法，它能够保持相同关键字元素的相对顺序不 变。②适用于外部排序：归并排序的特点使其非常适用于外部排序，即当排序的数据量太大无法完全加载到内存时，可以通过分阶段地读取和写入数据进行排序。③性能稳定：归并排序的时间复杂度始终保持在 O(nlogn)，无论是最佳、最坏还是平均情况下。缺点：①需要额外的空间：归并排序需要额外的空间来存储临时数组，因此它的空间复杂度相对较高。② 一般情况下，整体速度通常略低于快速排序。
13. 为什么排序需要稳定？★★★★
排序算法的稳定性意味着对于具有相同关键字的元素，排序后它们的相对顺序保持不变。 在很多实际应用中，我们需要保持数据中相等元素的顺序关系。例如，在排序员工工资的数据时，如果有多名员工拥有相同的工资水平，我们可能希望按照他们的入职时间来排序，以维持他们在公司内部的先后顺序。如果使用不稳定排序，就可能打乱他们的相对顺序。
14. 归并排序的最坏时间复杂度优于快排，为什么我们还是选择快排？★★★★★★
1）快速排序通常比归并排序更快。尽管快速排序在最坏情况下的性能可能较差，但 在大多数情况下，它的平均时间复杂度要比归并排序低。
2）快速排序是原地排序算法。原地排序算法是指排序过程中不需要额外的存储空间， 只利用原始输入数组进行排序。
15. 如何解决 TopK 问题？★★★★
TopK 问题是指在一组元素中，找出其中最大（或最小）的 K 个元素。
（1）排序法 将所有元素进行排序，然后取出最大（或最小）的 K 个元素即可。时间复杂度为 O(nlogn)， 其中 n 为元素的个数。这种方法简单直观，但对于大规模数据来说效率较低。
（2）堆 使用最大堆或最小堆来解决 TopK 问题。首先构建一个大小为 K 的堆，将前 K 个元素插入堆中，然后将剩余的元素与堆顶元素进行比较，如果大于（或小于）堆顶元素，则将其替换并进行堆调整操作。时间复杂度为 O(nlogK)，空间复杂度为 O(K)。
（3）快速选择算法 基于快速排序的思想，通过每次划分数组找到第 K 大（或第 K 小）的元素。将数组划分为两部分，左边的元素都大于（或小于）划分点，右边的元素都小于（或大于）划分点。 如果划分点的下标为 K-1，则找到了第 K 大（或第 K 小）的元素。时间复杂度为 O(n)，空间复杂度为 O(1)。