自考13003《数据结构与算法》背诵版速记清单（含高频大题）

自考13003《数据结构与算法》背诵版速记清单（含高频大题）说明：按教材章节排序，核心概念（单选+填空）直接记，高频大题标★（简答/算法重点），适配所有自考题型，背完无需额外翻书，重点标注优先级。第一章绪论（基础考点，单选+填空+简答）一、核心概念（必记）数据结构三要素：逻辑结构、存储结构、数据运算（填空高频）。逻辑结构：线性（一对一：线性表、栈、队列）、非线性（一对多：树；多对多：图）。存储结构（4种）：顺序、链式、索引、散列（哈希）（单选高频）。算法5个特性：有穷性、确定性、可行性、输入（可选）、输出（必选）（简答高频）。时间复杂度：用大O表示法，忽略常数、低次项、系数；常见复杂度排序：O(1)＜O(log₂n)＜O(n)＜O(nlog₂n)＜O(n²)＜O(2ⁿ)（单选+算法阅读高频）。算法6大设计策略：递推、迭代、递归、贪心、分治、动态规划（识记）。二、高频大题（★简答）★简述算法的5个特性：有穷性（有限步骤终止）、确定性（指令含义明确）、可行性（指令可执行）、输入（0个或多个）、输出（至少1个）。★简述数据结构三要素及逻辑结构与存储结构的关系：三要素为逻辑结构、存储结构、数据运算；逻辑结构是抽象关系（与存储无关），存储结构是其计算机实现，存储结构决定运算效率，二者相互依赖。第二章线性表（重中之重，全题型）一、核心概念（必记）线性表：n个元素的有限序列，一对一关系，分有序表、无序表。顺序表：连续存储，随机访问（O(1)），插入/删除需移动元素（O(n)）（单选+算法高频）。单链表：不连续存储，结点含数据域+指针域；带头结点判空：head->next=NULL（算法高频）。循环链表：表尾指针指向头结点，判空：head->next=head；双向链表：双指针域（前驱+后继）。二、高频大题（★简答+算法）★简述顺序表与链表的对比及适用场景（简答高频）：存储：顺序连续，链表不连续；访问：顺序随机，链表顺序；效率：顺序查询/取值快（O(1)），插入/删除慢（O(n)）；链表相反；适用：顺序表适用于元素固定、查询频繁；链表适用于元素动态、插入/删除频繁。★算法重点：单链表的初始化、插入、删除、遍历（算法设计/阅读高频，记核心逻辑）。第三章栈和队列（高频考点，全题型）一、核心概念（必记）栈：先进后出（LIFO），仅栈顶插入（入栈）、删除（出栈）；顺序栈判空：top=-1，栈满：top=容量-1。队列：先进先出（FIFO），队尾入队、队头出队；循环队列（重点）：判空：front==rear；判满：(rear+1)%容量==front；队列长度：(rear-front+容量)%容量（填空高频）。二、高频大题（★算法+应用）★栈的核心应用（综合应用高频）：括号匹配、中缀转后缀表达式、后缀表达式求值。★算法重点：循环队列的入队、出队操作（算法阅读/设计高频）。第四章数组、广义表和串（基础考点，单选+填空+解答）一、核心概念（必记）数组存储：行优先（C语言）、列优先；地址计算（解答题高频）：loc(aij)=首地址+(i×列数+j)×元素字节数。串：字符序列，子串（连续）、主串；KMP算法（识记思想：避免重复比较）。广义表：元素可为原子或广义表（仅识记）。二、高频大题（★解答）★已知二维数组首地址、元素字节数，计算指定元素地址（如A[2][5]，首地址1000，列数6，字节数4，计算过程记公式）。第五章树与二叉树（重中之重，全题型）一、核心概念（必记）二叉树性质（填空+单选高频）：性质1：第k层最多2^(k-1)个结点；性质2：深度k最多2ᵏ-1个结点；性质3：叶子结点数=度为2的结点数+1（必考）。特殊二叉树：满二叉树（每层满）、完全二叉树（最后一层左连续）。二叉树遍历（核心）：先序（根→左→右）、中序（左→根→右）、后序（左→右→根）（算法+填空高频）。哈夫曼树：WPL最小的二叉树；哈夫曼编码：前缀编码（数据压缩）。二、高频大题（★简答+算法）★已知两种遍历序列（如中序+先序），求第三种遍历序列（解答/算法高频）。★算法重点：二叉树的遍历（递归/非递归实现，算法设计/阅读高频）。★简述二叉树的3种遍历方式及步骤（简答）。第六章图结构（高频考点，单选+填空+解答+算法）一、核心概念（必记）图的存储（重点）：邻接矩阵（O(n²)，顶点少）、邻接表（O(n+e)，顶点多）（单选+解答高频）。图的遍历：深度优先（DFS，类似先序）、广度优先（BFS，类似层序，需队列）（算法高频）。核心术语：完全图、连通图、生成树、入度/出度（填空高频）。二、高频大题（★算法+应用）★算法重点：DFS、BFS遍历算法（算法阅读高频）。★高频应用：最小生成树（Prim、Kruskal）、最短路径（Dijkstra，简答+算法高频）、拓扑排序。第七章内部排序（重中之重，全题型）一、核心概念（必记）稳定排序：插入、冒泡、归并、基数；不稳定排序：快速、选择（单选高频）。高频排序算法（必记时间/空间/稳定性，填空+简答+算法高频）：插入排序：O(n²)，O(1)，稳定；冒泡排序：O(n²)，O(1)，稳定；快速排序：O(nlog₂n)，O(log₂n)，不稳定（重点）；归并排序：O(nlog₂n)，O(n)，稳定；基数排序：O(d×n)，O(n)，稳定。二、高频大题（★简答+算法）★简述常用排序算法的对比（简答高频）：按时间复杂度、空间复杂度、稳定性、适用场景区分。★算法重点：冒泡排序、快速排序、插入排序（算法设计高频，记类C代码核心逻辑）。第八章查找（重中之重，全题型）一、核心概念（必记）二分查找（重点）：仅适用于有序序列，O(log₂n)（算法+单选高频）。哈希表：哈希函数映射地址，O(1)效率；哈希函数构造方法（5种，解答高频）：直接定址、数字分析、平方取中、折叠、除留余数。冲突处理：开放定址法、链地址法（填空高频）。顺序查找：O(n)；分块查找：O(√n)（识记）。二、高频大题（★解答+算法）★列出5种构造哈希函数的方法（解答题高频，直接背名称）。★算法重点：二分查找算法（算法设计高频，记步骤+代码）。补充：自考必背高频大题汇总（直接背，提分关键）简述算法的5个