简介PDF文档总结了西安电子科技大学《数据结构与算法》课程的期末核心知识点面向西电相关专业学生及期末备考读者系统梳理了高频考点与易混概念。内容涵盖基本概念、线性表、栈与队列、树与二叉树、图、查找算法与排序算法等核心模块重点归纳了数据元素与数据项的区别、算法五大特性、顺序表与单链表的优缺点对比、循环队列队空与队满判定条件、二叉树性质与三种遍历方式、常见查找与排序算法等高频考点并以分点与对比形式呈现便于考前快速回顾与查漏补缺。资源包共1个PDF文件大小2.09MB为文本型知识点总结适合打印或导入平板随时翻阅。目前已有1230人浏览学习是期末冲刺阶段高效省时的复习资料。1. 这份期末总结数据结构与算法七块考点一页拉通期末准备数据结构临时抱佛脚的效率高到离谱前提是手头有一份按题型归纳的知识点总结。这份《西安电子科技大学-数据结构与算法-期末知识点总结》PDF把基本概念、线性表、栈与队列、树与二叉树、图、查找、排序七大块全部浓缩成可直接背诵的表述后面还附了递归分治、贪心、动态规划、回溯的算法分析要点。对本科期末考试来说把这份PDF过两遍再配合教材例题比漫无目的刷题有效得多对准备数据结构408或者考研数据结构复习的人来说它也是一份很好的查漏补缺清单。它的最大价值在于把所有判定条件和复杂度结论直接摆在明面上省掉自己去教材里翻推导的时间考前突击一周完全能覆盖大部分题型。2. 基本概念与线性表先把定义、结构与复杂度钉死期末试卷里选择题第一题基本都出自这一章而且考法非常固定给一句话让你判断是逻辑结构还是物理结构给四个性质让你挑哪个不属于算法的五个特性。这类题不靠理解靠熟记但记也要讲方法下面把最容易被绕的点拆开讲。2.1 基本概念数据元素、数据项与算法的五个性质数据元素是数据的基本单位数据项是数据不可分割的最小单位。这两个定义最容易考填空题注意区分「基本单位」和「最小单位」的措辞题目常把两个词互换来迷惑你。数据结构的逻辑结构是抽象的、与实现无关物理结构也叫存储结构分为顺序映像顺序存储结构和非顺序映像链式存储结构两种。算法的五个性质是正确性、有穷性、确定性、可行性和输入输出。这里常见的坑是有人把「有穷性」写成「有限性」概念上一样但按这份总结的标准表述背最稳妥。正确性指能按设计要求解决具体问题并得到正确结果有穷性指任何指令都只能执行有限次算法必须在有限步内结束确定性指每条指令含义明确不允许有二义性可行性指待执行的操作十分基本应该在有限时间内执行完毕。输入可以包含零个或多个数据输出则有一个或多个。算法设计的要求是另一道常考简答题正确性、可读性、健壮性、高效性时间复杂度、低存储量空间复杂度。注意「特性」和「要求」是两套不同的表述前者是算法本身必须满足的后者是设计算法时追求的目标考填空时别串。2.2 顺序表与链表O(n)的来源和空表判定线性表的一句话定义要背熟线性表是 n 个数据元素的有限序列。线性结构的特点是存在唯一的「第一个」和「最后一个」元素除第一个元素外每个元素都有唯一前驱除最后一个元素外每个元素都有唯一后继。顺序表用数组实现逻辑上相邻的元素在物理位置上也相邻天然支持随机访问。它的结构体定义长这样#define MAXSIZE 100 typedef struct { DataType elem[MAXSIZE]; int length; // 当前表长初始为 0 } SqList;elem是存放元素的数组length记录当前元素个数。表长为 n 时插入和删除的时间复杂度为 O(n)。推导逻辑是在第 i 个位置插入元素需要把第 i 到第 n 个元素全部后移平均移动约 n/2 个元素删除同理平均移动约 (n-1)/2 个元素。所以平均时间复杂度是 O(n)。考场问「为什么顺序表插入删除是 O(n)」答「需要移动元素」不算错但要说清「平均移动表中约一半元素」。单链表的定义是「数据 指针」typedef struct LNode { DataType data; // 数据域 struct LNode *next; // 指针域指向后继结点 } LNode, *LinkList;链表插入删除虽然不用物理移动元素但查找插入位置需要从头遍历时间复杂度同样是 O(n)。注意区分顺序表的 O(n) 花在移动元素上链表的 O(n) 花在查找位置上这一点是论述题的得分关键。空表判定也是高频考点。不带头结点的空表判定为L NULL带头结点的空表判定为L-next NULL因为头结点始终存在L 本身永远不为 NULL。循环单链表为空的判定条件是L-next L自己指向自己。三种判定条件记混是常见翻车点尤其是带头结点那句总有人记成L NULL。2.3 顺序表 vs 单链表考试对比题的标准答法这类对比简答题在西电期末里几乎年年出现答案要分优缺点两头写。顺序存储的优点存储密度大不需要额外指针空间可随机存取取第 i 个元素的时间复杂度是 O(1)。缺点大小固定不利于增删节点存储空间不能充分利用容量难扩充。链式存储的优点易于插入删除可动态申请空间表容量仅受内存空间限制。缺点增加了存储空间的开销每个结点要多存一个指针不可以随机存取元素取第 i 个元素得从头遍历O(n)。我一般建议用表格把两边列出来答题时按「存储密度、访问方式、插入删除代价、空间分配」四个维度展开基本能拿满分。3. 栈、队列与树三组判定条件与五条二叉树性质这一章内容量最大也是期末大题的主产区。栈与队列属于操作受限的线性表问题集中在判空判满条件上树与二叉树的性质题则喜欢考推导。下面把这些判定条件一个个过每个都要能背到条件反射。3.1 栈与队列判空判满的唯一考场版本栈是限定仅在表尾进行插入或删除操作的线性表表尾端叫栈顶表头端叫栈底后进先出LIFO。插入栈顶元素叫入栈删除栈顶元素叫出栈。栈分链栈和顺序栈链栈用不带头结点的单链表实现因为入栈出栈都在表尾操作带头结点反而多一层无用结构顺序栈类似顺序表插入和删除固定于表尾。队列是先进先出FIFO的线性表队尾入队队头出队。重点在循环队列结构体定义如下#define MAXSIZE 100 typedef struct { DataType elem[MAXSIZE]; int front; // 队头位置 int rear; // 队尾位置 } SqQueue;循环队列里最常考的两条判定要背死队空条件为front rear队满条件为(rear 1) % m front。注意这里 m 是队列容量队满时实际只用了 m-1 个存储单元牺牲一个单元来区别队空和队满这是必须说清楚的设计原因。删除元素时先移动队首指针入队时先移动队尾指针写代码的时候顺序别反。3.2 二叉树五条性质从编号推导到叶子计数二叉树性质题在西电期末里喜欢连考两三道选择题五条性质都需要信手拈来。第一条二叉树的第 i 层上至多有 2^(i-1) 个结点i 1。第二条深度为 k 的二叉树至多有 2^k - 1 个结点。这两条容易混记法第 i 层是「一层」的结点数上限所以是 2 的 i-1 次方深度为 k 是「整棵树」的结点数上限等比数列求和得到 2^k - 1。第三条是最常考的性质叶子结点数 n0 与度为 2 的结点数 n2 满足 n0 n2 1。推导要会写设度为 1 的结点数为 n1结点总数 n n0 n1 n2再看分支数除根结点外每个结点都有一个分支指向它所以分支数 n - 1同时分支数等于 2n2 1n1联立两式消掉 n1得到 n0 n2 1。考试时直接写结论能得分但推导步骤写上更保险。第四条n 个结点的完全二叉树深度为 ⌊log2 n⌋ 1。第五条n 个结点的完全二叉树按层次编号后结点 i 的双亲是 ⌊i/2⌋i 1 时为根无双亲结点 i 的左孩子是 2i如果 2i n则无左孩子右孩子是 2i 1如果 2i 1 n则无右孩子。这三组编号关系在做堆排序、完全二叉树存储时反复用到。二叉树的存储有两种顺序存储用数组编号 i 的结点存放在下标 i-1 处适合存储完全二叉树链式存储用二叉链表或三叉链表// 二叉链表 typedef struct BTNode { DataType data; struct BTNode *lchild, *rchild; // 左右孩子指针 } BTNode, *BinTree;含有 n 个结点的二叉链表有 n1 个空链域。计算方法是每个结点有两个指针域共 2n 个指针域n 个结点的二叉树有 n-1 条边非空指针域 n-1 个空链域就是 2n - (n-1) n1。这个结论是线索二叉树概念的引子。3.3 遍历、线索化与哈夫曼树递归视角下的考点先序 DLR根左右、中序 LDR左根右、后序 LRD左右根三种遍历方式的递归定义不难难的是「给定中序先序还原二叉树」这类题。做法是拿先序序列的第一个元素当根在中序序列里找到根的位置左边是左子树右边是右子树递归处理。同理中序后序也能还原但只有先序后序无法唯一确定一棵二叉树这算是一个常被忽略的边界知识点。线索二叉树这块记住一个核心n 个结点的二叉链表有 n1 个空指针利用空指针指向前驱或后继结点叫线索。标志位的规则要背清楚lchild 有左子树时指向左子树ltag 0没有左子树时可以作为前驱线索ltag 1。rchild 同理rtag 0表示右子树rtag 1表示后继线索。提示线索链表中空指针到底指向前驱还是后继取决于当前结点是缺左孩子还是缺右孩子别拿左右搞反。树、森林和二叉树的转换里有一条对应关系值得单独记树的第一个孩子对应二叉树的左孩子树的下一个兄弟对应二叉树的右孩子。遍历关系同样有规律树的先根遍历对应二叉树的先序遍历树的后根遍历对应二叉树的中序遍历森林的先序遍历和中序遍历同样对应二叉树的先序、中序遍历。这个映射关系在「把一棵树转成二叉树后怎么遍历能得到原树的后根序列」这类题里是唯一解题入口。哈夫曼树是叶子结点带权、带权路径长度最小的最优二叉树。构造方法每次取权值最小的两棵树合成新树循环到只剩一棵树。哈夫曼编码是前缀码向左分支记 0、向右分支记 1从根到叶子的路径就是叶子结点的编码。注意哈夫曼树只在叶子结点存放字符内部结点都是合成节点这个特性在选择题里出现过。4. 图与查找从 DFS/BFS 到二分查找的复习主线图这块在西电期末里属于「理论不难但细节多」的部分存储结构、遍历顺序、最小生成树、最短路径四种题型轮着考。查找则稳定出大题尤其二分查找代码和哈希冲突处理年年有位置。这一章把主线拽清楚存储结构决定遍历方式遍历方式决定生成树形态生成树再关联最小生成树算法。4.1 图的存储结构邻接矩阵、邻接表与十字链表怎么选图的基本概念先扫一遍。无向完全图边数为 n(n-1)/2有向完全图弧数为 n(n-1)。顶点 v 的度是和 v 相关联的边的数目有向图里分入度以 v 为头的弧数和出度以 v 为尾的弧数。回路是第一个和最后一个顶点相同的路径简单路径是序列中顶点不重复出现的路径。存储结构里最常用的是邻接表和邻接矩阵。邻接矩阵适合判断两个顶点之间是否有边时间复杂度 O(1)邻接表适合遍历所有边空间上比邻接矩阵省。邻接表结构体定义如下#define MAX_VERTEX 20 typedef struct ArcNode { // 弧结点 int adjvex; // 邻接点下标 struct ArcNode *nextarc; // 指向下一个邻接点 } ArcNode; typedef struct VexNode { // 顶点结点 VertexType data; // 顶点信息 ArcNode *firstarc; // 第一个邻接点指针 } VexNode; typedef struct Graph { VexNode vexs[MAX_VERTEX]; // 顶点向量 int vexnum, arcnum; // 顶点数和弧数 } Graph;十字链表是有向图的另一种链式存储相当于把邻接表和逆邻接表结合起来每个顶点既能找到发出的弧也能找到进入的弧。选择题里问「哪种结构适合对出度和入度都要频繁访问的有向图」答十字链表。无向图则用邻接多重表更合适避免一条边存两次。边多需要存储空间多这是邻接表方案的固有特点不适合稠密图。4.2 最小生成树与最短路径Kruskal 判环与 Floyd 技巧图遍历两种方式必须动手走一遍。深度优先 DFS 从某顶点出发访问顶点后沿未被访问的邻接点继续深入走不动了再退回上一个顶点继续本质是递归加回溯。广度优先 BFS 先访问顶点 v再依次访问 v 的所有未被访问的邻接点然后从这些邻接点出发访问它们的邻接点逐层扩散。每次遍历一个连通图把遍历经过的边和顶点抽出来就得到生成树因此存在 DFS 生成树和 BFS 生成树。最小生成树两个算法要按适用场景选。Kruskal 的核心一句话「不构成环的情况下每次选取最小边」具体做法是先把所有顶点画出来不画边然后把权值最小的边一条条画上去如果构成回路就舍弃这条边直到画完 n-1 条边。判环的做法是看要加边的两个顶点是否已经在同一个连通分量里用并查集实现。Prim 算法则是从一个顶点出发每次把「U 集合到 V-U 集合」最小代价的顶点并入 U边纳入生成树。两种算法的复杂度对比要背算法时间复杂度特点适用场景普里姆算法O(n^2)只与顶点个数 n 有关与边数 e 无关稠密图克鲁斯卡尔算法O(eloge)只与边的数目 e 有关与顶点数 n 无关稀疏图最短路径的 Dijkstra 算法求单源最短路特点是总是按照从小到大的顺序求得各顶点最短路径每次从未求出的顶点里选路径长度最小的 u然后用它去修订其他顶点。Floyd 算法求每对顶点之间的最短路径递推公式为 A(k)(i,j) min(A(k-1)(i,j), A(k-1)(i,k) A(k-1)(k,j))。计算技巧是第 k 行、第 k 列和对角线保持不变其余元素比较 A(i,j) 与 A(i,k) A(k,j)行列如果后者更小就替换。这个「行列」技巧在手工计算时非常实用比硬套矩阵快得多。关键路径问题里 AOE 网是带权的有向无环图顶点表示事件、弧表示活动、权表示活动持续时间。关键路径是从源点到汇点的最长路径工程上代表能影响整体工期的最长活动链这个「最长」的定性把它和普通最短路径区分开。4.3 查找算法二分前必须有序哈希冲突别只会拉链查找表分三类静态查找表只做查找操作动态查找表在查找过程中同时插入或删除元素哈希查找表属于第三类。顺序查找适用于顺序表和链表时间复杂度 O(n)没什么可说的。二分查找效率高但前提是表中元素必须按关键字有序排列这个「有序」先决条件经常被拿来和分块查找对比二分查找代码要能手写// 在有序表 a[0..n-1] 中折半查找关键字 key int BinarySearch(int a[], int n, int key) { int low 0, high n - 1; while (low high) { int mid (low high) / 2; if (a[mid] key) return mid; // 找到返回下标 else if (a[mid] key) low mid 1; // 去右半区 else high mid - 1; // 去左半区 } return -1; // 未找到 }注意循环条件是low high不是low high否则会漏查只剩一个元素的情况。mid 1和mid - 1必须带上 1/-1直接用mid会导致死循环。这三个细节是二分查找手写代码的默认扣分点。分块查找的特点是块内无序、块间有序先在索引表里二分找到所属块再在块内顺序查找。哈希函数构造方法有直接定址法、除留余数法、平方取中法、随机数法、数字分析法冲突解决有开放定址法、拉链法、公共溢出区法。注意哈希的性能取决于填装因子 αα 越大冲突越多但这份总结里没有给具体公式考试考到概念层面的话按教材为主。动态查找表还有二叉排序树左子树所有结点值均小于根右子树均大于根左右子树也都是二叉排序树。5. 排序复杂度与避坑清单一张稳定性表加五条血泪经验排序是期末大题的高发区经常要求写一趟排序后的序列状态或者给初始序列让你判断用的什么排序方法。复杂度表要背牢不是记数字而是要能说清楚为什么快排最坏是 O(n^2)、归并辅助空间为什么是 O(n)。5.1 七类排序复杂度表平均、最坏、辅助空间一次背全排序按类别拆开记。插入类排序包括直接插入、折半插入和希尔排序思想都是「把待排序元素插入到前面已排好序列的适当位置」希尔排序先把序列按增量分成若干子序列做直接插入排序等整体基本有序后再对全体做一次直接插入排序增量序列的选择影响最终性能。交换类排序有冒泡和快排冒泡每相邻两个记录比较关键字大小大的往下沉每遍记录最后一次下沉的位置下一遍只比较到该位置快排的核心是任取一个基准 X把序列分成左边全小于等于 X、右边全大于等于 X 的两部分递归处理。选择类排序有简单选择和堆排序堆排序利用完全二叉树中双亲结点和孩子结点的内在关系选最小元素。归并排序是二路归并基数排序则不做关键字间比较按多关键字从最低位优先LSD或最高位优先MSD逐位排。下面的表直接背期末考到这里就不丢分排序方法稳定性平均时间最坏情况辅助存储直接插入排序稳定O(n^2)O(n^2)O(1)快速排序不稳定O(nlog2n)O(n^2)O(log2n)归并排序稳定O(nlog2n)O(nlog2n)O(n)简单选择排序稳定O(n^2)O(n^2)O(1)堆排序不稳定O(nlog2n)O(nlog2n)O(1)基数排序稳定O(d(nrd))O(d(nrd))O(rd)选型策略是简答题常客。n 较小小于等于 50时用直接插入或直接选择排序记录本身信息量大时用简单选择排序更好因为插入排序移动操作更多文件的初始状态基本有序时选直接插入或冒泡排序n 较大时必须用 O(nlog2n) 级别的排序快排算基于比较的内部排序里公认最好的。另外任何借助关键字的比较排序算法理论上至少需要 O(nlog2n) 的时间这个结论可以拿二叉树描述比较判定过程来理解期末考到照写即可。5.2 五条高频踩坑记录现象、原因、解决第一条循环队列判空判满写反。现象是题目给一个循环队列问队空条件答成(rear1)%m front给队满条件答成front rear。原因是最开始记了公式但没理解设计目的。解决从「为什么牺牲一个单元」来记——如果不空一个位置队空和队满时 front 和 rear 都相等无法区分牺牲一个单元后存满时 rear 指向最后一个空位(rear1)%m才等于 front。理解了设计目的公式就不会串。第二条叶子结点 n0 n2 1 的推导写不出来。现象是选择判断会做简答题让证明就卡住。原因是只背结论没走推导过程。解决按分支数建立方程结点总数 n n0 n1 n2分支数 n-1 2n2 n1两式相减消 n1 得 n0 n2 1。考场上把这两行写出来推导分就拿到了。第三条快速排序最坏情况为什么是 O(n^2) 说不清。现象是复杂度表能背追问一句就愣住。原因是把表上的数字当结论记没理解「最坏」发生在哪。解决快排每次划分如果基准恰好是最大或最小值划分后一边为空、另一边是 n-1 个元素递归深度变成 n每层划分代价 O(n)总复杂度 O(n^2)。所以快排最坏发生在序列已经有序或基本有序的时候可以顺手答「三数取中」能缓解但不在这份总结的范围内不展开。第四条DFS 生成树和 BFS 生成树形态搞混。现象是让画出从顶点 A 出发的深度优先生成树画出了逐层扩散的样子。原因是把两种遍历的访问顺序记反了。解决DFS 是「一条路走到黑再回头」生成树的边是沿纵深方向延伸的BFS 是「逐层推进」生成树的边是沿层次方向铺开的。画图题只要先把访问序列写出来再按序列连边基本不会错。第五条排序稳定性判断题总有一两个记反尤其是堆排序和简单选择排序。现象是问堆排序稳不稳定答稳定问快速排序答稳定。原因是稳定性这个概念没有和算法过程绑定。解决稳定性看「相等元素的相对位置会不会变」。堆排序涉及父子交换相等元素可能被换走快排的基准划分也会改变相等元素顺序冒泡、插入、归并都是相邻或局部的两两比较不会跨位置交换这几个按「交换跨越位置就会不稳定」的口诀记。6. 算法设计技术递归、贪心、动态规划、回溯的快速识别期末最后一道算法题经常给一个具体问题让判断用什么算法设计技术或者直接给递归方程让求解复杂度。这章不需要背代码但需要一套快速识别套路。递归方程按递减方式分两类减法形式 n-b 的结果是 T(n) O(a^n)指数爆炸除法形式 n/b 的结果按 a 和 b^p 的关系分三种。设齐次解为 n^pp logb a如果 D(n) n则 a b 时 T(n) O(n^p)a b 时 T(n) O(n^p log n)a b 时 T(n) O(n)。原总结里给了三个实例T(n) 4T(n/2) n 得 O(n^2)加 n^2 得 O(n^2 log n)加 n^3 得 O(n^3)这种给方程求阶的题照套路套就行。汉诺塔的递归方程 T(n) 2T(n-1) 1 解出来是 O(2^n)属于减法递归的典型代表。贪心算法只在具有贪心选择性质时才能保证整体最优。识别要点活动安排问题、最优装载问题用贪心能拿到最优解旅行商问题、0-1 背包问题、单源最短路径这类贪心只能求近似或者需要换成别的方法。区分手段看是否存在「局部最优能推出全局最优」的结构存在就用贪心不存在就转动态规划。动态规划的两个基本要素是最优子结构和重叠子问题最短路径问题、凸多边形三角剖分都符合。与贪心的区别动规的子问题不是独立而是重叠的用自底向上的方式填表这也是它比暴力枚举高效的原因。回溯法实为深度优先搜索的通用算法可递归实现也可迭代实现。三类题型的复杂度级分别是求排列 O(n!)求子集 O(2^n)求路径 O(k^n)。做识别题时看到「所有解」「组合」「排列」字眼优先想到回溯看到「最优解」「极值」再结合重叠子问题想到动规。分支限界法虽然和回溯都在解空间树上搜索但回溯是深度优先找所有解分支限界是广度优先或最小耗费优先找一个最优解靠评价函数的界函数剪去不可能产生最佳解的子树。从那以后我每轮复习都强制把这张识别表过一遍先看问题是求数量还是求最优是排列组合还是路径选择再决定往回溯、贪心还是动规方向走。这份 PDF 里的表述已经足够支撑考前一周的突击配合教材例题把每一章的判定条件默写一遍期末基本稳了。希望这篇拆解能帮你把手里的资源用到刀刃上。本文还有配套的精品资源点击获取