数据结构与算法面试题
大约 12 分钟约 3579 字
数据结构与算法面试题
简介
数据结构与算法是编程的基础，也是技术面试中的核心考察内容。本篇涵盖数组、链表、树、排序、查找等常见数据结构和算法的面试题，提供详细的解题思路和 C# 代码实现，帮助读者系统性地准备算法面试。
特点
面试题目
1. 如何实现一个支持动态扩容的数组（List）？
答： 动态数组在容量不足时自动扩容（通常翻倍），支持随机访问、尾部插入等操作。
public class MyList<T>
{
private T[] _items;
private int _size;
public MyList(int capacity = 4)
{
_items = new T[capacity];
_size = 0;
}
public int Count => _size;
public int Capacity => _items.Length;
public T this[int index]
{
get
{
if (index < 0 || index >= _size)
throw new ArgumentOutOfRangeException(nameof(index));
return _items[index];
}
set
{
if (index < 0 || index >= _size)
throw new ArgumentOutOfRangeException(nameof(index));
_items[index] = value;
}
}
// 尾部添加 - 平均 O(1)，扩容时 O(n)
public void Add(T item)
{
if (_size == _items.Length)
EnsureCapacity(_size * 2);
_items[_size++] = item;
}
// 指定位置插入 - O(n)
public void Insert(int index, T item)
{
if (index < 0 || index > _size)
throw new ArgumentOutOfRangeException(nameof(index));
if (_size == _items.Length)
EnsureCapacity(_size * 2);
// 向后移动元素
Array.Copy(_items, index, _items, index + 1, _size - index);
_items[index] = item;
_size++;
}
// 删除指定位置 - O(n)
public void RemoveAt(int index)
{
if (index < 0 || index >= _size)
throw new ArgumentOutOfRangeException(nameof(index));
_size--;
if (index < _size)
Array.Copy(_items, index + 1, _items, index, _size - index);
_items[_size] = default!;
}
private void EnsureCapacity(int minCapacity)
{
if (_items.Length >= minCapacity) return;
var newItems = new T[minCapacity];
Array.Copy(_items, newItems, _size);
_items = newItems;
}
}2. 如何实现 LRU 缓存？
答： LRU（Least Recently Used）缓存使用哈希表 + 双向链表实现，get 和 put 操作均为 O(1)。
public class LRUCache
{
private readonly int _capacity;
private readonly Dictionary<int, LinkedListNode<CacheItem>> _cache;
private readonly LinkedList<CacheItem> _list;
public LRUCache(int capacity)
{
_capacity = capacity;
_cache = new Dictionary<int, LinkedListNode<CacheItem>>(capacity);
_list = new LinkedList<CacheItem>();
}
public int Get(int key)
{
if (!_cache.TryGetValue(key, out var node))
return -1;
// 移动到最前面（最近使用）
_list.Remove(node);
_list.AddFirst(node);
return node.Value.Value;
}
public void Put(int key, int value)
{
if (_cache.TryGetValue(key, out var existingNode))
{
// 更新已存在的 key
_list.Remove(existingNode);
var newNode = _list.AddFirst(new CacheItem(key, value));
_cache[key] = newNode;
return;
}
// 容量已满，移除最久未使用的
if (_cache.Count >= _capacity)
{
var lru = _list.Last!;
_list.RemoveLast();
_cache.Remove(lru.Value.Key);
}
// 添加新项
var node = _list.AddFirst(new CacheItem(key, value));
_cache[key] = node;
}
private record CacheItem(int Key, int Value);
}3. 如何判断链表是否有环？如何找到环的入口？
答： 使用快慢指针法（Floyd 判圈算法），快指针每次走两步，慢指针每次走一步。
public class ListNode
{
public int Val { get; set; }
public ListNode? Next { get; set; }
public ListNode(int val = 0, ListNode? next = null)
{
Val = val;
Next = next;
}
}
public class LinkedListAlgorithms
{
// 判断是否有环 - O(n) 时间 O(1) 空间
public static bool HasCycle(ListNode? head)
{
var slow = head;
var fast = head;
while (fast != null && fast.Next != null)
{
slow = slow!.Next;
fast = fast.Next.Next;
if (slow == fast) return true;
}
return false;
}
// 找到环的入口节点
public static ListNode? DetectCycle(ListNode? head)
{
var slow = head;
var fast = head;
var hasCycle = false;
while (fast != null && fast.Next != null)
{
slow = slow!.Next;
fast = fast.Next.Next;
if (slow == fast) { hasCycle = true; break; }
}
if (!hasCycle) return null;
// 从头和相遇点同时出发，相遇处即为入口
var ptr = head;
while (ptr != slow)
{
ptr = ptr!.Next;
slow = slow!.Next;
}
return ptr;
}
// 反转链表 - 迭代法
public static ListNode? Reverse(ListNode? head)
{
ListNode? prev = null;
var current = head;
while (current != null)
{
var next = current.Next;
current.Next = prev;
prev = current;
current = next;
}
return prev;
}
// 合并两个有序链表
public static ListNode? MergeTwoLists(ListNode? l1, ListNode? l2)
{
var dummy = new ListNode();
var current = dummy;
while (l1 != null && l2 != null)
{
if (l1.Val <= l2.Val)
{
current.Next = l1;
l1 = l1.Next;
}
else
{
current.Next = l2;
l2 = l2.Next;
}
current = current.Next;
}
current.Next = l1 ?? l2;
return dummy.Next;
}
}4. 二叉树的遍历方式有哪些？如何实现？
答： 主要有前序、中序、后序和层序四种遍历方式，每种都有递归和迭代两种实现。
public class TreeNode
{
public int Val { get; set; }
public TreeNode? Left { get; set; }
public TreeNode? Right { get; set; }
public TreeNode(int val = 0) => Val = val;
}
public class TreeTraversal
{
// 前序遍历 - 递归
public static IList<int> PreorderRecursive(TreeNode? root)
{
var result = new List<int>();
PreorderHelper(root, result);
return result;
}
private static void PreorderHelper(TreeNode? node, List<int> result)
{
if (node == null) return;
result.Add(node.Val);
PreorderHelper(node.Left, result);
PreorderHelper(node.Right, result);
}
// 前序遍历 - 迭代（使用栈）
public static IList<int> PreorderIterative(TreeNode? root)
{
var result = new List<int>();
if (root == null) return result;
var stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.Count > 0)
{
var node = stack.Pop();
result.Add(node.Val);
if (node.Right != null) stack.Push(node.Right);
if (node.Left != null) stack.Push(node.Left);
}
return result;
}
// 层序遍历（BFS）
public static IList<IList<int>> LevelOrder(TreeNode? root)
{
var result = new List<IList<int>>();
if (root == null) return result;
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0)
{
var levelSize = queue.Count;
var level = new List<int>();
for (int i = 0; i < levelSize; i++)
{
var node = queue.Dequeue();
level.Add(node.Val);
if (node.Left != null) queue.Enqueue(node.Left);
if (node.Right != null) queue.Enqueue(node.Right);
}
result.Add(level);
}
return result;
}
// 最大深度
public static int MaxDepth(TreeNode? root)
{
if (root == null) return 0;
return 1 + Math.Max(MaxDepth(root.Left), MaxDepth(root.Right));
}
// 判断是否是平衡二叉树
public static bool IsBalanced(TreeNode? root)
{
return CheckHeight(root) != -1;
}
private static int CheckHeight(TreeNode? node)
{
if (node == null) return 0;
var leftHeight = CheckHeight(node.Left);
if (leftHeight == -1) return -1;
var rightHeight = CheckHeight(node.Right);
if (rightHeight == -1) return -1;
if (Math.Abs(leftHeight - rightHeight) > 1) return -1;
return 1 + Math.Max(leftHeight, rightHeight);
}
}5. 排序算法的时间复杂度是多少？如何选择？
答：
| 算法 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(1) | 稳定 | 小规模数据 |
| 选择排序 | O(n^2) | O(n^2) | O(1) | 不稳定 | 小规模数据 |
| 插入排序 | O(n^2) | O(n^2) | O(1) | 稳定 | 近乎有序数据 |
| 快速排序 | O(n log n) | O(n^2) | O(log n) | 不稳定 | 通用排序 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 需要稳定排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 内存受限 |
public class SortingAlgorithms
{
// 快速排序
public static void QuickSort(int[] arr, int low = 0, int high = -1)
{
if (high == -1) high = arr.Length - 1;
if (low < high)
{
var pivotIndex = Partition(arr, low, high);
QuickSort(arr, low, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, high);
}
}
private static int Partition(int[] arr, int low, int high)
{
var pivot = arr[high];
var i = low - 1;
for (var j = low; j < high; j++)
{
if (arr[j] <= pivot)
{
i++;
(arr[i], arr[j]) = (arr[j], arr[i]);
}
}
(arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
return i + 1;
}
// 归并排序
public static void MergeSort(int[] arr)
{
if (arr.Length <= 1) return;
var mid = arr.Length / 2;
var left = arr[..mid];
var right = arr[mid..];
MergeSort(left);
MergeSort(right);
Merge(arr, left, right);
}
private static void Merge(int[] result, int[] left, int[] right)
{
var i = 0; var j = 0; var k = 0;
while (i < left.Length && j < right.Length)
{
result[k++] = left[i] <= right[j] ? left[i++] : right[j++];
}
while (i < left.Length) result[k++] = left[i++];
while (j < right.Length) result[k++] = right[j++];
}
// 堆排序
public static void HeapSort(int[] arr)
{
var n = arr.Length;
// 建最大堆
for (var i = n / 2 - 1; i >= 0; i--)
Heapify(arr, n, i);
// 逐个取出最大值
for (var i = n - 1; i > 0; i--)
{
(arr[0], arr[i]) = (arr[i], arr[0]);
Heapify(arr, i, 0);
}
}
private static void Heapify(int[] arr, int n, int i)
{
var largest = i;
var left = 2 * i + 1;
var right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i)
{
(arr[i], arr[largest]) = (arr[largest], arr[i]);
Heapify(arr, n, largest);
}
}
}6. 二分查找的变体有哪些？
答： 二分查找除了基本的精确查找外，还有查找第一个等于目标值、最后一个等于目标值、第一个大于等于目标值等变体。
public class BinarySearch
{
// 基本二分查找
public static int Search(int[] arr, int target)
{
var left = 0;
var right = arr.Length - 1;
while (left <= right)
{
var mid = left + (right - left) / 2; // 避免溢出
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// 查找第一个等于目标值的位置
public static int FindFirst(int[] arr, int target)
{
var left = 0;
var right = arr.Length - 1;
var result = -1;
while (left <= right)
{
var mid = left + (right - left) / 2;
if (arr[mid] == target)
{
result = mid;
right = mid - 1; // 继续向左找
}
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return result;
}
// 查找第一个大于等于目标值的位置（lower_bound）
public static int LowerBound(int[] arr, int target)
{
var left = 0;
var right = arr.Length;
while (left < right)
{
var mid = left + (right - left) / 2;
if (arr[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}
// 在旋转排序数组中查找
public static int SearchRotated(int[] arr, int target)
{
var left = 0;
var right = arr.Length - 1;
while (left <= right)
{
var mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
// 判断哪半边是有序的
if (arr[left] <= arr[mid])
{
if (target >= arr[left] && target < arr[mid])
right = mid - 1;
else
left = mid + 1;
}
else
{
if (target > arr[mid] && target <= arr[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}
}7. 如何用栈实现队列？用队列实现栈？
// 用栈实现队列
public class MyQueue
{
private readonly Stack<int> _input = new();
private readonly Stack<int> _output = new();
public void Enqueue(int x) => _input.Push(x);
public int Dequeue()
{
Peek();
return _output.Pop();
}
public int Peek()
{
if (_output.Count == 0)
{
while (_input.Count > 0)
_output.Push(_input.Pop());
}
return _output.Peek();
}
public bool Empty() => _input.Count == 0 && _output.Count == 0;
}
// 用队列实现栈
public class MyStack
{
private readonly Queue<int> _queue = new();
public void Push(int x)
{
_queue.Enqueue(x);
// 将前面的元素移到后面
for (int i = 0; i < _queue.Count - 1; i++)
_queue.Enqueue(_queue.Dequeue());
}
public int Pop() => _queue.Dequeue();
public int Top() => _queue.Peek();
public bool Empty() => _queue.Count == 0;
}8-20. 更多数据结构面试题简答
8. HashMap 的实现原理？ 哈希表通过哈希函数将键映射到数组索引，使用链地址法或开放寻址法处理冲突。C# 的 Dictionary<TKey, TValue> 使用链地址法。
9. 什么是红黑树？ 红黑树是一种自平衡二叉搜索树，通过颜色标记和旋转操作保证树的高度近似平衡，确保最坏情况下的 O(log n) 操作。C# 的 SortedDictionary 使用红黑树实现。
10. 如何实现前缀树（Trie）？ 前缀树是多叉树结构，每个节点存储一个字符，从根到某节点的路径构成一个字符串，常用于自动补全和拼写检查。
11. 什么是堆（Heap）？ 堆是完全二叉树，分为最大堆和最小堆。C# 使用 PriorityQueue<TElement, TPriority>（.NET 6+）实现优先队列。
12. 图的遍历方式有哪些？ 深度优先搜索（DFS）使用栈/递归，广度优先搜索（BFS）使用队列。DFS 适合寻找所有路径，BFS 适合寻找最短路径。
13. 什么是动态规划？ 动态规划将复杂问题分解为子问题，通过存储子问题的解避免重复计算。关键要素是最优子结构和重叠子问题。
14. 0-1 背包问题的解法？ 使用 DP 二维数组 dp[i, w] 表示前 i 个物品在容量 w 下的最大价值，状态转移：dp[i, w] = max(dp[i-1, w], dp[i-1, w-weight[i]] + value[i])。
15. 最长公共子序列（LCS）？ 使用 DP 二维数组，dp[i, j] 表示 s1[0..i] 和 s2[0..j] 的 LCS 长度。若 s1[i] == s2[j]，则 dp[i,j] = dp[i-1,j-1] + 1，否则取 max。
16. 什么是滑动窗口？ 滑动窗口是处理数组/字符串子区间问题的技巧，通过双指针维护一个窗口，动态调整窗口大小来求解。
17. 如何判断两个字符串是否是字母异位词？ 方法一：排序后比较（O(n log n)）；方法二：使用哈希表统计字符频率（O(n)）。
18. 什么是布隆过滤器？ 布隆过滤器是一种空间高效的概率数据结构，用于判断元素是否在集合中。可能有误判（false positive），但不会漏判（false negative）。
19. 如何找数组中的第 K 大元素？ 方法一：排序后取第 K 个（O(n log n)）；方法二：使用最小堆维护 K 个最大元素（O(n log k)）；方法三：快速选择算法（平均 O(n)）。
20. 什么是并查集？ 并查集（Union-Find）用于处理不相交集合的合并与查询，支持路径压缩和按秩合并优化，接近 O(1) 的时间复杂度。常用于连通性问题。
优点
缺点
总结
数据结构与算法面试的核心是理解基本原理和复杂度分析，而不是死记硬背代码。建议重点掌握数组、链表、树、排序、查找、动态规划等高频考点，并通过 LeetCode 等平台进行大量练习。在面试中，先分析问题、确定算法思路，再编写代码，最后检查边界条件和优化方案。
这组题真正考什么
- 面试官往往不只是考定义，而是在看你能否把基础概念放回真实 .NET 场景。
- 这类题经常沿着语言基础、框架设计、性能和工程实践往下追问。
- 高分答案通常有三层：结论、原因、项目中的例子。
60 秒答题模板
- 先用一句话给结论。
- 再补关键原理或底层机制。
- 最后说适用边界、常见坑或项目中的使用经验。
容易失分的点
- 只会背术语，不会举例。
- 回答太散，没有结构。
- 忽略版本差异和工程背景。
刷题建议
- 把答案拆成“定义、适用场景、风险点、实战例子”四段来复述。
- 遇到 .NET 基础题时，尽量补一个框架级别的落地场景，而不是只背术语。
- 高频概念题建议自己再追问一层：底层原理、常见坑、性能代价分别是什么。
高频追问
- 如果面试官继续追问底层实现，你能否解释运行机制或源码层面的关键点？
- 如果题目放到 ASP.NET Core、消息队列或数据库场景里，这个结论是否还成立？
- 是否存在版本差异、框架差异或特殊边界条件需要主动说明？
复习重点
- 把每道题的关键词整理成自己的知识树，而不是只背原句。
- 对容易混淆的概念要做横向比较，例如机制差异、适用边界和性能代价。
- 复习时优先补“为什么”，其次才是“怎么用”和“记住什么术语”。
面试作答提醒
- 先给结论，再补原因和例子。
- 回答基础题时不要只说“能用”，最好补一句为什么这样选。
- 如果记不清细节，优先说出适用边界和排查思路。