📖 数据结构（Data Structure）—— 408考研完全笔记

相关笔记 OS：进程、内存管理、文件系统与数据结构中的队列、树、图、查找结构有大量交叉。 CO：存储层次、地址映射、缓存结构会影响算法和数据结构的实际性能。 CN：图、队列、缓冲区、滑动窗口等模型能和数据结构知识互相验证。 编写说明 ：本笔记严格依据全国硕士研究生招生考试计算机学科专业基础（科目代码：408/11408）考试大纲编写，结合王道考研教材体系与历年真题，力求概念严谨、解释通俗、解题实用。 考试概况 ：408统考满分150分，考试时间180分钟（3小时）。其中 数据结构约占45分（30%） ，计算机组成原理约占45分（30%），操作系统约占35分（约23%），计算机网络约占25分（约17%）。题型包括： 单项选择题（80分

第一章 绪论 1.1 数据结构的基本概念 一、核心定义 数据（Data） ：信息的载体，是对客观事物符号化的表示，能够被计算机识别、存储和加工处理。 🗣️ 大白话 ：数据就是计算机能认识的东西。你的名字、年龄、一张照片、一段视频，只要能存进电脑里的，都叫数据。 数据元素（Data Element） ：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个 数据项（Data Item） 组成，数据项是构成数据元素的不可分割的最小单位。 🗣️ 大白话 ：好比一个学生信息表，每一行（一个学生的全部信息）就是一个数据元素，而"姓名""学号""成绩"这些列就是数据项。数据项是最小的，不能再拆了。 数据对象（D

第二章 线性表 2.1 线性表的定义和基本操作 一、线性表的定义 线性表（Linear List） ：具有 相同数据类型 的 $n$（$n \geq 0$）个数据元素的 有限序列 ，其中 $n$ 为表长，当 $n=0$ 时称为空表。记作： $$L = (a 1, a 2, \ldots, a i, \ldots, a n)$$ $a 1$ 是 表头元素 ，$a n$ 是 表尾元素 $a {i 1}$ 是 $a i$ 的 直接前驱 ，$a {i+1}$ 是 $a i$ 的 直接后继 除表头元素外，每个元素有且仅有一个直接前驱 除表尾元素外，每个元素有且仅有一个直接后继 🗣️ 大白话 ：线性表就是一排相同类型的东西排成一条线。就像食堂

第三章 栈、队列和数组 3.1 栈（Stack） 一、栈的基本概念 栈（Stack） ：只允许在 一端 进行插入和删除操作的线性表。允许操作的一端称为 栈顶（top） ，不允许操作的一端称为 栈底（bottom） 。 核心特征 ： 后进先出（LIFO, Last In First Out） 🗣️ 大白话 ：栈就像一摞盘子——你只能从最上面放盘子（入栈/压栈），也只能从最上面拿盘子（出栈/弹栈）。最后放上去的盘子最先被拿走，这就叫"后进先出"。 🔗 【跨学科联动·OS/计组】 栈在操作系统中无处不在： 函数调用栈 ：每次函数调用时，OS 将 返回地址、局部变量、参数 压入栈帧（Stack Frame），函数返回时弹出恢复现场。这就

第四章 串（String） 4.1 串的定义和基本操作 串（String） ：由零个或多个字符组成的有限序列。记作 $S='a 1a 2\ldots a n'$，其中 $n$ 为串长。$n=0$ 时称为 空串 （用 $\varnothing$ 表示）。 ⚠️ 空串 vs 空格串 ：空串长度为0（无任何字符），空格串 " " 长度为1（包含一个空格字符），二者不同！ 子串 ：串中任意个 连续 字符组成的子序列。 空串是任何串的子串，任何串是自身的子串 。 子串位置 ：子串在主串中第一次出现时 第一个字符的位置 （位序从1开始）。 串 vs 线性表 ： 串是特殊的线性表—— 数据对象限定为字符集 串的操作对象通常是 子串 （而非单个元素

第五章 树与二叉树 5.1 树的基本概念 一、树的定义 树（Tree） ：$n$（$n \geq 0$）个结点的有限集合。$n=0$ 时称为空树。在任一非空树中： 1. 有且仅有一个特定的称为 根（Root） 的结点 2. 当 $n 1$ 时，其余结点可分为 $m$（$m 0$）个互不相交的有限集合 $T 1, T 2, \ldots, T m$，其中每一个集合本身又是一棵树，称为根的 子树（SubTree） 🗣️ 大白话 ：树就像一棵倒过来的真实的树——根在最上面，树枝往下分叉。一个根可以有很多树枝（子树），每个树枝又可以继续分叉。 二、基本术语 术语 定义 大白话 结点的度 结点拥有的子树数目 这个人有几个亲儿子 树的度 树中

第六章 图 6.1 图的基本概念 一、图的定义 图（Graph） ：由 顶点集 $V$ 和 边集 $E$ 组成。记作 $G=(V, E)$，其中 $V(G)$ 是顶点的有穷非空集合，$E(G)$ 是边的有穷集合。 ⚠️ 注意 ：图的顶点集 $V$ 必须非空（至少有一个顶点），但边集 $E$ 可以为空。 有向图 vs 无向图 ： 类型 边的表示 特点 无向图 $(v i, v j)$ 边没有方向，$(v i, v j) = (v j, v i)$ 有向图 $\langle v i, v j \rangle$ 弧有方向，$\langle v i, v j \rangle \neq \langle v j, v i \rangle$ 🗣

第七章 查找 7.1 查找的基本概念 查找表 ：同一类型数据元素的集合。 关键字 ：数据元素中唯一标识该元素的某个数据项。 查找成功/失败 ：在查找表中找到/未找到给定关键字的记录。 平均查找长度ASL ： $$ASL = \sum {i=1}^{n} P i C i$$ 其中 $P i$ 是查找第 $i$ 个元素的概率，$C i$ 是找到第 $i$ 个元素需要比较的次数。 🗣️ 大白话 ：ASL 就是"平均要比较多少次才能找到"。ASL 越小，查找效率越高。 7.2 线性表的查找 一、顺序查找 思路 ：从头到尾一个一个比较。 $$ASL {成功} = \frac{n+1}{2}, \quad ASL {失败} = n+1$$ 哨

第八章 排序 8.1 排序的基本概念 排序 ：将一组无序数据按照关键字递增（或递减）排列。 稳定性 ：若排序前两个相等的元素 $R i$ 和 $R j$（$i < j$），排序后 $R i$ 仍在 $R j$ 前面，则称排序算法是 稳定的 ，否则是 不稳定的 。 🗣️ 大白话 ：假设班里有两个学生都叫"张三"，排序前 A张三 在 B张三 前面。如果排序后 A张三 还在前面，这种排序就是"稳定"的。 内部排序 vs 外部排序 ： 内部排序 ：数据全部在内存中 外部排序 ：数据量大，需借助外存 🔗 【跨学科联动·OS/计组】 排序算法的选择与 OS 和计组紧密关联： OS·外部排序 ：当数据无法全部装入内存时，需要利用 OS 的 文

📋 数据结构全书终极总结 一、各章节在408考试中的分值分布（近年趋势） 章节 常考题型 预估分值 第一章 绪论 选择题 2 4分 第二章 线性表 选择题 + 大题 6 10分 第三章 栈/队列/数组 选择题 4 6分 第四章 串 选择题（KMP） 2 4分 第五章 树与二叉树 选择题 + 大题 8 12分 第六章 图 选择题 + 大题 6 10分 第七章 查找 选择题 + 大题 6 8分 第八章 排序 选择题 + 大题 6 10分 二、高频考点清单（必须重点突破） 1. 时间复杂度分析 （选择题必考）——注意 $O(\sqrt{n})$、嵌套 $i \times i \leq n$ 等变形（2017, 2019, 2025） 2