软件设计师考试 - 数据结构与算法

一、数据结构基础

1. 数据结构的定义

• 数据结构是数据的组织、存储和管理方式，包括逻辑结构和物理结构。
• 逻辑结构：线性结构（如数组、链表）、非线性结构（如树、图）。
• 物理结构：顺序存储（数组）、链式存储（链表）。

2. 时间复杂度与空间复杂度（查看详细）

• 时间复杂度：描述算法执行时间随数据规模增长的趋势，常见表示法：O(1)、O(n)、O(n²)、O(logn)。
• 空间复杂度：描述算法运行时所需的额外存储空间。

二、线性结构

1. 数组（Array）（查看详细）

• 连续存储，支持随机访问（O(1)），插入/删除效率低（O(n)）。
• 真题考点：二维数组的地址计算（如2021年真题）。

2. 链表（Linked List）（查看详细）

• 非连续存储，插入/删除效率高（O(1)），访问效率低（O(n)）。
• 类型：单链表、双向链表、循环链表。
• 真题考点：链表反转、环检测（如2019年真题）。

3. 栈（Stack）（查看详细）

• 后进先出（LIFO），操作：push（入栈）、pop（出栈）。
• 应用：函数调用栈、表达式求值（如2020年真题）。

4. 队列（Queue）（查看详细）

• 先进先出（FIFO），操作：enqueue（入队）、dequeue（出队）。
• 特殊队列：循环队列、优先队列（堆实现）。

三、非线性结构

1. 树（Tree）（查看详细）

• 二叉树：每个节点最多两个子节点。
  • 遍历方式：前序（根-左-右）、中序（左-根-右）、后序（左-右-根）。
  • 真题考点：二叉树遍历的非递归实现（如2022年真题）。
• 二叉搜索树（BST）：左子树值 < 根 < 右子树值，查找效率O(logn)。
• 平衡二叉树（AVL树）：通过旋转保持平衡，避免退化为链表。
• 堆（Heap）：完全二叉树，分为大顶堆（父节点≥子节点）和小顶堆。

2. 图（Graph）（查看详细）

• 存储方式：邻接矩阵（空间O(n²)）、邻接表（空间O(n+e)）。
• 遍历算法：
  • 深度优先搜索（DFS）：递归或栈实现。
  • 广度优先搜索（BFS）：队列实现。
• 最短路径算法：
  • Dijkstra：单源最短路径（无权图或正权图）。
  • Floyd：多源最短路径（动态规划）。
• 最小生成树（MST）：
  • Prim算法：贪心策略，适合稠密图。
  • Kruskal算法：并查集实现，适合稀疏图。

四、排序算法（查看详细）

排序算法	时间复杂度（平均）	空间复杂度	稳定性	特点
冒泡排序	O(n²)	O(1)	稳定	简单，效率低
快速排序	O(nlogn)	O(logn)	不稳定	分治法，实际应用最广
归并排序	O(nlogn)	O(n)	稳定	外部排序常用
堆排序	O(nlogn)	O(1)	不稳定	适合大数据量
插入排序	O(n²)	O(1)	稳定	适合小规模或部分有序数据

真题考点：快速排序的分区过程（如2023年真题）、堆排序的建堆操作（如2021年真题）。

五、查找算法（查看详细）

1. 顺序查找

• 时间复杂度：O(n)，适用于无序数据。

2. 二分查找

• 时间复杂度：O(logn)，要求数据有序。

3. 哈希查找

• 时间复杂度：O(1)，需处理冲突（开放定址法、链地址法）。
• 真题考点：哈希函数设计（如2022年真题）。

六、算法设计思想（查看详细）

1. 分治法（Divide and Conquer）

• 将问题分解为子问题，递归求解（如归并排序、快速排序）。

2. 贪心算法（Greedy）

• 局部最优解推导全局最优解（如Dijkstra算法、哈夫曼编码）。

3. 动态规划（DP）

• 将问题分解为重叠子问题，保存中间结果（如背包问题、最长公共子序列）。
• 真题考点：0-1背包问题（如2020年真题）。

七、真题高频考点

1. 二叉树遍历：非递归实现、线索二叉树。
2. 图算法：DFS/BFS应用（如拓扑排序）。
3. 排序与查找：快速排序、堆排序、二分查找。
4. 动态规划：斐波那契数列、矩阵连乘。

八、备考建议

1. 掌握核心数据结构：数组、链表、树、图的存储与操作。
2. 熟练排序与查找算法：重点理解快速排序、堆排序、哈希查找。
3. 真题训练：精做近5年真题（如2020-2024年），分析高频考点。
4. 手写代码练习：实现常见算法（如二叉树遍历、快速排序）。

附：近3年新增趋势

• 算法优化题增多（如时间/空间复杂度的优化）。
• 结合实际场景的算法设计（如缓存淘汰算法LRU）。