简介：这份《西安电子科技大学-数据结构与算法-期末知识点总结》面向高校计算机及相关专业学生，尤其适合正在备考数据结构期末、需要系统梳理知识框架的读者。内容围绕基本概念、线性表、栈与队列、树与二叉树、图、查找与排序算法展开，对顺序表与单链表的存储结构对比、循环队列的队空队满判定、二叉树性质与遍历方式等高频考点均有归纳，可作为复习提纲与考前速查使用。资源包共1个PDF文件，约2.09MB，页面结构清晰，便于打印或平板阅读。目前已有1230人学习下载，说明其在同类复习资料中具有一定参考价值。读者可借助这份总结快速定位薄弱章节，配合教材与习题查漏补缺，提升期末复习效率。

1. 数据结构与算法期末复习：从「背了忘」到「考场能写」的 6 个关键动作

期末周的图书馆里，最常见的场景不是没人复习，而是复习方式本身出了问题：把《数据结构与算法》的知识点总结 PDF 从头翻到尾，链表、栈、队列、树、图、排序、查找全都「看过」，合上书却写不出一道完整的算法题。这份「西安电子科技大学-数据结构与算法-期末知识点总结.pdf」之所以被反复搜索，本质上是因为大家需要的不是又一份目录，而是一条能把零散知识点串成可答题能力的路径。数据结构与算法这门课，期末考的从来不是记忆力，而是你能不能在有限时间里判断该用哪种结构、写出关键代码、算对复杂度。这篇笔记面向正在准备期末、考研 408 数据结构，或者想把 C 语言版知识点重新捡起来的人，按「先立框架、再攻高频、最后避坑」的顺序，把复习动作拆到可以照着执行。

2. 先搭骨架：数据结构与算法知识点归纳的正确打开方式

2.1 为什么按「逻辑结构 + 存储结构 + 操作」三列归纳最省时间

很多人复习数据结构时习惯按章节顺序抄笔记，线性表、栈、队列、串、树、图一路抄下去，抄完发现脑子里还是一团。问题在于章节顺序是教材的叙述顺序，不是考点的组织顺序。真正高效的归纳方式，是给每个数据结构建一张三列表：逻辑结构是什么、存储结构怎么实现、核心操作有哪些。比如「栈」这一行，逻辑结构是受限线性表，存储结构可以是顺序栈或链栈，核心操作是入栈、出栈、取栈顶、判空。这样归纳的好处是，考试里一旦出现「用两个栈实现队列」这类题，你能立刻定位到操作层面，而不是从头回忆栈的定义。

我一般会建议用一张 A3 纸横过来，左边写结构名，中间写存储方式，右边写操作和时间复杂度。线性表、栈、队列、串、树、二叉树、图、查找结构、排序算法各占一行。这张表填完，你对整门课的覆盖范围就有了全局感，后面再往里填细节，不会出现「复习到图的时候忘了线性表」的情况。数据结构学习最怕的就是碎片化，先有骨架再填肉，效率差好几倍。

2.2 用一张表把线性表、树、图的操作复杂度钉死

复杂度是期末必考、也是很多人最容易记混的部分。与其死记，不如按操作类型横向对比。下面这张表是我复习时反复用的版本，覆盖了最高频的几类结构：

这张表的关键不是背，而是理解每一格背后的原因。比如单链表插入为什么是 O(1)，前提是「已知前驱节点」；如果只给了值要你先找位置，那查找本身就是 O(n)。考试里经常在这种前提条件上设陷阱，把「已知前驱」偷偷去掉，很多人就掉进去了。

2.3 复习顺序：先线性结构，再树，最后图与排序

知识点归纳做完之后，复习顺序也有讲究。我的建议是先攻线性表、栈、队列、串，这部分逻辑直观、代码短，容易建立信心；然后进树和二叉树，重点是遍历和递归思维；最后才是图和排序，因为图算法依赖队列和栈，排序依赖数组操作，前面的基础不牢后面会很痛苦。每复习完一个模块，立刻做三件事：手写核心代码、画一遍操作示意图、算一遍复杂度。这三件事做完，才算真正过了一遍。

3. 高频考点逐个拆：链表、KMP、树遍历、排序算法怎么落到笔头

3.1 单链表反转与合并：手写代码的三个边界

链表是期末代码题的重灾区，其中反转和合并出现频率最高。很多人觉得自己会，一上手就发现指针指丢了。下面是我复习时反复默写的单链表反转模板：

// 单链表节点定义 typedef struct ListNode { int val; struct ListNode *next; } ListNode; // 反转单链表，返回新头节点 ListNode* reverseList(ListNode* head) { ListNode *prev = NULL; // 前驱指针，初始为空 ListNode *curr = head; // 当前指针，从头开始 while (curr != NULL) { ListNode *nextTemp = curr->next; // 先保存下一个节点 curr->next = prev; // 当前节点指向前驱 prev = curr; // 前驱后移 curr = nextTemp; // 当前后移 } return prev; // prev 最终指向原链表尾，即新头 }

这段代码的逻辑核心是「先存后断再移」：保存 next、断开当前指针、移动 prev 和 curr。参数上唯一需要注意的是循环终止条件是 curr 为 NULL，返回的是 prev 而不是 curr。三个边界必须检查：空链表直接返回 NULL、只有一个节点时循环走一次就结束、反转后原头节点的 next 必须为 NULL。我见过太多人写完忘了最后一步，导致链表成环，考试直接扣分。

合并两个有序链表的思路类似，用哑节点（dummy node）可以省掉头节点特判：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy; // 栈上哑节点 ListNode *tail = &dummy; // 尾指针 while (l1 && l2) { if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = l1 ? l1 : l2; // 接上剩余部分 return dummy.next; }

哑节点的作用是让「第一个节点」和「后续节点」的处理逻辑统一，不用单独判断 tail 是否为空。参数上注意比较用<=保证稳定性，剩余部分直接接上不用循环。

3.2 KMP 算法：next 数组到底怎么手算不翻车

KMP 是字符串章节的必考算法，也是很多人复习时的玄学重灾区。核心就一句话：next 数组记录的是「模式串当前位置之前的最长相等前后缀长度」。手算的时候不要背公式，按下面步骤走：

第一步，next[0] 固定为 -1（或 0，取决于教材约定，西电教材常用 -1 版本）。第二步，从第二个字符开始，看它前面子串的最长相等前后缀。第三步，把这个长度填到 next 数组的对应位置。以模式串ababaa为例：

next[3]=1 是因为aba的最长相等前后缀是a，长度 1；next[4]=2 是因为abab的最长相等前后缀是ab，长度 2。手算时容易错的地方是把「前缀」和「后缀」搞反，或者把整个子串本身算进去。记住前后缀不能是子串本身，长度必须小于当前子串长度。

匹配阶段的代码模板：

// 计算 next 数组，模式串 pat，长度 m void getNext(char *pat, int m, int *next) { next[0] = -1; int i = 0, j = -1; while (i < m - 1) { if (j == -1 || pat[i] == pat[j]) { i++; j++; next[i] = j; // 记录最长相等前后缀长度 } else { j = next[j]; // 回退 } } } // KMP 匹配，返回首次出现下标，未找到返回 -1 int kmp(char *text, char *pat, int n, int m) { int next[m]; getNext(pat, m, next); int i = 0, j = 0; while (i < n && j < m) { if (j == -1 || text[i] == pat[j]) { i++; j++; } else { j = next[j]; // 模式串右滑 } } return j == m ? i - m : -1; }

参数说明：next 数组长度等于模式串长度，j 回退到 next[j] 而不是 next[j-1]，这是最容易写错的地方。KMP 的时间复杂度是 O(n+m)，比朴素匹配的 O(n*m) 快在「主串指针不回退」。

3.3 二叉树三种遍历：递归与非递归的转换套路

二叉树遍历是树章节的基础，递归写法几乎人人会，但期末经常要求写非递归版本。三种遍历的递归模板高度统一，区别只在访问根节点的时机：

// 中序遍历递归版 void inorder(TreeNode *root) { if (root == NULL) return; inorder(root->left); // 左 visit(root); // 根 inorder(root->right); // 右 }

非递归版本用栈模拟，中序的写法是「一路向左压栈，弹栈时访问，再转向右子树」：

void inorderIter(TreeNode *root) { TreeNode *stack[100]; // 假设树不超过 100 节点 int top = -1; TreeNode *curr = root; while (curr != NULL || top != -1) { while (curr != NULL) { // 一路向左 stack[++top] = curr; curr = curr->left; } curr = stack[top--]; // 弹栈 visit(curr); // 访问 curr = curr->right; // 转向右子树 } }

前序和后序的非递归只需调整访问时机和压栈顺序。后序稍麻烦，常见做法是用两个栈或者记录上次访问节点。考试里如果只要求写一种非递归，优先准备中序，因为它的逻辑最清晰，也最常考。

3.4 排序算法对比：冒泡、快排、归并、堆排的考场选择

排序是期末必考，选择题考复杂度稳定性，代码题考快排和归并。先把对比表钉死：

快排的核心是 partition，代码如下：

// 快排划分，返回基准最终位置 int partition(int *a, int low, int high) { int pivot = a[low]; // 取第一个元素为基准 while (low < high) { while (low < high && a[high] >= pivot) high--; a[low] = a[high]; // 右边小的移到左边 while (low < high && a[low] <= pivot) low++; a[high] = a[low]; // 左边大的移到右边 } a[low] = pivot; // 基准归位 return low; } void quickSort(int *a, int low, int high) { if (low < high) { int p = partition(a, low, high); quickSort(a, low, p - 1); quickSort(a, p + 1, high); } }

参数说明：pivot 取第一个元素时，必须先移动 high 指针再移动 low 指针，顺序反了会出错。快排最坏情况出现在数组已经有序时，退化成 O(n²)，这也是为什么工程实现里常用随机基准或三数取中。归并排序的 merge 操作是重点，两个有序子数组合并时用辅助数组暂存，再拷回原数组，空间换稳定。

4. 复杂度分析：O 和 Θ 什么时候用哪个，别再混着写

4.1 大 O、大 Θ、大 Ω 的区别与考场判断

复杂度分析是选择题高频考点，尤其是「什么时候用 O 什么时候用 Θ」这个问题。简单说：大 O 表示上界，大 Ω 表示下界，大 Θ 表示紧确界。如果一个问题的最坏情况和最好情况同阶，就可以用 Θ；如果只关心最坏情况的上界，用 O。比如快排平均时间是 Θ(n log n)，最坏时间是 O(n²)，这里用 O 是因为最坏情况只是一个上界估计，实际可能不到。考试里如果题目问「该算法的时间复杂度」，默认答最坏情况的大 O；如果问「紧确界」，才用 Θ。

4.2 递归式求解：主定理的三种情况怎么套

递归算法的时间复杂度常用递归式表示，比如归并排序是 T(n) = 2T(n/2) + O(n)。主定理（Master Theorem）是求解这类递归式的标准工具，形式是 T(n) = aT(n/b) + f(n)，比较 f(n) 和 n^(log_b a) 的大小：

• 情况一：f(n) = O(n^(log_b a - ε))，则 T(n) = Θ(n^(log_b a))
• 情况二：f(n) = Θ(n^(log_b a))，则 T(n) = Θ(n^(log_b a) * log n)
• 情况三：f(n) = Ω(n^(log_b a + ε)) 且满足正则条件，则 T(n) = Θ(f(n))

归并排序中 a=2, b=2, log_b a = 1，f(n) = O(n) = Θ(n^1)，属于情况二，所以 T(n) = Θ(n log n)。二分查找中 a=1, b=2, log_b a = 0，f(n) = O(1) = Θ(n^0)，也是情况二，T(n) = Θ(log n)。套公式时先算 log_b a，再和 f(n) 的阶比较，大部分期末题用这三种情况就够了。

5. 避坑与排查：期末复习里最容易翻车的 5 个地方

5.1 指针操作：链表代码写完不检查空指针

现象：手写链表插入或删除代码时，运行报段错误，或者考试时被扣分。原因：没有判断头节点为空、没有判断待删除节点是否存在、没有处理删除尾节点的情况。解决：写完链表代码后，强制自己走一遍三种边界——空链表、单节点、操作头节点。特别是删除操作，一定要先判断head == NULL，再判断是否删除的是头节点。

5.2 KMP 的 next 数组：教材版本不统一导致对不上答案

现象：自己算的 next 数组和答案不一样，但匹配结果又是对的。原因：不同教材对 next[0] 的约定不同，有的用 -1，有的用 0，有的从 1 开始编号。解决：考试时先看题目或教材用的是哪种约定，西电常用 -1 版本。如果题目没说明，在答题时标注你使用的约定，避免因为版本差异被判错。

5.3 排序稳定性：把不稳定排序当成稳定用

现象：选择题问「下列哪个排序是稳定的」，把快排或堆排选成稳定。原因：只记了时间复杂度，没记稳定性。解决：记住稳定排序的口诀「冒泡、插入、归并、基数稳定」，快排、选择、堆排、希尔不稳定。考试前把这张稳定性表默写一遍，比考场上临时想靠谱得多。

5.4 树的遍历：递归和非递归搞混访问顺序

现象：写非递归中序时，把访问时机写成了入栈时访问，结果变成前序。原因：没有理解「中序是弹栈时访问，前序是入栈时访问」。解决：记住一句话——前序在入栈前访问，中序在弹栈后访问，后序在左右子树都处理完后访问。写完后用一棵三节点的小树手动模拟一遍，立刻能发现错误。

5.5 复杂度分析：把平均当最坏，把最坏当平均

现象：题目问快排的时间复杂度，答 O(n log n)，但题目要的是最坏情况。原因：没有看清题目问的是平均还是最坏。解决：读题时圈出「平均」「最坏」「最好」这几个关键词。快排平均 O(n log n)、最坏 O(n²)；归并平均和最坏都是 O(n log n)；堆排平均和最坏都是 O(n log n)。这几个数字必须条件反射般准确。

6. 考前一周怎么用这份知识点总结：我的复盘习惯

最后一周不要再从头翻 PDF 了，效率极低。我的做法是拿一张白纸，按「线性表、栈队列、串、树、图、查找、排序」七个模块，每个模块默写三样东西：核心操作的代码框架、关键复杂度、一个易错点。写不出来的地方标记出来，只复习标记的部分。这个过程通常两小时能过完一轮，比翻一天书有用得多。

具体到这份「数据结构与算法期末知识点总结.pdf」，我建议的用法是：第一遍快速扫一遍，确认覆盖范围；第二遍只挑代码题高频章节（链表、树遍历、快排归并）精读；第三遍合上资料，手写默写。默写时用计时器，模拟考场压力。我自己的血泪经验是，平时写代码习惯开着编译器报错提示，考场上手写时一个分号漏了都发现不了，所以考前至少手写三遍完整代码，不借助任何工具。

验证复习效果的方法很简单：找一套往年期末题或 408 真题，限时做代码题部分。如果能在 20 分钟内写出链表反转、二叉树中序非递归、快排 partition 这三段代码且边界正确，基本就稳了。如果写不出来，回到对应章节重新默写，不要心存侥幸。复习数据结构没有捷径，但有针对性的重复可以省下大量时间。希望帮到你。

本文还有配套的精品资源，点击获取