【嵌入式八股】一、语言篇https://www.nowcoder.com/creation/manager/columnDetail/mwQPeM

【嵌入式八股】二、计算机基础篇（本专栏）https://www.nowcoder.com/creation/manager/columnDetail/Mg5Lym

【嵌入式八股】三、硬件篇https://www.nowcoder.com/creation/manager/columnDetail/MRVDlM

【嵌入式八股】四、嵌入式Linux篇https://www.nowcoder.com/creation/manager/columnDetail/MQ2bb0

数据结构

基础问题

第一章 绪论

1.数据结构的逻辑结构有哪些？物理结构有哪些？

数据的逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。数据的逻辑结构分为线性结构和非线性结构，线性结构包括一般的线性表、栈、队列、串、数组，非线性结构包括集合、树、图。

数据的物理结构是指数据结构在计算机中的表示（又称映像），也称存储结构。数据的物理结构主要有顺序存储、链式存储、索引存储和散列存储。

3.什么是数据结构？数据结构在学什么？

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构研究的是计算机操作对象的逻辑结构、物理结构以及数据的运算。

4.数据结构的复杂度是什么意思？

时间复杂度：算法中所有语句的频次。

空间复杂度：指算法运行过程中所使用的的辅助空间的大小。

5.常见的数据结构有哪些，说说他们之间的逻辑关系。

数据结构四种常见的逻辑结构：

1）集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

2）线性结构：数据结构中的元素存在一对一的相互关系；

3）树形结构：数据结构中的元素存在一对多的相互关系；

4）图形结构：数据结构中的元素存在多对多的相互关系。

第二章 线性表

1.顺序表和链表的比较

数组和链表的区别是什么？

解释一下顺序存储和链式存储

存取（读取）方式

顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。

逻辑结构与物理结构

采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来实现的。

查找、插入和删除操作

查找：对于按值查找，顺序表无序时，两者的时间复杂度均为O（n）；顺序表有序时，可采用折半查找，此时的时间复杂度为O (log2n)。对于按序号查找，顺序表支持随机访问，时间复杂度仅为O（1），而链表的平均时间复杂度为O（n）。

插入、删除：顺序表的插入、删除操作，平均需要移动半个表长的元素；链表的插入、删除操作，只需要修改相应的结点指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大。

空间分配

顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新的元素，则会出现内存溢出，因此需要预先分配足够大 的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态分配存储虽然存储空间可以扩 充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。

链式存储的结点空间只在需要时申请分配，只要内存有空间就可以连续分配，操作灵活、高效。

存存插删空

2.数组和链表的应用场景

数组适合的场景：

1. 当需要快速访问数据时，尤其是在随机访问时，因为数组支持通过下标直接访问元素，因此访问速度非常快。
2. 当数据量比较小且大小固定时，因为数组的空间是连续的，因此数组的存储效率较高。
3. 当需要在数组中进行排序和搜索操作时，因为数组支持随机访问和下标访问，因此这些操作可以在很短的时间内完成。

链表适合的场景：

1. 当需要频繁插入和删除元素时，因为链表的插入和删除操作比较方便，只需要改变指针指向即可，而不需要像数组那样移动元素。
2. 当数据量比较大且大小不确定时，因为链表的空间是动态的，因此可以根据需要进行扩展或缩小。
3. 当需要构建树形结构或图形结构时，因为链表可以通过指针相连的方式来表示树形结构或图形结构。

3.解释下头指针和头结点的区别？单链表增加头结点的目的是什么？

头指针：是指向第一个结点存储位置的指针，具有标识作用，无论链表是否为空，头指针都存在。

头结点：是为了操作统一和方便设立的，放在第一个元素结点之前，头结点的数据域可以不存储任何信息，因此头结点可有可无。

单链表增加头结点可以方便运算。

4.循环链表的优点是什么？

可以从任意一个结点访问整个链表。

5.循环链表怎么遍历

循环链表和普通链表类似，也是一种链式数据结构，只是循环链表的最后一个节点指向第一个节点，形成了一个环。

循环链表的遍历可以使用类似于普通链表的方式，只需定义一个指针变量从头节点开始遍历即可，不同的是，在遍历时需要注意循环终止的条件。

以下是一种常见的循环链表遍历的方式：

1. 定义一个指针变量 p，指向循环链表的头节点；
2. 如果循环链表不为空，则从头节点开始遍历，否则直接结束遍历；
3. 在循环中，每次将指针变量 p 指向下一个节点，直到 p 指向头节点，表示已经遍历完整个循环链表；
4. 在遍历过程中，可以对每个节点执行相应的操作，比如输出节点的值、删除节点等。

6.链表有环怎么处理

链表有环是指链表中存在一个节点的指针指向了链表中的某个已经访问过的节点，从而形成了一个环形结构。链表有环可能会导致一些问题，比如遍历链表时出现死循环，或者在查找某个节点时无法结束。

在判断链表是否有环时，可以使用快慢指针的方法。具体步骤如下：

1. 定义两个指针 slow 和 fast，初始时都指向链表的头节点；
2. slow 指针每次向后移动一个节点，fast 指针每次向后移动两个节点；
3. 如果链表中不存在环，fast 指针最终会指向链表的末尾（即为 NULL），此时可以结束遍历；
4. 如果链表中存在环，由于 fast 指针移动的速度是 slow 指针的两倍，因此在遍历的过程中 fast 指针一定会追上 slow 指针，并且在某个节点处相遇；
5. 如果两个指针相遇，则说明链表中存在环，此时可以使用类似于找到环的起点的方法来处理环形链表。

找到环的起点的方法可以使用双指针，具体步骤如下：

1. 定义两个指针 p1 和 p2，初始时都指向链表的头节点；
2. p1 指针向后移动一个节点，p2 指针向后移动两个节点，直到两个指针相遇；
3. 让 p1 指针重新指向链表的头节点，p2 指针不动；
4. 同时移动 p1 和 p2 指针，每次都向后移动一个节点，直到两个指针再次相遇，相遇的节点即为环的起点。

7.双向链表插入结点

插入：

不唯一，但是1、2必须在3前面

s->next=p->next; //将结点s插入到结点p之后
p->next->prior=s;
s->prior=p;
p->next=s;

删除：

p->next=q->next; 
p->next->prior=p; 
free(q); 

8.一道类似于数据接收处理，然后返回的题目

题目描述：

有一个从计算机接收数据的函数：

void data_recevied(uint8_t *data, size_t size, size_t offset);

这个函数的功能，是从计算机接收到数据，数据的大小，数据的偏移量；如果数据连续的话，就使用数据发送函数，将数据发送给用户，如果不连续的话，应该怎么处理。

考虑问题：

1.怎么样去判断数据是否连续；

2.在不知道数据大小的情况下，怎么去存储多个不连续的数据；

面试官给的实现思路：

定义一个存储数据，大小，偏移量三个元素的链表，在数据不连续的时候，将数据插入到链表中，形成一个有序链表，然后在数据连续之后，遍历链表，一次性的将链表的数据发送给用户，然后清除链表，只保留最后一个节点的信息。

第三章 栈和队列

1.请说明栈与队列的区别

首先，栈和队列都是操作受限的线性表，栈只能在表的一端进行插入和删除，队列只能在表的一端进行插入另一端进行删除。

其次，栈是先进后出，队列是先进先出。

2.栈的应用有哪些？

括号匹配：遇到左括号就将其压入栈中，遇到右括号就将栈顶的左括号弹出，检查其是否与当前扫描的右括号匹配。

表达式的计算：前缀、后缀表达书:运算符在两个操作数前面、后面。从左往右依次扫描下一个元素，直到处理完所有元素；若扫描 到操作数就将其压入栈中，并继续扫描，若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，并继续扫描。

递归的应用：每进一层递归，就将递归调用所需要的信息压入栈顶；每退出一层递归，就从栈顶弹出相应信息。

函数调用、多线程、中断

3.循环队列？

向循环队列插入一个元素。 (rear + 1) % capacity;

删除一个元素 (front + 1) % capacity;

获取队首元素 return elements[front];

获取队尾元素 return elements[(rear - 1 + capacity) % capacity];

判断队空 return rear == front;

判断队满

• 判断队满，((rear + 1) % capacity) == front这种写法会浪费一个空间，
• 可以多一个size的变量来记录元素个数，可以不浪费一个空间
• 可以增加tag标志，根据上一次是增加还是删除元素来区分rear==front是队空还是队满

队列中元素个数 (rear + capacity - front ) % capacity

class MyCircularQueue {
private:
    int front;
    int rear;
    int capacity;
    vector<int> elements;

public:
    MyCircularQueue(int k) {
        this->capacity = k + 1;
        this->elements = vector<int>(capacity);
        rear = front = 0;
    }

    bool enQueue(int value) { //向循环队列插入一个元素。
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    bool deQueue() { //从循环队列中删除一个元素。
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

    int Front() { //从队首获取元素。
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }

    int Rear() { //获取队尾元素
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];
    }

    bool isEmpty() { //判断队空
        return rear == front;
    }

    bool isFull() { //判断队满，这种写法会浪费一个空间，可以多一个size的变量来记录元素个数，可以不浪费一个空间
        return ((rear + 1) % capacity) == front;
    }
};

4.双端队列？

允许两端都可以进行入队和出队操作的队列。

5.优先队列

优先队列是一种常见的数据结构，通常用于存储具有优先级的元素，并能够按照其优先级来检索或删除元素。在计算机科学和算法设计中，优先队列经常用于解决各种问题，例如调度任务、图算法、堆排序等。

优先队列可以通过多种方式实现，其中最常见的两种是：

1. 二叉堆：二叉堆是一种基于二叉树结构的数据结构，分为最小堆和最大堆。最小堆保证根节点的值最小，而最大堆保证根节点的值最大。二叉堆的插入和删除操作的时间复杂度为O(log N)，其中N是元素的数量。
2. 斐波那契堆：斐波那契堆是一种更高级的数据结构，通常在某些特定应用中性能更好。它允许在较低的时间复杂度内执行合并操作，但插入和删除操作的平均时间复杂度仍然为O(log N)。

优先队列的选择取决于具体的应用需求和性能要求。在选择优先队列的实现方式时，需要考虑元素的优先级和数据量大小，以及所需的插入、删除和检索操作的性能要求。

第四章 串

1.介绍一下字符串模式匹配算法:朴素模式匹配算法的KMP算法。

串的模式匹配：在主串中找到与模式串相同的字串，并返回其所在位置。

朴素模式匹配算法：将模式串的字符与主串中的每一个字串一一进行对比。

KMP：指向主串的指针不回溯，依次往后进行匹配比较，而指向模式串的指针需要回溯，当某个位置的字符匹配失败时，模式串指针根据next数组（最长相等前后缀的数组）指向相应的位置，在进行匹配。（kmp算法思想在于：在当前对文本串和模式串检索的过程中，若出现了不匹配，如何充分利用已经匹配的部分。）

第五章 树与二叉树

1.树的遍历方式有哪些？

树与二叉树的转换

森林与二叉树的转换

树的遍历 树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有两种方式：

1）先根遍历。若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。 其遍历序列与这棵树相应二叉树的先序序列相同。

2）后根遍历。若树非空，先依次遍历根结点的每棵子树，再访问根结点，遍历子树时仍遵循先子树后根的规则。 其遍历序列与这棵树相应二叉树的中序序列相同。

森林的遍历 按照森林和树相互递归的定义，可得到森林的两种遍历方法。

先序遍历森林。若森林为非空，则按如下规则进行遍历： 1）访问森林中第一棵树的根结点。 2）先序遍历第一棵树中根结点的子树森林。 3）先序遍历除去第一棵树之后剩余的树构成的森林。

中序遍历森林。森林为非空时，按如下规则进行遍历： 1）中序遍历森林中第一棵树的根结点的子树森林。 2）访问第一棵树的根结点。 3）中序遍历除去第一棵树之后剩余的树构成的森林。

二叉树的遍历

1. 前序遍历（Pre-order Traversal）：先访问根节点，然后遍历左子树和右子树。
2. 中序遍历（In-order Traversal）：先遍历左子树，然后访问根节点，最后遍历右子树。
3. 后序遍历（Post-order Traversal）：先遍历左子树，然后遍历右子树，最后访问根节点。
4. 层序遍历（Level-order Traversal）：从上到下逐层遍历树节点。
5. 右序遍历（Right-order Traversal）：先遍历右子树，然后访问根节点，最后遍历左子树。

树和森林的遍历与二叉树的遍历关系见下表：

树 森林 二叉树

先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

2.什么是二叉树？介绍各种树？

二叉树：是一种树形结构，其特点是每个结点至多只有两颗子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。

平衡二叉树：树上任意结点的左子树和右子树的深度差不超过1。

满二叉树：一颗二叉树的结点要么是叶子结点要么它有两个子节点。

完全二叉树：若设二叉树的深度为h，除第h层外，其他各层节点数都达到最大个数，第h层结点都连续集中在最左边。

二叉堆：二叉堆是一种特殊的完全二叉树，它满足堆的性质，即父节点的值总是大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。二叉堆常用于实现优先队列等数据结构，可以高效地进行插入、删除最值等操作。

最优二叉树：也叫哈夫曼树，是一种用于数据压缩的二叉树结构。它是通过哈夫曼编码算法生成的，树中的每个叶节点都对应着一个字符，并且叶节点的权重（频率）越高，离根节点的距离越短。哈夫曼树可以实现高效的数据压缩和解压缩。

线索二叉树：线索二叉树是一种对普通二叉树进行改进的数据结构，它的节点除了包含左右子节点的指针外，还包含指向中序遍历的前驱和后继节点的线索。这样可以实现在不使用递归或栈的情况下，高效地遍历二叉树。

二叉搜索树（Binary Search Tree，BST）：又称二叉排序树：左子树结点值<根节点值<右子树结点值。二叉搜索树是一种特殊的二叉树，它满足以下性质：对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。这个性质使得二叉搜索树可以用来高效地进行查找、插入和删除操作。

自平衡二叉搜索树AVL：它通过在插入或删除节点时进行旋转操作来保持树的平衡。AVL树的特点是任何节点的左子树和右子树的高度差不超过1，这使得它具有较快的查找和插入操作的时间复杂度。

红黑树：红黑树是一种特殊的二叉搜索树，它在二叉搜索树的基础上增加了一些性质，以保证树的平衡性。红黑树的性质包括：每个节点要么是红色，要么是黑色；根节点是黑色的；每个叶节点（NIL节点，空节点）是黑色的；不能有相邻的两个红色节点等。

B树：B树是一种平衡多路查找树，广泛用于文件系统和数据库中。它的特点是每个节点可以存储多个关键字和对应的值，并且可以拥有多个子节点。B树通过增加节点的容量和调整树的结构来保持平衡，从而提供高效的数据检索和插入/删除操作。

B+树：B+树是一种平衡的多路查找树，它在数据库和文件系统中被广泛应用。

平满完堆哈线搜自红B+

3.二叉树与度为2的树有什么区别？

• 结点的度：有几个孩子（分支）
• 树的度：各结点的度的最大值
• m叉树：每个结点最多只能有m个孩子的树（可以小于m）

度为2的树至少有三个结点，而二叉树可以为空。

度为2 的有序树的孩子的左右次序是相对于另一孩子而言的，若某个结点只有一个孩子，则这个孩子就无需区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，即二叉树的节点次序不是相对于另一结点而言，而是确定的。

4.引入线索二叉树有什么作用？

引入线索二叉树是为了加快查找结点前驱和后继的速度。将二叉树的空链域接入指针，根据二叉树的遍历方式左指针指向直接前驱结 点，右指针指向直接后继结点，以加快查找前驱和后继的速度。

5.如何构造哈夫曼树？哈夫曼编码的意义是什么？

数据结构——五分钟搞定哈夫曼树，会求WPL值，不会你打我_哔哩哔哩_bilibili

哈夫曼树:带权路径长度（WPL）最小的二叉树。

构造哈夫曼树的算法描述如下：

1）将n个结点分别看作n棵仅含一个结点的二叉树。

2）在所有的根节点中选取两个根节点权值最小的数构造成新的二叉树，再将根节点与其他n-1个根节点进行比较，选出根节点权值最小的两棵树进行归并，重复上述步骤，直至所有结点都归并到一个树上为止。

哈夫曼编码的意义：

将出现频率高的字符使用较短的编码，反之出现频率较低的则使用较长的编码，降低字符串的平均期望长度。频繁使用的机器指令操作使用较短的编码，这样会提高执行的效率。

6.什么是二叉树退化？

二叉树的退化是指二叉树变成了一条链，即每个节点只有一个子节点或没有子节点。这种情况下，二叉树的高度就变成了n-1，其中n是树中的节点数。

二叉树的退化可能是由于插入节点的顺序导致的。例如，如果我们按照升序或降序依次插入节点，那么得到的二叉树就是一条链。这种情况下，二叉树的查找操作和插入操作的时间复杂度都变成了O(n)，因为它们需要遍历整个链。

二叉树的退化还可能是由于树的不平衡导致的。例如，如果树的左子树或右子树过深，而另一侧子树过浅，那么树就会退化成一条链。这种情况下，我们需要通过旋转操作或者平衡二叉树等方法来重新平衡树的结构，以保证树的高度尽可能地小，从而提高查找和插入的效率。

在实际应用中，为了避免二叉树的退化，我们可以使用平衡二叉树等数据结构来代替普通的二叉树。平衡二叉树能够自动调整节点的位置，以保证树的高度始终是log(n)，从而保证了查找和插入操作的时间复杂度是O(log(n))。

7.什么是平衡二叉树？

平衡二叉树是一种特殊的二叉搜索树，它的左右子树的高度差不超过1。平衡二叉树可以保证在最坏情况下，二叉树的高度始终是log(n)，其中n是二叉树中节点的数量，这样可以保证二叉树的查找、插入和删除操作的时间复杂度都是O(log(n))。

常见的平衡二叉树包括AVL树、红黑树、Treap等。其中AVL树是一种最早被提出的平衡二叉树，它保证每个节点的左右子树的高度差不超过1。红黑树则是一种基于颜色标记的平衡二叉树，它能够自动进行旋转操作，以保证树的平衡性。Treap则是一种将二叉搜索树和堆结合起来的平衡二叉树，它通过随机化的方式保证树的平衡性。

由于平衡二叉树的平衡性，它在数据检索方面有很好的表现。被广泛应用于数据库索引、文件系统、编译器等领域。

8.为什么要引入平衡二叉树?

平衡二叉树，一定是二叉排序树，之所以将其排序调整为平衡状态，是为了在二叉排序树近似为链的情况下增强其查找性能，降低时间复杂度。

9.什么是红黑树

【数据结构】红 黑 树_哔哩哔哩_bilibili

红黑树（Red-Black Tree）是一种自平衡二叉查找树（BST），它在树的每个节点上增加了一个存储位来表示节点的颜色，可以保证任何一个节点的左右子树的高度差小于两倍，从而保证了红黑树的查找、插入、删除的时间复杂度都是O(log n)。

红黑树的特点如下：

1. 每个节点都有一个颜色，红色或黑色。
2. 根节点是黑色的。
3. 所有叶子节点（NIL节点）都是黑色的。
4. 如果一个节点是红色的，则它的子节点必须是黑色的。
5. 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

红黑树的自平衡性是通过节点颜色和旋转操作来实现的。当插入或删除一个节点时，如果破坏了红黑树的特性，就需要通过重新着色和旋转操作来保持平衡。

（应对面试），面试官问红黑树怎么旋转调整的，一般能问到这么细的就看真本事了，要我我选择放弃，但是问我红黑树是什么，有什么意义还是可以回答的：排序二叉树有不平衡的问题，可能左子树很长但是右子树很短，造成查询时性能不佳（logn退化成n），完全平衡的二叉树能保证层数平均，从而查询效率高，但是维护又很麻烦，每次插入和删除有很大的可能要大幅调整树结构。红黑树就是介于完全不平衡和完全平衡之间的一种二叉树，通过每个节点有红黑两种颜色、从节点到任意叶子节点会经过相同数量的黑色节点等一系列规则，实现了【树的层数最大也只会有两倍的差距】，这样既能提高插入和删除的效率，又能让树相对平衡从而有还不错的查询效率。从整体上讲，红黑树就是一种中庸之道的二叉树。

10.红黑树的优缺点

红黑树是一种自平衡的二叉查找树，它在插入、删除等操作后能够自动调整以保持树的平衡，从而保证了其在最坏情况下的时间复杂度为 O(log n)。红黑树的优缺点如下：

优点：

1. 平衡性：红黑树通过对节点进行特定的着色和旋转操作，保持了树的平衡性，使得树的高度保持在一个相对较小的范围内，保证了查找、插入和删除操作的高效性，最坏情况下的时间复杂度为 O(log n)。

2. 高效的插入与删除：红黑树的自平衡特性使得插入和删除节点的操作相对简单快速，并且不会导致树的过度深度。

3. 数据顺序性：红黑树是二叉查找树的一种，它保持了节点之间的有序性，因此支持一些特定的操作，如范围查找。

4. 广泛应用：红黑树被广泛用于实现C++的STL中的map和set，以及Java的TreeMap和TreeSet等标准库中，这些数据结构要求高效的查找、插入和删除操作，红黑树正好满足这些需求。

缺点：

1. 略微复杂：红黑树的实现比较复杂，包括节点着色、旋转等操作，容易出错，需要仔细处理边界情况，使得其实现相对困难。

2. 内存占用较大：相比于其他平衡二叉查找树，红黑树的节点需要额外存储用于表示节点颜色的位，因此相对于简单的二叉查找树，红黑树的内存占用会更大一些。

3. 不适合频繁的插入和删除操作：尽管红黑树能够保持相对平衡，但在频繁插入和删除节点的情况下，可能会引起频繁的调整操作，导致性能下降。

4. 不适合小规模数据集：对于小规模的数据集，红黑树的优势可能无法充分体现，因为它的平衡性带来的好处在小规模情况下可能并不明显。

综上所述，红黑树在大规模数据集上具有较好的平衡性和高效的查找、插入和删除操作，但对于小规模数据集和频繁插入删除操作，可能不是最优选择。在实际应用中，需要根据具体情况综合考虑数据规模和操作类型来选择合适的数据结构。

11.什么是B+树

终于把B树搞明白了(一)_B树的引入，为什么会有B树_哔哩哔哩_bilibili

设计一个文件系统的索引：

• 数组/顺序表：慢，插入删除移动成本很高

• 哈希：

  缺点: 1.hash冲突后，数据散列不均匀，产生大量线性查询，效率低 ⒉.等值查询可以，但是遇到范围查询，得挨个遍历，hash就不合适了 优点:等值查询比较快

• 二叉树

• BST二叉查找树：问题：二叉树退化。

• AVL平衡二叉树：问题：变平衡移动成本很高（插入少，查询多时使用比较好）

• 红黑树：（最长子树不超过最短子树的二倍，保证了插入效率和查找效率）问题：数据量大时，树的深度变深，查找的IO次数越多，影响读取效率。

• B树（一个有序的多路查询树）

• B+树（相对B树：数据在叶子节点上，数据之间有关系，查找要最终找到叶子节点上）

第六章 图

1.图的概念

图是由一些点（或顶点）和它们之间的边（或弧）组成的一种数据结构。图用来描述节点之间的关系，比如社交网络中的好友关系、地图上的交通路线、网络中的数据传输路径等等。在图中，节点通常用圆圈表示，边则用连接这些节点的线表示。

图可以分为有向图和无向图两种类型，其中有向图中的边是有方向的，而无向图中的边是无方向的。如果图中的边还带有权值，则称为带权图。

在图中，一个节点的度数是指与该节点相邻的边的数量。对于有向图来说，一个节点的入度是指指向该节点的边的数量，出度则是指从该节点出发的边的数量。

图的应用非常广泛，比如在社交网络中可以用图来寻找共同好友、推荐朋友等；在地图上可以用图来寻找最短路径、计算交通流量等

2.图的存储方式

邻接矩阵：矩阵的第i行第j列表示i到j是否连接。 邻接表：链表后面跟着所有指向的点。 邻接矩阵的优点是可以很方便的知道两个节点之间是否存在边，以及快速的添加或删除边；缺点是如果节点个数比较少容易造成存储 空间的浪费。

邻接表的优点是节省空间，只给实际存在的边分配存储空间；缺点是在涉及度时可能需要遍历整个链表。

十字链表法

邻接多重表

3.图的遍历

简述一下广度优先遍历和深度优先遍历

广度优先搜索BFS：首先访问结点v，由近至远依次访问和v邻接的未被访问过的结点，类似于层次遍历。

深度优先搜索DFS：首先访问顶点v，若v的第一个邻接点没有被访问过，则访问该邻接点；若v的第一个邻接点已经被访问，则访问其第 二个邻接点；类似于先序遍历。

4.简述一下求最小生成树的两种算法。

最小生成树：生成树集合中，边的权值之和最小的树。

普利姆（prim）算法：从某一个顶点开始构建生成树，每次将代价最小的新的顶点纳入生成树中，直到所有顶点都纳入为止，适用于边稠密图。

克鲁斯卡尔（kruskal）算法：按照边权值递增的次序构建生成树，每次选择一条权值最小的边，使这条边的两头连通（原本已连通就不选），直到所有结点都连通为止，适用于边稀疏图。

5.简述一下求最短路径的两种算法

最短路径：把带权路径长度最短的那条路径称为最短路径。

迪杰斯特拉（Dijkstra）算法：数据结构——看完这个视频终于会用迪杰斯特拉算法求最短路径啦_哔哩哔哩_bilibili

求单源最短路径，用于求某一顶点到其他顶点的最短路径，它的特点是以起点为中心层层向外扩展， 直到扩展到终点为止，迪杰斯特拉算法要求的边权值不能为负。

弗洛伊德（Floyd）算法：数据结构——看完这个视频终于会用Floyd算法求最短路径啦_哔哩哔哩_bilibili

求各顶点之间的最短路径，用于解决任意两点间的最短路径，它的特点是可以正确处理有向图或负权值的 最短路径问题。

6.简述一下什么是拓扑排序？

数据结构——拓扑排序和逆拓扑排序_哔哩哔哩_bilibili

拓扑排序：它是一个有向边无环图，它的思想是选择一个入度为0的顶点并输出，然后删除此顶点以及所有出度，循环直到结束。

第七章 查找

1.数据结构有哪些查找算法？它们分别适用于什么样的存储结构？

线性查找：

• 顺序查找：又称线性查找，它对顺序表和链表都是适用的，对于顺序表，可通过数组下标递增的顺序来扫描每个元素；对于链表，可 通过next来依次扫描每个元素。

• 折半查找：又称二分查找，它仅适用于有序的顺序表。

• 分块查找：又称索引顺序查找，它将查找表分为了若干子块，块内元素可以无序，但块间元素是有序的。

树形查找：

• 二叉排序树
• 二叉平衡树
• 红黑树
• B树/B+树

散列查找

• 哈希表
• set
• map

2.谈谈你对散列表的认识

散列表又称哈希表，是一种数据结构，特点是数据元素的关键字与其存储地址直接相关。

常用的散列函数的构造方法有：直接定址法、除留取余法、数字分析法、平方取中法。

常见的处理冲突的方法有：开放定址法（线性探测法、平方取中法、再散列法、伪随机 序列法）、拉链法、再哈希。

散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子。

3.什么时候用哈希？

哈希（Hash）是一种用于快速定位数据的数据结构。它将任意长度的输入数据（例如字符串或数字）映射到固定长度的输出（哈希值或摘要），并将该输出用作索引来查找数据。

哈希的主要应用是在需要快速访问和查找数据的情况下，例如在数据库中查找记录或在文件系统中查找文件。

当使用哈希时，哈希冲突是一种可能发生的情况，即两个或多个输入数据被映射到相同的哈希值。这种情况可能会导致数据丢失或错误的结果。

4.哈希冲突怎么解决？

哈希冲突是指不同的输入数据在经过哈希函数计算后得到相同的哈希值，这是一种常见的情况。解决哈希冲突的方法有以下几种常见的技术：

1. 链地址法（Chaining）：在哈希表的每个槽位（桶）中，使用链表等数据结构存储冲突的元素。当发生冲突时，新元素可以直接插入到链表的末尾。这种方法可以高效地解决冲突，但需要额外的空间来存储链表。
2. 开放地址法（Open Addressing）：在哈希表的每个槽位中存储一个元素，当发生冲突时，通过一定的探测方法（如线性探测、二次探测、双重哈希等）找到下一个可用的槽位。这种方法不需要额外的数据结构存储冲突的元素，但可能导致聚集性冲突，即一旦发生冲突，后续的插入操作可能会更加耗时。
3. 再哈希（Rehashing）：当发生冲突时，重新计算哈希函数，使用新的哈希值来定位元素的位置。这种方法可以一定程度上避免冲突，但如果哈希函数设计不合理，仍然可能导致冲突。

记忆：再开链

5.哈希表是怎么扩张的

哈希表在存储数据时，将数据映射到一个固定大小的数组中的特定位置，这个位置通过哈希函数计算得到。当哈希表中的数据量增加，超过了哈希表的负载因子阈值时，就需要进行扩张操作。

哈希表的扩张通常涉及以下步骤：

1. 创建一个更大的数组：扩张哈希表时，首先需要创建一个更大的数组，新数组的大小通常是原数组大小的两倍或更多。这样可以提供足够的空间来容纳更多的数据项。

2. 重新哈希：接下来，需要将原数组中的所有数据项重新插入到新数组中的合适位置。这个过程称为重新哈希。重新哈希涉及对每个数据项应用哈希函数，以确定在新数组中的位置。

   2.1 首先，遍历原数组中的每个非空槽位。

   2.2 对于每个非空槽位，使用哈希函数计算数据项的新位置，并将其插入新数组中的相应位置。如果新位置已经被占用，可能需要解决冲突，如使用链表或开放寻址等解决冲突的方法。

   2.3 最后，将原数组中的所有数据项都重新插入到新数组中后，新数组就成为了扩张后的哈希表。

3. 更新引用：完成重新哈希后，哈希表的内部数据结构需要更新。通常，哈希表会维护一个指向内部数组的指针，该指针需要更新为新的数组的地址。这样，哈希表就能正确地访问和操作扩张后的数据。

扩张哈希表的目的是为了降低负载因子，以减少碰撞和提高性能。通过提供更大的数组空间，可以减少槽位之间的冲突，使得数据项能够更均匀地分布在哈希表中。

6.常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

• 数组
• set(集合
• map(映射)

这里数组就没啥可说的了，我们来看一下set。

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

集合 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率

std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率

std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过给我们的使用方式，还是哈希法的使用方式，即key和value。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。

7.一致性哈希

一致性Hash算法原理总结 - 知乎 (zhihu.com)

一致性哈希是一种用于分布式系统中的数据分片和负载均衡的算法。它的目标是在动态增减服务器节点时，尽可能地减少数据迁移，以及降低系统中断带来的影响。

工作原理：

1. 首先，确定服务器节点的哈希空间，通常通过对服务器节点的标识（如IP地址或名称）进行哈希计算来实现。
2. 将数据的哈希值映射到相同的哈希空间，确定数据的位置。
3. 当需要定位数据时，计算数据的哈希值，并根据顺时针方向找到第一个比数据哈希值大的服务器节点，将数据映射到该节点。

优势：

1. 在服务器节点动态增减时，只有部分数据需要重新映射，大部分数据可以保持不变，降低了数据迁移的开销。
2. 负载均衡效果较好，因为数据分布在哈希空间中，节点之间的数据分布相对均匀。

应用场景：

• 缓存系统：在分布式缓存中使用一致性哈希可以减少缓存失效时的数据迁移，提高缓存系统的性能。
• 分布式数据库：在分片数据库中使用一致性哈希可以实现数据的均衡分布，避免数据倾斜问题。

一致性哈希是分布式系统设计中一个重要的算法，可以帮助解决很多与节点分布和数据分片相关的问题。

第八章 排序

1.什么是算法的稳定性？

算法的稳定性是指关键字值相同的元素在排序之后相对位置不改变。算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。

2.数据结构有哪些排序算法？说一到两种排序算法的优劣？并比较时间复杂度？

记忆：

插帽龟，桶计基，走的稳 选帽插，有点方，快归堆nlogn

3.快速排序、堆排序、归并排序速度比较

快速排序，堆排序和归并排序谁更快？_快速排序和堆排序和归并排序平均哪个更快_lrq的博客-CSDN博客

快速>堆>归并

4.你认为最好的排序算法是什么？简述理由

1. 快速排序（Quick Sort）： 快速排序是一种基于分治的排序算法，它的平均时间复杂度为O(nlogn)。它在实际应用中表现出色，而且非常适用于大规模数据的排序。
2. 归并排序（Merge Sort）： 归并排序也是一种基于分治的排序算法，它的平均时间复杂度也是O(nlogn)。相对于快速排序，它具有更好的稳定性，但需要额外的空间来存储中间结果。
3. 堆排序（Heap Sort）： 堆排序是一种基于堆的排序算法，它的平均时间复杂度为O(nlogn)。相比于快速排序和归并排序，堆排序对数据的随机性不敏感，因此在某些特殊情况下表现更优。

5.循环比递归效率高？

递归和循环两者完全可以互换。不能完全决定性地说循环地效率比递归的效率高。

①递归

优点：代码简洁、清晰，并且容易验证正确性。

缺点：效率较低，递归是有时间和空间消耗的，递归中很多计算都是重复的，从而给性能带来很大的负面影响。

②循环

优点：速度快，结构简单。

缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。

6.说下你知道的排序算法？说下快排的过程，快排的时间复杂度:heart:

快速排序是一种常用的排序算法，它是基于分治法的思想，其基本思路是选定一个基准元素，将待排序数组分为左右两部分，左部分的元素均小于等于基准元素，右部分的元素均大于等于基准元素，然后对左右两部分递归地进行快速排序，最终将整个数组排好序。

下面是快速排序的详细过程：

1. 选择基准元素：从数组中选择一个元素作为基准元素，通常选择数组的第一个元素或者最后一个元素。
2. 分割操作：将数组分成两部分，小于等于基准元素的放在左边，大于等于基准元素的放在右边，相等的可以放在任意一边。这个过程叫做分割操作，也称为划分操作。
3. 递归排序：对左右两部分递归进行快速排序。
4. 合并结果：将左右两部分已经排好序的结果合并起来，就得到了最终的排序结果。

下面是快速排序的时间复杂度：

快速排序的时间复杂度为 O(nlogn)，其中 n 是数组的长度。最坏情况下的时间复杂度是 O(n^2)，出现在每次选取的基准元素都是当前序列的最大或最小值的情况下。但是，实际上快速排序的平均时间复杂度是 O(nlogn)，且它的常数因子比归并排序要小，所以它在实际应用中表现很好。

7.解释快速排序的时间复杂度为什么是NlogN?

快速排序的时间复杂度分析主要基于分治法的思想。在快排中，每次选定一个基准元素并将整个序列分成两个部分，然后对这两个部分递归地进行排序，这个过程可以用以下的递归式描述：

T(n) = 2T(n/2) + O(n)

其中 n 是数组的长度，T(n) 表示对一个长度为 n 的数组进行快速排序所需要的时间。

在这个递归式中，第一项 2T(n/2) 表示对数组进行划分后，分别对左右两个子数组进行快排的时间，这里的时间复杂度是 T(n/2)。第二项 O(n) 表示对一个长度为 n 的数组进行划分操作的时间。在最好情况下，快排每次都能将数组均匀地分成两部分，那么递归树的深度为 logn，每层需要 O(n) 的时间，因此快排的时间复杂度为 O(nlogn)。在最坏情况下，快排每次都只能将数组分成一个元素和 n-1 个元素两部分，那么递归树的深度为 n，每层需要 O(n) 的时间，因此快排的时间复杂度为 O(n^2)。

然而，在实际应用中，快速排序的平均时间复杂度为 O(nlogn)，这是因为快排划分子数组的方式不是等分，而是将大于等于基准元素的元素放到右边，小于等于基准元素的元素放到左边。这样，大约一半的元素会被排在右边，一半的元素会被排在左边，因此递归树的深度大约是 logn，每层需要 O(n) 的时间，所以快排的平均时间复杂度是 O(nlogn)。

8.快速排序什么时候最坏?如何避免？:heart:

快速排序在以下情况下可能变得最坏：

1. 当输入数组已经按照相反的顺序排列时，即数组已经是按照降序排列的情况。这是因为快速排序的分割过程选择第一个元素作为基准，如果数组已经按照相反的顺序排列，每次分割都会产生最不平衡的子数组，导致快速排序的性能变差。

2. 当输入数组中存在大量相同的元素时，即存在重复元素的情况。这是因为快速排序的分割过程通常将数组划分为两个子数组，如果有很多重复元素，可能会导致两个子数组的大小差异很大，使得快速排序的性能下降。

为了避免快速排序在最坏情况下的性能问题，可以采取以下措施：

1. 随机选择基准元素：在选择基准元素时，可以随机选择数组中的一个元素作为基准，而不是固定选择第一个元素。这样可以减少最坏情况的出现概率，提高算法的平均性能。

2. 使用三数取中法选择基准元素：三数取中法是一种选择基准元素的方法，它选择数组的头部、尾部和中间位置的元素，然后取这三个元素的中间值作为基准元素。这样可以避免在已经有序或接近有序的数组中选择最小或最大的元素作为基准而导致的最坏情况。

3. 使用插入排序优化：在数组的大小较小（通常小于一定阈值）时，可以切换到使用插入排序等简单排序算法，而不是继续使用快速排序。这是因为对于小规模的数组，简单排序算法的性能可能比快速排序更好。

9.概述一下大根堆的构造过程？并说说堆排序的适用场景。:heart:

数据结构——堆排序_哔哩哔哩_bilibili

• 堆排序是完全二叉树，但不是排序二叉树
• 第一个非叶子节点，即第[n/2]个结点

排序

对于第[n/2]个结点为根的子树进行筛选，使得它的根结点大于等于左右子树（小根堆反之），之后向前依次（[n/2]-1~1）为根的子树进行筛选，看该结点值是否大于其左右子树结点，若不大于，则将左右子结点中较大者与之交换，交换后可能会破坏下一级堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构建成堆为止。

插入

直接放到完全二叉树最后，然后排序它相关的父节点

删除

把最后一个节点放到删除的元素的位置，，然后排序它相关的父节点

堆排序适用于关键字较多的情况，比如在1亿个数中选出前100个最大值。

数据结构基础总结

#C++##嵌入式##笔试##校招##八股#