RETURN_TO_GRID
面试2025-11-16 00:00:00+08:008 MIN READ

数据结构面试题

非常好 👍
数据结构是所有编程与算法面试的底层核心，无论是 Java、C++ 还是 Python，只要涉及逻辑与优化，就绕不开它。
下面我帮你整理一份系统版《💾数据结构常考面试题讲解》，内容覆盖 线性结构 → 树结构 → 图结构 → 算法思维，并穿插典型代码与面试思路。

🧩 一、数组（Array）

1️⃣ 数组的特点？

答：

  • 元素在内存中连续存放；

  • 支持 随机访问（O(1)）；

  • 插入、删除代价高（O(n)）。

适用场景：
频繁访问、不频繁插入删除的场景。

2️⃣ 常考题：找出数组中出现次数最多的元素

思路：
使用哈希表统计频次。

text
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums)
    map.put(num, map.getOrDefault(num, 0) + 1);

时间复杂度： O(n)

text
int binarySearch(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

时间复杂度： O(log n)

🧱 二、链表（Linked List）

1️⃣ 链表的类型？

DATA_TABLE
类型特点
单链表每个节点只指向下一个节点
双向链表节点有前后两个指针
循环链表尾节点指向头节点

2️⃣ 常考题：判断链表是否有环

解法：快慢指针（Floyd 算法）

text
boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

时间复杂度： O(n)

3️⃣ 常考题：反转链表

text
ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

🪜 三、栈（Stack）与队列（Queue）

1️⃣ 栈的特点？

后进先出（LIFO）
常用于：括号匹配、函数调用栈、DFS。

2️⃣ 常考题：括号匹配

text
boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');
        else if (c == '{') stack.push('}');
        else if (c == '[') stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();
}

3️⃣ 队列的特点？

先进先出（FIFO）
常用于：消息队列、层次遍历、BFS。

4️⃣ 常考题：用两个栈实现队列

text
Stack<Integer> in = new Stack<>();
Stack<Integer> out = new Stack<>();

void push(int x) { in.push(x); }

int pop() {
    if (out.isEmpty())
        while (!in.isEmpty()) out.push(in.pop());
    return out.pop();
}

🌳 四、树（Tree）与二叉树（Binary Tree）

1️⃣ 二叉树的遍历方式？

DATA_TABLE
遍历方式顺序
前序遍历根 → 左 → 右
中序遍历左 → 根 → 右
后序遍历左 → 右 → 根
层序遍历按层从上到下

2️⃣ 常考题：二叉树最大深度

text
int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

复杂度： O(n)

3️⃣ 常考题：判断是否是平衡二叉树

text
boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}
int height(TreeNode node) {
    if (node == null) return 0;
    int left = height(node.left);
    int right = height(node.right);
    if (Math.abs(left - right) > 1 || left == -1 || right == -1) return -1;
    return 1 + Math.max(left, right);
}

4️⃣ 常考题：二叉搜索树（BST）的性质？

  • 左子树所有节点 < 根节点；

  • 右子树所有节点 > 根节点；

  • 中序遍历结果是有序的。

🕸️ 五、哈希表（HashMap / HashSet）

1️⃣ 哈希表的原理？

通过 哈希函数 (hash function) 将键映射为数组索引。
当发生冲突时：

  • 拉链法（链表存储冲突元素）

  • 开放寻址法（向后探测空位）

2️⃣ 常考题：两数之和

text
int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement))
            return new int[]{map.get(complement), i};
        map.put(nums[i], i);
    }
    return new int[]{};
}

复杂度： O(n)

🔗 六、堆（Heap）与优先队列（PriorityQueue）

1️⃣ 什么是堆？

  • 一种完全二叉树；

  • 大顶堆：父节点 ≥ 子节点；

  • 小顶堆：父节点 ≤ 子节点。

2️⃣ 常考题：求数组中第 K 大的元素

text
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
    minHeap.offer(num);
    if (minHeap.size() > k)
        minHeap.poll();
}
return minHeap.peek();

🔄 七、图（Graph）

1️⃣ 图的表示方式？

DATA_TABLE
表示法说明
邻接矩阵用二维数组存储，空间大但查找快
邻接表用链表存储，节省空间

2️⃣ 图的遍历

  • 深度优先搜索（DFS）

  • 广度优先搜索（BFS）

text
// DFS 示例
void dfs(int v, boolean[] visited, List<List<Integer>> graph) {
    visited[v] = true;
    for (int next : graph.get(v))
        if (!visited[next]) dfs(next, visited, graph);
}

🧠 八、时间复杂度与空间复杂度

DATA_TABLE
操作平均时间复杂度空间复杂度
数组访问O(1)O(n)
链表查找O(n)O(n)
哈希查找O(1)O(n)
二叉搜索树查找O(log n)O(n)
堆插入/删除O(log n)O(n)
图遍历O(V+E)O(V+E)

🧩 九、综合面试题总结（记忆版）

DATA_TABLE
题型考点思路
链表反转指针操作迭代或递归
环检测快慢指针Floyd
栈实现队列双栈转换in/out 栈
二叉树深度递归max(left,right)+1
二叉搜索树验证中序有序递归或栈
K大元素小顶堆PriorityQueue
两数之和哈希表一遍扫描
最短路径Dijkstra优先队列

🔮 十、面试高频考察趋势（前瞻性视角）

✅ 企业趋势

  • 大厂（如阿里/字节） 更关注算法思维（如复杂度优化、递归与迭代转换）。

  • 中小厂 更注重实战能力（链表、哈希、排序、堆栈应用）。

  • AI/后端岗位 偏重图与树结构，如推荐系统或编译器分析。

是否希望我帮你整理一份「✅数据结构 + 算法常考题速记表（中英对照 + 复杂度总结）」？
这份表非常适合在面试前快速复盘记忆。

END_OF_FILESLUG: 数据结构面试题
# COMMENTS