《数据结构》期末复习完全手册（直接使用版）

《数据结构》期末复习完全手册（直接使用版）第一部分：考试题型与分值分布（通用）题型题量分值主要考查范围策略选择题20-25题20-30分数据结构定义、存储结构特点、算法复杂度、排序查找过程、树图性质辨析概念，牢记各种结构特点和算法特征填空题10-15题10-15分关键性质（树结点数、图连通分量等）、算法步骤、存储公式熟记公式和结论判断题10题10分概念正误辨析注意细节，如链表存储密度、栈的应用等简答题3-4题15-20分算法思想、数据结构对比、散列冲突解决、图的应用分点作答，逻辑清晰算法阅读/填空题2-3题10-15分链表操作、二叉树遍历、排序算法片段根据上下文理解算法意图算法设计/应用题2-3题15-25分链表插入删除、二叉树的建立与遍历、图的遍历、排序过程、哈希表构造掌握经典算法模板，注意边界和复杂度第二部分：数据结构基础知识速查2.1数据结构三要素要素含义逻辑结构数据元素之间的逻辑关系。分线性结构（线性表、栈、队列）和非线性结构（树、图、集合）。存储结构（物理结构）数据结构在计算机中的表示。主要有顺序存储、链式存储、索引存储、散列存储。数据的运算施加在数据上的操作，如增删改查等。2.2算法分析（时间复杂度）时间复杂度是算法执行时间随问题规模n增长的趋势。常见阶：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)空间复杂度算法运行所需额外存储空间。第三部分：线性表速查3.1顺序表与链表对比对比项顺序表单链表存储方式连续存储单元结点（数据+指针），不连续存取效率随机存取O(1)顺序存取O(n)插入/删除需移动元素，平均O(n)修改指针O(1)（前提已知插入位置）空间利用率高（不需指针域），需预分配低（需指针域），动态分配适用场景频繁查找、元素个数固定频繁插入删除、元素个数变化大3.2双向链表与循环链表双向链表：结点有prior和next两个指针，便于前驱查找，空间开销稍大。循环链表：尾结点指针指向头结点，判空条件：head->next==head。双向循环链表：兼具两者特性。3.3顺序表与链表常用操作核心代码（理解）顺序表插入：后移元素，L->length++。单链表头插法建表：新结点插入到头结点后。单链表删除：p->next=q->next;free(q);第四部分：栈和队列速查4.1栈（Stack）后进先出（LIFO），只允许在栈顶操作。存储结构：顺序栈、链栈。基本操作：Push、Pop、GetTop。应用：括号匹配、表达式求值、递归、进制转换、迷宫求解。4.2队列（Queue）先进先出（FIFO），一端入队，另一端出队。存储结构：循环队列（顺序存储）、链队列。循环队列判空：front==rear；判满：(rear+1)%MAXSIZE==front（牺牲一个单元）。链队列无满问题。4.3双端队列两端都可以入队和出队。第五部分：串、数组和广义表5.1串由零个或多个字符组成的有限序列。存储：定长顺序存储、堆分配存储、块链存储。模式匹配：朴素匹配：O(m*n)KMP算法：主串不回溯，通过next数组优化到O(m+n)5.2数组一般用顺序存储。按行优先、列优先存储。特殊矩阵压缩存储：对称矩阵：只存上三角或下三角。三角矩阵：存非零区域+一个常数。稀疏矩阵：三元组顺序表、十字链表。第六部分：树与二叉树（重点）6.1树的基本概念结点、度、叶子结点、深度、高度、路径。树的存储：双亲表示法、孩子链表表示法、孩子兄弟表示法。6.2二叉树性质（常考填空）序号性质1第i层最多有2i-1个结点（i≥1）2深度为k的二叉树最多有2k-1个结点3若叶子结点数为n0，度为2的结点数为n2，则n0=n2+14具有n个结点的完全二叉树深度为⌊log2n⌋+15对于完全二叉树，编号为i的结点：左孩子2i，右孩子2i+1，双亲⌊i/2⌋（i>1）6.3满二叉树与完全二叉树满二叉树：深度k有2k-1个结点，每层都满。完全二叉树：与满二叉树编号一一对应，仅在最后一层可能缺少右边若干结点。6.4二叉树的遍历（必考）遍历方式顺序递归描述先序根左右访问根，先序左子树，先序右子树中序左根右中序左子树，访问根，中序右子树后序左右根后序左子树，后序右子树，访问根层次从上到下，从左到右借助队列实现遍历序列特性：由前序+中序或后序+中序可唯一确定二叉树。前序和后序不能唯一确定。6.5线索二叉树利用空的左、右指针存放前驱和后继线索，方便遍历。6.6树、森林与二叉树的转换树转二叉树：左孩子右兄弟原则。森林转二叉树：每棵树转换后，依次作为前一棵树的右子树。6.7哈夫曼树（Huffman）带权路径长度WPL=∑(权值×路径长度)构造：每次选权值最小的两棵树合并。哈夫曼编码：左0右1，前缀编码。应用：数据压缩。第七部分：图速查7.1图的基本概念概念说明完全图无向图有n(n-1)/2条边，有向图有n(n-1)条弧连通图/连通分量无向图任意两顶点连通；极大连通子图为连通分量强连通图/强连通分量有向图双向连通概念生成树极小连通子图，包含全部n个顶点和n-1条边度无向图：依附该顶点的边数；有向图：出度+入度7.2图的存储存储结构特点邻接矩阵n×n矩阵，AHYPERLINKi=1/权值。适合稠密图，空间O(n2)邻接表顶点数组+边链表。适合稀疏图，空间O(n+e)7.3图的遍历深度优先搜索（DFS）：递归或栈，类似树的先序遍历。广度优先搜索（BFS）：借助队列，类似树的层次遍历。遍历生成树/森林。7.4图的最小生成树算法复杂度描述PrimO(n2)稠密图从点出发，每次选连接生成树的最小权边KruskalO(elog2e)稀疏图每次选不构成回路的最小权边，用到并查集7.5最短路径问题算法复杂度适用单源最短路径DijkstraO(n2)边权非负多源最短路径FloydO(n3)负权边可（无负权回路）7.6拓扑排序与关键路径AOV网：顶点表示活动，拓扑排序判断有无环。算法：每次选入度为0的顶点删除。AOE网：边表示活动，求关键路径。四个关键量：ve（最早发生）、vl（最迟发生）、e（最早开始）、l（最迟开始）。关键活动：e=l。第八部分：查找速查8.1常见查找算法复杂度查找方式数据结构平均查找长度（ASL）时间复杂度顺序查找顺序表/链表(n+1)/2O(n)折半查找有序顺序表log2(n+1)-1O(log2n)分块查找索引表+块内顺序约log2(n/s+1)+s/2介于两者之间二叉排序树二叉链表O(log2n)平衡时O(h)平衡二叉树（AVL）二叉链表O(log2n)O(log2n)B-树/B+树多路搜索树O(logmn)—哈希查找散列表与装填因子和冲突解决有关O(1)平均8.2折半查找（二分查找）仅适用于有序的顺序表。mid=low+(high-low)/2防止溢出。判定树为平衡二叉树。8.3二叉排序树（BST）左子树值<根<右子树值。中序遍历得到有序序列。插入/删除：删除结点分三种情况（叶子、单支、双支——用直接前驱或后继替换）。8.4平衡二叉树（AVL）每个结点左右子树高度差不超过1。平衡因子=左子树高-右子树高（0,1,-1）。旋转方式：LL、RR、LR、RL。8.5哈希表哈希函数：直接定址、除留余数、平方取中等。冲突处理：开放定址法：线性探测、二次探测、伪随机探测。链地址法：同义词链在同一链表。装填因子α=表中记录数/哈希表长度。α越大，冲突越多。第九部分：排序速查9.1排序算法总结（必考）排序算法平均时间最好时间最坏时间空间复杂度稳定性特点直接插入排序O(n2)O(n)O(n2)O(1)稳定基本有序时高效希尔排序约O(n1.3)—O(n2)O(1)不稳定缩小增量冒泡排序O(n2)O(n)O(n2)O(1)稳定交换快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)不稳定每次确定枢轴位置简单选择排序O(n2)O(n2)O(n2)O(1)不稳定选最小交换堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定建堆+交换归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定分治，需要辅助数组基数排序O(d(n+rd))O(d(n+rd))O(d(n+rd))O(rd)稳定多关键字，适合整数等9.2排序过程常考点快速排序：划分时从两端交替扫描，确定枢轴最终位置。堆排序：大根堆（升序），小根堆（降序）。建堆：从⌊n/2⌋开始向下调整。归并排序：二路归并，递归/非递归实现。第十部分：高频选择题题库（50题）模块一：基本概念与复杂度题号题目ABCD答案1数据结构中，与计算机无关的结构是存储结构物理结构逻辑结构链式结构C2算法的时间复杂度取决于问题的规模待处理数据的初态A和B计算机性能C3以下不属于线性结构的是栈队列二叉树线性表C4顺序存储结构的优点是插入删除方便存储密度大便于动态分配不要求连续空间B5某算法时间复杂度O(n2)，表明问题规模是n2执行时间与n2成正比执行时间等于n2问题规模增加时执行时间不变B模块二：线性表、栈和队列题号题目ABCD答案6在单链表中删除p所指结点的后继结点，操作为p=p->nextp->next=p->next->nextp=p->next->nextp->next=pB7栈和队列的共同点是都是先进先出都是后进先出只允许在端点操作没有共同点C8循环队列用数组A[0..M-1]存放，front指向队头，rear指向队尾后一个位置，则入队时rear变化为rear=rear+1rear=(rear+1)%Mrear=(rear-1)%Mrear=rearB9表达式a*(b+c)-d的后缀表达式（逆波兰）为abc+*d-abc+*d-abcd*+-abc*+d-B10递归调用时使用哪种数据结构保存返回地址队列数组栈树C模块三：树和二叉树题号题目ABCD答案11高度为k的二叉树最多有结点数k2k2k-12k-1C12100个结点的完全二叉树，叶子结点数为504951不确定A13二叉树的先序遍历序列和中序遍历序列相同，则该二叉树所有结点无左孩子所有结点无右孩子只有一个结点以上都不对B14哈夫曼树中带权路径长度是指所有结点权值之和所有叶子结点权值与路径长度乘积之和树的深度结点数B15线索二叉树中，结点左指针为空的标志是LTag=0LTag=1rtag=0指针为NULLB模块四：图题号题目ABCD答案16n个顶点的无向完全图边数为nn-1n(n-1)/2n(n-1)C17最小生成树指的是边数最少的生成树顶点最少的生成树权值之和最小的生成树结点度最小的生成树C18图的深度优先遍历类似于树的先序遍历中序遍历后序遍历层次遍历A19拓扑排序可以检测图中是否存在环连通分量最短路径重边A20求图中某顶点到其余各顶点最短路径，常用算法DFSPrimDijkstraKruskalC模块五：查找题号题目ABCD答案21折半查找要求查找表顺序存储顺序存储且有序链式存储索引存储B22二叉排序树中序遍历得到无序序列递减序列递增序列不确定C23哈希表中冲突是指同义词存储在同一位置不同关键字有相同哈希地址同义词被多次查找表满了B24装填因子α越大，则哈希表冲突越多冲突越少不变查找越容易A25平衡二叉树的平衡因子范围-1到1-2到20到2任意A模块六：排序题号题目ABCD答案26下列排序中，不稳定的是直接插入冒泡归并快速排序D27快速排序在哪种情况下效率最低序列基本有序序列逆序序列无序枢轴选择正好平分A28堆排序空间复杂度为O(n)O(log2n)O(1)O(n2)C29若需要对1000个整数排序，要求最快且稳定，选用快速排序归并排序堆排序希尔排序B30下列排序方法中，时间复杂度不受数据初始状态影响的是直接插入简单选择快速排序冒泡排序B模块七：综合题号题目ABCD答案31串的KMP算法优点是主串指针不回溯模式串指针不回溯减少比较次数以上都对A32稀疏矩阵常用的压缩存储是二维数组三元组顺序表邻接表十字链表B33具有n个结点的二叉树，采用二叉链表存储，空指针域个数nn-1n+12nC34图的广度优先遍历需要使用栈队列数组树B35对n个记录进行快速排序，辅助空间大致为O(1)O(log2n)O(n)O(n2)B36哈希函数构造方法不包括除留余数法平方取中法折半查找法数字分析法C37下列哪种排序一趟之后，一定能选出一个元素放在最终位置归并冒泡快速直接插入C38设哈夫曼树有199个结点，则叶子结点数为99100101198B39将长度为m的单链表接在长度为n的单链表后，时间复杂度O(m)O(n)O(1)O(m+n)B40图的广度优先遍历类似于树的先序中序后序层次D41拓扑排序算法输出顶点时，图仍有未输出的顶点，则图中不存在环存在环不确定连通分量多B42堆的形状是二叉排序树完全二叉树平衡二叉树B-树B43散列函数处理冲突的链地址法，装填因子可以小于1大于等于1只能等于1无法确定B44对n个元素进行冒泡排序，在最好情况下比较次数为nn-1n(n-1)/2n2B45一棵深度为6的满二叉树结点数为316364127B46在循环队列中，若front与rear相等，则队列状态为空满空或满不可能C47下列数据结构中，按先进后出原则组织数据的是队列栈顺序表链表B48对有n个记录的表进行直接选择排序，所需关键码比较次数为O(n)O(n2)O(nlog2n)O(log2n)B49具有n个顶点的强连通图至少的弧数是nn-1n+1n(n-1)A50在一个图中，所有顶点的度数之和等于边数的1倍2倍1/2倍4倍B第十一部分：填空题高频考点（直接背诵）序号题目答案1数据结构三要素：逻辑结构、存储结构、____。数据的运算2时间复杂度O(1)表示算法的执行时间与____无关。问题规模n3单链表中头结点的作用是____。便于操作（空表统一）4栈是____的线性表。后进先出5循环队列判空条件：front____rear。==6用数组Q[0..M-1]存储循环队列，队满条件是____。(rear+1)%M==front7串的模式匹配KMP算法的时间复杂度是____。O(m+n)8深度为k的满二叉树有____个结点。2k-19完全二叉树第i个结点的左孩子编号（如果存在）是____。2i10一棵二叉树有n个结点，则它的空链域个数为____。n+111哈夫曼树带权路径长度WPL=____。∑(权值×路径长度)12图的存储结构主要有邻接矩阵和____。邻接表13图的深度优先搜索类似于二叉树的____遍历。先序14n个顶点的连通图至少____条边。n-115求最小生成树的Prim算法时间复杂度为____。O(n2)16Dijkstra算法用于求解____问题。单源最短路径17折半查找要求表必须采用__存储结构且__。顺序、有序18平衡二叉树的平衡因子绝对值不超过____。119哈希函数解决冲突的两种主要方法是开放定址法和____。链地址法20快速排序在平均情况下的时间复杂度是____。O(nlog2n)21堆排序中，若升序排序则应建____堆。大根22归并排序的空间复杂度是____。O(n)23在直接插入排序中，若序列基本有序，则时间复杂度接近____。O(n)24排序算法的____性是指相同关键字的记录在排序前后相对位置不变。稳定25图的遍历中，广度优先搜索需借助____数据结构。队列第十二部分：判断题速记（15题）序号题目答案1数据元素是数据的最小单位。错（数据项）2顺序存储结构只能存储线性结构。错（也可存储二叉树等）3单链表中增加头结点是为了方便运算。对4栈和队列的存储方式只有顺序存储。错（也可链式）5循环队列判满只能用(rear+1)%MAXSIZE==front。错（可设置标志位）6二叉树就是度为2的树。错（二叉树区分左右）7完全二叉树一定是满二叉树。错（满则完全）8哈夫曼树中没有度为1的结点。对（只有0和2）9图的深度优先遍历序列是唯一的。错（不唯一）10最小生成树一定是唯一的。错（权值相同边可能不唯一）11折半查找适用于有序链表。错（需随机存取）12哈希查找中，装填因子越大查找效率越高。错（越低）13快速排序是稳定的排序算法。错（不稳定）14归并排序在任何情况下时间复杂度都是O(nlog2n)。对15堆排序所需辅助空间与待排序记录数n无关。对（O(1)）第十三部分：简答题高频考点1.顺序存储与链式存储的优缺点比较。顺序存储优点：可随机存取，存储密度大；缺点：插入删除需移动元素，需预分配空间。链式存储优点：插入删除方便，动态分配；缺点：顺序存取，存储密度低（有指针域）。2.栈和队列的区别及各自应用。栈是后进先出（LIFO），用于递归、括号匹配、表达式求值等；队列是先进先出（FIFO），用于缓冲区、层次遍历等。3.简述二叉树的三种遍历方式，并说明由哪两种序列可唯一确定二叉树。先序（根左右）、中序（左根右）、后序（左右根）。由先序和中序，或后序和中序可唯一确定二叉树。4.简述Prim和Kruskal算法的基本思想与区别。Prim：从任意顶点开始，每次选连接生成树的最小权边。时间复杂度O(n2)，适合稠密图。Kruskal：每次选不构成回路的最小权边，直到n-1条边，O(elog2e)，适合稀疏图。5.简述哈希表处理冲突的链地址法原理。将所有哈希地址相同的记录（同义词）存储在同一个单链表中，哈希表的每个单元存放对应链表的头指针。查找时先计算地址，再在链表中顺序查找。装填因子可以大于1。6.简述快速排序的基本思想与一趟划分过程。任选一个元素作为枢轴（pivot），通过一趟排序将序列分为两部分，左边小于枢轴，右边大于枢轴，枢轴放在最终位置。然后递归对左右两部分进行同样操作。划分通常从两端交替扫描。第十四部分：算法阅读与填空示例例1：单链表插入（在p之后插入s）s->next=____①____;

p->next=____②____;答案：①p->next②s例2：折半查找intBinarySearch(inta[],intn,intkey){

intlow=0,high=n-1,mid;

while(low<=high){

mid=(low+high)/2;

if(a[mid]==key)returnmid;

elseif(a[mid]>key)high=____①____;

elselow=____②____;

}

return-1;

}答案：①mid-1②mid+1例3：直接插入排序voidInsertSort(inta[],intn){

for(inti=1;i<n;i++){

inttemp=a[i];

intj=____①____;

while(j>=0&&a[j]>temp){

a[j+1]=a[j];

j--;

}

____②____=temp;

}

}答案：①i-1②a[j+1]例4：二叉树先序遍历（递归）voidPreOrder(BiTree