计算机保研/考研面试复习系列

专业课（PDF整理版下载）：

计算机保研/考研面试复习专业课篇——数据结构

计算机保研/考研面试复习专业课篇——计算机网络

计算机保研/考研面试复习专业课篇——操作系统

计算机保研/考研面试复习专业课篇——计算机组成原理

数学（PDF整理版下载）：

计算机保研/考研面试复习数学篇——高等数学

计算机保研/考研面试复习数学篇——线性代数

计算机保研/考研面试复习数学篇——概率论

计算机保研/考研面试复习数学篇——离散数学

人工智能 （PDF整理版下载）：

计算机保研/考研面试复习——机器学习篇

计算机保研/考研面试复习——深度学习篇

1. *O(n)的大O是什么意思？什么是时间复杂度? ★★★

这个大O表示的是最坏情况下的时间复杂度，时间复杂度是指执行算法所需要的计算工作量，对程序规模的一个描述。

2. *线性存储结构和链式存储结构的优点★★★

线性存储结构地址空间连接，可随机访问，但是顺序存储的缺点是插入、删除操作需要花费很多时间在移动元素上。链式存储结构不要求逻辑上相邻的元素在物理位置上是相邻，但也同时失去了顺序表可随机存取的优点，但方便插入与删除

3. *解释一下顺序存储与链式存储★★★

顺序存储结构把逻辑上相邻的元素存放到物理位置上相邻的存储单元中，数据元素之间的逻辑关系由存储单元的邻接位置关系来体现。链接存储结构不要求逻辑上相邻的元素在物理位置上也相邻，元素之间的逻辑关系由附加的指针指示。

4. *头指针和头结点的区别？★★

头指针是指向链表第一个结点的指针，用来标识链表的起点。头结点是链表的第一个结点，它的数据域可以为空，主要用于操作的统一和简化。

5. *栈和队列的区别和内存结构★★★

区别：栈是后进先出（LIFO）的数据结构，只能在一端进行插入和删除操作。队列是先进先出（FIFO）的数据结构，在一端插入，在另一端删除。

内存结构：栈通常用数组或链表实现，在内存中，栈可以被看作是一块连续的内存区域，具有一个栈顶指针，指向栈中当前最顶端的元素。队列通常用链表或数组实现，有时也用循环数组，在内存中，队列有两个指针，分别指向队首和队尾，元素从队尾添加，从队首移除。

6. 有一个循环队列Q，里面的编号是0到n-1，头尾指针分别是f，p，现在求Q中元素的个数？★★

元素个数为

7. 如何区分循环队列是队空还是队满？★★★

在循环队列中，通常通过一个额外的标志位或者维护一个计数器来区分队空和队满状态。如果仅通过头尾指针来区分，常用的方法是保留一个空间不存放元素，当 (rear + 1) % n == front 时表示队满，而rear == front 表示队空。

8. 堆、大顶堆、小顶堆实现及应用★★

堆 (Heap) 是一种特殊的完全二叉树。堆可以分为大顶堆和小顶堆：

• 大顶堆 (Max Heap)：每个节点的值都大于或等于其子节点的值。
• 小顶堆 (Min Heap)：每个节点的值都小于或等于其子节点的值。

实现：

• 插入操作：将新元素添加到堆的末尾，然后向上调整，使堆的性质得以保持
• 删除操作：通常删除堆顶元素，将最后一个元素放到堆顶，然后向下调整，使堆的性质得以保持

应用：

• 优先队列：可以高效地获取最大或最小元素
• 堆排序：利用大顶堆或小顶堆进行排序
• 图算法中的最短路径算法（如Dijkstra算法）

9. 哈希表的概念、构造方法、哈希有几种类型？哈希冲突的解决办法？★★★★

哈希表是一种通过键值对存储数据的数据结构，它使用哈希函数将键映射到数组中的某个位置，从而实现快速的数据查找。

构造方法包括：

• 选择一个合适的哈希函数，将键转换为数组的索引。
• 初始化一个固定大小的数组来存储数据。

哈希类型主要有：

• 直接地址法：直接使用键值作为数组索引。
• 除留余数法：键值对某个素数取模。
• 平方取中法：键值平方后取中间几位。
• 折叠法：将键值分割后求和。

哈希冲突的解决办法：

• 开放地址法：出现冲突时，在数组中找到下一个空闲位置。包括线性探测、二次探测和双重散列。
• 链地址法：每个数组元素都是一个链表，所有哈希值相同的元素存储在同一个链表中。
• 再哈希法：出现冲突时，使用第二个哈希函数计算新位置。
• 建立公共溢出区：将冲突元素存储在一个公共的溢出区中。

10. *判断链表是否有环（非常重要！）★★★★★★★

（1）快慢指针：起初，快指针和慢指针一起指向头节点。快指针每次走2 步，慢指针每次走1 布，直到走到尾节点 。若快指针与慢指针相遇，则说明链表中有环；若不相遇，则说明链表中无环。

（2）哈希表：通过检查一个节点此前是否被访问过来判断链表中是否有环。每访问一个节点，将它的引用存储到哈希表中。

11. *平衡二叉树、二叉排序树、完全二叉树、二叉搜索树的区别及如何构造★★★

二叉搜索树和二叉排序树是一个东西。二叉排序树每一个节点都是用于排序的关键码，左子树所有节点关键码都小于根节点的关键码，右子树的所有关键码都大于根节点的关键码，其中，左右子树都是二叉树。对一棵二叉排序树进行中序遍历就可以得到关键码从小到大的排列。

二叉排序树的构造方法主要执行插入操作，进行插入之前必须先检查是否该节点的关键码已经在树中存在，也就是要先查找，假如查找成功，不执行任何操作，假如搜索不成功，就在搜索停止的地方添加新元素。

平衡二叉树是一种二叉搜索树，它的左右子树高度差的绝对值不超过1。构造一棵平衡二叉树仍然是通过插入节点的方式，每插入一个结点，都应该检查平衡因子，并通过旋转操作使之平衡化。

完全二叉树的每一个节点都与高度为的满二叉树的编号一一对应。

12. *如何由遍历序列构造一颗二叉树？已知先序序列和后序序列能否重现二叉树？（笔试经常考）★★★

从遍历序列构造二叉树：

• 先序和中序遍历：先序的第一个元素是根节点，利用中序序列将树划分为左子树和右子树，递归构建。
• 中序和后序遍历：后序的最后一个元素是根节点，利用中序序列划分左右子树，递归构建。

先序和后序遍历不能唯一确定一棵二叉树，因为缺乏中序遍历的信息无法唯一划分左右子树。

13. *B树是什么?在数据库中有什么应用？（B数和B+树的区别）★★★

B树是一种自平衡的多路搜索树，它特别适用于数据库和文件系统等需要频繁进行数据查找、插入和删除操作的场景。B树的设计允许它在多级存储结构中保持较低的高度，从而减少磁盘I/O操作的次数，提高数据检索效率。

B树的特点：

• 每个节点可以有多个子节点（通常是）。
• 所有叶子节点都位于同一层，保证了树的高度较低。
• 节点可以包含多个键值对，这使得B树在读取时可以一次性读取整个节点，减少I/O操作。

B树在数据库中的应用：

• 作为索引结构，B树可以快速定位到数据存储的位置，提高查询效率。
• 支持顺序访问，适合执行范围查询和排序操作。

B树的缺点：不利于高效的范围查找。在B树中进行范围查询时，可能需要从根节点开始，逐个节点地查找直到找到所需的范围。

B+树的特点：

• B+树是B树的变种，它将所有的数据记录节点放在叶子节点，并且叶子节点之间通过链表相连。
• 内部节点仅存储键值，不存储数据记录，这样可以存储更多的键值，从而减少树的高度。
• 由于所有数据都在叶子节点，且叶子节点有序连接，B+树非常适合执行范围查询。

B+树在数据库中的应用：

• B+树的叶子节点链表允许数据库系统通过简单的链表遍历来执行范围查询，这比B树更加高效。
• 由于内部节点不存储数据，B+树可以拥有更多的键值，进一步降低树的高度，减少I/O操作。

14. 红黑树原理是什么？建立过程？★★★

红黑树 (Red-Black Tree) 是一种自平衡的二叉查找树，每个节点都有一个颜色属性（红色或黑色），并且满足以下规则（左根右，根叶黑，不红红，黑路同）：

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

建立过程：

• 插入新节点，并将其颜色设为红色。
• 如果违反红黑树的性质，进行适当的调整，如旋转和重新着色，直到红黑树的性质得到恢复。

15. 二分搜索和单纯的线性搜索的区别/时间复杂度★★★

线性搜索 (Linear Search)：从数据结构的第一个元素开始，逐个比较，直到找到目标元素或搜索结束。时间复杂度为O(n)。

二分搜索 (Binary Search)：用于有序数组，每次将搜索范围缩小一半，直到找到目标元素或搜索结束。时间复杂度为O(log n)。

区别：

• 线性搜索不需要数据有序，适用于任何数据结构。
• 二分搜索需要数据有序，适用于有序数组。

16. *插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法的基本思想是什么？时间复杂度？是否稳定？给一个例子，问冒泡和快速排序在最坏的情况下比较几次？（排序必考）★★★★★★

• 插入排序：将数组划分为已排序和未排序部分，依次将未排序部分的元素插入到已排序部分的适当位置。
• 希尔排序：对间隔为h的元素进行插入排序，并逐渐减少h的值直到h=1。
• 选择排序：在未排序部分中选择最小元素并交换到已排序部分的末尾。
• 冒泡排序：反复交换相邻的逆序元素，使每次遍历后最大元素移动到末尾。
• 归并排序：将数组递归地分成两半，对每一半分别排序后再合并。
• 快速排序：选择一个基准元素，将数组分为小于和大于基准元素的两部分，再递归排序这两部分。
• 堆排序：构建最大堆，每次取出堆顶元素并调整堆。
• 基数排序：按位排序，从最低位开始依次进行稳定排序。

冒泡排序最坏情况：如4,3,2,1升序排序，当数组完全逆序时，每次冒泡都需要比较相邻的两个元素，需要比较 次

快速排序最坏情况：当选择的基准元素是数组中的最小值或最大值时，每次分区操作都会将数组分为一个非常大的部分和一个空的部分，导致递归树的深度为4，比较

17. *最小生成树和最短路径用什么算法来实现？（迪杰斯特拉、弗洛依德、普利姆、克鲁斯卡尔）算法的基本思想是什么？算法的时间复杂度？如何进行优化？★★★★★★★

最小生成树算法：

（1）普利姆（Prim）算法：从任意一个节点开始，逐步扩展到其他节点，每次选择连接生成树和不在生成树中的节点的最小权重边。

• 优化：使用最小优先队列可以提高效率。

（2）克鲁斯卡尔（Kruskal）算法：将所有边按权重排序，然后逐次添加边到生成树中，确保不形成环。

• 优化：使用并查集（Union-Find）可以提高效率。

最短路径算法：

（1）迪杰斯特拉（Dijkstra）算法：从起点开始，逐步更新到其他所有节点的最短路径长度，每次选择未处理节点中距离最小的节点，更新其相邻节点的距离。适用于处理带有正权边的图。

（2）弗洛伊德（Floyd）算法：通过考虑每个节点作为中间节点，更新所有节点对之间的最短路径。适用于处理带有正权边和负权边的图。

（3）贝尔曼-福特（Bellman-Ford）算法：通过多次迭代更新节点间的最短路径，每次迭代考虑所有边。特别适用于处理带有负权边的图。

算法类型总结：

• 贪心算法：普利姆、克鲁斯卡尔、迪杰斯特拉（这些算法在每一步选择局部最优解，逐步构建全局最优解）
• 动态规划：弗洛伊德(通过枚举中间点，逐步优化解决方案)

优化方法:

• 堆优化：使用优先队列（最小堆）优化迪杰斯特拉、克鲁斯卡尔、普利姆算法
• 并查集：使用并查集优化克鲁斯卡尔算法，提高边的合并效率。

18. 邻接表和邻接矩阵（如何存储大数据）★

邻接表 (Adjacency List) 和邻接矩阵 (Adjacency Matrix) 是存储图的两种常见方法。

邻接表：

• 每个顶点存储一个链表，链表中的每个节点表示一个与该顶点相邻的顶点。
• 适用于稀疏图，节省空间。
• 存储大数据时，可以使用链表或哈希表等动态数据结构。

邻接矩阵：

• 使用一个二维数组表示顶点之间的连接关系，数组元素为1表示有边，为0表示无边。
• 适用于稠密图，但空间复杂度高（）。
• 存储大数据时，可以使用稀疏矩阵的存储方式，如压缩存储。

19. 介绍一下深度优先搜索和广度优先搜索是如何实现的？★★★

深度优先搜索（DFS）：

• 实现：使用递归或栈，从起始节点开始，深入访问每一个未访问的节点，直到不能继续为止，然后回溯。
• 应用：拓扑排序、连通分量、检测环。

广度优先搜索（BFS）：

• 实现：使用队列，从起始节点开始，访问所有相邻节点，然后依次访问这些节点的相邻节点。
• 应用：最短路径（无权图）、层次遍历。

20. 介绍一下字符串匹配算法：朴素的匹配算法和KMP算法（如何实现要会用语言描述）★★★

朴素的匹配算法 (Naive String Matching Algorithm)：

• 从目标字符串的每一个位置开始，尝试匹配模式字符串。
• 时间复杂度为，其中为目标字符串长度，为模式字符串长度。

int naive_match(const char* text, const char* pattern) {
    int text_len = strlen(text);
    int pattern_len = strlen(pattern);

    for (int i = 0; i <= text_len - pattern_len; i++) {
        int j;
        for (j = 0; j < pattern_len; j++) {
            if (text[i + j]!= pattern[j]) {
                break;
            }
        }
        if (j == pattern_len) {
            return i; // match found
        }
    }
    return -1; // no match found
}

KMP算法 (Knuth-Morris-Pratt Algorithm)：

• 使用部分匹配表（前缀函数）来加速匹配过程，避免重复匹配已经匹配过的部分。
• 时间复杂度为。

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
//求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}