考研笔记

数据结构 第 1~4 章 名词库

每条最多四行：是／不是／易混／范围。

建设进度：✅ 第 1 章 绪论　✅ 第 2 章 线性表　✅ 第 3 章 栈、队列和数组　✅ 第 4 章 串　（四章完整）

1.1 数据结构的基本概念

数据元素 / 数据项

  • 是：数据元素是数据的基本单位；数据项是构成数据元素的不可分割的最小单位。
  • 易混：「基本单位」≠「最小单位」。一条学生记录是数据元素，学号、姓名是数据项。

数据对象

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

抽象数据类型（ADT）

  • 是：一个数学模型及定义在该模型上的一组操作，常用（数据对象，数据关系，基本操作集）三元组表示。
  • 范围：可以定义一个完整的数据结构。

数据结构三要素

  • 是：逻辑结构、存储结构、数据的运算。
  • 范围：缺一不可。

逻辑结构

  • 是：数据元素之间的逻辑关系，独立于存储结构，与计算机无关。
  • 范围：线性结构（线性表、栈、队列、串、数组）；非线性结构（集合、树、图）。
  • 易混：有序表是逻辑结构；顺序表、哈希表、单链表是完整的数据结构。

存储结构（物理结构）

  • 是：数据结构在计算机中的表示，既表示元素，也表示元素之间的关系。
  • 不是：不能独立于逻辑结构；它依赖于计算机语言。
  • 范围：顺序、链式、索引、散列四种。

顺序存储 / 链式存储

  • 是：顺序存储靠存储单元的邻接关系表示逻辑关系；链式存储靠指针。
  • 范围：顺序存储可随机存取，但可能产生较多外部碎片；链式存储不会出现碎片，但只能顺序存取。

索引存储 / 散列存储

  • 是：索引存储另建索引表，索引项为（关键字，地址）；散列存储由关键字直接计算地址。
  • 范围：索引检索快，但增删要改索引表；散列增删查都快，但会冲突。

数据的运算

  • 是：运算的定义针对逻辑结构（功能）；运算的实现针对存储结构（步骤）。

1.2 算法和算法评价

算法

  • 是：对特定问题求解步骤的一种描述，是指令的有限序列。
  • 范围：五个特性——有穷性、确定性、可行性、输入、输出。

有穷性 / 确定性 / 可行性

  • 是：有穷步后结束且每步有穷时间；相同输入只能得到相同输出；操作可由已实现的基本运算执行有限次实现。
  • 易混：可读性、健壮性、正确性是**「好」算法的设计目标**，不是特性。

输入 / 输出

  • 范围：输入零个或多个；输出一个或多个。

频度

  • 是：一条语句在算法中被重复执行的次数。所有语句的频度之和记为 。

时间复杂度

  • 是：基本运算（最深层循环内的语句）执行次数的数量级，。
  • 不是：不是 CPU 时间； 也不表示问题规模是 。
  • 范围：依赖问题规模 和输入数据的初始状态。

最坏 / 平均 / 最好时间复杂度

  • 是：平均时间复杂度指所有可能输入等概率出现时的期望运行时间。
  • 范围：一般考虑最坏情况。

加法规则 / 乘法规则

  • 是：并列取 ；嵌套取 。
  • 易混：内层次数依赖外层变量时不能直接相乘，要求和（2022 为 ）。

空间复杂度

  • 是：算法所需的存储空间，。
  • 范围：只分析除输入和程序之外的额外空间。

原地工作

  • 是：算法所需的辅助空间为常量，即 。
  • 不是：不是「不需要任何辅助空间」。

2.1~2.2 线性表与顺序表

线性表

  • 是：具有相同数据类型的 个数据元素的有限序列。
  • 不是：不是存储结构。顺序表、链表才是存储结构。
  • 范围： 为空表；表头无前驱，表尾无后继。

位序

  • 是：元素 在线性表中的序号 ，从 1 开始。
  • 易混：数组下标从 0 开始，位序 的元素是 data[i-1]。

顺序表

  • 是：用一组地址连续的存储单元依次存储线性表，逻辑顺序与物理顺序相同。
  • 范围：，随机存取。

随机存取 / 顺序存取

  • 是：随机存取指访问序号为 的元素的时间与 无关，；顺序存取指只能从表头依次访问。
  • 易混：顺序表是「顺序存储、随机存取」的结构。

静态分配 / 动态分配

  • 是：静态分配数组大小固定，满了就溢出；动态分配满了就另开更大的空间整体拷贝。
  • 不是：动态分配不是链式存储，仍可随机存取。

顺序表的插入 / 删除

  • 范围：插入 ，移 个，平均 ；删除 ，移 个，平均 。

2.3 线性表的链式表示

头指针 / 头结点

  • 是：头指针始终指向链表的第一个结点；头结点是带头结点的链表中第一个数据结点之前附加的结点。
  • 范围：头结点的两个好处——首位置操作与其他位置一致；空表与非空表处理统一。

单链表判空

  • 是：带头结点 L->next==NULL；不带头结点 L==NULL。

头插法 / 尾插法

  • 是：头插法新结点插在头结点之后，得到逆序；尾插法设尾指针 r，得到正序，最后 r->next=NULL。

双链表

  • 是：结点有 prior 和 next 两个指针。
  • 范围：插入 *s 到 *p 后，s->next=p->next 必须在 p->next=s 之前；两结点间插入改 4 个指针域。

循环单链表 / 循环双链表

  • 是：尾结点的 next 指向头结点；循环双链表的头结点 prior 还指向尾结点。
  • 范围：判空 L->next==L；循环双链表判空 L->prior==L && L->next==L。带头结点的循环单链表中没有空指针。
  • 易混：循环单链表常只设尾指针，r->next 即头结点，表头表尾插入都是 。

静态链表

  • 是：用数组描述链式存储，next 是数组下标（游标）。
  • 范围：预先分配连续空间，容量固定；next==-1 表示结束；插入删除不移动元素。
  • 不是：不能随机存取第 个元素。

3.1 栈

栈

  • 是：只允许在一端进行插入或删除操作的线性表，后进先出（LIFO）。
  • 范围：栈顶是允许插入删除的一端；栈底固定。

出栈序列的个数

  • 是： 个不同元素入栈，出栈序列共 个（卡特兰数）。
  • 不是：不是 。 时是 5 个， 不可能。
  • 范围：判定准则——在某元素之前入栈、却晚于它出栈的元素，必定按逆序出栈。

顺序栈 / 栈顶指针

  • 是：用连续存储单元存放元素，附设 top 指示栈顶位置。
  • 范围：默认 top 指向栈顶元素、初值 ，入栈 data[++top]=x；top 指向下一位置时入栈 data[top++]=x。
  • 易混：出栈只移动指针，数据仍可能留在原单元（2009）。

共享栈

  • 是：两个栈底设在共享空间两端，栈顶向中间延伸。
  • 范围：栈满 top1-top0==1；只在整个空间占满时才上溢。
  • 易混：降低的是上溢的可能，存取时间仍是 。

上溢 / 下溢

  • 是：上溢是存储器满了还往里写；下溢是存储器空了还往外读。

链栈

  • 是：用单链表实现的栈，所有操作在表头进行，教材规定没有头结点。
  • 范围：不存在栈满上溢；入栈 x->next=top; top=x;。

3.2 队列

队列

  • 是：只允许在一端插入（队尾）、另一端删除（队头）的线性表，先进先出（FIFO）。
  • 易混：栈与队列的本质区别是插入、删除操作的限定不同，不是逻辑结构或存储结构。

假溢出

  • 是：顺序队列 rear==MaxSize 时无法入队，但数组中仍有空位置。
  • 范围：循环队列就是为解决假溢出引入的。

循环队列

  • 是：把顺序队列从逻辑上视为一个环，指针进 1 用 %MaxSize。
  • 不是：不是用循环链表实现的队列，循环队列指顺序存储的队列。
  • 范围：长度 (rear-front+MaxSize)%MaxSize；牺牲一个单元时队满 (rear+1)%MaxSize==front，最多存 MaxSize-1 个。

链式队列

  • 是：同时带队首指针和队尾指针的单链表，通常带头结点。
  • 范围：带头结点时队空 front==rear；删除最后一个元素时 rear=front。

双端队列

  • 是：两端都可以插入和删除的线性表。
  • 范围：输出受限——一端可进可出、另一端只能入；输入受限——一端可进可出、另一端只能出。
  • 易混：2010、2021 都是输出受限。 时两种受限双端队列各能得到 22 种序列。

3.3 栈和队列的应用

括号匹配

  • 是：左括号入栈，右括号与栈顶匹配后出栈；扫描完栈空才算匹配。

中缀 / 后缀 / 前缀表达式

  • 是：后缀表达式（逆波兰式）运算符在操作数之后，不需要括号。
  • 范围：中缀转后缀用运算符栈，界限符 ( 也占栈位；后缀求值用操作数栈，中间结果也占栈位。

递归工作栈

  • 是：递归调用时系统用栈保存每一层的返回点、局部变量、传入实参。
  • 范围：递归次数过多容易栈溢出；递归的效率不高，原因是包含很多重复计算。

队列的应用

  • 范围：层次遍历、BFS；主机与打印机之间的缓冲区；多用户争用 CPU 时的就绪队列。

3.4 数组和特殊矩阵

数组

  • 是： 个相同类型元素构成的有限序列，是线性表的推广。
  • 范围：维数和维界定义后不再改变，只有存取、修改元素的操作。

行优先 / 列优先

  • 是：（行优先）；列优先把 与 对调。

压缩存储 / 特殊矩阵

  • 是：值相同的元素只分配一个空间，零元素不分配；特殊矩阵是相同元素或零元素分布有规律的矩阵。
  • 范围：对称 ；三角 ；三对角 ，。

稀疏矩阵 / 三元组

  • 是：非零元素个数 元素总数 ；三元组为（行标，列标，值）。
  • 范围：压缩后失去随机存取特性；三元组表可用数组或十字链表存储；还要保存行数、列数、非零元素个数。

4.1 串（*，不在统考大纲范围）

串

  • 是：由零个或多个字符组成的有限序列。
  • 易混：与线性表的区别仅在于数据对象限定为字符集；基本操作以子串为操作对象。

空串 / 空格串

  • 是：空串长度为 0；空格串由一个或多个空格组成，长度为空格个数。
  • 不是：空格串不是空串。

子串 / 主串 / 位置

  • 是：子串是串中任意多个连续字符组成的子序列；子串的位置以其第 1 个字符在主串中的位置表示。

最小操作子集

  • 是：StrAssign、StrCompare、StrLength、Concat、SubString。
  • 不是：Index（定位）不在其中。

定长顺序存储 / 堆分配存储 / 块链存储

  • 是：定长数组，超长被截断；堆分配仍是连续单元但动态分配；块链是每个结点存一个或多个字符的链表。

4.2 串的模式匹配

模式匹配

  • 是：在主串中找到与模式串相同的子串，并返回其所在的位置。
  • 易混：求子串是截取子串，不是模式匹配。

简单的模式匹配算法

  • 是：失配时 i=i-j+2、j=1，主串指针回溯。
  • 范围：最多 趟，每趟最多 次，最坏 ；一般情况下实际执行时间近似 。

前缀 / 后缀 / 部分匹配值（PM）

  • 是：前缀是除最后一个字符外的所有头部子串；后缀是除第一个字符外的所有尾部子串；PM 是最长相等前后缀的长度。
  • 范围：右滑位数 = 已匹配的字符数 − 对应的部分匹配值。

next 数组

  • 是：next[j] 为模式串第 个字符失配时跳到的位置，。
  • 范围：位序从 1 起时 next[1]=0、next[2]=1；从 0 起时整体减 1。2015、2019、2024 的王道解析都按位序从 0 算。

KMP 算法

  • 是：失配时 不变、； 时 、 同时加 1。
  • 范围：；主要优点是主串不回溯，仅在部分匹配多时明显快于简单匹配。

nextval 数组

  • 是：若 ，把 next[j] 修正为 next[next[j]]，直至不等。
  • 范围：匹配算法不变；右滑距离 （2024）。

高频范围限定清单

说法判定
「数据项是基本单位」错。数据元素是基本单位，数据项是最小单位
「有序表是存储结构」错。是逻辑结构
「顺序表是逻辑结构」错。是完整的数据结构
「集合是线性结构」错。非线性
「存储结构独立于逻辑结构」错。逻辑结构独立于存储结构
「数据结构仅由逻辑结构和存储结构决定」错。还有运算
「链式存储会产生碎片」错。顺序存储才会产生外部碎片
「可读性是算法的特性」错。是设计目标
「算法至少一个输入」错。零个或多个
「 空间 = 不需要辅助空间」错。辅助空间与 无关
「空间复杂度算上输入数据」错。只算额外空间
「一般讨论平均时间复杂度」错。一般考虑最坏
「两层循环一定 」错。2014 为 ，2022 为
「线性表是存储结构」错。是逻辑结构
「顺序表是顺序存取结构」错。是随机存取结构
「动态分配的顺序表是链式存储」错。仍是顺序存储
「插入合法位置 」错。
「插入、删除平均都移 」错。删除是
「头结点的目的是让链表至少有一个结点」错。是方便运算的实现
「结点内存储单元可以不连续」错。结点内必须连续
「有尾指针就能 删尾结点」错。要找前驱，单链表
「建立有序单链表最低 」错。
「双链表的优点是插入删除更方便」错。是访问前后结点更灵活
「循环单链表判空 L->next==NULL」错。L->next==L
「head->next->next==head ⟹ 表长 1」错。0 或 1
「静态链表可随机存取」错。要按游标依次找
「 个元素的出栈序列有 个」错。卡特兰数， 时 5 个
「出栈后数据就被清除」错。只移动 top
「共享栈降低下溢」错。降低上溢
「链栈的优势是插入删除容易」错。是不会栈满
「栈和队列的区别是逻辑结构不同」错。是操作的限定不同
「循环队列 = 循环链表实现的队列」错。循环队列是顺序存储
「A[0…n] 的循环队列用 mod n」错。mod (n+1)
「链式队列出队只改头指针」错。删最后一个元素时也改尾指针
「输出受限 = 一端只能出」错。是一端只能入
「三对角矩阵需 个单元」错。
「稀疏矩阵压缩后仍可随机存取」错。失去随机存取
「存稀疏矩阵只存三元组」错。还要存行数、列数
「空格串是空串」错。长度为空格个数
「Index 属于最小操作子集」错。不属于
「简单模式匹配是 」错。理论 ，实际近似
「PM 是公共前后缀的个数」错。是最长相等前后缀的长度
「next[j]=PM[j]+1」错。
「KMP 失配时 加 1」错。 不变
「nextval 改变匹配算法」错。算法不变
「真题的 next 一律从 1 起」错。2015/2019/2024 解析按从 0 起
「比较次数不算失配那一次」错。失配也算

链接

反向链接