企业官网建设流程全解析

简介：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 个结点的二叉链表有 n+1 个空链域。计算方法是：每个结点有两个指针域，共 2n 个指针域；n 个结点的二叉树有 n-1 条边，非空指针域 n-1 个，空链域就是 2n - (n-1) = n+1。这个结论是线索二叉树概念的引子。

3.3 遍历、线索化与哈夫曼树：递归视角下的考点

先序 DLR（根左右）、中序 LDR（左根右）、后序 LRD（左右根），三种遍历方式的递归定义不难，难的是「给定中序+先序，还原二叉树」这类题。做法是拿先序序列的第一个元素当根，在中序序列里找到根的位置，左边是左子树，右边是右子树，递归处理。同理中序+后序也能还原，但只有先序+后序无法唯一确定一棵二叉树，这算是一个常被忽略的边界知识点。

线索二叉树这块，记住一个核心：n 个结点的二叉链表有 n+1 个空指针，利用空指针指向前驱或后继结点叫线索。标志位的规则要背清楚：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，边纳入生成树。

两种算法的复杂度对比要背：

最短路径的 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）逐位排。

下面的表直接背，期末考到这里就不丢分：

选型策略是简答题常客。n 较小（小于等于 50）时用直接插入或直接选择排序，记录本身信息量大时用简单选择排序更好，因为插入排序移动操作更多；文件的初始状态基本有序时选直接插入或冒泡排序；n 较大时必须用 O(nlog2n) 级别的排序，快排算基于比较的内部排序里公认最好的。另外任何借助关键字的比较排序算法理论上至少需要 O(nlog2n) 的时间，这个结论可以拿二叉树描述比较判定过程来理解，期末考到照写即可。

5.2 五条高频踩坑记录：现象、原因、解决

第一条：循环队列判空判满写反。现象是题目给一个循环队列，问队空条件，答成(rear+1)%m == front；给队满条件，答成front == rear。原因是最开始记了公式但没理解设计目的。解决：从「为什么牺牲一个单元」来记——如果不空一个位置，队空和队满时 front 和 rear 都相等，无法区分；牺牲一个单元后，存满时 rear 指向最后一个空位，(rear+1)%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^p（p = 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 里的表述已经足够支撑考前一周的突击，配合教材例题把每一章的判定条件默写一遍，期末基本稳了。希望这篇拆解能帮你把手里的资源用到刀刃上。

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