数据结构面试题整理

吧表格中的面试题按照知识体系进行了归类重组，并对部分长篇大论的答案进行了格式优化，使其更适合背诵和理解

搭配下面的播客使用效果更佳

📂 第一板块：数据结构与算法基础 (核心地基)

这部分是计算机通识必考题，考察你对基本概念的理解。

问题	级别	核心考点与精简回答
谈一下什么是数据结构	重点	核心定义：数据结构 = 数据 + 结构。 1. 数据：描述客观事物的符号，存储在计算机中。 2. 结构：包括逻辑结构（集合、线性、树形、图形）和存储结构（物理存储）。关键点：逻辑结构决定操作（增删查改），存储结构决定物理实现。表和树是最常用的两种高效结构。
衡量算法性能的指标有哪些	重点	1. 时间复杂度：算法执行时间随输入规模增长的趋势（越低越好）。 2. 空间复杂度：算法所需额外内存随输入规模增长的趋势。 3. 稳定性：排序前后相同数值的相对位置是否改变（不变即稳定）。 4. 正确性：能否得出正确结果。 5. 其他：可读性（代码易懂）、可伸缩性（处理大数据时的表现）。
什么是查表法	了解	思想：以空间换时间。做法：预先计算结果存储在表中，使用时直接查表获取，而非实时计算。优缺点：大幅提升速度，但占用更多内存。适用于重复计算多、结果范围有限的场景。

📂 第二板块：线性数据结构 (数组、链表、栈、队列)

这部分考察最常用的数据容器，重点在于“对比”和“特性”。

问题	级别	核心考点与精简回答
数组与链表的区别	必问	1. 内存：数组静态连续分配；链表动态离散分配。 2. 大小：数组固定；链表按需增减。 3. 访问：数组随机访问快（下标），链表慢（需遍历）。 4. 增删：数组慢（需移动大量元素），链表快（仅修改指针）。 5. 结构：数组靠位置定序，链表靠指针定序。
栈和队列的区别	必问	1. 规则：栈是后进先出 (LIFO)；队列是先进先出 (FIFO)。 2. 操作口：栈只在栈顶操作；队列在队尾入、队头出。 3. 遍历：栈通常只看栈顶；队列可同时访问队头队尾。 4. 场景：栈用于递归、函数调用、表达式求值；队列用于缓冲、广度优先搜索(BFS)、任务调度。
如何理解环形队列	必问	痛点：普通队列出队后空间无法复用（假溢出）。解决：逻辑上首尾相接，形成环状。实现：使用数组 + 模运算（`%`）。当尾指针到达数组末尾时，回绕到数组头部，从而重复利用已出队的空间。
动态链表和静态链表的区别	了解	静态链表：用数组模拟链表，物理连续，无需动态分配内存，但大小固定。动态链表：使用 `malloc/new` 动态申请节点，物理不连续，通过指针连接，大小无限制。

📂 第三板块：排序与查找 (算法核心)

问题	级别	核心考点与精简回答
了解过哪些排序算法	重点	口诀：冒插选，快归堆，希桶计基。 1. 基础：冒泡、插入、选择（简单但慢，O(n²)）。 2. 进阶：快速排序、归并排序、堆排序、希尔排序（高效，O(nlogn)）。 3. 特殊：计数排序、桶排序、基数排序（非比较排序，特定场景极快）。
快速排序原理	重点	思想：分治法 (Divide & Conquer)。步骤： 1. 选基准（pivot）。 2. 分区：比基准小的放左边，大的放右边。 3. 递归：对左右两边重复上述过程，直到有序。
链表如何排序	重点	链表排序比数组难，因为不能随机访问。 1. 归并排序 (首选)：最适合链表。利用快慢指针找中点断开，递归排序后合并（Merge），无需额外移动节点数据，只需改指针。 2. 快速排序：交换节点数据或仅交换指针（较繁琐）。 3. 插入排序：维护一个有序链表，将原链表节点逐个插入。
了解过哪些查找算法	重点	1. 顺序查找：无序简单，O(n)。 2. 二分查找：有序高效，O(logn)。 3. 哈希查找：通过映射直接定位，O(1)。 4. 树表查找：BST、AVL、B树（数据库索引常用）。 5. 插值/斐波那契查找：二分查找的优化变种。
二叉树如何进行遍历	重点	均指根节点的访问时机： 1. 前序：根 $\to$ 左 $\to$ 右 2. 中序：左 $\to$ 根 $\to$ 右 3. 后序：左 $\to$ 右 $\to$ 根

📂 第四板块：链表进阶与Linux内核 (高阶/嵌入式方向)

这部分题目具有较强的针对性，常出现于C/C++或嵌入式岗位面试。

问题	级别	核心考点与精简回答
怎样检测链表中存在循环	经典	(注：已合并重复问题) 最优解（快慢指针法）：定义两个指针 P1, P2。P1 每次走 1 步，P2 每次走 2 步。若有环，P2 终会追上 P1；若 P2 走到 NULL，则无环。其他解法： 1. 标记法：修改节点数据结构，增加 visited 标记（需改代码，不推荐）。 2. 哈希表/数组：存下所有遍历过的节点地址，查重（空间复杂度高）。
对内核链表的理解	重点	Linux内核链表 (Kernel List) 是为了在内核极其讲究性能的环境下设计的。特点： 1. 双向循环链表：只有指针域（prev, next），没有数据域。 2. 嵌入式：链表节点嵌入在宿主结构体中，通过 `container_of` 宏反推数据地址。 3. 通用性：一套链表代码可管理任何类型的数据结构。 4. 并发：通常配合自旋锁使用。
内核链表 vs 普通循环链表	了解	1. 包含关系：普通链表节点包含数据；内核链表节点不包含数据，它被包含在数据结构中。 2. 复用性：内核链表定义在 `list.h`，高度封装，无需为每种数据重写链表逻辑。
用伪代码写链表模块	基础	见下文附录代码块

📂 第五板块：数据库 (SQL基础)

问题	级别	核心考点与精简回答
SQL中DDL和DML的区别	基础	DDL (定义)：建/改/删结构。关键字：`CREATE`, `ALTER`, `DROP`, `TRUNCATE`。 DML (操作)：增/删/改数据。关键字：`SELECT`, `INSERT`, `UPDATE`, `DELETE`。
SQL的约束有哪些	基础	1. 主键 (Primary Key)：唯一且非空。 2. 外键 (Foreign Key)：关联其他表。 3. 唯一 (Unique)：内容不重复。 4. 非空 (Not Null)。 5. 检查 (Check)：自定义规则。 6. 默认 (Default)。
SQL中的事件	了解	Event：类似操作系统的“定时任务”。在指定时间或循环周期内自动执行的 SQL 任务（如每天凌晨清理日志）。
SQL查重去重语句	实战	题目：在表里找某字段等于某值，并去重。 `SELECT DISTINCT 字段名 FROM 表名 WHERE 字段名 = '目标值';`

📝 附录：链表伪代码参考

题目：用伪代码写一下实现链表的模块

结构体定义:
    Node {
        Data data       // 数据域
        Node next       // 指针域
    }

    LinkedList {
        Node head       // 头指针
    }

函数模块:
    1. init(): 
       return new LinkedList(head = null)
    
    2. insert(list, value):
       newNode = new Node(value)
       if list.head is null:
           list.head = newNode
       else:
           current = list.head
           while current.next is not null:
               current = current.next
           current.next = newNode
           
    3. delete(list, value):
       if list.head.data == value:
           list.head = list.head.next
           return
       prev = list.head
       while prev.next is not null:
           if prev.next.data == value:
               prev.next = prev.next.next // 跳过该节点
               return
           prev = prev.next
           
    4. traverse(list):
       current = list.head
       while current is not null:
           print(current.data)
           current = current.next