数据结构考研重点知识总结

数据结构考研重点知识总结数据结构作为计算机科学与技术领域的核心基础课程，在研究生入学考试中占据着举足轻重的地位。它不仅是算法设计与分析的基石，也与操作系统、数据库等多门后续课程紧密相关。本文旨在梳理数据结构考研的重点知识，帮助考生系统复习，巩固核心概念与算法，提升解题能力。一、绪论1.1数据结构基本概念数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包含数据的逻辑结构、存储结构以及数据的运算三要素。理解数据的逻辑结构（集合、线性、树形、图状）与物理结构（顺序、链式、索引、散列）的区别与联系，是学好后续内容的基础。1.2算法及其评价算法是对特定问题求解步骤的一种描述，它具有有穷性、确定性、可行性、输入和输出五个基本特性。评价一个算法的优劣，主要从时间复杂度和空间复杂度两个维度进行。时间复杂度分析的关键在于找出语句的执行次数与问题规模之间的函数关系，通常关注最坏情况下的时间复杂度。空间复杂度则关注算法在执行过程中临时占用存储空间的大小。掌握常见的时间复杂度量级（如O(1)、O(logn)、O(n)、O(nlogn)、O(n²)等）及其比较。二、线性表2.1线性表的定义与基本操作线性表是具有相同数据类型的n个数据元素的有限序列，其特点是元素之间存在一对一的线性关系。熟练掌握线性表的初始化、插入、删除、查找、遍历等基本操作的逻辑实现。2.2顺序表顺序表是用一组地址连续的存储单元依次存储线性表中的数据元素。其优点是可以随机存取，缺点是插入和删除操作需要移动大量元素。重点掌握顺序表插入和删除操作中元素的移动策略，以及由此带来的时间复杂度分析。2.3链表链表是通过指针或引用将节点连接起来实现的线性表，节点包含数据域和指针域。常见的链表形式有单链表、双链表、循环链表和静态链表。*单链表：每个节点只有一个指向下一个节点的指针。重点掌握单链表的建立（头插法、尾插法）、插入、删除、查找操作，以及如何判断链表是否有环、寻找环入口、合并两个有序链表等经典问题。*双链表：每个节点有两个指针，分别指向前驱和后继节点，使得双向遍历和某些操作（如删除前驱节点）更为方便。*循环链表：首尾相接的链表，可以从表中任意节点出发遍历整个链表。*静态链表：借助数组来模拟链表，数组元素包含数据域和游标（模拟指针），适用于不支持动态内存分配的环境。三、栈与队列3.1栈栈是一种限定仅在表尾进行插入和删除操作的线性表，遵循“先进后出”（LIFO）原则。*基本操作：入栈（push）、出栈（pop）、取栈顶元素（top）、判空（empty）等。*存储实现：顺序栈（利用数组实现，注意栈满和栈空的判断，以及可能的共享栈技术）和链栈（利用单链表实现，通常以头节点作为栈顶）。*应用：表达式求值（中缀转后缀、后缀表达式计算）、括号匹配、函数调用与递归实现、迷宫求解等。3.2队列队列是一种限定仅在表头进行删除操作、在表尾进行插入操作的线性表，遵循“先进先出”（FIFO）原则。*基本操作：入队（enqueue）、出队（dequeue）、取队头元素（front）、判空（empty）等。*存储实现：顺序队列（利用数组实现，关键问题是假溢出，通常通过循环队列来解决。循环队列的判空和判满条件是重点，常见的有牺牲一个单元或使用计数器两种方法）和链队列（利用单链表实现，通常设置队头和队尾指针）。*应用：缓冲处理、层次遍历（如二叉树的层序遍历）、生产者-消费者模型等。*特殊队列：双端队列（允许在两端进行插入和删除）、优先队列（元素的出队顺序由优先级决定，通常用堆实现）。四、字符串4.1字符串的定义与操作字符串是由零个或多个字符组成的有限序列。掌握字符串的比较、连接、求子串等基本操作。4.2模式匹配算法模式匹配是判断一个子串（模式串）是否存在于主串中的过程。*朴素模式匹配算法：简单直观，但效率不高，最坏时间复杂度为O(n*m)。*KMP算法：通过预处理模式串，计算出部分匹配表（next数组），从而在匹配过程中避免主串指针的回溯，将时间复杂度优化到O(n+m)。重点理解KMP算法的基本思想，以及next数组的定义、求解方法及其优化（nextval数组）。五、树与二叉树5.1树的基本概念理解树的定义、节点、度、深度、高度、路径、森林等基本术语。掌握树的性质，如树中节点数等于所有节点度数之和加1。5.2二叉树二叉树是每个节点最多有两棵子树的有序树，子树有左右之分。*二叉树的性质：重点掌握二叉树的五大性质，如第i层最多有2^(i-1)个节点；深度为k的二叉树最多有2^k-1个节点；对于任何一棵二叉树，若叶子节点数为n0，度为2的节点数为n2，则n0=n2+1等。*特殊二叉树：满二叉树（每一层都是满的）、完全二叉树（除最后一层外均满，最后一层节点集中在左侧）。完全二叉树具有良好的性质，适合顺序存储，其节点的父、左孩子、右孩子节点的索引关系是重点。*二叉树的存储结构：顺序存储（适用于完全二叉树）和链式存储（二叉链表：左孩子指针、右孩子指针；三叉链表：增加父指针）。5.3二叉树的遍历遍历是二叉树最基本的操作，目的是按某种次序访问树中的所有节点，且每个节点仅被访问一次。*深度优先遍历：*前序遍历（根左右）*中序遍历（左根右）*后序遍历（左右根）掌握这三种遍历的递归实现和非递归实现（通常借助栈）。*广度优先遍历（层序遍历）：从根节点开始，逐层访问各节点，通常借助队列实现。*由遍历序列构造二叉树：已知前序和中序、中序和后序遍历序列，可以唯一确定一棵二叉树，掌握其构造方法。5.4线索二叉树线索二叉树是为了利用二叉树中大量的空指针域，将其改为指向节点前驱或后继的线索，从而提高遍历效率。理解线索化的过程，以及线索二叉树的前序、中序、后序线索化和遍历方法。5.5树和森林*树的存储结构：双亲表示法、孩子表示法、孩子兄弟表示法（重点，可将树和森林转换为二叉树）。*树和森林的遍历：树的先根遍历、后根遍历；森林的先序遍历、中序遍历。理解树/森林遍历与二叉树遍历的对应关系。*树、森林与二叉树的转换：重点掌握树转换为二叉树、森林转换为二叉树的方法，以及二叉树还原为树或森林的方法。5.6哈夫曼树与哈夫曼编码哈夫曼树（最优二叉树）是带权路径长度（WPL）最小的二叉树。哈夫曼编码是基于哈夫曼树的一种前缀编码，能有效实现数据压缩。掌握哈夫曼树的构造算法（哈夫曼算法）和哈夫曼编码的生成方法。六、图6.1图的基本概念理解图的定义、顶点、边、弧、度（入度、出度）、路径、回路、连通图、强连通图、生成树、网等基本术语。6.2图的存储结构*邻接矩阵：用一个二维数组来表示顶点之间的邻接关系，适用于稠密图。优点是查找方便，缺点是空间复杂度高。*邻接表：对每个顶点建立一个单链表，存储其所有邻接顶点，适用于稀疏图。优点是节省空间，缺点是查找某条边是否存在不如邻接矩阵方便。*十字链表：针对有向图的一种存储结构，能同时方便地找到以某顶点为尾和为头的弧。*邻接多重表：针对无向图的一种存储结构，解决了邻接表中每条边被存储两次的问题。6.3图的遍历*深度优先搜索（DFS）：类似于树的先序遍历，尽可能深地搜索图的分支，使用栈（或递归）实现。*广度优先搜索（BFS）：类似于树的层序遍历，逐层访问图的节点，使用队列实现。掌握DFS和BFS的实现过程，并能根据遍历序列还原图的可能结构，以及求解连通分量、判断图是否连通等问题。6.4最小生成树（MST）对于带权连通图，最小生成树是所有生成树中权值之和最小的生成树。*Prim算法：从一个顶点开始，逐步添加边以形成最小生成树，适用于稠密图。*Kruskal算法：按边的权值从小到大排序，依次添加不构成回路的边，适用于稀疏图，通常借助并查集（DisjointSetUnion,DSU）来判断是否构成回路。理解两种算法的基本思想、步骤和时间复杂度，并能手动模拟求解过程。6.5最短路径*Dijkstra算法：求解单源最短路径问题，即从一个顶点到其他所有顶点的最短路径，要求图中边的权值非负。掌握其贪心思想和实现步骤。*Floyd算法：求解每对顶点之间的最短路径问题，可以处理带负权边的图，但不能处理带负权回路的图。其核心思想是动态规划。*Bellman-Ford算法：也可用于单源最短路径，能处理含负权边的图，并能检测是否存在从源点可达的负权回路。6.6有向无环图（DAG）及其应用*拓扑排序：对DAG的顶点进行线性排序，使得对于任何有向边u->v，u都排在v之前。掌握拓扑排序的两种实现方法（Kahn算法：基于入度；DFS-based算法：基于后序遍历逆序），并能判断一个图是否为DAG。*关键路径：在带权DAG中，从源点到汇点的最长路径称为关键路径，其上的活动称为关键活动。掌握关键路径的求解方法，包括事件的最早发生时间、最迟发生时间，活动的最早开始时间、最迟开始时间、松弛时间的计算。七、查找7.1查找的基本概念理解查找、查找表、关键字、平均查找长度（ASL）等概念。7.2顺序查找与折半查找*顺序查找：从表的一端开始逐个比较。对顺序表和链表均适用，ASL较高，为O(n)。*折半查找（二分查找）：仅适用于有序的顺序表。通过不断将查找区间折半，ASL为O(logn)。重点掌握折半查找的过程、递归与非递归实现，以及查找成功和失败的ASL计算。7.3分块查找（索引顺序查找）结合了顺序查找和折半查找的优点，将表分成若干块，块内无序，块间有序。先对索引表进行查找（可折半），再对块内进行顺序查找。7.4树表查找*二叉排序树（BST）：左子树所有节点值小于根节点值，右子树所有节点值大于根节点值，左右子树也分别是BST。掌握BST的插入、删除、查找操作，以及其查找效率分析（与树的形态有关）。*平衡二叉树（AVL树）：左右子树的高度差（平衡因子）的绝对值不超过1的BST。重点掌握AVL树在插入和删除操作后如何通过旋转（LL、RR、LR、RL）来维持平衡。*B树与B+树：多路平衡查找树，主要用于文件系统和数据库索引。理解B树的定义（阶、节点结构）、插入（可能导致分裂）和删除（可能导致合并或借位）操作的基本原理。了解B+树的特点（所有关键字在叶子节点，形成有序链表，便于范围查询）。7.5散列表（哈希表）根据关键字直接计算出存储地址的数据结构，期望达到O(1)的查找效率。*哈希函数的构造方法：直接定址法、数字分析法、平方取中法、折叠法、除留余数法等。*处理冲突的方法：开放定址法（线性探测、二次探测、伪随机探测）、链地址法（拉链法）、再哈希法、建立公共溢出区。*哈希表的查找及其效率分析：影响因素包括哈希函数、处理冲突的方法和装填因子。八、排序8.1排序的基本概念理解排序的定义、稳定性（相同关键字元素的相对顺序是否保持）、内排序与外排序。8.2插入排序*直接插入排序：将待排序元素插入到已排好序的子序列中。稳定，时间复杂度O(n²)，空间复杂度O(1)。*折半插入排序：在直接插入排序的基础上，使用折半查找确定插入位置，减少比较次数，但元素移动次数不变。*希尔排序（缩小增量排序）：按不同增量对序列进行分组插入排序。不稳定，平均时间复杂度O(n^1.3)，空间复杂度O(1)。8.3交换排序*冒泡排序：重复比较相邻元素，将大的元素“冒泡”到末尾。稳定，时间复杂度O(n²)，空间复杂度O(1)。*快速排序：基于分治思想，选择一个基准元素，将序列分为两部分，左边都小于基准，右边都大于基准，然后递归排序。不稳定，平均时间复杂度O(nlogn)，最坏O(n²)，空间复杂度O(logn)~O(n)（递归栈）。重点掌握其划分过程（如Hoare法、Lomuto法）。8.4选择排序*简单选择排序：每次从待排序序列中选择最小（或最大）元素放到已排序序列的末尾。不稳定，时间复杂度O(n²)，空间复杂度O(1)。*堆排序：利用堆（大根堆或小根堆）这种数据结构进行排序。将待排序序列构造成堆，然后依次取出堆顶元素（最大或最小）并调整堆。不稳定，时间复杂度O(nlogn)，空间复杂度O(1)。重点掌握堆的构建、调整（向下调整、向上调整）过程。8.5归并排序基于分治思想，将序列分成两半分别排序，然后将两个有序子序列合并。稳定，时间复杂度O(nlogn)，空间复杂度O(n)（外部归并排序可优化）。重点掌握二路归并的合并过程，以及递归和非递归实现。8.6基数排序按照关键字的各位数字（或字符）依次进行排序，如LSD（最低位优先）和MSD（最高位优先）。稳定，时间复杂度O(d*(n+r))，其中d是关键字位数，r是