前言：数据结构与算法是408计算机学科专业基础综合核心必考模块，也是计算机求职笔试、面试的核心重难点。吃透基础概念，是后续刷题、拔高、攻坚高阶算法的关键。

一、数据结构

1.1 数据结构基本概念（核心名词辨析）

本节为考研基础选择题高频考点，重点区分数据、数据元素、数据项、数据对象四个易混概念。

点击展开：五大核心概念详解
  • 数据：信息的载体，是描述客观事物属性的数、字符，以及所有能输入计算机、可被程序识别和处理的符号集合。是计算机处理的所有信息的统称。
  • 数据元素：数据的基本处理单位，程序中通常作为整体处理。一个数据元素可由多个数据项组成。

    举例：学生整体信息记录（学号+姓名+性别+成绩）。

  • 数据项：数据元素中不可分割的最小单位，是数据的最小粒度。

    举例：单独的学号、学生姓名、单科成绩。

  • 数据对象：具有相同性质的数据元素的集合，是数据的子集。

    举例：全班所有学生的信息记录、所有整数数据。

  • 数据结构：相互之间存在一种或多种特定关系的数据元素的集合，核心研究数据元素之间的相互关系。

1.2 数据类型分类

点击展开：三类数据类型详解
  • 原子类型：值不可再拆分的基础数据类型，是最小数据单元。

    示例：int、bool、char、float 等基本类型。

  • 结构类型：值可拆分为多个独立分量的数据类型，由多个原子类型或结构类型组合而成。

    示例：结构体、数组、链表节点等。

  • 抽象数据类型（ADT）：抽象的数据组织形式 + 对应专属操作的总称，不局限于具体编程语言，侧重逻辑定义。

    核心特点：数据抽象、操作抽象，典型如栈、队列、树、图。

1.3 数据结构三要素（考研重中之重）

所有数据结构的学习，均围绕以下三要素展开，是分析各类结构特性的核心依据。

  • 逻辑结构：数据元素之间的抽象逻辑关系，与存储位置无关。
    常见分类：线性结构（线性表、栈、队列）、非线性结构（树、图、集合）。
  • 存储结构（物理结构）：逻辑结构在计算机内存中的具体存储形式。
    四大基础结构：顺序存储、链式存储、索引存储、散列存储。
  • 数据运算：对数据结构可执行的操作，核心运算：查找、插入、删除、修改、排序。

二、算法

经典公式：程序 = 数据结构 + 算法

数据结构负责存储数据、组织数据，算法负责处理数据、解决问题，二者相辅相成。

算法定义：对特定问题求解步骤的有限、有序指令序列，每一条指令对应一个或多个基础操作。

2.1 算法五大基本特性（必考选择题）

点击展开：算法五大特性完整解析
  • 有穷性：算法必须在有限步骤、有限时间内执行结束，不能无限循环、永久执行。（区别于程序，程序可以无限运行）
  • 确定性：每一条指令含义唯一、无歧义，相同输入必然得到完全相同的输出，不存在随机、模糊执行逻辑。
  • 可行性：算法中所有操作，都可通过计算机已实现的基本运算，经过有限次执行完成，不存在无法落地的操作。
  • 输入：零个或多个输入，输入数据取自特定对象集合，可无外部输入（内部赋值）。
  • 输出：一个或多个输出，输出结果与输入数据存在明确的逻辑对应关系，无输出的算法无意义。

2.2 优质算法的四大评判标准

  • 正确性：核心标准，算法能够准确求解问题，合法输入可得到正确结果，满足题目需求。
  • 可读性：代码逻辑清晰、注释规范、结构工整，便于他人阅读理解、调试和二次修改，工程开发优先级极高。
  • 健壮性：面对非法输入、异常数据时，可主动处理、合理报错，不会崩溃、输出乱码或未知结果。
  • 高效率、低存储：时间复杂度低、空间复杂度小，在问题规模增大时，仍能保持良好的运行性能。

2.3 算法时间复杂度

核心定义：算法基本操作的执行次数，是问题规模 $n$ 的函数，用于衡量算法运行时间的增长趋势。

记作：$T(n)=O(f(n))$

含义：算法执行时间的增长率与 $f(n)$ 的增长率趋于一致，只关注高阶主导项，忽略常数、低阶项。

2.4 算法空间复杂度

核心定义：算法运行过程中，所耗费的最大内存存储空间，同样是问题规模 $n$ 的函数。

记作：$S(n)=O(g(n))$

包含两部分：算法本身指令占用空间 + 运行时临时变量、辅助空间占用。

:::tip 💡408考研核心总结

  1. 概念题重点区分：数据/数据元素/数据项/数据对象；算法五大特性
  2. 计算题核心：时间复杂度、空间复杂度分析
  3. 设计题基础：基于三要素分析各类数据结构特性
    :::