自考13003《数据结构与算法》核心内容（精简备考版）

自考13003《数据结构与算法》核心内容（精简备考版）本课程是计算机类及相关专业核心基础课，核心围绕“数据组织+算法设计”展开，考核层次分为识记、领会、简单应用、综合应用四级，以下为高频考点、核心概念及必背知识点，严格贴合自考大纲与教材，适配各类考试题型，无需额外翻书冗余内容。第一章绪论（基础考点，单选+填空+简答）（一）核心概念（识记必背）数据：描述客观事物的数、字符及能输入计算机处理的符号集合，是计算机处理的基本对象。数据元素：数据的基本单位，也称结点，是进行数据处理的基本单元（如一个学生信息）。数据项：具有独立含义的最小标识单位，是数据元素的组成部分（如学生的姓名、学号）。数据结构：相互之间存在一种或多种特定关系的数据元素的集合，包含三要素：逻辑结构、存储结构、数据运算。逻辑结构：数据元素之间的抽象关系（与存储无关），分为两类：线性结构：元素之间一对一（如线性表、栈、队列）；非线性结构：元素之间一对多（树）、多对多（图）。存储结构（物理结构）：数据在计算机中的存储表示，核心4种：顺序存储、链式存储、索引存储、散列（哈希）存储，存储结构决定运算的实现效率。抽象数据类型（ADT）：由数据对象、数据关系和基本操作构成的数学模型，隐藏内部实现，仅暴露接口。算法：解决特定问题的有穷指令序列，必须满足5个特性：有穷性、确定性、可行性、输入（可选）、输出（必选）。（二）算法分析（高频考点，领会+简单应用）核心指标：时间复杂度、空间复杂度，用于评估算法效率，自考重点考查时间复杂度。时间复杂度：算法执行所耗费的时间（与问题规模n相关），用大O表示法描述（忽略常数、低次项、系数），高频考法：分析程序段的时间复杂度。常见复杂度（按效率排序）：O(1)（常数阶）<O(log₂n)（对数阶）<O(n)（线性阶）<O(nlog₂n)（线性对数阶）<O(n²)（平方阶）<O(n³)（立方阶）<O(2ⁿ)（指数阶）。高频示例：循环1次→O(1)；单层循环→O(n)；双层嵌套循环→O(n²)；二分查找→O(log₂n)。空间复杂度：算法执行所需的额外存储空间（不包含输入数据本身），常用大O表示法，高频考法：判断算法的空间开销。（三）算法设计策略（识记+简单应用）核心6种策略，掌握每种特点及简单应用场景：递推法：从已知条件出发，逐步推导得出结果；迭代法：重复执行某一操作，逐步逼近目标（如求阶乘）；递归法：函数调用自身，将复杂问题分解为简单子问题（如斐波那契数列）；贪心法：每次选择局部最优解，最终得到全局最优（如找零问题）；分治法：将问题分解为多个独立子问题，求解后合并结果（如快速排序、归并排序）；动态规划法：存储子问题结果，避免重复计算（如最长公共子序列）。（四）高频简答1.简述数据结构的三要素及逻辑结构、存储结构的关系：答：三要素为逻辑结构、存储结构、数据运算；逻辑结构是数据元素的抽象关系，与存储无关；存储结构是逻辑结构在计算机中的具体实现，存储结构决定运算的实现方式和效率，二者相互依赖、相互影响。2.简述算法的5个特性：答：有穷性（有限步骤内终止）、确定性（每步指令含义明确）、可行性（指令可执行）、输入（0个或多个输入）、输出（至少1个输出）。第二章线性表（重中之重，全题型覆盖）（一）核心概念（识记必背）线性表：n个数据元素的有限序列，元素之间一对一的线性关系，分为有序表（元素按关键字有序）和无序表（元素无序）。核心术语：表长（元素个数）、表头元素（第一个元素）、表尾元素（最后一个元素）、直接前驱（前一个元素）、直接后继（后一个元素）。线性表的存储结构：顺序存储（顺序表）、链式存储（单链表、双向链表、循环链表）、静态链表。（二）顺序表（领会+简单应用）定义：将数据元素按线性关系依次存储在连续的存储单元中，逻辑相邻则物理相邻（如数组）。特点：随机访问（可直接通过下标访问任意元素）、存储密度高；插入/删除操作需移动大量元素，效率低。核心操作及实现（简单应用）：初始化、求表长、取值（按下标）、查找（按值）、插入、删除；地址计算公式：loc(ai)=loc(a1)+(i-1)×L（L为单个元素所占字节数）；时间复杂度：查找、取值→O(1)；插入、删除→O(n)（最坏情况需移动全部元素）。（三）链表（领会+简单应用+综合应用）核心考点，自考高频考查链表操作及算法实现，重点掌握单链表，兼顾双向链表、循环链表。单链表：定义：数据元素（结点）存储在不连续的存储单元中，每个结点包含数据域（存储元素值）和指针域（指向后继结点）；核心术语：表头结点（头结点，不存储数据，简化操作）、首结点（第一个存储数据的结点）、表尾结点（指针域为NULL）、表头指针（指向头结点的指针）；核心操作：初始化、求表长、查找、插入、删除、遍历；判空条件：带头结点的单链表为空→head->next=NULL；时间复杂度：查找、插入、删除→O(n)（需遍历链表）；遍历→O(n)。循环链表：表尾结点的指针域指向头结点，特点：从表中任意结点出发均可访问整个链表，判空条件→head->next=head。双向链表：每个结点包含两个指针域（前驱指针、后继指针），可双向遍历，插入/删除操作需同时修改两个指针域。静态链表：用数组模拟链表，结点包含数据域和游标（模拟指针），适用于不支持指针的语言，核心掌握基本操作及时间复杂度。（四）顺序表与链表的对比（简答高频）答：1.存储方式：顺序表连续存储，链表不连续存储；2.访问方式：顺序表随机访问，链表顺序访问；3.操作效率：顺序表查找/取值效率高（O(1)），插入/删除效率低（O(n)）；链表相反；4.存储密度：顺序表高（无额外指针开销），链表低（有指针域开销）；5.适用场景：顺序表适用于元素个数固定、查询频繁的场景；链表适用于元素个数动态变化、插入/删除频繁的场景。第三章栈和队列（高频考点，全题型覆盖）（一）栈（领会+简单应用+综合应用）核心定义：限定仅在表尾进行插入和删除操作的线性表，表尾称为栈顶，表头称为栈底，遵循先进后出（LIFO）原则（如叠盘子）。核心术语：栈容量、入栈（push，栈顶插入）、出栈（pop，栈顶删除）、栈空、栈满。存储结构：顺序栈：用数组实现，栈顶指针top标记栈顶位置，栈空→top=-1，栈满→top=容量-1；链式栈：用链表实现，栈顶为链表头结点，入栈插表头，出栈删表头，无需判断栈满（仅需判断栈空）。核心应用（综合应用高频）：括号匹配算法（自考高频）；中缀表达式转换为后缀表达式（逆波兰表达式）；后缀表达式求值；递归调用的底层实现。时间复杂度：入栈、出栈→O(1)；遍历→O(n)。（二）队列（领会+简单应用+综合应用）核心定义：限定仅在表尾插入、表头删除的线性表，表尾称为队尾，表头称为队头，遵循先进先出（FIFO）原则（如排队买票）。核心术语：队列长度、入队（enqueue，队尾插入）、出队（dequeue，队头删除）、队空、队满。存储结构（重点掌握循环队列）：顺序队列：用数组实现，存在“假溢出”问题（队尾满但队头有空位）；循环队列（自考高频）：将数组视为环形，用队头指针front、队尾指针rear标记，解决假溢出；判空条件：front==rear；判满条件：(rear+1)%容量==front（浪费一个元素空间，简化判断）；队列长度计算公式：(rear-front+容量)%容量。链式队列：用链表实现，队头为链表头结点，队尾为链表尾结点，无需判断队满。时间复杂度：入队、出队→O(1)；遍历→O(n)。（三）补充：双端队列（识记+简单应用）允许在两端插入、删除的队列，分为输入受限双端队列（仅一端可输入）、输出受限双端队列（仅一端可输出），掌握基本操作及空/满判定。第四章数组、广义表和串（基础考点，单选+填空+解答）（一）数组（领会+简单应用）定义：按顺序存储的多维线性表，元素具有相同的数据类型，下标唯一确定元素位置（如二维数组A[5][6]）。存储方式（自考高频）：行优先存储（C语言采用）：先存储第一行，再存储第二行，依次类推；列优先存储（Fortran语言采用）：先存储第一列，再存储第二列，依次类推；地址计算（解答题高频）：已知数组首地址、单个元素字节数，计算指定元素的起始地址（如二维数组A[i][j]的地址计算）。高频示例：二维数组A(5)(6)，每个元素占4字节，首地址1000，行优先存储时A(2)(5)的起始地址=1000+(2×6+5)×4=1000+17×4=1068。（二）广义表（识记）由n个元素组成的有限序列，元素可以是原子（不可再分）或广义表（可再分），掌握基本定义及结构表示，自考仅考查识记，无需深入应用。（三）串（领会+简单应用）定义：由n个字符组成的有限序列（如“abc”），也称字符串，n=0时为空串。核心术语：子串（串中连续的字符序列）、主串（包含子串的串）、串长（字符个数）、空串（无字符）、空格串（仅含空格）。核心操作：串的赋值、比较、连接、求子串、查找（如子串定位，KMP算法为高频考点，掌握基本思想及步骤）。第五章树与二叉树（重中之重，全题型覆盖）（一）树的基本概念（识记+领会）定义：n个结点的有限集合，有且仅有一个根结点（无前驱），其余结点分为若干个互不相交的子树，每个子树也是一棵树，属于非线性结构（一对多关系）。核心术语：根、叶子结点（无后继）、父结点、子结点、兄弟结点、结点的度（子结点个数）、树的度（最大结点度）、树的深度（层数，根为第一层）。特点：无环、仅有一个根、任意两个结点有且仅有一条路径。（二）二叉树（领会+简单应用+综合应用）自考核心，重点掌握定义、性质、遍历及应用，高频考查算法阅读与设计。定义：每个结点最多有两个子树（左子树、右子树）的树，左、右子树有顺序（不能互换），五种基本形态：空二叉树、仅根结点、左子树为空、右子树为空、左右子树均非空。核心性质（填空+单选高频）：性质1：第k层最多有2^(k-1)个结点（k≥1）；性质2：深度为k的二叉树最多有2ᵏ-1个结点（k≥1）；性质3：任意二叉树，叶子结点数=度为2的结点数+1；性质4：深度为k、仅含度0和度2的二叉树，最少有2k-1个结点。特殊二叉树：满二叉树：每一层结点数均为最大值（2^(k-1)）；完全二叉树：除最后一层外，每一层结点数均为最大值，最后一层结点从左到右连续排列（自考高频，掌握存储及性质）。二叉树的遍历（综合应用高频）：从根结点出发，按某种顺序访问所有结点（每个结点仅访问一次），三种核心遍历方式，需掌握递归/非递归实现及遍历序列：先序遍历（根→左→右）；中序遍历（左→根→右）；后序遍历（左→右→根）；补充：层序遍历（按层数依次访问，从上到下、从左到右）。高频考点：已知两种遍历序列（如中序+先序），求第三种遍历序列；遍历算法的代码阅读与编写。（三）堆及优先队列（领会+简单应用）堆：完全二叉树，分为大根堆（根结点为最大值，每个父结点≥子结点）、小根堆（根结点为最小值，每个父结点≤子结点），掌握堆的构建、插入、删除操作。优先队列：基于堆实现，元素按优先级排列，优先级高的先出队，掌握基本操作及应用场景。（四）哈夫曼树及哈夫曼编码（领会+简单应用）哈夫曼树（最优二叉树）：给定n个权值，构造的二叉树中，所有叶子结点的权值×路径长度之和（WPL）最小，掌握哈夫曼树的构造步骤。哈夫曼编码：基于哈夫曼树的前缀编码（无一个编码是另一个编码的前缀），用于数据压缩，掌握编码方法及应用。第六章图结构（高频考点，单选+填空+解答+算法）（一）核心概念（识记+领会）定义：由顶点集合V和边集合E组成的非线性结构，顶点之间为多对多关系（如社交网络）。核心术语：顶点、边（无向图）、弧（有向图）、顶点的度（关联的边/弧的个数）、有向图的入度/出度、完全图（无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条弧）、连通图（任意两个顶点可达）、生成树（连通图的极小连通子图，包含所有顶点，边数最少）。图的分类：无向图（边无方向）、有向图（边有方向，称为弧）、加权图（边/弧有权重）。（二）图的存储结构（领会+简单应用）自考高频考查邻接矩阵和邻接表，掌握两种存储方式的表示及适用场景：邻接矩阵：用二维数组表示，arr[i][j]=1（顶点i与j相邻），arr[i][j]=0（不相邻）；加权图中存储权重值；优点：查询相邻关系快（O(1)）；缺点：空间复杂度高（O(n²)），适用于顶点少的图。邻接表：用链表表示，每个顶点对应一个链表，存储其相邻的顶点；优点：空间复杂度低（O(n+e)，e为边数）；缺点：查询相邻关系慢（O(n)），适用于顶点多、边少的图。（三）图的遍历（综合应用高频）两种核心遍历方式，需掌握算法思想、代码实现及应用：深度优先搜索（DFS）：从起始顶点出发，优先访问当前顶点的邻接顶点，再递归访问邻接顶点的邻接顶点（类似树的先序遍历）；广度优先搜索（BFS）：从起始顶点出发，先访问当前顶点的所有邻接顶点，再依次访问邻接顶点的邻接顶点（类似树的层序遍历），需借助队列实现。（四）图的高频应用（简单应用+综合应用）最小生成树（Prim算法、Kruskal算法）：连通加权图中，找到一棵权重和最小的生成树；最短路径（Dijkstra算法、Floyd算法）：求两个顶点之间的最短路径，自考高频考查Dijkstra算法；有向无环图（DAG）：无环的有向图，用于拓扑排序（如课程安排问题）。第七章内部排序（重中之重，全题型覆盖）（一）排序的基本概念（识记+领会）定义：将无序的记录序列整理为有序序列（升序或降序）的操作。核心术语：稳定排序（相等元素相对位置不变，如插入排序、归并排序）、不稳定排序（相等元素相对位置可能变化，如快速排序、选择排序）、内部排序（所有数据在内存中完成排序）。考核重点：每种排序算法的思想、步骤、时间复杂度、空间复杂度、稳定性，及算法代码阅读与设计。（二）高频排序算法（必背，简单应用+综合应用）按自考高频度排序，重点掌握前6种，牢记时间/空间复杂度及稳定性：插入排序：思想：将每个元素插入到已排序序列的合适位置（类似整理扑克牌）；时间复杂度：O(n²)（最好O(n)，有序序列）；空间复杂度：O(1)；稳定排序；特点：简单，适用于数据量小、部分有序的场景。交换排序（冒泡排序、快速排序）：冒泡排序：相邻元素比较，逆序则交换，重复直至有序；时间O(n²)，空间O(1)，稳定；快速排序（自考高频）：选基准元素，将序列分为小于、大于基准的两部分，递归排序；时间O(nlog₂n)（最坏O(n²)），空间O(log₂n)，不稳定；是冒泡排序的改进，效率高。选择排序：思想：每次选最小（大）元素，与当前位置交换；时间复杂度：O(n²)；空间复杂度：O(1)；不稳定排序；特点：不额外占用内存，适用于数据量小的场景。归并排序：思想：分治法，将序列分成两半，分别排序后合并；时间复杂度：O(nlog₂n)；空间复杂度：O(n)；稳定排序；特点：效率高，适用于大数据量场景。分配排序（基数排序）：思想：按数字的每一位（个位、十位）分配到对应桶中，依次收集；高频考法：给定序列，求基数排序某一趟后的结果（如序列{55,46,13,94,17,42}，第一趟按个位排序后为{13,42,55,94,46,17}）；时间复杂度：O(d×n)（d为位数）；空间复杂度：O(n)；稳定排序。（三）排序算法对比（简答高频）答：1.时间复杂度：O(nlog₂n)（快速、归并）>O(n²)（插入、冒泡、选择）；2.空间复杂度：归并排序O(n)，快速排序O(log₂n)，其余O(1)；3.稳定性：稳定（插入、冒泡、归并、基数），不稳定（快速、选择）；4.适用场景：大数据量选快速、归并；小数据量选插入、选择；部分有序选插入、冒泡。第八章查找（重中之重，全题型覆盖）（一）查找的基本概念（识记+领会）定义：在数据集合中查找满足指定条件的元素（如按关键字查找）。核心术语：查找成功（找到元素）、查找失败（未找到）、平均查找长度（ASL，查找过程中关键字的平均比较次数，自考高频考查）。（二）高频查找算法（必背，简单应用+综合应用）顺序查找（线性查找）：思想：从第一个元素开始，依次遍历查找；特点：无需排序，简单；时间复杂度O(n)；ASL=(n+1)/2（查找成功）；适用场景：无序序列、数据量小的场景。二分查找（折半查找，自考高频）：思想：仅适用于有序序列，取中间元素比较，缩小查找范围；步骤：初始化low=0，high=n-1；mid=(low+high)/2；比较关键字与mid位置元素，相等则成功；小于则high=mid-1；大于则low=mid+1；重复直至low>high（失败）；时间复杂度：O(log₂n)；ASL=log₂(n+1)-1；特点：效率高，适用于有序序列。树形结构查找（二叉排序树、平衡二叉树）：二叉排序树（BST）：左子树所有元素<根结点<右子树所有元素，查找、插入、删除效率O(log₂n)（最坏O(n)）；平衡二叉树（AVL树）：二叉排序树的改进，左右子树深度差≤1，确保查找效率稳定O(log₂n)。哈希表（散列表，自考高频）：思想：通过哈希函数将关键字映射为存储地址，实现直接访问（O(1)效率）；核心考点：哈希函数的构造方法（解答题高频，5种：直接定址法、数字分析法、平方取中法、折叠法、除留余